放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

CS224n笔记6 句法分析

目录

hankcs.com 2017-06-16 下午9.34.30.png句法分析还算熟悉,就跟着复习了神经网络句法分析的动机与手法,了解一下比较前沿的动向。

语言学的两种观点

如何描述语法,有两种主流观点,其中一种是短语结构文法,英文术语是:Constituency = phrase structure grammar = context-free grammars (CFGs)。

这种短语语法用固定数量的rule分解句子为短语和单词、分解短语为更短的短语或单词……一个取自WSJ语料库的短语结构树示例:

hankcs.com 2016-12-30 下午1.06.21.png

另一种是依存结构,用单词之间的依存关系来表达语法。如果一个单词修饰另一个单词,则称该单词依赖于另一个单词。一个由HanLP输出的依存句法树如下:

神经网络依存句法分析51.png

歧义

通过句法树可以表达歧义,一个确定的句法树对应句子的一个确定解读,比如对介词短语依附(attachment of prepositional phrases (PPs)):

hankcs.com 2017-06-12 下午5.08.57.png

from space这个介词短语到底依附谁?不同的答案导致对句子不同的理解。

依附歧义

很难确定如何把一个短语(介词短语、状语短语、分词短语、不定式)依附到其他成分上去,比如下列句子:

hankcs.com 2017-06-12 下午5.18.05.png

每个括号中都是一个短语,它们依附的对象各不相同。对于$n$个短语来讲,组成的树形结构有$C_n=\frac{(2n)!}{(n+1)!n!}$。这是Catalan数,指数级增长,常用于树形结构的计数问题。

标注数据集的崛起:Universal Dependencies treebanks

虽然上下文无关文法中的语法集很容易写,无非是有限数量的规则而已,但人工费时费力标注的树库却茁壮成长了起来。在1993年首次面世的Universal Dependencies treebanks如今在Google的赞助下发布了2.0,其授权大多是署名-相同方式共享,覆盖了全世界绝大多数语言(不包括简体中文)。

其官网是:http://universaldependencies.org/

GitHub主页是:https://github.com/UniversalDependencies

树库示例:

hankcs.com 2017-06-12 下午5.49.15.png

人们偏好树库多于规则的原因是显而易见的,树库虽然标注难度高,但每一份劳动都可被复用(可以用于词性标注命名实体识别等等任务);而每个人编写的规则都不同,并且死板又丑陋。树库的多用性还是得其作为评测的标杆数据,得到了越来越多的引用。

依存文法与依存结构

这节课以及练习用的都是依存句法树,而不是短语结构树。这并不是随机选择,而是由于前者的优势。90年代的句法分析论文99%都是短语结构树,但后来人们发现依存句法树标注简单,parser准确率高,所以后来(特别是最近十年)基本上就是依存句法树的天下了(至少80%)。

不标注依存弧label的依存句法树就是短语结构树的一种:

hankcs.com 2017-06-12 下午6.10.12.png

一旦标上了,两者就彻底不同了:

hankcs.com 2017-06-12 下午6.10.59.png

这里箭头的尾部是head(被修饰的主题),箭头指向的是dependent(修饰语)。

起源

语法依存的概念可以追溯到公元前4世纪印度语言学家Panini对语义、句法和形态依存的分类研究,但一般认为现代依存语法理论的创立者是法国语言学家Lucien Tesnière(1893—1954)。L.Tesnière的思想主要反映在他1959年出版的《结构句法基础》(Eléments de syntaxe structurale)一书中[Tesnière,1959]。

——《统计自然语言处理》

hankcs.com 2017-06-12 下午6.23.28.png

课件中还有更详细的历史,不太感兴趣,跳过;只记录一点,第一个computational句法分析器也是依存句法分析器。

一些细节

人们画依存句法树的弧的方式不同,这门课是head指向dependent(即箭头指向的词语是依赖者,箭头尾部的词语是被依赖者),我的偏好是反过来。

每个句子都有一个虚根,代表句子之外的开始,这样句子中的每个单词都有自己的依存对象了。

句法分析可用的特征

  • 双词汇亲和(Bilexical affinities),比如discussion与issues。

  • 词语间距,因为一般相邻的词语才具有依存关系

  • 中间词语,如果中间词语是动词或标点,则两边的词语不太可能有依存

  • 词语配价,一个词语最多有几个依赖者。

