Inside-Outside Probability Computation for Belief Propagation

1 Introduction

Bayesian networks (BNs) and probabilistic context free grammars (PCFGs) are two basic probabilistic frameworks in uncertainty modeling (BNs) and in statistical natural language processing respectively. Although they are independently developed, there is a strong indication of their close relationship. For example both include hidden Markov models (HMMs) as a common subclass. Furthermore belief propagation (BP) applied to HMMs coincides with the forwardbackward algorithm for HMMs [Smyth et al., 1997] which is a specialization of probability computation used in the InsideOutside (IO) algorithm for PCFGs [Baker, 1979]. Nonetheless, however, no exact correspondence beyond this one is known to our knowledge.

In this paper 1 we upgrade this correspondence. We prove that the inside-outside probability computation in the IO algorithm, when generalized for probabilistic logic programs and applied to junction trees, yields BP. In particular we prove that collecting evidence (resp. distributing evidence) in BP coincides with the computation of inside probabilities (resp. outside probabilities) in this generalized IO computation.

To prove the computational correspondence between BNs and PCFGs in a unified manner, we need a general language that can describe BNs and PCFGs 2 . We choose PRISM [Sato and Kameya, 2001] as a first-order probabilistic language for this purpose. We also need "propositionalization" of BNs [Sato and Kameya, 2001; McAllester et al., 2004; Chavira and Darwiche, 2005]. By propositionalization we mean to represent a discrete random variable X having n values {v1, . . . , vn} by a set {Xv1 , . . . ,Xvn } of mutually exclusive binary random variables such that Xvi = 1 (true) iff X = vi (1 ≤ i ≤ n). This propositionalization explodes the number of states in a BN. However the benefit often outweighs the explosion because it makes possible to share computation with finer grain size value-dependently at runtime by dynamic programming and rule out 0 probability computation at compile time. It explains, though we omit details, why probability computation in polynomial time cannot be expected of the direct application of BNs to PCFGs [Pynadath and Wellman, 1996] while it is carried out in O(n3 ) time where n is the sentence length by PRISM and by case-factor diagrams (CFDs) [McAllester et al., 2004].

1 We assume in this paper that BNs are discrete and BP is without normalization.

2 Note that BNs are a propositional framework that deal with finitely many random variables while PCFGs allow recursion and have to deal with infinitely many random variables describing probabilistic choices in a sentence derivation.

In what follows, we first review basic notions in Section 2. We then prove main theorems after a series of lemmas in Section 3. Due to space limitations, the description is sketchy and the reader is assumed to be familiar with logic programming [Doets, 1994] and BP in junction trees [Jensen, 1996; Lauritzen and Spiegelhalter, 1988; Shafer and Shenoy, 1990]. PRISM, a probabilistic logic programming language used in this paper, is detailed in [Sato and Kameya, 2001].

2 Background

2.1 Bayesian networks and junction trees

A Bayesian network BN is a directed acyclic graph defining a joint distribution P(X1 = x1, . . . ,XN = xN) = ΠNi=1P(Xi = xi | Πi = πi) such that nodes are random variables X1, . . . ,XN and if a node Xi has parent nodes Πi = Xs1 , . . . ,Xsk (k ≥ 0), a conditional probability table representing a conditional distribution P(Xi = xi | Πi = πi) is associated with Xi (1 ≤ i ≤ N). Here a lower case letter xi denotes a value of Xi and similarly for πi. We denote the range of Xi by R(Xi) and the direct product R(Xs1 )×· · ·×R(Xsk ) by R(Πi) and write xi ∈ R(Xi) and πi ∈ R(Πi). Hereafter we use P(x1, . . . , xN) for P(X1 = x1, . . . ,XN = xN) etc. When we consider P(xi | πi) as a function of xi, πi, the set {xi} ∪ πi is called the arguments of P(xi | πi). Let α = {s1, . . . , sk} be a set of variable indices (⊆ {1, . . . ,N}). Xα stands for the set of variables {Xs1 , . . . ,Xsk }. For example if α = {1, 2, 3}, Xα = {X1, X2, X3}. This notation extends to vectors.

