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.