While standard Context-Free Grammars (CFGs) delineate whether a sentence is grammatically licensed, they cannot adjudicate between competing syntactic interpretations when ambiguity arises. Probabilistic Context-Free Grammars (PCFGs) augment formal rewrite rules with conditional probability distributions, enabling statistical ranking of trees and unsupervised grammar induction via the Inside-Outside algorithm.
1. Formal Definition of Probabilistic CFGs
A Probabilistic Context-Free Grammar (PCFG) is a 5-tuple:
[
G = langle V_N, V_T, P, S, D
angle
]
where (V_N, V_T, P, S) constitute a standard CFG, and (D: P o [0, 1]) assigns a conditional probability (P(A o alpha)) to each production rule such that for every non-terminal (A in V_N), the probabilities of all rules expanding (A) sum strictly to unity:
[
sum_{alpha} P(A o alpha) = 1, quad orall A in V_N
]
The probability of a complete syntactic parse tree (T) generating terminal string (W) is defined by the product of the probabilities of all (k) rule expansions utilized in the derivation:
[
P(T, W) = prod_{i=1}^k P(A_i o alpha_i)
]
The total probability of generating sentence (W) is the marginal sum over all valid parse trees licensed by the grammar: (P(W) = sum_{T in au(W)} P(T, W)).
2. Structural Disambiguation via Probabilistic CYK
Given an ambiguous sentence with multiple valid trees, the optimal parse tree (hat{T}) is the one that maximizes conditional probability:
[
hat{T} = argmax_{T in au(W)} P(T mid W) = argmax_{T in au(W)} P(T, W)
]
To compute (hat{T}) efficiently without enumerating exponentially many trees, the CYK chart parser is extended into Probabilistic CYK. The chart table stores the maximum probability (pi[i, j, A]) of non-terminal (A) spanning substring (w_{i+1} dots w_j):
[
pi[i, j, A] = max_{k=i+1}^{j-1} max_{A o B C} left[ P(A o B C) imes pi[i, k, B] imes pi[k, j, C]
ight]
]
By recording backpointers to the maximizing rule (A o B C) and split point (k), the most probable parse tree is reconstructed in (mathcal{O}(n^3 |P|)) time.
3. Inside and Outside Probabilities
To evaluate marginal probabilities and train PCFG rule parameters from unparsed text, James Baker (1979) formulated the Inside-Outside algorithm—the recursive structural analogue of the Baum-Welch (Forward-Backward) algorithm for HMMs.
Inside Probability (beta_j(p, q)):
The probability of non-terminal (N^j) generating the specific substring spanning from word (w_p) through (w_q):
[
beta_j(p, q) = P(w_p dots w_q mid N^j ext{ dominates span } p dots q)
]
Calculated bottom-up: for terminals, (beta_j(k, k) = P(N^j o w_k)). For larger spans:
[
beta_j(p, q) = sum_{k=p}^{q-1} sum_{B, C} P(N^j o B C) beta_B(p, k) beta_C(k+1, q)
]
Outside Probability (alpha_j(p, q)):
The probability that the start symbol (S) generates the entire sentence prefix (w_1 dots w_{p-1}), non-terminal (N^j) at span ((p, q)), and sentence suffix (w_{q+1} dots w_n):
[
alpha_j(p, q) = P(w_1 dots w_{p-1}, N_{p,q}^j, w_{q+1} dots w_n mid S)
]
Calculated top-down from root (alpha_{ ext{root}}(1, n) = 1) down to base constituents.
4. The Expectation-Maximization (EM) Step
The expected number of times rule (A o B C) is used across a corpus of sentences is computed in the E-step by combining inside and outside probabilities:
[
E[ ext{count}(A o B C)] = sum_{ ext{corpus}} rac{1}{P(W)} sum_{p=1}^{n-1} sum_{q=p+1}^n sum_{k=p}^{q-1} alpha_A(p, q) P(A o B C) beta_B(p, k) beta_C(k+1, q)
]
In the M-step, updated rule probabilities are normalized by the expected count of the parent non-terminal:
[
hat{P}(A o B C) = rac{E[ ext{count}(A o B C)]}{sum_{alpha} E[ ext{count}(A o alpha)]}
]
Iterating to convergence guarantees monotonic non-decreasing likelihood (mathcal{L}(G mid ext{Corpus})), enabling unsupervised grammatical induction from raw acoustic or textual corpora.
