An efficient probabilistic context-free. Parsing algorithm that computes prefix probabilities

Overview

What is this paper all about?
Key ideas from the title:
Context-Free Parsing
Probabilistic
Computes

Context-Free Parsing

The ball is heavy.
Parser

The ball is heavy

Context-Free Parsing
Parser
Grammar

The ball is heavy.

The ball is heavy

Context-Free Parsing
Parser
Grammar
Lexicon

The ball is heavy.

The ball is heavy

Context-Free Parsing

What if there are multiple legal parses?
Example: “Yair looked over

Probabilistic Parsing

Use probabilities to find the most likely parse
Store typical probabilities

Prefix Probabilities

How likely is a partial parse?

Yair looked over …

Yair looked

Efficiency
The Earley algorithm (upon which Stolcke builds) is one of the

Parsing Algorithms
How do we construct a parse tree?
Work from grammar to

Earley Parsing Overview

Start with a root constituent, e.g. sentence
Until the sentence

Earley Parsing Overview

Earley parsing uses a chart rather than a tree

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Earley Parsing Example

S → NP VP NP → ART N VP →

Probabilistic Parsing
How do we parse probabilistically?
Assign probabilities to grammar rules and

Probabilistic Parsing

Terminology
Earley state: each step of the processing that a constituent

etc.

Probabilistic Parsing

Can represent the parse as a Markov chain:
Markov assumption (state

Probabilistic Parsing

Every Earley path corresponds to a parse tree
P(tree) = P(path)
Assign

Probabilistic Parse Example

Grammar

Lexicon

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Probabilistic Parse Example

Prefix Probabilities
Current algorithm reports parse tree probability when the sentence is

Prefix Probabilities
Solution: add a separate path probability
Same as before, but propagate

Prefix Probability Example

Prefix Probability Example

Prefix Probability Example

Prefix Probability Example

Prefix Probability Example

Prefix Probability Example

Prefix Probability Example

Prefix Probability Example

Prefix Probability Example