A junction (join) tree T = (V,E) for BN is a tree satisfying the following conditions. First a node is a set Xα of variables in BN. In what follows we use Xα and its index set α interchangeably. An edge connecting α and β is labeled by α ∩ β. Second P(x1, . . . , xN) = Πα∈V φα(xα) must hold where φα(xα), a potential (function), is a product of some (or no) conditional distributions such that their arguments are included in xα. The third condition is the running intersection property (RIP) which dictates that if nodes α and β have a common variable, it must be contained in every node on the path between α and β. RIP ensures the conditional independence of the subtrees given variables in the node and is the key property for efficient probability computation by BP. Given a BN, a junction tree is constructed by way of triangulation or variable elimination [Jensen, 1996; Kask et al., 2001; Lauritzen and Spiegelhalter, 1988].

2.2 PCFGs and inside-outside probabilities

A PCFG is a CFG with probabilities assigned to production rules in such way that if a nonterminal A has N rules, A → α1, . . . ,A → αN, a probability pi is assigned to A → αi for i (1 ≤ i ≤ N) and ∑Ni=1 pi = 1 holds. pi is the probability of choosing A → αi to expand A in a probabilistic derivation. PCFGs are a basic tool for statistical natural language processing and include HMMs as a subclass.

Let A(i, j) denote an event that a nonterminal A probabilistically derives the substring wi, . . . ,wj of a sentence L = w1, . . . , wn (1 ≤ i ≤ j ≤ n). The probability of A(i, j) is called the inside probability of A(i, j) and defined as the sum of the products of probabilities associated with rules in a derivation belonging to A(i, j). Similarly the outside probability of A(i, j) w.r.t. L is the sum of products of the probabilities associated rules used in a derivation that starts from the start symbol and derives w1, . . . ,wi-1Awj+1, . . . ,wn. The product of inside-outside probabilities of A(i, j) gives the probability of deriving L via A(i, j). Inside-outside probabilities are computed by dynamic programming in time O(|L|3 ). We next generalize inside-outside probabilities in the context of probabilistic logic programming.

2.3 Probabilistic logic programming language PRISM

We briefly explain a probabilistic logic programming language PRISM. In a nutshell, PRISM is Prolog extended with tabling 3 , a probabilistic built-in predicate called msw (multiary random switch) and a generic parameter learning routine that learn parameters embedded in a program by computing generalized inside-outside probabilities [Sato and Kameya, 2001].

One of the basic ideas of PRISM is propositionalization of random variables using a special built-in predicate msw/3. Let V be a discrete random variable with a set R(V ) of ground terms as its range. To represent a proposition V = v

3 Tabling here means to memoize goals whose predicate symbol is declared as table predicate and to cache successful goals in a table for later reuse [Zhou and Sato, 2003]. An atom containing a table predicate is called a tabled atom.

(v ∈ R(V )), we introduce a ground term i as a name (identifier) for V and a ground msw atom msw(i, n, v) which is true iff the outcome of an n-th trial of V named i is v. Here n is a natural number. V as iids are represented by the set {msw(i, n, v) | v ∈ R(V ), n = 0, 1, . . .} of msw atoms. These msw atoms must satisfy certain conditions 4 . The probability of msw(i, n, v) being true is called a parameter.

In PRISM a program DB = R ∪ F consists of a set R of definite clauses whose head is not an msw atom and a set F of msw atoms together with a base distribution PF defining probabilities (parameters) of msw atoms in F. Simple distributions are definable soley in terms of msw atoms but complex distributions are constructed by using definite clauses. In our semantics, DB defines a probability measure PDB(·) over the set of Herbrand interpretations (distribution semantics [Sato and Kameya, 2001]). Hereafter we consider PDB (·) as a distribution on ground atoms as well.

2.4 Propositionalization through tabled search

In our approach, PDB(G), the probability of an atom G defined by a program DB, is computed in two steps. The first step is propositionalization. We apply the SLD refutation procedure [Doets, 1994] to DB and ⇐ G as a top-goal, we search for all SLD proofs of G and reduce G to a logically equivalent but propositional DNF formula E1 ∨ · · · ∨ Ek where Ei (1 ≤ i ≤ k), an explanation of G, is a conjunction of ground msw atoms. They record probabilistic choices made in the process of constructing an SLD proof of G and each msw atom represents a probabilistic event V = v for some random variable V . Then in the second step, we compute the probability of G as PDB (G) = PDB (E1 ∨ · · · ∨ Ek).

