课程主页: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)$映射到局部特征向量。

我们的目标是计算

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

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

本讲测验题

Coursera部分

1.

(b)(d)

2.

$m$的选择有$5$,$h$的选择有$4$,所以结果为