Inside Outside algorithm

This is a Method page for the Inside-outside algorithm.

Background

The inside-outside algorithm is a way of estimating probabilities in a PCFG. It is first introduced [| Baker, 1979]. The inside outside algorithm is in fact a generalization of the forward-backward algorithm (for hidden Markov models) to PCFGs.

It is often used as part of the EM algorithm for computing expectations.

Algorithm

The algorithm is a dynamic programming algorithm that is often used with chart parsers to estimate expected production counts. Here, we assume the grammar $G$ is of Chomsky Normal Form.

The algorithm works by computing 2 probabilities for each nonterminal $A$ and span $i,j$.

Inside probabilities

The inside probability is defined as $\alpha (A,i,j)=P(A{\overset {*}{\Rightarrow }}w_{i}...w_{j}|G,\mathbf {w} )$, which is the probability of a nonterminal $A$ generating the word sequence $w_{i}$ to $w_{j}$.

The inside probability can be calculated recursively with the following recurrence relation:

$\alpha (A,i,j)=\sum _{B,C}\sum _{i\leq k\leq j}p(A\rightarrow BC)\alpha (B,i,k)\alpha (C,k+1,j)$