Inside–outside algorithm

Computing inside probabilities

Base Case:

${\displaystyle {\beta }_j(p,p)=P(w_p|N^j,G)}$

General case:

Suppose there is a rule ${\displaystyle N_j\to N_r{N}_s}$ in the grammar, then the probability of generating ${\displaystyle w_p\cdots w_q}$ starting with a subtree rooted at ${\displaystyle N_j}$ is:

${\displaystyle \sum _{k=p}^{k=q-1}P(N_j\to N_r{N}_s){\beta }_r(p,k){\beta }_s(k+1,q)}$

The inside probability ${\displaystyle {\beta }_j(p,q)}$ is just the sum over all such possible rules:

${\displaystyle {\beta }_j(p,q)=\sum _{N_r,N_s}\sum _{k=p}^{k=q-1}P(N_j\to N_r{N}_s){\beta }_r(p,k){\beta }_s(k+1,q)}$

Computing outside probabilities

Base Case:

${\displaystyle {\alpha }_j(1,n)=\{\begin{array}{ll}1& \text{if }j=1\\ 0& \text{otherwise}\end{array}}$

Here the start symbol is ${\displaystyle N_1}$.

General case:

Suppose there is a rule ${\displaystyle N_r\to N_j{N}_s}$ in the grammar that generates ${\displaystyle N_j}$. Then the left contribution of that rule to the outside probability ${\displaystyle {\alpha }_j(p,q)}$ is:

${\displaystyle \sum _{k=q+1}^{k=n}P(N_r\to N_j{N}_s){\alpha }_r(p,k){\beta }_s(q+1,k)}$

Now suppose there is a rule ${\displaystyle N_r\to N_s{N}_j}$ in the grammar. Then the right contribution of that rule to the outside probability ${\displaystyle {\alpha }_j(p,q)}$ is:

${\displaystyle \sum _{k=1}^{k=p-1}P(N_r\to N_s{N}_j){\alpha }_r(k,q){\beta }_s(k,p-1)}$

The outside probability ${\displaystyle {\alpha }_j(p,q)}$ is the sum of the left and right contributions over all such rules:

${\displaystyle {\alpha }_j(p,q)=\sum _{N_r,N_s}\sum _{k=q+1}^{k=n}P(N_r\to N_j{N}_s){\alpha }_r(p,k){\beta }_s(q+1,k)+\sum _{N_r,N_s}\sum _{k=1}^{k=p-1}P(N_r\to N_s{N}_j){\alpha }_r(k,q){\beta }_s(k,p-1)}$