Distributed revision of composite beliefs (Q1096412)

This paper extends the applications of Bayesian analysis and belief network models to include revision of belief commitments, i.e., the tentative categorial acceptance of a subset of hypotheses which, together, constitute the most satisfactory explanation of the evidence at hand. Using probabilistic terminlogy that task amounts to finding the most probable instantiation of all hypothesis variables, given the observed data. The resulting output is an optimal list of jointly accepted propositions that may vary dynamically as more evidence obtains. It is shown that, in singly connected networks, globally optimal explanations can be configured by local and autonomous message-passing processes, similar to those used in belief updating; conceptually related propositions communicate with each other via a simple protocol, and the process converges to the correct solution in time proportional to the network diameter. In multiply connected networks, the propagation method must be assisted either by clustering (i.e., locally supervised groups of variables) or conditioning (i.e., reasoning by assumptions); each exploiting different aspects of the network topology. In general, assembling the most believable combination of hypotheses is no more complex than computing the degree of belief for any individual hypothesis. Applications to circuit and medical diagnosis are illustrated.