Inside-Outside Probability Computation for Belief Propagation
Taisuke Sato
Tokyo Institute of Technology
2-12-1 Ôokayama Meguro-ku Tokyo Japan 152-8552

Abstract
In this paper we prove that the well-known correspondence between the forward-backward algorithm for hidden Markov models (HMMs) and belief propagation (BP) applied to HMMs can be generalized to one between BP for junction trees andthe generalized inside-outside probability computation for probabilistic logic programs applied tojunction trees.

1 Introduction
Bayesian networks (BNs) and probabilistic context freegrammars (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 isa 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 paper1 we upgrade this correspondence. We provethat the inside-outside probability computation in the IO algorithm, when generalized for probabilistic logic programs andapplied to junction trees, yields BP. In particular we provethat 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 languagethat can describe BNs and PCFGs2 . We choose PRISM [Satoand Kameya, 2001] as a first-order probabilistic language
for this purpose. We also need “propositionalization” of1

We assume in this paper that BNs are discrete and BP is withoutnormalization.
2
Note that BNs are a propositional framework that deal withfinitely many random variables while PCFGs allow recursion andhave to deal with infinitely many random variables describing probabilistic choices in a sentence derivation.

BNs [Sato and Kameya, 2001; McAllester et al., 2004;
Chavira and Darwiche, 2005]. By propositionalization wemean 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].
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 inthis 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 ) =ΠN
i=1 P (Xi = xi | Πi = πi ) such that nodes are randomvariables 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 caseletter xi denotes a value of Xi and similarly for πi . We
denote the range of Xi by R(Xi ) and the direct productR(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 ) asa function of xi , πi , the set {xi } ∪ πi is called the arguments of P (xi | πi ). Let α = {s1 , . . . , sk } be a set ofvariable indices (⊆ {1, . . . , N }). Xα stands for the set ofvariables {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 β islabeled 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 theirarguments 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 inevery node on the path between α and β. RIP ensures theconditional 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 toPN
A → αi for i (1 ≤ i ≤ N ) and i=1 pi = 1 holds. pi is theprobability 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 thesum 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 thestart symbol and derives w1 , . . . , wi−1 Awj+1 , . . . , wn . The
product of inside-outside probabilities of A(i, j) gives theprobability of deriving L via A(i, j). Inside-outside probabil3
ities are computed by dynamic programming in time O(|L| ).
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 withtabling3 , a probabilistic built-in predicate called msw (multiary random switch) and a generic parameter learning routinethat learn parameters embedded in a program by computing
generalized inside-outside probabilities [Sato and Kameya,
2001].
One of the basic ideas of PRISM is propositionalizationof random variables using a special built-in predicate msw/3.
Let V be a discrete random variable with a set R(V ) ofground terms as its range. To represent a proposition V = v
3Tabling 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 tablepredicate 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 istrue iff the outcome of an n-th trial of V named i is v. Heren 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 conditions4 . 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 ofdefinite 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 firststep 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 whereEi (1 ≤ i ≤ k), an explanation of G, is a conjunction ofground msw atoms. They record probabilistic choices madein the process of constructing an SLD proof of G and each
msw atom represents a probabilistic event V = v for somerandom variable V . Then in the second step, we compute theprobability of G as PDB (G) = PDB (E1 ∨ · · · ∨ Ek ).
In general since there are exponentially many proofs andso 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 thesetabled atoms is acyclic. For convenience we sometimes thinkof each definition as an AND-OR graph and conventionallycall 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)W∧ msw(i, n, v 0 )) = 0
for v 6= v 0 ∈ R(V ) and PF ( v∈R(V ) msw(i, n, v)) =P
0v∈R(V ) PF (msw(i, n, v)) = 1 holds for any n. Also when i 6= ior n 6= n0 , msw(i, n, v) and msw(i0 , n0 , v) must be independent andmsw(i, n, v) and msw(i, n0 , v) must be identically distributed.

