条件随机场的预测算法

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

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

维特比算法

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

y∗=arg⁡max⁡yPw(y∣x)=arg⁡max⁡yexp⁡(w⋅F(y,x))Zw(x)=arg⁡max⁡yexp⁡(w⋅F(y,x))=arg⁡max⁡y(w⋅F(y,x))\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}

其中:

w=(w1,w2,⋯ ,wK)T\textbf{w}=(w_1,w_2,\cdots,w_K)^T

F(y,x)=(f1(y,x),f2(y,x),⋯ ,fK(y,x))T\textbf{F}(y,x)=(f_1(y,x),f_2(y,x),\cdots,f_K(y,x))^T

fk(y,x)=∑i=1nfk(yi−1,yi,x,i), k=1,2,⋯ ,Kf_k(y,x)=\sum\limits_{i=1}^{n}f_k(y_{i-1},y_{i},x,i),\ k=1,2,\cdots,K

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

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

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

max⁡y∑i=1nw⋅Fi(yi−1,yi,x)\max\limits_{y}\sum\limits_{i=1}^{n}\textbf{w}\cdot{F_i(y_{i-1},y_i,x)}

其中FiF_i是一个长度为KK的局部特征向量:

Fi(yi−1,yi,x)=(f1(yi−1,yi,x,i),f2(yi−1,yi,x,i),⋯ ,fK(yi−1,yi,x,i))TF_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的各个标记(y1y_1取值的所有可能)j=1,2,⋯ ,mj=1,2,\cdots,m的非规范化概率为:

δ1(j)=wF1(y0=start,y1=j,x), j=1,2,⋯ ,m\delta_1(j)=\textbf{w}F_1(y_0=\text{start},y_1=j,x),\ j=1,2,\cdots,m

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

δi(l)=max⁡1≤j≤m{δi−1(j)+wFi(yi−1=j,yi=l,x)}\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\}

对应的路径为:

Φi(l)=arg⁡max⁡1≤j≤m{δi−1(j)+wFi(yi−1=j,yi=l,x)}\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=ni=n时终止. 此时求得的非规范化概率的最大值为:

max⁡y(w⋅F(y,x))=max⁡1≤j≤mδn(j)\max\limits_{y}\left(\textbf{w}\cdot{F(y,x)}\right)=\max\limits_{1\le{j}\le{m}}\delta_n(j)

及最优路径的终点:

yn∗=arg⁡max⁡1≤j≤mδn(j)y_n^*=\arg\max\limits_{1\le{j}\le{m}}\delta_n(j)

由最优路径的终点返回:

yi∗=Φi+1(yi+1∗), i=n−1,n−2,⋯ ,1y_i^*=\Phi_{i+1}(y_{i+1}^*),\ i=n-1,n-2,\cdots,1

得到最优路径y∗=(y1∗,y2∗,⋯ ,yn∗)y^*=(y^*_1,y^*_2,\cdots,y^*_n)

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

  • 输入:

    • 特征向量F(x,y)F(x,y)

    • 条件随机场权值向量ww

    • 观测序列x=(x1,x2,⋯ ,xn)x=(x_1,x_2,\cdots,x_n)

  • 输出:

    • 最优路径y∗=(y1∗,y2∗,⋯ ,yn∗)y^*=(y^*_1,y^*_2,\cdots,y^*_n)

  • 过程

    • 初始化

      δ1(j)=wF1(y0=start,y1=j,x), j=1,2,⋯ ,m\delta_1(j)=\textbf{w}F_1(y_0=\text{start},y_1=j,x),\ j=1,2,\cdots,m

    • 递推, 对i=1,2,⋯ ,ni=1,2,\cdots,n

      δi(l)=max⁡1≤j≤m{δi−1(j)+wFi(yi−1=j,yi=l,x)}, l=1,2,⋯ ,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\},\ l=1,2,\cdots,m

      Φi(l)=arg⁡max⁡1≤j≤m{δi−1(j)+wFi(yi−1=j,yi=l,x)}, l=1,2,⋯ ,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⁡y(w⋅F(y,x))=max⁡1≤j≤mδn(j)\max\limits_{y}\left(\textbf{w}\cdot{F(y,x)}\right)=\max\limits_{1\le{j}\le{m}}\delta_n(j)

      yn∗=arg⁡max⁡1≤j≤mδn(j)y_n^*=\arg\max\limits_{1\le{j}\le{m}}\delta_n(j)

    • 返回路径

      yi∗=Φi+1(yi+1∗), i=n−1,n−2,⋯ ,1y_i^*=\Phi_{i+1}(y_{i+1}^*),\ i=n-1,n-2,\cdots,1

      求得最优路径: y∗=(y1∗,y2∗,⋯ ,yn∗)y^*=(y^*_1,y^*_2,\cdots,y^*_n)

上一页条件随机场的学习算法下一页聚类算法

最后更新于