In general since there are exponentially many proofs and so are explanations, the naive proof search would produce an exponential size DNF. Fortunately however by introducing tabling in the first step, we can often produce an equivalent but polynomial size boolean formula such that common subexpressions in the Ei's are factored out as tabled atoms. The factored formula, Expl(G), becomes a set (conjunction) of definitions of the form H ⇔ W where a tabled atom H is defined by W which is a conjunction of tabled atoms and msw atoms. We assume the defining relation of these tabled atoms is acyclic. For convenience we sometimes think of each definition as an AND-OR graph and conventionally call Expl(G) an explanation graph as the collection of such AND-OR graphs. Hereafter Expl(G) stands for the factored formulas and their graphical representation as well.

2.5 Generalized inside-outside probabilities

To compute PDB (G), we convert each definition H ⇔ A1 ∨ . . .∨AL in Expl(G) where Ai = B1∧· · ·∧BMi ∧msw1∧· · ·∧

4 We require that PF (msw(i, n, v) ∧ msw(i, n, v′ )) = 0 for v ̸= v′ ∈ R(V ) and PF (Wv∈R(V ) msw(i, n, v)) = Pv∈R(V ) PF (msw(i, n, v)) = 1 holds for any n. Also when i ̸= i′ or n ̸= n′ , msw(i, n, v) and msw(i′ , n′ , v) must be independent and msw(i, n, v) and msw(i, n′ , v) must be identically distributed.

mswNi (1 ≤ i ≤ L) to a numerical sum-product equation.

Note that this conversion assumes the mutual exclusiveness of disjuncts {A1, . . . ,AL} and the independence of conjuncts {B1, . . . ,BMi , msw1, . . . , mswNi }. Although guaranteeing these two conditions is basically the user's responsibility, they are automatically satisfied as far as the PRISM program describing junction trees is concerned (see Section 3 and Lemma 3.3). We denote by Eq(G) the set of converted equations.

For a ground atom A, we call PDB(A) a P-variable. P-variables are just numerical variables named by ground atoms. As we assume the defining relation of tabled atoms is acyclic, P-variables in Eq(G) can be linearly ordered so that Eq(G) is efficiently solved in a bottom-up manner by dynamic programming in time proportional to the size of Eq(G). Also the acyclicity implies that a higher P-variable is a multivariate polynomial in the lower P-variables, and hence we can take the derivative of a higher P-variable as a function of the lower P-variables.

Suppose we are given a program DB. In an analogy to inside-outside probabilities in PCFGs, we define a generalized inside probability inside(A) of a ground atom A by inside(A) def = PDB(A) and extend the definition to a conjunction W of ground atoms by inside(W) def = PDB(W).

We also define a generalized outside probability outside(G;A) of A w.r.t. a top-goal G as follows. First enumerate A's occurrences in Expl(G) as

Then outside(G ; A) is recursively computed by Eq. 2 5 .

Using Eq. 2, all outside probabilities are computed in time in the size of Eq(G) [Sato and Kameya, 2001]. We can prove that for a ground atom A, the product inside(A) · outside(A) is the average number of occurrences of A in a proof of G and that our definition is a generalization of the usual definition of inside-outside probabilities in PCFGs [Lafferty, 1993].

5 As mentioned above, PDB(G), a P-variable, is a function of other P-variables PDB(A) and the mathematical definition of outside(G;A) is

3 Belief propagation as the generalized IO computation

In this section, we prove that the generalized IO computation, i.e. the computation of generalized inside-outside probabilities, subsumes BP in junction trees.

3.1 Program for BPmessages

Suppose we have a BN defining a joint distribution P(X1 = x1, . . . ,XN = xN) = ΠNi=1P(xi = Xi | Πi = πi) and a junction tree T = (V,E) such that P(x1, . . . , xN) = Πα∈V φα(xα). Let δ be the root node of T 6 .

We construct a PRISM program DBT = FT ∪ RT that describes BP in T as follows 7 . Introduce for each conditional probability P(xi | πi) a ground msw atom msw(bn(i, πi), once, xi). If Xi has no parent put πi = [] (null list). Define a finite set FT of msw atoms by

