Breaking Dependence in Graphical Belief Models

Graphical models are a useful organizational tool for complex models. Local models, using either conditional Bayesian probability distributions (random values) or belief functions (random sets), describe interactions among closely related variables. The collection of local models induces a hypergraph over all the variables; this hypergraph describes conditional independence conditions among the variables in a problem. More importantly, the graphical model suggest local computation strategies for finding the marginal distribution (belief or probability) of certain collections of the attributes. Unfortunately, cycles in the model hypergraph an indication of dependence among widely separated variables in the model increases the computational complexity of a given problem, sometimes to the point of intractability. One known method for breaking such dependence is to condition on a known value for a variable whose removal would break the cycle. After conditioning, the variable can be replaced by two pseudo-variables both with the same value, creating a new model in which the dependence is broken. If the information about the variable which breaks the cycle is probabilistic, then the mechanism described above is used as the basis of a Monte Carlo algorithm for calculating marginal distributions. Unfortunately, if the information about the variable is in the form of a belief function (a random set), then conditioning can be done only on sets, not exact values. For certain margins in certain models, conditioning on the sets does not bias the calculations. This paper attempts to characterize such models. The problem is illustrated using a simple example from risk analysis.