条件随机场的预测算法

条件随机场的预测问题是给定条件随机场$P(Y|X)$和输入序列(观测序列)$x$, 求条件概率最大的输出序列(标记序列)$y^*$(例如应用在对观测序列进行标注的问题上).

条件随机场的预测算法与HMM一样, 都是采用维特比算法.

维特比算法

由条件随机场的简化(向量)表示形式得:

$\begin{aligned} y^* &= \arg\max\limits_{y}P_w(y|x) \\ &= \arg\max\limits_{y}\frac{\exp\left(\textbf{w}\cdot{F(y,x)}\right)}{Z_w(x)} \\ &= \arg\max\limits_{y}\exp\left(\textbf{w}\cdot{F(y,x)}\right) \\ &= \arg\max\limits_{y}\left(\textbf{w}\cdot{F(y,x)}\right) \end{aligned}$

其中:

$\textbf{w}=(w_1,w_2,\cdots,w_K)^T$

$\textbf{F}(y,x)=(f_1(y,x),f_2(y,x),\cdots,f_K(y,x))^T$

$f_k(y,x)=\sum\limits_{i=1}^{n}f_k(y_{i-1},y_{i},x,i),\ k=1,2,\cdots,K$

于是, 条件随机场的预测问题就称为求非规范化概率最大的最优路径问题.

$\max\limits_{y}\left(\textbf{w}\cdot{F(y,x)}\right)$

这时, 就只需要计算非规范化概率, 不必计算概率, 可以大大提高效率, 将上式写成如下形式:

$\max\limits_{y}\sum\limits_{i=1}^{n}\textbf{w}\cdot{F_i(y_{i-1},y_i,x)}$

其中$F_i$是一个长度为$K$的局部特征向量:

$F_i(y_{i-1},y_i,x)=(f_1(y_{i-1},y_{i},x,i),f_2(y_{i-1},y_{i},x,i),\cdots,f_K(y_{i-1},y_{i},x,i))^T$

维特比算法如下进行:

对于位置1的各个标记($y_1$取值的所有可能)$j=1,2,\cdots,m$的非规范化概率为:

$\delta_1(j)=\textbf{w}F_1(y_0=\text{start},y_1=j,x),\ j=1,2,\cdots,m$

由地推公式, 求出各个位置$i$的各个标记$j=1,2,\cdots,m$的非规范化概率的最大值, 同时记录非规范化概率最大值的路径:

$\delta_i(l)=\max\limits_{1\le{j}\le{m}}\left\{\delta_{i-1}(j)+\textbf{w}F_i(y_{i-1}=j,y_i=l,x)\right\}$

对应的路径为:

$\Phi_i(l)=\arg\max\limits_{1\le{j}\le{m}}\left\{\delta_{i-1}(j)+\textbf{w}F_i(y_{i-1}=j,y_i=l,x)\right\}$

迭代直到$i=n$时终止. 此时求得的非规范化概率的最大值为:

$\max\limits_{y}\left(\textbf{w}\cdot{F(y,x)}\right)=\max\limits_{1\le{j}\le{m}}\delta_n(j)$

及最优路径的终点:

$y_n^*=\arg\max\limits_{1\le{j}\le{m}}\delta_n(j)$

由最优路径的终点返回:

$y_i^*=\Phi_{i+1}(y_{i+1}^*),\ i=n-1,n-2,\cdots,1$

得到最优路径$y^*=(y^*_1,y^*_2,\cdots,y^*_n)$

条件随机场预测的维特比算法

• 输入:

  • 特征向量$F(x,y)$
  • 条件随机场权值向量$w$
  • 观测序列$x=(x_1,x_2,\cdots,x_n)$
• 输出:

  • 最优路径$y^*=(y^*_1,y^*_2,\cdots,y^*_n)$
• 过程

  • 初始化

    $\delta_1(j)=\textbf{w}F_1(y_0=\text{start},y_1=j,x),\ j=1,2,\cdots,m$
  • 递推, 对$i=1,2,\cdots,n$

    $\delta_i(l)=\max\limits_{1\le{j}\le{m}}\left\{\delta_{i-1}(j)+\textbf{w}F_i(y_{i-1}=j,y_i=l,x)\right\},\ l=1,2,\cdots,m$

    $\Phi_i(l)=\arg\max\limits_{1\le{j}\le{m}}\left\{\delta_{i-1}(j)+\textbf{w}F_i(y_{i-1}=j,y_i=l,x)\right\},\ l=1,2,\cdots,m$
  • 终止

    $\max\limits_{y}\left(\textbf{w}\cdot{F(y,x)}\right)=\max\limits_{1\le{j}\le{m}}\delta_n(j)$

    $y_n^*=\arg\max\limits_{1\le{j}\le{m}}\delta_n(j)$
  • 返回路径

    $y_i^*=\Phi_{i+1}(y_{i+1}^*),\ i=n-1,n-2,\cdots,1$

    求得最优路径: $y^*=(y^*_1,y^*_2,\cdots,y^*_n)$