and set parameters θbn(i,πi),xi by

Then it is easy to see that every joint probability is represented by a conjunction of these ground msw atoms, i.e. we have

Next introduce an atom msw(bn(i,Πi), once,Xi) containing variables Xi and Πi for each i (1 ≤ i ≤ N). msw(bn(i, Πi), once, Xi) represents the conditional distribution P(Xi = xi | Πi = πi)8 . For every node α in the junction tree T , define a conjunction Wα(Xα) representing the potential φα(xα) of α and introduce a clause Cα defining a message atom qαγ(Xα∩γ) that describes a message in BP sent from α to its parent node γ. They are respectively defined as

6 In what follows, for simplicity we assume no evidence is given. When some variables are observed however, all conclusions remain valid, except that they are fixed to the observed values.

7 Programming convention follows Prolog.

8 Here we use intentionally Xi both as a logical variable and as a random variable to make explicit the correspondence between general msw atoms and conditional distributions in BN.

Here β1, . . . , βK (K ≥ 0) are the child nodes of α in T . The next lemma states that Wα(Xα) correctly describes the potential of node α. The proof is straightforward and omitted.

Lemma 3.1

For the root node δ in T , it has no parent but we add a special parent node 0 to V and define Cδ as

where β′1, . . . , β′K′ are the child nodes of δ. qδ0 has no arguments but calls every message atom directly or indirectly. Finally put

We illustrate a small example. Take a discrete Bayesian network BN1 on {X1, . . . ,X5} on the left-hand side of Figure 2 and its junction tree T1 on the right-hand side with the root node γ1. Dotted lines in BN1 indicate edges added by triangulation. Figure 3 shows the definitions of message atoms for T1.

3.2 Explanation graphs for BPmessages

Let DBT = FT ∪RT be the program constructed in Subsection 3.1. After declaring every qαγ predicate as a table predicate, we apply tabled search for all proofs to a top-goal ⇐ qδ0 where δ is the root node of T . The search always terminates and yields an explanation graph Expl(qδ0) which contains a

Figure 3: The definitions of message atoms for T1.

definition of tabled atom qαγ(xα∩γ) for every node α in T as shown below.

Here xα∩γ denotes an arbitrary ground instantiation of Xα∩γ and qαγ(xα∩γ) represents the message sent from α to γ, α's parent node, after receiving messages from α's child nodes β1, . . . , βK (see Figure 1).

We next prove that the recursive equations Eq. 3 are "solved" uniquely. Let Tα be the subtree of T rooted at Xα and Xξα be the set of variables appearing in Tα. We first introduce a formula τα(Xξα ) for α by Eq. 4 and rewrite it to Eq. 5. It represents the potential of the subtree Tα.

Lemma 3.2

□

(Proof) By well-founded induction on T . When α is a leaf in T , the proposition is obviously true. Assume it is true w.r.t. the child nodes of α.

3.3 BP and the generalized IO computation

Let PDBT be the distribution defined by DBT . The generalized inside probability of the tabled atom inside(qαγ(xα∩γ)) and the generalized outside probability outside(qδ0 ; qαγ(xα∩γ)) w.r.t. qδ0 can be computed using Eq. 3 by sum-product computation specified in Eq. 1 if the independence of conjuncts and the mutual exclusiveness of disjuncts on the right-hand side of Eq. 3 are guaranteed.

Since each msw atom msw(bn(i,Πi), once,Xi) occurs only once in some Wα reflecting the fact that a conditional distribution function P(xi | πi) in the BN belongs exclusively to one potential φα in the junction tree, Wα(xα) and the qβiα(xβi∩α)'s do not share any msw atoms. Hence the first condition, the independence condition, is satisfied automatically. On the other hand, proving the mutual exclusiveness condition is not straightforward. Lemma 3.3 below assures the exclusiveness condition when combined with Proposition 3.1.

Note that ξα ∩ γ = α ∩ γ holds thanks to RIP of T . So we rewrite τα(Xξα ) as

Lemma 3.3 Let xξα\γ and x′ξα\γ be two different ground instantiations of Xξα\γ. Then for an arbitrary ground instantiation xα∩γ of Xα∩γ, we have ¬ (τα(xξα\γ , xα∩γ ) ∧ τα(x′ξα\γ , xα∩γ )). □

