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

贝叶斯信念网络中基于搜索的高效信念更新、决策和解释算法

• 批准号: 9624629
• 负责人: Marek Druzdzel
• 金额: $ 22.73万
• 依托单位: University of Pittsburgh
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-06-01 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9624629&HistoricalAwards=false
• 关键词: Towards; Efficient; Search; Based; Algorithms

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.

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