Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems

SUMMARY A causal network is used in a number of areas as a depiction of patterns of ‘influence’ among sets of variables. In expert systems it is common to perform ‘inference’ by means of local computations on such large but sparse networks. In general, non-probabilistic methods are used to handle uncertainty when propagating the effects of evidence, and it has appeared that exact probabilistic methods are not computationally feasible. Motivated by an application in electromyography, we counter this claim by exploiting a range of local representations for the joint probability distribution, combined with topological changes to the original network termed ‘marrying’ and ‘filling-in‘. The resulting structure allows efficient algorithms for transfer between representations, providing rapid absorption and propagation of evidence. The scheme is first illustrated on a small, fictitious but challenging example, and the underlying theory and computational aspects are then discussed.