句法

形式语言推导不考!

CYK## PCFGS

Inside-Outside（内外）算法的问题 - 计算速度慢 - 每次迭代的时间复杂度为 $O(m^3 n^3)$，其中 $m=\sum_{i=1}^{w} l_i$，$n$ 表示文法中非终结符的数量。 - 容易陷入局部最优 - Charniak 指出，在每一次试验中，算法往往会收敛到不同的局部最大值。

PCFG 的缺点 - 独立性假设过强 - 非终结符规则的应用未利用词汇信息 - 对父子节点关系之外的结构差异不够敏感

Eager

依存句法 4 条公理 - 一个句子只有一个独立的成分 - 句子的其他成分都从属于某一成分 - 任何成分都不能依存于两个或多个成分 - 如果成分 A 直接从属于成分 B, 而成分 C 在句子中位于 A 和 B 之间, 那么成分 C 或者从属于 A, 或者从属于 B, 或者从属于 A 和 B 之间的某一成分.

句法分析算法: - 生成式的分析方法 - 判别式的分析方法 - 决策式的分析方法 - 基于约束满足的分析方法.

Arc-eager 分析算法: 是一种决策式的分析方法.

一共四种操作: - (1) Shift: 将右侧队列队首元素移至左侧栈顶. - (2) Left-arc: 将左侧栈顶元素移除栈, 并连在右侧队首元素下放, 此时该元素部分的树已构建完成. - (3) Right-arc: 将右侧队首元素移至左侧栈顶, 并将其挂在原栈顶元素下. - (4) Reduce: 将左侧栈顶元素弹出, 此时该元素及其子树部分已构建完成.

注意: Right-arc 操作后不可能也不应该直接跟 Left-arc 操作, 但可以跟其余三种操作.