Towards Efficient Search-Based Algorithms for Belief Updating, Decision Making, and Explanation in Bayesian Belief Networks

图形概率模型，如贝叶斯信念网络和影响图，为基于知识系统的推理提供了一种有吸引力的知识表示工具。由于许多实际系统往往很大，这种方法面临的主要问题是概率推理的复杂性，对于精确和近似推理都显示为最坏情况np困难。由于复杂性证明是针对最坏的情况，因此研究真实模型的性质并随后开发将探索这些性质的算法非常重要。本研究的目的是开发一种有效的算法，用于非常大概率模型的近似信念更新和决策。这些算法探索模型变量上联合概率分布的不对称性，并搜索模型的最可能状态。通常一小组状态覆盖了大部分概率空间。该项目包括对基于搜索的算法的收敛速度和误差边界预测方法的理论研究，以及对实际模型的理论预测的经验验证。在项目过程中开发的算法在非常大的基于知识的系统中实现和经验评估。由于信念网络中概率推理的复杂性是概率方法在基于知识的系统中广泛应用的主要障碍之一，本项目开发的理论结果和算法有望对该领域产生重大影响。

Graphical probabilistic models, such as Bayesian belief networks and influence diagrams, offer an attractive knowledge representation tool for reasoning in knowledge-based systems. As many practical systems tend to be large, the main problem faced by this approach is the complexity of probabilistic reasoning, shown to be worst-case NP-hard both for exact and approximate inference. Since the complexity proofs are for the worst case, it is important to study the properties of real models and subsequently to develop algorithms that will explore these properties. The purpose of this research is to develop efficient algorithms for approximate belief updating and decision making in very large probabilistic models. These algorithms explore asymmetries in joint probability distributions over model variables and search for the most likely states of the model. Very often a small set of states covers the bulk of the probability space. The project includes theoretical studies of methods for prediction of convergence speed and error bounds in search-based algorithms and empirical verification of the theoretical predictions on practical models. The algorithms developed in the course of the project are implemented and empirically evaluated in very large knowledge-based systems. As the complexity of probabilistic inference in belief networks is one of the main obstacles to wide application of probabilistic methods in knowledge-based systems, the theoretical results and the algorithms developed in this project can be expected to have a major impact on the field.