对弧进行删除的Bayes网络近似方法

On Approximating Bayesian Networks by Removing Arcs

弧的删除是一种对 Bayes网络模型进行近似的方法 .文中以 Kullback- L eibler偏差作为近似网络和原网络概率分布误差的测度 ,给出了近似网络在此测度意义下的最优参数 .同时 ,也给出了通过对原网络删除多条弧进行近似的启发式算法 ,当给定一个误差上界时 。

As a knowledge representation framework and a kind of probability inference engine, Bayesian networks are widely used in applications for reasoning and decision making with inherent uncertainty. Since the exact algorithms of probability inference in Bayesian networks is NP-hard, as the topology of the network becomes more dense, the run-time complexity of probabilistic inference increases dramatically and real-time decision making eventually becomes prohibitive, so many approximate algorithms based on simulation or model simplification are proposed. The method discussed in this paper is based on the model simplification of arc removal. In this method, a subset of arcs are selected and removed, which simplifies the network structure and we obtain an approximate network, then any probability inference algorithm can be applied to this approximate network to get a solution within the error bound we predefined. By using the Kullback-Leibler information divergence as the measure of the difference between two probability distributions, this paper discusses the multiple arc removal problem in the gen eral case and presents the optimal parameters for the approximate network. Final ly, a heuristic algorithm is provided which searches a set of arcs to be removed under the upper bound on the probability error allowed.