CS224N-2017-笔记:06 句法分析

CS224N-2017-笔记:06 句法分析

课程官网:http://web.stanford.edu/class...

CS224N:深度自然语言处理课程(Natural Language Processing with Deep Learning)

个人学习的视频来自B站上雷锋字幕组的翻译,在此感谢课程的分享、翻译人员。

I think that it's extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. -- Alan J. Perlis, SICP序言
  • Lecture 6 介绍了句法分析和依存句法解析器。

1. 句法结构

一致与依赖

  • 描述语法结构(Phrase Structure)有两种观点,一致(constituency)和依存(dependency)。
  • 一致

    • 术语:一致 Constituency = 短语结构文法 phrase structure grammar = 上下文无关文法 context-free grammars (CFGs)
    • 短语结构使用规则把单词组成为嵌套成分(nested constituents)
    • 一个短语结构树示例如下,

      06-01.png

  • 依存

    • 依存结构展示一个词和其他词的依赖关系,即一个词如何修饰另一个词,而非嵌套关系。
    • 示意图如下,

      06-02.png

歧义(Ambiguity)

  • 示例:介词短语依附(PP attachments)

    06-03.png

  • 依附歧义(Attachment Ambiguities)

    • 语法解析的一个关键点是:如何将不同的成分加上(attach),如介词短语、状语/分词短语、不定式、连词等。
    • 示例

      06-04.png

    • 依附可能性为卡兰特数(Catalan number):$C_n=(2n)!/[(n+1)!n!]$

