Bangda Sun

Practice makes perfect

Stanford NLP (Coursera) Notes (13) - Probabilistic Parsing

Probabilistic Parsing, PCFG and More.

1. CFG and PCFG

CFG (Context-Free-Grammar) can be simply regarded as rules or lexicon, some examples of CFG:

\[
\begin{aligned}
S &\rightarrow NP\hspace{3mm} VP \\
VP &\rightarrow V\hspace{3mm} NP \\
VP &\rightarrow V\hspace{3mm} NP\hspace{3mm} PP \\
N &\rightarrow \text{people} \\
N &\rightarrow \text{fish}
\end{aligned}
\]

A tree structure can be built based on the CFG.

The formal definition of CFG: \(G = (T, N, S, R)\), where \(T\) is a set of terminal nodes, \(N\) is a set of non-terminal nodes, \(S\) is the start symbol, \(R\) is a set of rules and productions of the form \(X\rightarrow \gamma\) , and \(X\in N\) and \(\gamma\in(N\cup T)\).

In NLP, another structure - PCFG (Probabilistic CFG) is used. Compared with CFG, it add \(P\): probability function. \(P: R \rightarrow [0, 1]\), for \(\forall X\in N\),

\[
\sum_{X\rightarrow \gamma\in R} P(X\rightarrow \gamma) = 1.
\]

2. Chomsky Normal Form

Chomsky Normal Form is a type of transforms that restricting the grammar form for efficient parsing. All rules are of the form: \(X\rightarrow YZ\) or \(X\rightarrow w\), where \(X, Y, Z\in N\) and \(w\in T\). In detail:

  • Empties and Unaries are removed recursively
  • \(n\)-ary rules are divided by introducing new non-terminals

Binarization is crucial for cubic time CFG parsing.

3. CKY Parsing Algorithm

CKY (Cocke Kasami Younger) algorithm can extract polynomial time parsing of PCFGs (find the most probable parse of the sentence according to PCFG).

A detailed example can be found in original slides.