Networked bubble propagation: a polynomial-time hypothetical reasoning method for computing near-optimal solutions

摘要

Hypothetical reasoning (abduction) is an important knowledge processing framework because of its theoretical basis and its usefulness for solving practical problems including diagnosis, design, etc. In many cases, the most probable hypotheses set for diagnosis or the least expensive one for design is desirable. Cost-based abduction, where a numerical weight is assigned to each hypothesis and an optimal solution hypotheses set with minimal sum of element hypotheses' weights is searched, deals with such problems. However, slow inference speed is its crucial problem: cost-based abduction is NP-complete. In order to achieve a tractable inference of cost-based abduction, we aim at obtaining a nearly, rather than exactly, optimal solution. For this approach, an approximate solution method exploited in mathematical programming is quite beneficial. On the other hand, from the standpoint of knowledge processing, it is also important to realize inference on a network which reflects knowledge structure. Knowledge structure is a fruitful information for an efficient inference. In this paper, we propose an inference method which works on a knowledge network, based on a mechanism similar to the pivot and complement method, an efficient approximate 0–1 integer programming method to find a near-optimal solution within a polynomial time of O(N4), where N is the number of variables or hypotheses. We reformalize this method by a new type of network on which inference is executed by propagating bubbles. This method achieves an inference time of O(N2) by executing each bubble propagation within a small sub-network, i.e., by taking advantage of the knowledge structure.