Michael Collins NLP Lecture 14

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

课程网盘地址：

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

这一讲介绍了用全局线性模型解决标注问题。

回顾标注问题：

在全局线性模型下，标注模型的元素如下：

输入$x$是句子$w_{[1:n]}= \{w_1…w_n\}$
定义$\mathcal T$为标注的集合
$\text{GEN}(w_{[1:n]}) =\mathcal T^n$，即所有长度为$n$的标注序列。

注意此时$\text{GEN}$和句子长度呈指数关系。接下来的问题是如何定义$f$？

我们首先回顾历史的概念：

历史是$4$元组$\langle t_{-2}, t_{-1}, w_{[1:n]},i \rangle$
$t_{-2},t_{-1}$是之前两个标注
$ w_{[1:n]}$是输入句子的$n$个单词
$i$是正在被标注的单词的索引

来看个具体例子：

局部特征向量表示

给定历史/标注对$(h,t)$，$g_s(h,t), s=1,…,d$是上下文$h$中表示标记决策$t$的局部特征，例如：

现在假设我们有如下信息：

根据局部特征定义全局特征：

$f(t_{[1:n]},w_{[1:n]}) = \sum_{i=1}^n g(h_i, t_i)$

其中$t_i$是第$i$个标注，$h_i$是第$i$个历史。

将内容总结如下：

$\text{GEN}(w_{[1:n]}) $为所有长度为$n$的标注序列的集合。
$\text{ GEN},f,v$，定义
$\begin{aligned} F(w_{[1:n]}) &= \arg \max_{t_{[1:n]}\in \text{GEN}(w_{[1:n]}) } v.f(w_{[1:n]},t_{[1:n]}) \\ &= \arg \max_{t_{[1:n]}\in \text{GEN}(w_{[1:n]}) } v.\sum_{i=1}^n g(h_i,t_i)\\ &= \arg \max_{t_{[1:n]}\in \text{GEN}(w_{[1:n]}) } \sum_{i=1}^nv. g(h_i,t_i) \end{aligned}$

可以用动态规划算法求解$\arg \max$（因为历史只考虑前两个标注）。

（备注，这部分老师没有介绍具体的算法。）

用感知机算法训练标注器

输入：训练集$\left(w_{\left[1: n_{i}\right]}^{i}, t_{\left[1: n_{i}\right]}^{i}\right),i=1…n$
初始化：$\mathrm v=0$
算法：
- 对$t=1,….,T$
  - 对$i=1,…,n$
    - $z_{\left[1: n_{i}\right]}=\arg \max _{u_{\left[1: n_{i}\right]} \in \mathcal{T}^{n_{i}}} \mathbf{v} \cdot \mathbf{f}\left(w_{\left[1: n_{i}\right]}^{i}, u_{\left[1: n_{i}\right]}\right)$
    - 如果$z_{\left[1: n_{i}\right]} \neq t_{\left[1: n_{i}\right]}^{i}$，那么
      $\mathbf{v}=\mathbf{v}+\mathbf{f}\left(w_{\left[1: n_{i}\right]}^{i}, t_{\left[1: n_{i}\right]}^{i}\right)-\mathbf{f}\left(w_{\left[1: n_{i}\right]}^{i}, z_{\left[1: n_{i}\right]}\right)$
输出：参数$\mathrm v$

下面给出计算$z$的方法：

$\begin{aligned} z_{\left[1: n\right]} &=\arg \max _{u_{\left[1: n\right]} \in \mathcal{T}^{n}} \mathbf{v} \cdot \mathbf{f}\left(w_{\left[1: n\right]}, u_{\left[1: n\right]}\right)\\ &=\arg \max _{u_{\left[1: n\right]} \in \mathcal{T}^{n}}\sum_{i=1}^{n} \mathbf{v} \cdot g\left(h_{i}, t_{i}\right) \\ v_{\left[1: n\right]}&=\max _{u_{\left[1: n\right]} \in \mathcal{T}^{n}} \mathbf{v} \cdot \mathbf{f}\left(w_{\left[1: n\right]}, u_{\left[1: n\right]}\right)\\ &=\max _{u_{\left[1: n\right]} \in \mathcal{T}^{n}}\sum_{i=1}^{n} \mathbf{v} \cdot g\left(h_{i}, t_{i}\right) \end{aligned}$

定义

$\begin{aligned} \pi(k, p,q) &=\max_{t_1,\ldots, t_{k-2};t_{k-1}=p,t_{k-2}=q} \sum_{i=1}^{k} \mathbf{v} \cdot g\left(h_{i}, t_{i}\right) \\ bp(k, p,q) &=\underset{t_{k-2};t_{k-1}=p,t_{k-2}=q} {\arg\max} \sum_{i=1}^{k} \mathbf{v} \cdot g\left(h_{i}, t_{i}\right) \end{aligned}$

以及

$\begin{aligned} \pi(1, p, q ) &=\pi(1, \star, \star) \\ &= \mathbf{v} \cdot g\left(h_{1}, q\right) \end{aligned}$

递推：

$\begin{aligned} \pi(k, p,q) &= \max_r \pi(k-1,r, p) + g(h_k, q) \\ bp(k, p,q) &= \underset{r}{\arg\max}\ \pi(k-1,r, p) + g(h_k, q) \end{aligned}$

最后

$\left(z_{n-1}, z_{n}\right)={\arg \max}_{u,v}\pi(n, u, v)$

然后利用递推式

$z_{k} = bp(k+2, z_{k+1}, z_{k+2})$

计算其余部分。