Abstract
This paper establishes a formal mathematical equivalence between Belief Propagation (BP), the standard inference algorithm for Bayesian Networks, and the Inside-Outside (IO) algorithm commonly used in natural language processing. By leveraging the PRISM probabilistic logic programming language, the research demonstrates that the "collecting evidence" and "distributing evidence" phases of BP correspond directly to the computation of "inside" and "outside" probabilities, respectively.
Introduction
In probabilistic modeling, two frameworks have historically developed in parallel: Bayesian Networks (BNs) for general uncertainty modeling and Probabilistic Context-Free Grammars (PCFGs) for statistical linguistics. While their relationship through models like Hidden Markov Models (HMMs) was known, a unifying theory for their core inference algorithms—Belief Propagation and the Inside-Outside algorithm—was missing. This paper bridges that gap, proving these algorithms are functionally identical when viewed through the lens of logic programming.
Methods
The study utilizes PRISM, a probabilistic logic programming language that integrates Prolog with statistical modeling. The proof is constructed through several key stages:
- Propositionalization: Discrete random variables from a BN are represented as sets of binary choices using PRISM’s
msw(multi-ary random switch) predicate. - Program Construction: A PRISM program defines the message-passing structure of a junction tree, where each message is a logical goal.
- Explanation Graphs: The program generates an "explanation graph" (an AND-OR graph) using tabling techniques to represent all ways to satisfy logical goals.
- Generalized IO Computation: A generalized IO algorithm is applied to this graph. Inside probabilities are computed bottom-up to find goal probabilities, while outside probabilities are computed top-down as partial derivatives of the top-goal probability to find contextual probabilities.
Key Insights and Results
The core contribution is the formal unification of BP and the IO algorithm. The two phases of Belief Propagation map perfectly onto the two phases of IO:
- Collecting Evidence (moving toward the junction tree root) is equivalent to computing Inside Probabilities.
- Distributing Evidence (moving away from the root) is equivalent to computing Outside Probabilities.
The paper provides formal proofs (Theorems 3.1, 3.2, and Corollary 3.1) showing that the equations for generalized inside/outside probabilities in a PRISM-encoded junction tree are identical to the evidence-passing equations in standard BP. Furthermore, it confirms that the product of these probabilities yields the correct marginal probability, consistent with both frameworks.
Limitations and Future Work
The current proof assumes discrete Bayesian Networks and BP without normalization. While PRISM can achieve $O(n^3)$ complexity for certain tasks, direct BN-to-PCFG mapping can lead to exponential complexity if propositionalization is not carefully managed. Future work includes relating this logic-based approach to Case-Factor Diagrams (CFDs).
Summary updated