PCFG 与 CYK 算法：句法分析的概率化

📐 概率上下文无关文法（PCFG）——句法分析的概率化

PCFG 为每条产生规则赋概率，形式化为 $G = (N, \Sigma, S, R, q)$：

• $N$：非终结符集合（S, NP, VP, PP, …）
• $\Sigma$：终结符集合（词汇表）
• $S$：起始符号
• $R$：规则集合，如 $\text{VP} \to \text{V} \ \text{NP}$
• $q(r)$：规则概率，满足 $\sum_{r: \text{LHS}(r)=A} q(r) = 1$

句子的概率 = 其解析树 $\tau$ 中所有规则概率的乘积： $P(\tau) = \prod_{r \in \tau} q(r)$

CYK 算法（Cocke-Younger-Kasami，$O(n^3 |G|)$）：

• 要求 CNF（Chomsky Normal Form）：$A \to BC$ 或 $A \to w$
• 填表：$\pi(i,j,A) = \max_{A \to BC, s} \left[q(A \to BC) \cdot \pi(i,s,B) \cdot \pi(s{+}1,j,C)\right]$
• $\pi(i,i,A) = q(A \to w_i)$ 若规则存在，否则为 0

与 HMM 的关系：HMM 可视为 PCFG 的特例——正则文法（所有规则形如 $A \to aB$ 或 $A \to a$），只能生成正则语言；PCFG 能表达嵌套结构（如括号匹配），表达力严格更强。