Simplifying bayesian belief nets while preserving MPE or MPGE ordering

The abstraction of probability inference is a process of searching for a representation in which only the desirable properties of the solutions are preserved. Simplification is one of such abstraction which reduces the size of large databases and speeds transmission and processing of probabilistic information[Sy & Sher, 941. Given a set of evidence S,, human beings are often interested in finding the few Most Probable Explanations (MPE) or Most Probable General Explanations (MPGE) in a Bayesian belief network, i.e., to identify and order a set of His or Lis (for MPGE), P(Hr]S,) 2 . . . > P(HnlSe), or P(Li]$) 2 . . . 2 P(Ln]Se), where Hi z an instantiation of all non-evidence variables and Li is an instantiation of a subset of all non-evidence variables. Furthermore, the ordering is often more important than the quantitative probability values in certain domain such as in diagnosis and prediction. The complexity of deriving MPEs or MPGEs is exponential if straight forward computation is employed. Various algorithms have been developed to reduce the computational complexity. Yet, so far no attemp has been made to explore the idea of simplification which is based on searching an alternative representation, i.e., a different Bayesian belief network which preserves the MPE or MPGE ordering relevant to queries of particular interests. This approach will try to reduce the connectivity of the network so that it is more sparse but has a probability distribution which preserves the orders of MPEs or MPGEs. Our idea is to relax the probability constraints so that only the orders of MPEs or MPGEs are preserved. Since many probability distributions may preserve the desired orders, different belief networks may be realized because a belief network is uniquely defined by its topological structure and probability distribution. Ideally, we hope to find a network whose structure has only few connections (i.e., a network which manifests many independency relations). If such a network can be found, one can discard irrelevant information and reduce the size of the Bayesian belief network. Consequently, the complexity of deriving MPEs and MPGEs is reduced. One can conceptualize the abstraction process as a search which attempts to find appropriate network structures and probability distributions. In finding the structure of a simplified network, the MDL (minimum description length) principle can be used. The idea is to define a cost function whose value is proportional to the sparsity of a network [Lam and Bacchus, 931. In finding the probability distributions, one may use a measure which can quantify the independency relations represented by the network. Cross entropy is one such measure proposed by Chow and Liu. So far all the research for automated learning or construction of the Bayesian belief network are taking the approach that attempts to recover the original probability distribution as much as possible. Our approach is different in the sense that deviation is allowed and encouraged as long as the probability distribution preserves the orders of MPEs or MPGEs and a simple structure of a network can be obtained. A heuristic method, which is reported elsewhere [Sy 94a], has been developed to achieve the construction of a network with a simple structure. An experimental study will be conducted on a set of multiply connected Bayesian belief networks. Each of this network consists of eight variables and has a high interconnectivities among the variables. After the new network with a simpler structure is generated, comparisons will be made between the orders generated by using the original belief network and the s&nplified network generated by the heuristic algorithm. The particular questions to be addressed in this expreimental study are listed below: (1) Although it is theoretically possible to have networks which preserve the orderings of all possible MPE and MPGE, it is still unknown the level of complexity involved in finding these networks. We would like to know the possible ways of characterizing the complexity. (2) If the networks mentioned in (1) are found, we would like to know whether there are any networks whose structure are simple such as singly connected configuration. If the singly connected configuration does not exist, we would like to know which one, among these multiply connected networks, is the best in terms of the fators affecting the computation and also, which one is more spare and preserving more independency assumptions ? (3) If we can get a belief network which preserves all possible MPE and MPGE ordering, then this new Bayesian belief network is a new representation of the underlying probability inference system. This network is considered as a summary of the original network within the context of the abstraction theory proposed by Bon and Sher [94b]. Otherwise this network is considered as a simplification. When a network is only a simplification, we would like to know the percentage of the orderings being preserved.