迁移来源

• 旧站标题：句法
• 新站标题：NLP / 相关资料 / 句法
• 旧站路径：/ai-kb/课程/nlp/resources/句法/
• 旧页面 ID：268

句法

形式语言推导不考!

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 操作, 但可以跟其余三种操作.