0 序：标注问题

image.png

图1
本篇部分文字和公式为阅读<统计学习方法>(李航)第11章，条件随机场所做笔记。图部分为结合个人理解所画，可能有误，欢迎指正~

1 定义

1.1 条件随机场

设X和Y是随机变量，P(Y|X)是在给定X的条件下Y的条件概率分布，若随机变量Y构成一个由无向图G=（V，E）表示的马尔可夫随机场，即
$P=(P_v|X,Y_w, 节点v以外的所有节点)=P(Y_v|X,Y_w,与节点v有边连接的所有结点)$
对任意节点v成立，则称条件概率分布P(Y|X)为条件随机场。

1.2 线性条件随机场

设
$X=(X_1,X_2,...,Y_{i-1},Y_{i+1},...,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})$
$i=1,2,...,n(在i=1和n时只考虑单边)$

则称P(Y|X)为线性条件随机场。

image.png

图2 条件随机场

线性条件随机场
X和Y具有相同的图结构为线性条件随机场

image.png

图 3 线性条件随机场

在标注问题中，

X表示输入的观测序列，Y表示对应的输出标记序列或状态序列。

1.3 参数化形式

设P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量y的条件概率具有如下形式：
$P(y|x)= \frac{1}{Z(x)}exp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i))$
其中
$Z(x)=\sum_yexp(\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i))$
$t_k和S_l是特征函数，\lambda_k,\mu_l是对应的权值，t_k和s_l的取值为1or0,所以条件随机场完全由对应的权值\lambda_k,\mu_l确定。$
$Z(x)是规范化因子，求和是在所有可能的输出序列上进行的。$

2 举个栗子

设有一标注问题，输入观测序列为

$X=(X_1,X_2,X_3)$
输出标记序列为
$Y=(Y_1,Y_2,Y_3)，其中Y_1,Y_2,Y_3的取值范围为（1，2）$
$假设特征t_k,s_l和对应的权值\lambda_k, \mu_l如下：$
$\begin{align} &t_1=t_1(y_{i-1}=1, y_i=2,x,i),\qquad i=2,3,\qquad\qquad \lambda_1=1 \\ &t_2=t_2(y_1=1,y_2=1,x,2),\qquad\qquad\qquad\lambda_2=0.6\\ &t_3=t_3(y_2=2,y_3=1,x,3),\qquad\qquad\qquad \lambda_3=1\\ &t_4=t_4(y_1=2,y_2=1,x,2),\qquad\qquad\qquad \lambda_4=1\\ &t_5=t_5(y_2=2,y_3=2,x,3),\qquad\qquad\qquad \lambda_5=0.2\\ &S_1=S_1(Y_1=1,x,1),\qquad\qquad\qquad \mu_1=1\\ &S_2=S_2(Y_i=2,x,i),\qquad i=1,2\qquad\qquad \mu_2=0.5\\ &S_3=S_3(Y_i=1,x,i),\qquad i=2,3\qquad\qquad \mu_3=0.8\\ &S_4=S_4(Y_3=2,x,3),\qquad\qquad\qquad \mu_3=0.5 \end{align}$

image.png

图 4 状态矩阵

3 维特比算法求最优路径

3.1 初始化
$\delta_1(j)=w*F_1(y_0=start,y_1=j,x),j=1,2$
$\begin{align} &i=1,y=1,\qquad\qquad \delta_1(1)=w*F_1(y_0=start,y_1=1,x) = S_1=1 \end{align}$
$\begin{align} &i=1,y=2,\qquad\qquad \delta_1(2)=w*F_1(y_0=start,y_1=2,x) = S_2=0.5 \end{align}$
3.2 递推
$\begin{align} &i=2 \qquad\delta_2(l)=max_j\{ \delta_1(j)+w*F_2(j,l,x)\}\\ &\qquad\qquad i=2,y=1 \qquad\qquad \delta_2(1)=max\{1+\lambda_2t_2+\mu_3s_3,0.5+\lambda_4t_4+\mu_3s_3\}=2.4,\qquad\psi_2(1)=1\\ &\qquad\qquad i=2,y=2 \qquad\qquad \delta_2(2)=max\{1+\lambda_1t_1+\mu_2s_2,0.5+\mu_2s_2\}=2.5,\qquad\psi_2(2)=1 \end{align}$
$\begin{align} &i=3 \qquad\delta_3(l)=max_j\{ \delta_2(j)+w*F_3(j,l,x)\}\\ &\qquad\qquad i=3,y=1 \qquad\qquad \delta_3(1)=max\{2.4+\mu_3s_3,2.5+\lambda_3t_3+\mu_3s_3\}=4.3,\qquad\psi_3(1)=2\\ &\qquad\qquad i=3,y=2 \qquad\qquad \delta_3(2)=max\{2.4+\lambda_1t_1+\mu_4s_4,2.5+\lambda_5t_5+\mu_4s_4\}=3.9,\qquad\psi_3(2)=1 \end{align}$