(Sketch of proof) Without loss of generality, we can write Xξα\γ = Xi1 , . . . ,XiM in such a way that if Xij is a parent node of Xik in the original BN, Xij precedes Xik in this list. As xξα\γ = (xi1 , . . . , xiM ) ̸= x′ξα\γ = (x′i1 , . . . , x′iM ), there is a variable Xis such that xi1 = x′i1 , . . . , xis-1 = x′is-1 , xis ̸= x′is (1 ≤ s ≤ M). Then first we note Πis ⊆ Xξα holds since Xis appears only in Tα and the conditional distribution P(Xis | Πis ) must be contained in some potential in Tα by RIP. Second we have Πis ∩ Xξα\γ ⊆ {Xi1 , . . . ,Xis-1 }. We also have Πis ∩ Xξα∩γ = Πis ∩ Xα∩γ. We can conclude from these facts that (xξα\γ, xα∩γ) instantiates P(Xis | Πis ) to P(xis | πis ) while (x′ξα\γ , xα∩γ) instantiates P(Xis | Πis ) to P(x′is | πis ) where xis ̸= x′is . The rest is immediate and omitted. Q.E.D.

We now prove main theorems by applying computation in Eq. 1 to the tabled atoms defined by Eq. 3. Recall that inside(A) = PDBT (A) for a ground atom A where PDBT is the distribution defined by DBT. We derive an equation satisfied by inside probabilities of tabled atoms.

Theorem 3.1

□

Theorem 3.1 tells us that the generalized inside probabilities of tabled atoms satisfy exactly the same equations as messages in the collecting evidence phase of BP in T with the root node δ [Jensen, 1996; Lauritzen and Spiegelhalter, 1988; Shafer and Shenoy, 1990]. Hence, the bottom-up computation of generalized inside probabilities is identical to BP in the collecting evidence phase.

Let P1 be the distribution defined by BN1 in Figure 2. The equations for generalized inside probabilities of tabled atoms for the junction tree T1 are:

We next compute generalized outside probabilities of tabled atoms. Without loss of generality, we compute the outside probability of a tabled atom for β1. We apply the definition of generalized outside probability in Eq. 2 to Expl(qδ0) while noting that a tabled atom qβ1α(xβ1∩α) occurs in Expl(qδ0) as in Eq. 3. We obtain recursive equations about generalized outside probabilities as follows.

Theorem 3.2

(Proof)

outside(qδ0) = 1 holds for the top-node δ. Therefore we have the following corollary:

Corollary 3.1 Let β′1 , . . . , β′K′ be δ's child nodes.

Theorem 3.2 in conjunction with Corollary 3.1 clearly shows that the computation of generalized outside probabilities of tabled atoms in a top-down manner that starts from the topnode δ and proceeds to lower layers in Expl(qδ0) is exactly the same as the distributing evidence phase of BP in T with the root node δ [Jensen, 1996; Lauritzen and Spiegelhalter, 1988; Shafer and Shenoy, 1990]. We illustrate below the computation of the generalized outside probabilities of atoms in RT1 w.r.t. the junction tree T1 in Figure 2.

Finally we confirm that since inside(qδ0) = 1 and every tabled atom occurs only once in the proof of qδ0, the product of generalized inside-outside probabilities equals a marginal probability as follows.

4 Conclusion

We have proved that BP in junction trees is nothing but the generalized IO computation applied to junction trees (Theorem 3.1 and 3.2, Corollary 3.1). This equivalence is a generalization of the well-known equivalence between the forwardbackward algorithm and BP applied to HMMs [Smyth et al.,

1997] and provides a missing link between BP and PCFGs for the first time.

The most closely related work to ours is CFDs proposed by McAllester et al. [McAllester et al., 2004]. CFDs are a propositional framework for probabilistic inference of Markov random fields. They proved that a single algorithm can efficiently compute probabilities both for PCFGs and for BNs in their framework but the relationship between BP and their algorithm remains unclear. Since PRISM also generates propositional expressions (explanation graphs) from first order expressions by (tabled) search, it is an interesting future topic to relate CFDs to PRISM.