成分句法与上下文无关分析

使用上下文无关文法、CKY和Earley等动态规划算法以及解决歧义的概率文法来计算句子的短语结构树。

Definition

成分句法分析根据上下文无关文法为句子分配一个嵌套的短语结构树，通常在概率文法下选择最可能的树。

Scope

涵盖使用上下文无关文法进行句法分析：CKY和Earley算法、乔姆斯基范式、概率上下文无关文法及其词汇化改进，以及基于树库训练的统计句法分析器。它涉及歧义消解和句法分析器评估。依存表示和非上下文无关形式主义在相关主题中讨论。

Core questions

• CKY算法如何以立方时间解析句子？
• 为什么文法通常必须首先转换为乔姆斯基范式？
• 概率文法和词汇化文法如何改进消歧？
• 句法分析器的准确性如何根据树库进行衡量？

Key concepts

• 上下文无关文法
• CKY算法
• Earley算法
• 乔姆斯基范式
• 概率上下文无关文法
• 词汇化
• 句法分析树
• 树库

Key theories

动态规划句法分析

CKY和Earley算法通过填充子成分图表，在多项式时间内计算所有句法分析结果，避免了朴素搜索的指数级爆炸。

词汇化概率句法分析

将规则概率与中心词关联起来，通过捕获普通PCFGs中缺失的词汇偏好，显著提高了句法分析的准确性。

History

CKY算法（1960年代）和Earley的1970年算法提供了高效的上下文无关识别。随着宾州树库的出现，Collins和Charniak的概率句法分析器以及后来的词汇化句法分析器在1990年代后期取得了高准确率，定义了神经网络模型出现之前的统计句法分析时代。

Debates

需要多少词汇化？

词汇化句法分析器准确但稀疏；争论点在于，通过仔细的状态分裂，非词汇化PCFGs是否能与它们匹敌，后来的研究表明这在一定程度上是可能的。

Key figures

• Jay Earley
• Michael Collins
• Eugene Charniak

Seminal works

• earley1970
• collins2003

Frequently asked questions

句法分析中的图表是什么？

图表是一个表格，存储句子每个跨度上找到的所有部分成分，以便共享的子结构只计算一次并重复使用，从而实现多项式时间句法分析。