序列标注

教师：邱锡鹏微博：@邱锡鹏

助教：施展、龚经经

复旦大学计算机学院大数据学院

$\hat y = \mathop{argmax}_yf(\phi(x,y),\theta) \hspace{8cm} (1)$

x为句子序列，y为标注序列

argmax 对应解码过程， $y$ 若是序列，需要使用动态规划算法， $y$ 若是分类，否则使用穷举法即可。

中文分词简介

1.1 BMES 编码

单个字作为词：S

双字作为词：B（起始），E（结束）

多字作为词：B（起始），M（中间字），E（结束）

例子：他（S）说（S）的（S）确（B）实（E）在（B）理（E）

1.2 特征抽取

$y$ 序列之间存在依赖关系（如 $y_{i-1}=B$ 和 $y_i=B$ 这种组合是不会出现的）

设计如下模板来抽取特征：

$[y_{-1},y_{0}]$ 抽取 $y$ 序列之间的特征
$[x_{-1},x_{0},y_{0}]$ 抽取(x,y)之间的特征

模板1抽出的特征例子如下：

$\phi_k(x,y_{i})=\left\{ \begin{array}{11} 1 & if\ y_{i-1}=B,\ y_{i}=E\\ 0 & \textrm{otherwise} \end{array} \right..$

模板2抽出的特征例子如下：

他

$\phi_n(x,y_i) =\left\{ \begin{array}{11} 1 & if\ x_{i}\ =\ 他\ and\ x_{i-1}\ =\ <s>\ and \ y_{i}=S\\ 0 & \textrm{otherwise} \end{array} \right.$

1.3 优化方法

若将 $y$ 序列代入式（1），则 $y$ 的解空间共有 $4^L$ 大小（L为序列长度），无法穷举获得最佳解

简化步骤：

$\theta^{T}\phi(x,y) \approx \sum_{i=1}^{L}\theta^{T}\phi(x,y_{i-1},y_{i})\approx\sum_{i=1}^{L}\theta_{1}^{T}\phi_{1}(x,y_i)+\theta_{2}^{T}\phi_{2}(y_{i-1},y_i)\hspace{3cm}(2)$

特征提取模板与 $\phi$ 空间维数的关系：

$[x_0,y_0]\to\phi_1\in R^{|V|*4}$

$[y_{-1},y_{0}]\to\phi_{2}\in R^{16}$

$[x_{-1},x_{0},y_{0}]\to\phi_{1}\in R^{|V|*4*4}$

问题转化为：

$\hat{y_{1}}...\hat {y_L} = \mathop {argmax}_{y_1...y_L} \sum_{i=1}^{L}\theta_{1}^{T}\phi_{1}(x,y_i)+\theta_{2}^{T}\phi_{2}(y_{i-1},y_i)$

1.4 预测y序列

$max(a+b,a+c) = a + max(b+c)$

抽取只和 $y_1$ 相关的特征，（2）式又可写成

$\mathop {argmax}_{y_1}(\theta_{1}^{T}\phi_{1}(x,y_1)+\theta_{2}^{T}\phi_{2}(y_0,y_1)+\theta_{2}^{T}\phi_{2}(y_1,y_2))+\mathop {argmax}_{y_2}(\cdots)+\cdots$

运算次数由 $4^L$ 降低为 $4L$

viterbi算法：

定义 $\alpha_{t,i}:t\in{B,M,E,S}$

$\left( \begin{array} {ccc} \alpha_{t,0}=0\\ \alpha_{t,i} = \mathop {max}_{t^{'}}(\alpha_{t,i-1}+\theta_1^{T}\phi_{1}(x,t^{'})+\theta_2^{T}\phi_2(t^{'},t)) \end{array} \right.$

记录路径，得到最佳序列。