mswNi (1 ≤ i ≤ L) to a numerical sum-product equation.
PDB (H) = PDB (A1 ) + · · · + PDB (AL )PDB (Ai ) = PDB (B1 ) · · · PDB (BMi )·PDB (msw1 ) · · · PDB (mswNi )

TD

(1)

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 groundatoms. As we assume the defining relation of tabled atoms
is acyclic, P-variables in Eq(G) can be linearly ordered sothat Eq(G) is efficiently solved in a bottom-up manner bydynamic programming in time proportional to the size of
Eq(G). Also the acyclicity implies that a higher P-variable isa multivariate polynomial in the lower P-variables, and hence
we can take the derivative of a higher P-variable as a functionof the lower P-variables.
Suppose we are given a program DB . In an analogy toinside-outside probabilities in PCFGs, we define a generalized inside probability inside(A) of a ground atom A bydef

inside(A) = PDB (A) and extend the definition to a condef

junction W of ground atoms by inside(W ) = 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(

H1 ⇔ (A ∧ W1,1 ) ∨ · · · ∨ (A ∧ W1,i1 )···HJ ⇔ (A ∧ WJ,1 ) ∨ · · · ∨ (A ∧ WJ,iJ ).

E.
G
root
node

J

q

D

( x JDDJ)WDE
Figure 1: Junction tree T = hV, Ei

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 BP messages

Suppose we have a BN defining a joint distribution P (X1 =x1 , . . . , X N = x N ) = Π N
i=1 P (xi = Xi | Πi = πi ) anda 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 DB T = FT ∪ RT
that describes BP in T as follows7 . Introduce for eachconditional 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 bydef

FT = { msw(bn(i, πi ), once, xi ) |1 ≤ i ≤ N, xi ∈ R(Xi ), πi ∈ R(Πi ) }and set parameters θbn(i,πi ),xi by

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

θbn(i,πi ),xi = PF (msw(bn(i, πi ), once, xi )) = P (xi | πi ).

outside(G ; G) = 1
Qi1
outside(G ; A) = outside(G ; H1 ) j=1
inside(W1,j )Q iJ+ · · · + outside(G ; HJ ) j=1 inside(WJ,j ).
(2)
Using Eq. 2, all outside probabilities are computed in time inthe size of Eq(G) [Sato and Kameya, 2001]. We can provethat for a ground atom A, the product inside(A) · outside(A)is the average number of occurrences of A in a proof of G andthat our definition is a generalization of the usual definition of
inside-outside probabilities in PCFGs [Lafferty, 1993].

Then it is easy to see that every joint probability is represented
by a conjunction of these ground msw atoms, i.e. we haveVN
P (x1 , . . . , xN ) = PFi=1 msw(bn(i, πi ), once, xi ) .

5

As mentioned above, PDB (G), a P-variable, is a functionof other P-variables PDB (A) and the mathematical definition ofoutside(G ; A) isdef

outside(G ; A) =which derives Eq. 2.

∂ PDB (G)∂ PDB (A)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
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 arandom variable to make explicit the correspondence between general msw atoms and conditional distributions in BN.

from α to its parent node γ. They are respectively defined asdef V
Wα (Xα ) =P (xi |πi )∈φα msw(bn(i, Πi ), once, Xi ),def

Cα = qαγ (Xα∩γ ) ⇐ Wα (Xα )∧qβ1 α (Xβ1 ∩α ) ∧ · · · ∧ qβK α (XβK ∩α ).

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


qγ1 0 ⇐ msw(bn(1, once, []), X1 ) ∧msw(bn(5, once, [X4 , X1 ]), X5 )∧qα1 γ1 (X1 , X4 )qα1 γ1 (X1 , X4 ) ⇐R T1
msw(bn(2, once, [X1 ]), X2 ) ∧ qβ1 α1 (X2 , X4 )qβ1 α1 (X2 , X4 ) ⇐msw(bn(3, once, [X2 ]), X3 ) ∧
msw(bn(4, once, [X3 ]), X4 )Figure 3: The definitions of message atoms for T1 .

PF (Wα (xα ))=YP (xi | πi ) = φα (xα ).

i:P (xi |πi )∈φα
For the root node δ in T , it has no parent but we add a special
parent node 0 to V and define Cδ asdef

Cδ = qδ0 ⇐ Wδ (Xδ )∧0 δ (Xβ 0 ∩δ )qβ10 δ (Xβ10 ∩δ ) ∧ · · · ∧ qβK0
K00
where β10 , . . . , βK
0 are the child nodes of δ. qδ0 has no arguments but calls every message atom directly or indirectly.
Finally put
def

RT = {Cα | α ∈ V, T = (V, E)}.
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 theroot node γ1 . Dotted lines in BN1 indicate edges added by triangulation. Figure 3 shows the definitions of message atoms
for T1 .

,X
X1

X1

P(x1)
P(x5 |x1, x4)
X 1, X 4, X 5

definition of tabled atom qαγ (xα∩γ ) for every node α in T as
shown below.
WVKqαγ (xα∩γ ) ⇔ xα\γ Wα (xα ) ∧ i=1 qβi α (xβi ∩α ) .
(3)Here xα∩γ denotes an arbitrary ground instantiation of Xα∩γ
and qαγ (xα∩γ ) represents the message sent from α to γ, α’sparent 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 toEq. 5. It represents the potential of the subtree Tα .
def V
τα (Xξα ) =(4)ρ∈Tα Wρ (Xρ )VK= Wα (Xα ) ∧ i=1 τβi (Xξβi )(5)Lemma 3.2ξαξβi \ γξα \ γ4J1={1,4,5}

X2

Proposition 3.1 qαγ (xα∩γ ) =P(x2 |x1)
X 1, X 2, X 4

D1={1,2,4}

X

4

X3

X

2,

X4
X5

P(x3 |X 2)
P(x4 |x3)
X 2, X 3, X 4
E1={2,3,4}

BN 1

Junction tree T 1

Figure 2: BN1 and a junction tree T1

3.2

SK= α ∪ i=1 ξβi= (ξβi \ α) ∪ (βi ∩ (α \ γ)) (from RIP of T )SK(6)= (α \ γ) ∪ i=1 (ξβi \ α)Explanation graphs for BP messages

Let DB T = 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 aWxξα \γ τα (xξα )(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 α.
_τα (xξα )xξα \γ=_ _xα\γ xβ1 \α···_τα (xξα ) by Eq. 6

xβK \α((α \ γ) and (βi \ α)’s are mutually disjoint)



K
_
^
_
Wα (xα ) ∧=τβi (xξβi ) by Eq. 5
=

xα\γ

i=1

_

K
^

xα\γ

Wα (xα ) ∧i=1= qαγ (xα∩γ ) by Eq. 3xξβ \αiqβi α (xβi ∩α )!

by induction
Q.E.D.

3.3

BP and the generalized IO computation

Let PDB T be the distribution defined by DB T . 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 exclusivenessof 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α ) andthe qβi α (xβi ∩α )’s do not share any msw atoms. Hence thefirst 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 werewrite τα (Xξα ) asτα (Xξα ) = τα (Xξα \γ , Xξα ∩γ )= τα (Xξα \α , Xα∩γ ).
Lemma 3.3 Let xξα \γ and x0ξα \γ be two different
ground instantiations of Xξα \γ .
Then for an arbitrary
groundinstantiation
xofα∩γ
 Xα∩γ , we have¬ τα (xξα \γ , xα∩γ ) ∧ τα (x0ξα \γ , xα∩γ ) .

(Sketch of proof) Without loss of generality, we can writeXξα \γ = Xi1 , . . . , XiM in such a way that if Xij is a parent node of Xik in the original BN, Xij precedes Xik in thislist. As xξα \γ = (xi1 , . . . , xiM ) 6= x0ξα \γ = (x0i1 , . . . , x0iM ),there is a variable Xis such that xi1 = x0i1 , . . . , xis−1 =x0is−1 , xis 6= x0is (1 ≤ s ≤ M ). Then first we noteΠis ⊆ Xξα holds since Xis appears only in Tα and theconditional distribution P (Xis | Πis ) must be contained insome 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 (x0ξα \γ , xα∩γ ) instantiates P (Xis | Πis ) to P (x0is | πis ) where xis 6= x0is . The
rest is immediate and omitted.
Q.E.D.

(Proof)inside(qαγ (xα∩γ ))= PDB T (qαγ (xα∩γ ))
W

τ
(x
)
by Proposition 3.1= PDB Tαξαxξα \γP=xξ \γ PDB T (τα (xξα )) by Lemma 3.3
P α P
P
=
xα\γ
xβK \α PDB T (Wα (xα )) ·xβ1 \α · · ·QK
i=1 PDB T (τβi (xξβi )) by Eq. 6


K
X
_
Y
=
PDB T (Wα (xα )) PDB T τβi (xξβi )
xα\γ

=

i=1

X

φ(xα )X

φ(xα )

xα\γ

=

K
Y

xβi \αPDB T (qβi α (xξβi ∩α )) by Lemma 3.1

i=1

xα\γ

K
Y

inside(qβi α (xξβi ∩α ))Q.E.D.

i=1

Theorem 3.1 tells us that the generalized inside probabilitiesof tabled atoms satisfy exactly the same equations as messages in the collecting evidence phase of BP in T with theroot 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:inside(qα1 γ1 (x1 , x4 ))P=
x2 PDB T1 (msw(bn(2, [x1 ]), x2 )) ·=P

inside(qβ1 α1 (x2 , x4 ))x2 P1 (x2 | x1 )inside(qβ1 α1 (x2 , x4 ))inside(qβ1 α1 (x2 , x4 ))P=
x3 PDB T1 (msw(bn(3, [x2 ]), x3 )) ·PDB T1 (msw(bn(4, [x3 ]), x4 ))=P

x3 P1 (x3 | x2 ) · P1 (x4 | x3 ).

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

We next compute generalized outside probabilities oftabled atoms. Without loss of generality, we compute theoutside probability of a tabled atom for β1 . We apply
the definition of generalized outside probability in Eq. 2 toExpl(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.1

Theorem 3.2

inside(qαγ (xα∩γ )) =

X

xα\γ

φα (xα )K
Yinside(qβi α (xβi ∩α )).

i=1



P

φα (xα )x
QKα\β1outside(qαγ (xα∩γ )) i=2 inside(qβi α (xβi ∩α )).

outside(qβ1 α (xβ1 ∩α )) =(Proof)outside(qXβ1 α (xβ1 ∩α ))=outside(qαγ (xα∩γ ))=Xx(α∩γ)\(β1 ∩α)QKi=2 inside(qβi α (xβi ∩α ))x(α\γ)\(β1 ∩α)

x∆

i=2

X

φα (xα )by Eq. 2
KY
outside(qαγ (xα∩γ ))φα (xα ) inside(qβi α (xβi ∩α ))where ∆ = ((α ∩ γ) \ (α ∩ β1 )) ∪ ((α \ γ) \ (β1 ∩ α))= α \ β1KYX
φα (xα )outside(qαγ (xα∩γ )) inside(qβi α (xβi ∩α )).
=
xα\β1

i=2

Q.E.D.
outside(qδ0 ) = 1 holds for the top-node δ. Therefore wehave the following corollary:0
Corollary 3.1 Let β10 , . . . , βK
0 be δ’s child nodes.
0

outside(qβ10 δ (xβ10 ∩δ )) =Xxδ\β 01

φδ (xδ )K
Yinside(qβi0 δ (xβi0 ∩δ )).

i=2


Theorem 3.2 in conjunction with Corollary 3.1 clearly showsthat the computation of generalized outside probabilities oftabled 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 withthe root node δ [Jensen, 1996; Lauritzen and Spiegelhalter,
1988; Shafer and Shenoy, 1990]. We illustrate below thecomputation of the generalized outside probabilities of atoms
in RT1 w.r.t. the junction tree T1 in Figure 2.
outside(qα1 γ1 (x1 , x4 ))P=
x5 PDB T1 (msw(bn(1, []), x1 ) ∧=P

msw(bn(5, [x1 , x4 ]), x5 ))P(x)P
1 (x5 | x1 , x4 )x5 1 1outside(qβ1 α1 (x2 , x4 ))P=
x1 outside(qα1 γ1 (x1 , x4 )) ·PDB T1 (msw(bn(2, [x1 ]), x2 ))=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 intheir 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 torelate CFDs to PRISM.

P

x1 ,x5 P1 (x1 )P1 (x5 | x1 , x4 )P1 (x2 | x1 ).

Finally we confirm that since inside(qδ0 ) = 1 and every
tabled atom occurs only once in the proof of qδ0 , the productof generalized inside-outside probabilities equals a marginal
probability as follows.
inside(qβP
1 α1 (x2 , x4 ))outside(qβ1 α1 (x2 , x4 ))= P
x3 P1 (x3 | x2 )P1 (x4 | x3 )x1 ,x5 P1 (x1 )P1 (x5 | x1 , x4 )P1 (x2 | x1 )= P1 (x4 | x2 )P1 (x2 ) = P1 (x2 , x4 ).

4 Conclusion
We have proved that BP in junction trees is nothing but thegeneralized 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.,References[Baker, 1979] J. K. Baker. Trainable grammars for speech recognition. In Proceedings of Spring Conference of the AcousticalSociety of America, pages 547–550, 1979.
[Chavira and Darwiche, 2005] M. Chavira and A. Darwiche. Compiling bayesian networks with local structure. In Proceedings ofthe 19th International Joint Conference on Artificial Intelligence(IJCAI’05), pages 1306–1312, 2005.
[Doets, 1994] K. Doets. From Logic to Logic Programming. The
MIT Press, 1994.
[Jensen, 1996] F. V. Jensen. An Introduction to Bayesian Networks.
UCL Press, 1996.
[Kask et al., 2001] K. Kask, R. Dechter, J Larrosa, and F. Cozman.
Bucket-tree elimination for automated reasoning. ICS Technical
Report Technical Report No.R92, UC Irvine, 2001.
[Lafferty, 1993 ] J.D. Lafferty. A derivation of the Inside-Outside
Algorithm from the EM algorithm. Technical Report TR-IT0056, IBM T.J.Watson Research Center, 1993.
[Lauritzen and Spiegelhalter, 1988] S.L. Lauritzen and D.J.
Spiegelhalter. Local computations with probabilities on graphical structures and their applications to expert systems. Journalof the Royal Statistical Society, B, 50:157–224, 1988.
[McAllester et al., 2004] D. McAllester, M. Collins, and F. Pereira.
Case-factor diagrams for structured probabilistic modeling. In
Proceedings of the 20th Annual Conference on Uncertainty in
Artificial Intelligence (UAI-04), pages 382–391, Arlington, Virginia, 2004. AUAI Press.
[Pynadath and Wellman, 1996] D. V. Pynadath and M. P. Wellman.
Generalized queries on probabilistic context-free grammars. In
Proceedings of the 14th National Conference on Artificial Intelligence (AAAI’96), pages 1285–1290, 1996.
[Sato and Kameya, 2001 ] T. Sato and Y. Kameya. Parameter learning of logic programs for symbolic-statistical modeling. Journalof Artificial Intelligence Research, 15:391–454, 2001.
[Shafer and Shenoy, 1990 ] G.R. Shafer and P.P. Shenoy. Probability propagation. Annals of Mathematics and Artificial Intelligence, 2:327–352, 1990.
[Smyth et al., 1997] P. Smyth, D. Heckerman, and M. Jordan. Probabilistic independence networks for hidden markov probability
models. Neural Computation, 9(2):227–269, 1997.
[Zhou and Sato, 2003 ] Neng-Fa Zhou and T. Sato. Efficient Fixpoint Computation in Linear Tabling. In Proceedings of theFifth ACM-SIGPLAN International Conference on Principles
and Practice of Declarative Programming (PPDP2003), pages
275–283, 2003.