Computing Marginals with Hierarchical Acyclic Hypergraphs.

How to compute marginals efficiently is one of major concerned problems in probabilistic reasoning systems. Traditional graphical models do not preserve all conditional independencies while computing the marginals. That is, the Bayesian DAGs have to be transformed into a secondary computational structure, normally, acyclic hypergraphs, in order to compute marginals. It is well-known that some conditional independencies will be lost in such a transformation. In this paper, we suggest a new graphical model which not only equivalents to a Bayesian DAG, but also takes advantages of all conditional independencies to compute marginals. The input to our model is a set of conditional probability tables as in the traditional approach. Introduction In probabilistic reasoning systems (Neapolitan, 1989; Pearl, 1988), the domain knowledge is represented in terms of a joint probability distribution (JPD). The JPD is factorized in terms of conditional probability tables (CPTs) according to the conditional independencies (CIs) encoded by the graphical model using Bayesian directed acyclic graphs (DAGs) or acyclic hypergraphs (AHs). One of the problems in probabilistic reasoning systems is how to compute marginals from an input set of CPTs. This problem has been studied intensively. One method is to transform the DAG into a AH and apply local propagation techniques (Jensen, 1996; Shafer et al., 1990) to compute the marginal for every hyperedge of the AH. However, AHs cannot represent some embedded CIs (Pearl, 1988). This means that some CIs encoded in the DAG cannot be preserved by such a transformation. Many graphical models have been suggested for taking advantage of all CIs in the computation of marginals. Geiger (Geiger, 1988) and Shachter (Shachter, 1990) proposed multiple undirected graphs (MUGs) to faithfully represent a DAG. More recently, Kjaerulff (Kjaerulff, 1997) has demonstrated that multiple AHs (nested junction trees) can be used to compute marginals in a more efficient manner than one single AH. However, it is not known if these proposed models are not equivalent to the Bayesian DAGs. Copyright c © 2004, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. In this paper, we use the split-free hierarchical acyclic hypergraphs (HAHs) model, which is equivalent to a Bayesian DAG (Wong et al., 2003), to compute the marginals without losing CI information. We show that a set of CPTs can be specified according to the graphical structure, there exists a computation sequence enable us to compute the marginals, and the JPD factorization is represented in terms of the product of such a set of CPTs. It is worth mentioning that the complexity of our method for computing marginals is NPComplete (Cooper,1990) as the local propagation technique. The important point is that our model preserves all CIs in computing the marginals. This paper is organized as follows. We include a brief review of basic concepts about probabilistic networks in Section 2. Section 3 introduces the notion of HAH. In Section 4, we introduce a special type of HAHs called split-free HAHs. Section 5 discusses how to compute the marginals with respect to every hyperedge of an AH. Section 6 suggests an approach to specify the input set of CPTs for the split-free HAHs. In Section 7, we show that the JPD can be factorized as a product of the input CPTs. The conclusion is presented in Section 8. Background Knowledge Here we briefly review some pertinent notions of probabilistic networks including Bayesian networks and acyclic hypergraphs. Let U be a set of domain variables. We say Y and Z are conditionally independent given X with respect to a JPD P (U), if P (Y |XZ) = P (Y |X), where X , Y , Z are disjoint subsets of U . This conditional independence statement (CI) can be conveniently represented by a triplet: I(Y, X, Z). A Bayesian network (Pearl, 1988) is a directed acyclic graph (DAG) together with a set of CPTs corresponding to each node Ai in the DAG. A Bayesian JPD is defined by the product of those CPTs, namely: