关于CKY句法分析效率的实验性研究

论文摘要

句法分析是自然语言处理领域非常基础而重要的问题,提高句法分析的准确度和分析效率一直都是人们研究的重点。在各种句法分析算法中,CKY是最著名、最常用的一种。本文对CKY算法的分析效率进行了实验性的研究,力图探索影响CKY算法效率的各种因素,进而提高CKY算法在实践应用中的分析速度。具体地,本文关注于两方面问题的研究:1.CKY算法的各种具体实现。尽管CKY算法具有理论的O(n~3)复杂度,然而实践中还是可以有多种不同效率的实现方式。本文系统地总结了各种实现方式,分析了时间复杂度,并提出了两种优化策略。实验表明了不同的实现的分析效率相差的确比较大,并且不同的文法上,最优的实现也并不一致。针对后一问题,我们提出了一种新的综合了其他实现的方式,称做联合实现。实验证明,联合实现可以在任何文法上都获得接近最优的分析效率。这对CKY算法的实践应用有着比较大的指导意义。2.不同的文法二元化方式。文法二元化对CKY算法获得O(n~3)的复杂度是至关重要的。然而,不同的二元化文法也会导致CKY分析效率上的差异。在做出简化假设的基础上,水文细致地分析了二元化对CKY分析效率的影响,认为好的二元化依赖于输入语言的某种内在性质,并提出了一种基于训练语料库信息的二元化方法。实验表明本文的二元化文法,相比现有的各种二元化方法,可以获得更高的分析效率。尽管在句法分析领域早面已经有许多研究CKY算法的工作,但据我们所知,还没有已知的工作总结研究过CKY的各种具体实现和文法二元化对CKY分析效率的影响。本文的工作对这两个基本问题做了有益的探索和研究。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景及意义
• 1.2 相关研究综述
• 1.3 本文的主要研究内容
• 第2章 CKY算法效率分析
• 2.1 引言
• 2.2 文法二元化
• 2.2.1 常见的二元化方法
• 2.2.2 中间非终结符的编码问题
• 2.3 CKY算法回顾
• 2.4 CKY运行效率分析
• 2.5 本章小结
• 第3章 关于CKY具体实现的实验性研究
• 3.1 引言
• 3.2 CKY的各种实现算法研究
• 3.2.1 基本实现
• 映射到'>3.2.2 优化1:将枚举空间从映射到
• 3.2.3 优化2:更精确地枚举Y和Z
• 3.2.4 CKY实现算法小结
• 3.3 实验结果及讨论
• 3.3.1 实验设定
• 3.3.2 不同实现间的比较
• 3.3.3 不同的二元化文法间的比较
• 3.4 相关工作回顾
• 3.5 本章小结
• 第4章 关于文法二元化的实验性研究
• 4.1 引言
• 4.2 最优文法二元化
• 4.2.1 模型简化假设
• 4.3 文法二元化对分析边数量的影响
• 4.3.1 中间边与完全边
• 4.3.2 文法二元化对完全边的影响
• 4.3.3 文法二元化对中间边的影响
• 4.3.4 二元化与输入句子性质
• 4.4 推理算法
• 4.4.1 指标计算
• 4.4.2 排序函数
• 4.5 实验
• 4.5.1 实验设置
• 4.5.2 实验1:各种二元化方法效果比较
• 4.5.3 实验2:结合迭代CKY分析算法
• 4.5.4 文法符号的结合趋势
• 4.6 相关工作回顾
• 4.7 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