Inside Outside algorithm

From Cohen Courses
Revision as of 12:56, 29 November 2011 by Ysim (talk | contribs)
Jump to navigationJump to search

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 is of Chomsky Normal Form.

The algorithm works by computing 2 probabilities for each nonterminal and span .

Inside probabilities

The inside probability is defined as , which is the probability of a nonterminal generating the word sequence to .

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

Intuitively, this can be seen as computing the sum over all possible ways of building trees rooted by and generating the word span .

For the base case, it is simply .

Outside counts

The outside probability is defined as , which is the probability of generating a parse tree spanning the entire sentence that uses nonterminal to span .

The reccurrence relation is thus:

The first term is the expected count of generating trees where is used as a right subtree, and the second term is that of being generated as a left subtree.

Dynamic programming: Putting them together