第五讲-句法分析与依存解析

1.句法结构：成分与依赖

1.1 语言结构的两种观点：无上下文语法

句子是使用逐步嵌套的单元构建的

  • 可以通过CFG（context-free grammars 无上下文语法）规则表示语法

起步单元：单词被赋予一个类别（part of speech = pos 词性）

  • the, cat, cuddly, by, door
  • Det, N, Adj, P, N

单词按类别组合成短语

  • the cuddly cat ：NP => Det Adj N
  • by the door ：PP =>P N P

短语可以递归地组合成更大的短语

  • the cuddly cat by the door：=> NP → NP PP

补充：

  • Det 指的是 Determiner，在语言学中的含义为 限定词
  • NP 指的是 Noun Phrase，在语言学中的含义为 名词短语
  • VP 指的是 Verb Phrase，在语言学中的含义为 动词短语
  • P 指的是 Preposition，在语言学中的含义为 介词
  • PP 指的是 Prepositional Phrase，在语言学中的含义为 介词短语

1.2 语言结构的两种观点：依赖结构

不是使用各种类型的短语，而是直接通过单词与其他的单词关系表示句子的结构，显示哪些单词依赖于(修饰或是其参数)哪些其他单词

  • look是整个句子的根源，look依赖于crate(或者说crate是look的依赖

    • in，the，large 都是 crate 的依赖

    • in the kitchen 是 crate 的修饰

    • in，the 都是 kitchen 的依赖

    • by the door 是 crate 的依赖

1.3 为什么我们需要句子结构？

为了能够正确地解释语言，我们需要理解句子结构

人类通过将单词组合成更大的单元来传达复杂的意思，从而交流复杂的思想

我们需要知道什么与什么相关联

1.4 介词短语依附歧义

1、San Jose cops kill man with knife

  • 警察用刀杀了那个男子
    • cops 是 kill 的 subject (subject 指 主语)
    • man 是 kill 的 object (object 指 宾语)
    • knife 是 kill 的 modifier (modifier 指 修饰符)
  • 警察杀了那个有刀的男子
    • knife 是 man 的 modifier (名词修饰符，简称为 nmod)

2、Scientists count whales from space

  • from space这一介词短语修饰的是前面的动词count还是名词whales?
    • 这就是人类语言和编程语言中不同的地方

1.5 介词短语附加歧义成倍增加

关键的解析决策是我们如何“依存”各种成分

  • 介词短语、状语或分词短语、不定式、协调等。

The board approved [ its acquisition ] [ by Royal Trustco Ltd. ] [ of Toronto ] [ for $27 a share ] [ at its monthly meeting ].

  • board 是 approved 的主语，acquisition 是 approved 的谓语
  • by Royal Trustco Ltd. 是修饰 acquisition 的，即董事会批准了这家公司的收购
  • of Toronto 可以修饰 approved，acquisition，Royal Trustco Ltd. 之一，经过分析可以得知是修饰 Royal Trustco Ltd.，即表示这家公司的位置
  • for $27 a share 修饰 acquisition
  • at its monthly meeting 修饰 approved，即表示批准的时间地点

面对这样复杂的句子结构，我们需要考虑 指数级 的可能结构，这个序列被称为 卡特兰数/Catalan numbers \[ C_{n}=(2 n) ! /[(n+1) ! n !] \]

1.6 协调范围模糊

1、Shuttle veteran and longtime NASA executive Fred Gregory appointed to board

  • 一个人：[[Shuttle veteran and longtime NASA executive] Fred Gregory] appointed to board
  • 两个人：[Shuttle veteran] and [longtime NASA executive Fred Gregory] appointed to board

2、Students get first hand job experience

  • first hand表示第一手的，直接的，即学生获得了直接的工作经验
    • first 是 hand 的形容词修饰语(amod)
  • first 修饰 experience，hand 修饰 job

1.7 动词短语(VP)依存歧义

Mutilated body washes up on Rio beach to be used for Olympic beach volleyball

  • to be used for Olympic beach volleyball 是 动词短语 (VP)
  • 修饰的是 body 还是 beach

2.依赖语法与树库

2.1 #论文解读# 依赖路径识别语义关系

2.2 依存文法和依存结构

关联语法假设句法结构包括词汇项之间的关系，通常是二元不对称关系(“箭头”)，称为依赖关系

Dependency Structure有两种表现形式

  1. 一种是直接在句子上标出依存关系箭头及语法关系

  2. 另一种是将其做成树状机构(Dependency Tree Graph)

  • 箭头通常标记(type)为语法关系的名称(主题、介词对象、apposition等)
  • 箭头连接头部(head)(调速器，上级，regent)和一个依赖(修饰词，下级，下属)
  • 通常，依赖关系形成一棵树(单头，无环，连接图)

2.3 依存语法/解析历史

  • 依赖结构的概念可以追溯到很久以前
    • Paṇini的语法(公元前5世纪)
    • 一千年，阿拉伯语的语法的基本方法
  • 选区/上下文无关文法是一个新奇的发明
    • 20世纪发明(R.S.Wells,1947; then Chomsky)
  • 现代依赖工作经常源于 L. Tesnière(1959)
    • 是20世纪“东方”的主导方法(俄罗斯，中国，…)
      • 有利于更自由的语序语言
  • NLP中最早类型的解析器在美国
    • David Hays 是美国计算语言学的创始人之一，他很早就(第一个?)构建了依赖解析器(Hays 1962)

2.4 依存语法和依赖结构

  • 人们对箭头指向的方式不一致：有些人把箭头朝一个方向画；有人是反过来的
    • Tesnière 从头开始指向依赖，本课使用此种方式
  • 通常添加一个伪根指向整个句子的头部，这样每个单词都精确地依赖于另一个节点

2.5 带注释数据的兴起：通用依存句法树库

2.6 带注释数据的兴起

  • 从一开始，构建 treebank 似乎比构建语法慢得多，也没有那么有用

  • 但是 treebank 给我们提供了许多东西

    • 可重用性
      • 许多解析器、词性标记器等可以构建在它之上
      • 语言学的宝贵资源
    • 广泛的覆盖面，而不仅仅是一些直觉
    • 频率和分布信息
    • 一种评估系统的方法

2.7 依赖条件首选项

依赖项解析的信息来源是什么？

1.Bilexical affinities (两个单词间的密切关系) - [discussion → issues] 是看上去有道理的

2.Dependency distance 依赖距离 - 主要是与相邻词

3.Intervening material 介于中间的物质 - 依赖很少跨越介于中间的动词或标点符号

4.Valency of heads - How many dependents on which side are usual for a head?

2.8 依赖关系分析

  • 通过为每个单词选择它所依赖的其他单词(包括根)来解析一个句子

  • 通常有一些限制

    • 只有一个单词是依赖于根的
    • 不存在循环 A→B，B→A

  • 这使得依赖项成为树

  • 最后一个问题是箭头是否可以交叉(非投影的 non-projective)

    • 没有交叉的就是non-projectice

2.9 射影性

  • 定义：当单词按线性顺序排列时，没有交叉的依赖弧，所有的弧都在单词的上方

  • 与CFG树并行的依赖关系必须是投影的

    • 通过将每个类别的一个子类别作为头来形成依赖关系

  • 但是依赖理论通常允许非投射结构来解释移位的成分

    • 如果没有这些非投射依赖关系，就不可能很容易获得某些结构的语义

2.10 依存分析方法

1.Dynamic programming

  • Eisner(1996)提出了一种复杂度为 O(n3) 的聪明算法，它生成头部位于末尾而不是中间的解析项

2.Graph algorithms

  • 为一个句子创建一个最小生成树
  • McDonald et al.’s (2005) MSTParser 使用ML分类器独立地对依赖项进行评分(他使用MIRA进行在线学习，但它也可以是其他东西)

3.Constraint Satisfaction

  • 去掉不满足硬约束的边 Karlsson(1990), etc.

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

  • 良好的机器学习分类器 MaltParser(Nivreet al. 2008) 指导下的依存贪婪选择。已证明非常有效。

3.基于转换的依存分析模型

3.1 #论文解读# Greedy transition-based parsing [Nivre 2003]

  • 贪婪判别依赖解析器一种简单形式
  • 解析器执行一系列自底向上的操作
    • 大致类似于shift-reduce解析器中的“shift”或“reduce”，但“reduce”操作专门用于创建头在左或右的依赖项
  • 解析器如下：
    • 栈\(\sigma\)以 ROOT 符号开始，由若干组\(w_i\)成
    • 缓存\(\beta\)以输入序列开始，由若干\(w_i\)组成
    • 一个依存弧的集合\(A\)，一开始为空。每条边的形式是\((w_i,r,w_j)\)，其中\(r\)描述了节点的依存关系
    • 一组操作

3.2 基本的基于转换的依存关系解析器