改良型ネットワーク化バブル伝播法による低次多項式時間仮説推論法

概要

論文の詳細を見る
A hypothetical reasoning is an important knowledge system's framework because of its theoreticalbasis and its usefulness for practical problems including diagnosis, design, etc. One crucial problem with the hypothetical reasoning is, however, its slow inference speed. To achieve practical or tractable speed, an approximate solution method of O-1 integer prograrmming has been appliced so far to a weight-based hypothetical reasoning, where a numerical weight is assigned to each possible element hypothesis and the optimal solution hypothesis-set with the minimal sum of its element hypotheses' weights is searched. In order to take advantage of considering the knowledge structure of a given problem, the authors have previously proposed a network-based inference method called networked bubble propagation (NBP) method, which allows faster inference speed than that of the original approximate solution method of O-1 integer programming. In this paper, we present an improved NBP (I-NBP) method which has the preferreble property that it can always find the optimal solution (not near-optimal one) in polynomial-time if the knowledge structure is fairly simple including the case of singly-connected network. This new method can also achieve faster inference speed than the previous NBP method for finding a near-optimal solution when the knowledge stucture is in the general form. A theoretical study on the inference complexity related to the knowledge structure is also shown, and a new sufficient condition of polynomial-time inference is suggested.
1995-01-01

改良型ネットワーク化バブル伝播法による低次多項式時間仮説推論法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク