Michael Collins NLP Lecture 15

课程主页:http://www.cs.columbia.edu/~cs4705/

课程网盘地址:

链接:https://pan.baidu.com/s/1r0f7I2j6rtlK31VplwHa1Q
提取码:pw02

这一讲介绍了用感知机算法解决依存句法分析(Dependency Parsing)。

依存句法分析

(备注,这部分介绍的为没有标签的依存句法分析)

首先介绍依存句法分析,每个依存句由如下两个元素构成:

  • $\text{root}$是特殊的根符号。
  • 每个依存句是一对$(h,m)$,其中$h$是首单词的索引,$m$是修饰词的索引。 在图中,我们通过从$h$到$m$的有向边表示依存关系$(h,m)​$。

来看个例子:

上图中的依存关系为$(0, 2),(2,1),(2,4),(4,3)$,其中$0$表示根。句子$\text{John saw Mary}$的全部可能的依存关系如下:

我们讨论的依存结构有如下两个条件:

  • 依赖关系弧形成有向树,$\text{root}$符号位于树的根部。(定义:以$\text{root}$为根的有向树是树,如果对于除根之外的每个单词$w$,都有从$\text{root}$到$w$的有向路径。)
  • 没有“交叉依赖关系”。没有交叉依赖关系的依赖关系结构有时被称为投射结构。

这里解释下第二点,首先看一个例子:

如果两个依赖关系弧相交,那么称为有“交叉依赖关系”,例如上图中如果存在$\text{today}$到$\text{he}​$的关系弧,那么有“交叉依赖关系”。

那么我们该如何获得依存关系的数据呢?一种方法是直接从依存关系库中获取,另一种是从解析树中获取,例如:

假设句子长度为$n$,没有标签的依存句法分析的时间复杂度为$O(n^3)​$,这比之前介绍的PCFG以及词汇化PCFG都要快很多。

用于依存句法分析的全局线性模型(GLM)

这部分将介绍如何用全局线性模型处理依存句法分析,首先回顾GLM的三个元素:

  • $x$为一个句子。
  • $\text{GEN}(x)$为$x$的所有依存句法结构的集合。
  • $f(x,y)$是$x$和依存句法分析$y$对应的特征向量。

利用局部特征向量定义全局特征向量$f$:

其中$ g(x, h,m)$将句子$x$和依存关系$(h,m)$映射到局部特征向量。

我们的目标是计算

老师说可以用动态规划算法计算上述结果,但是没有具体给出。

最后给出一些常用的局部特征:

本文标题:Michael Collins NLP Lecture 15

文章作者:Doraemonzzz

发布时间:2019年03月10日 - 22:02:00

最后更新:2019年05月06日 - 20:21:21

原始链接:http://doraemonzzz.com/2019/03/10/Michael Collins NLP Lecture 15/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。