NLP-CS224n学习讲义PART 4——Dependency Parsing

ゞ浴缸里的玫瑰 2023-02-17 03:49 6阅读 0赞

## 1 依存语法和依存结构 ##

NLP中的解析树与编译器中的解析树类似，用于**分析句子的句法结构**。主要有两个类型的结构——**成分结构和依存结构**。成分语法结构使用短语结构语法将单词组织成嵌套的成分。而我们主要关注的是**依存结构解析**。

句子的依存结构主要分析的是哪些词依赖于其他哪些词。这些单词之间的二元非对称关系称为依存关系，并被描述为从首领(或上级)到附属(或修饰词、下级)的指向关系。通常这些依存关系形成一个树结构。它们通常与语法关系的名称(主语、介词宾语、同位语等)一起输入。下图是一个依存树的例子。

> Bills on ports and immigration were submitted by Senator Brownback, Republican of Kansas
> 
> \[港口和移民法案是由堪萨斯州共和党参议员布朗巴克提交的\]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70_pic_center]

### 1.1 依存关系语法分析 ###

依存关系语法分析是分析给定输入句 S S S的语法依赖结构的任务。依存解析器的输出是一个依赖树 G G G其中输入句中的单词通过类型化的依存关系连接。形式上，依存分析问题要求创建一个如下的映射：

( S = W 0 W 1 . . . W n ) → G (S = W\_0W\_1...W\_n) \\rightarrow G (S=W0W1...Wn)→G

确切地说，依存解析中有两个子问题：

1.  Learning：给定一组用依赖关系图注释的句子训练集 D D D，归纳出一个解析模型 M M M，该模型可用于解析新句子。
2.  Parsing：给出一个解析模型 M M M和一个句子 S S S，根据 M M M推导出 S S S的最优依赖图 D D D。

### 1.2 基于跃迁的依存解析 ###

基于跃迁的依存解析依赖于一种状态机，其通过定义可能的转换来创建从输入语句到依赖项树的映射。

*  *Learning problem* 就是根据状态机的转移历史，归纳出一个可以预测状态机下一次转移的模型。
 *  *Parsing problem* 是给定前面归纳的模型，然后为输入语句构造最优的转换序列。

### 1.3 基于贪心确定性转换的解析 ###

这个转换系统是一个状态机，它由**状态**和这些**状态之间的转换**组成。该模型推导出从某一**初始状态**到几种**终态之一**的一系列跃迁，

#### **States:** ####

对于任意句子 S = w 0 w 1 . . . w n S = w\_0w\_1...w\_n S=w0w1...wn，一个状态可以描述为一个三元组 c = ( σ , β , A ) c = (\\sigma, \\beta, A) c=(σ,β,A)：

1.   σ \\sigma σ为单词 w i w\_i wi的一个堆栈，
2.   β \\beta β为单词 w i w\_i wi的一个缓冲区，
3.  一组形式为 ( w i , r , w j ) (w\_i, r,w\_j) (wi,r,wj)的依赖弧 A A A，其中 w i , w j w\_i,w\_j wi,wj来自 S S S，而  r r r描述了一种依赖关系。

对于任意句子 S = w 0 w 1 . . . w n S = w\_0w\_1...w\_n S=w0w1...wn，

1.  一个初始状态 c 0 c\_0 c0的形式 ( \[ w 0 \] σ , \[ w 1 , … , w n \] β , ∅ ) (\[w\_0\]\_\\sigma,\[w\_1,…, w\_n\]\_\\beta,\\emptyset) (\[w0\]σ,\[w1,…,wn\]β,∅)(只有root在堆栈 σ \\sigma σ，所有其他词都在缓冲区 β \\beta β中，并且没有任何依赖关系)
2.  一个终止的状态形式为 ( σ , \[ \] β , A ) (\\sigma, \[ \\ \]\_\\beta, A) (σ,\[\]β,A)（缓冲区为空）

#### **Transitions:** ####

状态之间有三种类型的转换：

