Computational Techniques for Probabilistic Inference

摘要

The objectives of this research project were to develop pragmatic andtheoretically sound methods for the computation of probabilistic information within expert systems. We explored the use of Bayesian belief networks as a probabilistic representation. We implemented and evaluated several previously described belief-network inference algorithms that perform exact inference, as well as developing a hybrid algorithm and a new algorithm. Our conclusion is that no single algorithm is best for all inference problems. Moreover, our analysis revealed that the belief-network inference problem is NP-hard. Thus, it is unlikely we can develop an exact algorithm that is uniformly efficient (polynomial time) across all networks and inference problems. This led us to investigate special-case and approximation algorithms, as well as methods for controlling multiple algorithms in solving a single inference problem. Our investigation indicates that moderately complex expert systems based on belief networks can be constructed using these current methods. The development of improved methods for controlling the application of multiple inference algorithms is likely to allow tractable inference in increasingly complex expert systems based on belief networks. The construction of complex belief networks also presents significant challenges. We developed automated and semi-automated knowledge-acquisition techniques which show significant promise in preliminary tests.