课程主页：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$，所以结果为