1.   S h i f t Shift Shift：删除缓冲区中的第一个单词并将其插入到堆栈的顶部。（先决条件：缓冲区非空）
2.   L e f t − A r c r Left-Arc\_r Left−Arcr：向集合A中增加依赖弧 ( w j , r , w i ) (w\_j, r, w\_i) (wj,r,wi)， w i w\_i wi为在栈顶的第二位的单词， w j w\_j wj为栈顶的单词。将单词 w i w\_i wi从栈顶删除。（先决条件：堆栈需要包含至少两个单词， w i w\_i wi不能是根。）
3.   R i g h t − A r c r Right-Arc\_r Right−Arcr：向集合A中增加依赖弧 ( w i , r , w j ) (w\_i, r, w\_j) (wi,r,wj)， w i w\_i wi为在栈顶的第二位的单词， w j w\_j wj为栈顶的单词。将单词 w j w\_j wj从栈顶删除。（先决条件：堆栈需要包含至少两个单词）

### 1.4 基于神经网络依赖解析 ###

虽然有许多用于依存分析的深度模型，但本节特别关注贪心且基于转换的神经网络依存分析器。与传统的基于特征的依赖解析器相比，这类模型具有相当的性能和显著的效率。与以前的模型的主要区别是在于它依赖于密集而非稀疏的特征表示。

此节描述的模型也将使用第1.3节所示的arc-standard系统进行转换。最后，模型的目标是预测从某个初始配置 c c c到一个终止配置的转换序列，其中对依赖解析树进行了编码。由于模型是贪心的，它试图基于从当前配置中提取的特征 c = ( σ , β , A ) c = (\\sigma, \\beta, A) c=(σ,β,A)，来正确地一次预测一个转换 T ∈ \{ S h i f t , L e f t − A r c r , R i g h t − A r c r \} T \\in \\\{Shift, Left-Arc\_r, Right-Arc\_r\\\} T∈\{ Shift,Left−Arcr,Right−Arcr\}。

#### **Feature Selection:** ####

一个句子的特征一般包括:

1.   S w o r d S\_\{word\} Sword：在堆栈 σ \\sigma σ和缓冲区 β \\beta β顶部的句子 S S S中一些单词(及其依赖项)的向量表示。
2.   S t a g S\_\{tag\} Stag：在句子 S S S中一些单词的词性(POS)标签。词性标签包括一个小的，离散的集合： P = \{ N N , N N P , N N S , D T , J J ， . . . \} P = \\\{NN, NNP, NNS, DT, JJ，...\\\} P=\{ NN,NNP,NNS,DT,JJ，...\}。
3.   S l a b e l S\_\{label\} Slabel：在句子 S S S中一些单词的arc-labels由一个小的、离散的集合组成，其描述了依赖关系: L = \{ a m o d , t m o d , n s u b j , c s u b j d o b j , . . . \} L = \\\{amod, tmod, nsubj, csubj dobj,...\\\} L=\{ amod,tmod,nsubj,csubjdobj,...\}。

对于每个特征类型，我们将有一个相应的嵌入矩阵，从特征的一个热编码映射到d维稠密向量表示。 S w o r d S\_\{word\} Sword完整的嵌入矩阵为 E w ∈ R d × N w E^w \\in R^\{d\\times N\_w\} Ew∈Rd×Nw，其中 N w N\_w Nw为字典中词汇量大小。相应地，POS和label的嵌入矩阵为 E t ∈ R d × N t 和 E l ∈ R d × N l E^t \\in R^\{d \\times N\_t\} 和 E^l \\in R^\{d\\times N\_l\} Et∈Rd×Nt和El∈Rd×Nl，其中 N t N\_t Nt为POS tags的数量， N l N\_l Nl为arc labels的数量。

最后，让从每组特征中选择的元素个数分别记为 n w o r d 、 n t a g 和 n l a b e l n\_\{word\}、n\_\{tag\}和\\ n\_\{label\} nword、ntag和nlabel

#### 前向神经网络模型 ####

网络包含一个输入层 \[ x w , x t , x l \] \[x^w, x^t, x^l\] \[xw,xt,xl\]，一个隐藏层和一个最后带有cross-entropy的softmax层。模型如下图所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200612104604264.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200612104618706.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag==,size_16,color_FFFFFF,t_70#pic_center