依存句法分析

有几个约束条件:

  • ROOT只能被一个词依赖。

  • 无环。

英语中大部分句子是projective的,少数是non-projective的:

hankcs.com 2017-06-15 下午8.59.51.png

有个学生问是否可以将一个依存句法树还原成句子,答案是否定的。

文献中的依存句法分析方法有:

Dynamic programming

估计是找出以某head结尾的字串对应的最可能的句法树。

Graph algorithms

最小生成树。

Constraint Satisfaction

估计是在某个图上逐步删除不符合要求的边,直到成为一棵树。

“Transition-based parsing” or “deterministic dependency parsing”

主流方法,基于贪心决策动作拼装句法树。

Arc-standard transition

动作体系的formal描述如下:

hankcs.com 2017-06-16 下午9.01.26.png

图解还是我自己整理的更清晰:http://www.hankcs.com/nlp/parsing/neural-network-based-dependency-parser.html/2#h2-6

课件上画得没有这么详细。

MaltParser

无搜索,贪婪地下转移决策,线性复杂度,只损失了一点效果。加个beam search会上升一点。

传统特征表示

2017-06-16_21-08-13.png

无非是栈和队列中单词、词性、依存标签的组合的特征函数,一个超长的稀疏01向量。

效果评估

评测指标是UAS(不考虑标签只考虑弧)或LAS(同时考虑标签和弧):

hankcs.com 2017-06-16 下午9.11.38.png

课件上有一页讲依存弧可以用来判断蛋白质的相互作用:

hankcs.com 2017-06-16 下午9.14.13.png

投射性

Manning也跳过了这一张PPT,大意就是CFG转换得到的依存树一定是投射性的,但依存理论允许非投射性的依存句法树(一些语义需要通过非投射性表达)。

hankcs.com 2017-06-16 下午9.17.56.png

arc-standard算法只能拼装投射性的句法树,但换个体系、加上后处理、采用graph-based方法就能得到非投射的句法树。

为什么需要神经网络句法分析器

传统特征表示稀疏、不完全、计算代价大(SVM之类的线性分类器本身是很快的,而传统parser的95%时间都花在拼装查询特征上了)。

神经网络依存句法分析器

从理论到代码的分析参考:http://www.hankcs.com/nlp/parsing/neural-network-based-dependency-parser.html

无非是传统方法拼接单词、词性、依存标签,新方法拼接它们的向量表示:

hankcs.com 2017-06-16 下午9.32.16.png

然后模型是一个司空见惯的三层神经网络:

hankcs.com 2017-06-16 下午9.34.30.png

事实上,在“深度学习”“神经网络”的喧嚣中冷静下来回顾一下,相较于传统的graph-based方法,花了这么多功夫得到的只是0.1%的LAS提升:

hankcs.com 2017-06-16 下午9.26.01.png

他们说速度上升很大啊,我的实际体验是取决于矩阵运算模块的加速比。如果用一些类似于Eigen之类高度优化的C++并行矩阵运算库就很快,如果是手写的串行线性代数库就很慢。

为何需要非线性

以前的课上讲过,又讲了一遍,不啰嗦了。

有很多S形函数可选:

hankcs.com 2017-06-16 下午9.41.54.png

tanh是sigmod的缩放偏移版:

$$\tanh(z) = 2logistic(2z) −1$$

还有其他各种备选:

hankcs.com 2017-06-16 下午9.43.32.png

其中ReLU成为新贵,Manning说他简直不敢相信这种疯狂的函数竟然效果最好(也许神经网络本来就是疯狂的)。ReLU在反向传播时要么不反馈残差,要么原样反馈残差。

未来工作

Chen&Manning的工作被许多人继续往前推进,走在最前沿的是Google。趋势是:

  • 更大更深调参调得更好(更昂贵)的神经网络

  • Beam Search

  • 在决策序列全局进行类似CRF推断的方法(CRF宝刀未老,老当益壮啊)

Google的SyntaxNet 中的 Parsey McParseFace的效果:

hankcs.com 2017-06-16 下午9.49.18.png

 财大气粗就是好。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » CS224n笔记6 句法分析

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    完全看不懂这节课了….

    FatherSucker2天前回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机