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.
