Probabilistic inference

In recent years, computational methods for probabilistic inference has received a lot of attention, especially in the field of probabilistic expert systems based on the notion of causal structure. These systems provide a consistent and statistically correct handling of uncertainty, in sharp constrast to traditional rule-based expert systems. An example of such a system is the HUGIN system. The main difficulty for these systems is the complexity of the inference mechanism, which require the manipulation of exponentially large probability distributions. The current state of the art is graph theoretic decomposition methods that can handle moderately sized problems if the network structure is not too complex. For very large problems however, and without particular restrictions on the structure, these methods become intractable. We therefore focus on the question of approximate probabilistic inference with the aim to solve larger problems than those solvable by present methods.

We have developed a propagation method for probabilistic networks, that through local operations in the network provides exact probabilistic inference if the probabilistic network is acyclic. In this respect, the operations are structurally similar to those of a neural network, although we have a probabilistic interpretation of the computation. The network explicitly manipulates probabilities to compute the marginals of a discrete probability distribution defined as a markov graph. The method can be considered as a probabilistic relaxation method, in contast to the more well known stochastic relaxation methods. The algorithm is similar to the algorithm of Pearl, but operates on an undirected structure. The algorithm operates by local operations on the probabilistic network, and is therefore possible to run also for networks with cycles, and we have investigated its performance for approximate probabilistic inference on unrestricted networks.

More information about our approach can be found in the dissertation Probabilistic Inference, Combinatorial Optimization and the Discovery of Causal Structure from Data (1993) which can be obtained from the author.

dag@cs.chalmers.se
Last modified: Fri Nov 7 15:01:52 MET 1997