标注数据集:Universal Dependencies treebanks

  • [Universal Dependencies: http://universaldependencies.... ; cf. Marcus et al. 1993, The Penn Treebank, Computational Linguistics]
  • 建立这样的树库比建立一个文法看似慢得多,也没有很大用处;
  • 但这样的树库具有以下优点:

    • 可重用性
    • 更广的覆盖率,而不只是一种直觉认知
    • 更频繁、更广泛的信息
    • 提供一种评估系统的方式

2. 依存语法(Dependency Grammar)

依存语法和依存结构

  • 依存语法(dependency syntax)假设语法结构由词汇项(lexical items)之间的关系构成,通常这种二元非对称(binary asymmetric)的关系被称为依存关系(dependencies),箭头表示。

    06-05.png

    • 箭头上表示的是语法关系(grammatical relations)。
    • 箭头包含head(被修饰的对象)和dependent(修饰词)。
    • 绘制方法可能不同,一半会增加一个fake ROOT。

依存语法/解析的历史

  • 依存结构思想的起源可以追溯到:

    • Pāṇini’s grammar (c. 5th century BCE)
    • 公元1000年左右的阿拉伯文法学家
  • 而上下文无关语法是20世纪的发明(R. S. Wells, 1947)
  • 现代依存文法工作的建立人是 L. Tesnière (1959),是东方语言(俄语、汉语等)的主要方法,对更自由的语言效果更好。
  • 自然语言处理早期的解析器,也是依存解析器(David Hays, 1962)

依存解析的信息来源

  • 双词汇亲和(Bilexical affinities):两个词之间的关系,如discussion与issues;
  • 词语间距(Dependency distance):一般依存关系位于相邻词之间;
  • 中间物质(Intervening material):以来很少跨越位于中间的动词或标点;
  • 箭头的价(? Valency of heads):一个head的依赖个数一般是有限的。

依存解析(Dependency Parsing)

  • 一句话的解析通过逐一选择每个词,然后分析其它词和它的依存关系(包括ROOT)。
  • 一般分析的约束:

    • 只有一个词依赖ROOT;
    • 不出现环,无环 (即依赖结构是一棵树)。
  • 若箭头可以交叉则为non-projective,反之为non-projectice。

依存解析的方法

  • 动态规划 (Dynamic Programming):Eisner于1996年提出的一种复杂度为$O(n^3)$的方法,通过在末尾产生head而不是在中间产生;
  • 图算法 (Graph algorithms):McDonald等人在2005年提出的MSTParser使用ML分类器对依赖项单独评分(他使用了MIRA来在线学习,但也可以使用其他的方法);
  • 约束适应 (Constraint Satisfaction):Karlsson于1990年提出,去除不满足硬约束的边;
  • Transition-based parsing 或 "deterministic dependency parsing":Nivre等人在2008年提出的MaltParser,指导贪婪算法,被证明很有效。

3. 基于转移的依存解析

Greedy transition-based parsing [Nivre 2003]

  • 是贪婪判别依存解析器(greedy discriminative dependency parser)的一种简单形式。
  • 执行一系列的bottom-up操作:大致类似于移入-规约解析器(shift-reduce parser)中的移入、规约操作,但规约操作专门用于创建head左或右的依存项。
  • 解析器含有:

    • 栈$\sigma$,以ROOT符号开始,右边为栈顶;
    • 缓存$\beta$,以输入序列开始,左边为顶部;
    • 依存弧集合(dependency arcs)$A$,一开始为空;
    • 一组操作(actions)
  • 基本基于转移的依存解析器

    开始:$\sigma=[ROOT]$, $\beta=w_1,w_2, ..., w_n$, $A=\emptyset$

    1. 移入 shift: $\sigma,w_i|\beta,A\rightarrow\sigma|w_i,\beta,A$

      ​ 将缓存中第一个词移入到栈上

    2. Left-Arc$_r$: $\sigma|w_i|w_j,\beta,A\rightarrow\sigma|w_j,\beta,A\cup\{r\{w_j,w_i\}\}$
    3. Right-Arc$_r$: $\sigma|w_i|w_j,\beta,A\rightarrow\sigma|w_i,\beta,A\cup\{r\{w_i,w_j\}\}$

    终止:$\sigma=[w]$, $\beta=\emptyset$

  • 弧标准的基于转移的解析器(Arc-standard transition-based parser)示例

    06-06.png

    • 也可以用其他方法

MaltParser [Nivre and Hall 2005]

  • 对下一个动作的选择进行预测
  • 每个动作都由独立的分类器(一般是SVM,也可以是感知机perceptron、最大熵分类器MaxEnt Classifier等)对每个合法移动进行预测

    • 最多三种无类型的选择,有类型时最多$|R|\times2+1$种;
    • 特征:栈顶单词,POS;缓存中第一个单词,POS;等。
  • 在最简单的形式中没有搜索,但也可以用beam search(速度慢但效果更好)
  • 很快的线性解析时间
  • 模型的精度略低于最好的依存解析,但速度快,接近于最好的解析表现

特征表示

06-07.png

依存解析的评价:带标记的依存精度

  • 原句和结果示例

    06-08.png

  • 评价

    • 精度:$Acc=\frac{\#\ correct\ deps}{\#\ of\ deps}$
    • 无标记依存正确率(unlabeled attachment score):$UAS=4/5=80\%$
    • 有标记依存正确率(labeled attchment score):$LAS=2/5=20\%$

投射(projectivity)和非投射(non-projectivity)

  • 依存弧识别语义关系的例子--判断蛋白质的相互作用[Erkan et al. EMBLP 07, Fundel et al. 2007, etc.]
  • 投射性(projectivity)

    • 与CFG相近的依存树一定是投射性的(在单词线性顺序排布时,没有交叉的弧);
    • 但依存理论也允许非投射的结构
  • 非投射性(non-projectivity)的处理

    • 弧标准(arc-standard)算法只能构建投射性的依存树。
    • head可能的方向(emmm,这里就不记了)

4. 神经网络依存解析器

使用神经网络依存句法解析器的原因

  • 传统指标特性稀疏;
  • 指标不完全;
  • 计算复杂(超过95%的解析时间花在了特征计算)
  • 解决方法:学习一种稠密(dense)、复杂(compact)的特征表示。

神经网络依存句法解析器

  • A neural dependency parser [Chen and Manning 2014]
  • 优势:以更快的速度极为接近最好的结果。
  • 分布式表示(Distributed Representations)

    • 用一个$d$维的稠密向量表示每个词(如词嵌入),相近的词被表示为相近的向量;
    • 词性标签(part-of-speech tags, POS)和依存标签(dependency labels)也表示为$d$维向量,较小的离散集也表现出许多语义上的相似性。
    • NNS(复数名词)和NN(单数名词)相近;num(数值修饰符)和amod(形容词修饰符)相近。
  • 向量表示

    • 基于栈/缓存位置提取一系列令牌(tokens)

      06-09.png

    • 拼接单词、词性、依存标签的向量表示(传统方法拼接原内容)

      $$ \begin{aligned} &\quad\ word\quad\quad\quad\ \ POS\quad\quad\quad\ dep. \\ \begin{bmatrix}s_1\\s_2\\b_1\\l_c(s_1)\\r_c(s_1)\\l_c(s_2)\\r_c(s_2)\end{bmatrix} \rightarrow &\begin{bmatrix}good\\has\\control\\\emptyset\\\emptyset\\He\\\emptyset\end{bmatrix}+ \begin{bmatrix}JJ\\VBZ\\NN\\\emptyset\\\emptyset\\PRP\\\emptyset\end{bmatrix}+ \begin{bmatrix}\emptyset\\\emptyset\\\emptyset\\\emptyset\\\emptyset\\nsubj\\\emptyset\end{bmatrix} \end{aligned} $$

  • 模型结构(Model Archicture)

    06-10.png

  • 各层间的非线性函数

    • 使用原因:

      • 如果不使用非线性函数,那么深度网络将等效于线性转换。
      • 使用非线性函数,是因为如果使用线性函数,那么所有层都等效为一层:$W_1W_2x=Wx$
      • 更多层,可以更好地拟合复杂的函数。
    • 非线性函数

      06-11.png

未来工作

  • 更大更深的网络与更好调参的超参数;
  • Beam Search;
  • 在决策序列全局进行CRF(conditional random field)。
​ 间隔了一段时间后的整理,在被CV烦恼一段时间后再回看NLP,舒服~一些解析器应该还要实际实现后才能更清楚。

参考资料:

  1. CS224n笔记6 句法分析
  2. 依存语法:从短语结构树转换为依存树
  3. [CS224n笔记] L5 Dependency Parsing

评论

暂无评论