Inside–outside algorithm

For parsing algorithms in computer science, the inside–outside algorithm is a way of re-estimating production probabilities in a probabilistic context-free grammar. It was introduced by James K. Baker in 1979 as a generalization of the forward–backward algorithm for parameter estimation on hidden Markov models to stochastic context-free grammars. It is used to compute expectations, for example as part of the expectation–maximization algorithm (an unsupervised learning algorithm).

wp⋯wq, given the root nonterminal βj(p,q)=P(wpq|Npqj,G)

The outside probability Npqj and all the words outside αj(p,q)=P(w1(p−1),Npqj,w(q+1)m|G)

Base Case:

wp⋯wq starting with a subtree rooted at βj(p,q) is just the sum over all such possible rules:

N1.

General case:

Suppose there is a rule αj(p,q) is:

αj(p,q) is:

αj(p,q)=∑Nr,Ns∑k=q+1k=nP(Nr→NjNs)αr(p,k)βs(q+1,k)+∑Nr,Ns∑k=1k=p−1P(Nr→NsNj)αr(k,q)βs(k,p−1)

---

View original on Wikipedia | Back | FazBrowse Home