月度归档:2020年01月

linear chain crf 数学推导

问题定义

在序列标注任务中,我们有

  • X= (x1,x2...x_k) 观测值,或者是观测序列对应的激活值序列;
  • y= (y1,y2...y_k) 要预测的标签或者说是隐状态序列;
  • K 是序列长度;
  • n 标签类别数;
    我们要从 n^{K} 条路径中选择概率最大的一条
p(\mathbf{y} | \mathbf{X})=p\left(y_{1}, \dots, y_{K} | \mathbf{x}_{1}, \dots, \mathbf{x}_{K}\right)

问题建模

naive 做法是对每个 time_step 的激活值做 n 分类,然后求累乘的最大概率。
建模公式如下

\begin{aligned} p(\mathbf{y} | \mathbf{X}) &=\prod_{k} p\left(y_{k} | \mathbf{x}_{k}\right)=\prod_{k} \exp \left(a^{(L+1)}\left(\mathbf{x}_{k}\right)_{y_{k}}\right) / Z\left(\mathbf{x}_{k}\right) \\ &=\exp \left(\sum_{k} a^{(L+1)}\left(\mathbf{x}_{k}\right)_{y_{k}}\right) /\left(\prod_{k} Z\left(\mathbf{x}_{k}\right)\right) \end{aligned}

naive 做法没有利用标签之间的约束信息和统计规律,比如 bmes 标注的分词序列标注问题,s 后面不能接 m 或者 e,其它 bigram 的统计规律也无法被利用,做出来还不如纯统计的 hmm。
线性链crf考虑到了这些问题,但为了计算方便计算假设 y_{k} 仅在相邻标签之间有关联(马尔可夫假设)。V 是一个二维矩阵,建模公式如下

p(\mathbf{y} | \mathbf{X})=\exp \left(\sum_{k=1}^{K} a^{(L+1)}\left(\mathbf{x}_{k}\right)_{y_{k}}+\sum_{k=1}^{K-1} V_{y_{k}, y_{k+1}}\right) {/ Z(\mathbf{X})}

=\exp \left(\sum_{k=1}^{K} a_{u}\left(y_{k}\right)+\sum_{k=1}^{K-1} a_{p}\left(y_{k}, y_{k+1}\right)\right) / Z(\mathbf{X})

计算配分函数

Z(\mathbf{X})=\sum_{y_{1}^{\prime}} \sum_{y_{2}^{\prime}} \cdots \sum_{y_{K}^{\prime}} \exp \left(\sum_{k=1}^{K} a_{u}\left(y_{k}^{\prime}\right)+\sum_{k=1}^{K-1} a_{p}\left(y_{k}^{\prime}, y_{k+1}^{\prime}\right)\right)

前向算法

思路
算法流程
为了进一步熟悉上面的迭代计算,
写一下 1,2,3 三个 tag ,当 k+1 time_step 的 tag 是 2 的情况;
同时说明如何从上面的公式转化成向量化计算
手写推导

后向算法

[TODO]

计算 loss function

要最大化

p(\mathbf{y} | \mathbf{X})

等价于最小化 negative log-likehood 即可完成优化

l(\mathbf{f}(\mathbf{X}), \mathbf{y})=-\log p(\mathbf{y} | \mathbf{X})

继续阅读linear chain crf 数学推导