Inside-Outside Probability Computation for Belief Propagation

Taisuke SatoIJCAI 2007

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:

  1. Propositionalization: Discrete random variables from a BN are represented as sets of binary choices using PRISM’s msw (multi-ary random switch) predicate.
  2. Program Construction: A PRISM program defines the message-passing structure of a junction tree, where each message is a logical goal.
  3. Explanation Graphs: The program generates an "explanation graph" (an AND-OR graph) using tabling techniques to represent all ways to satisfy logical goals.
  4. 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.
Conversion of a Bayesian Network (BN1) into a Junction Tree (T1) with associated cliques.

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.
Message passing structure in a junction tree, illustrating the flow of evidence.

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

BibTeX
@inproceedings{sato2007inside,
  author = {Taisuke Sato},
  title = {{Inside-Outside Probability Computation for Belief Propagation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure