条件随机场

条件随机场是给定随机变量X，输出随机变量Y的条件随机场，隐马尔科夫模型事实上就是一种线性链条件随机场，因此隐马尔科夫模型中的三个问题在这里同样是讨论的重点。

概率无向图

概率无向图模型又称为马尔科夫随机场，是一个由无向图表示的联合概率分布。

定义

概率图模型G=(V, E)是由图表示的概率分布，设有联合概率分布$P(Y), Y\in{y}$是一组随机变量，在对应无向图G中，结点$v\in{V}$表示一个随机变量$Y_V$，$Y=(Y_V), v\in{V}$，边$e\in{E}$表示随机变量之间的概率依赖关系。如果联合概率分布$P(Y)$满足成对、局部或全局马尔可夫性，则此联合概率分布称为概率无向图模型或者马尔科夫随机场。

马尔可夫性

• 成对马尔可夫性
• 局部马尔可夫性
• 全局马尔可夫性

成对马尔可夫性

u和v是无向图G中任意两个没有边连接的结点，对应随机变量为$Y_u$和$Y_v$，其他所有结点为O。
给定随机变量组$Y_O$的条件下随机变量$Y_u$和$Y_v$是条件独立。

$$P(Y_u, Y_v | Y_O) = P(Y_u | Y_O)P(Y_v | Y_O)$$

局部马尔可夫性

v是G中任意一个结点，W是与v有边连接的所有结点，O是v，W以外所有的其他结点。
给定随机变量组$Y_W$的条件下随机变量$Y_V$与$Y_O$是条件独立的。

$$P(Y_v, Y_O | Y_W) = P(Y_v | Y_W)P(Y_O | Y_W)$$

成对马尔可夫性

给定随机变量组$Y_C$条件下随机变量组$Y_A$和$Y_B$是条件独立的

$$P(Y_A, Y_B | Y_C) = P(Y_A | Y_C)P(Y_B | Y_C)$$

因子分解

团与最大团

无向图中任何两个节点均有链接的结点子集称为团，若这个团是无向图G中的一个团，且不能从G中再加入任何一个结点，则称它为最大团。

Hammersley-Clifford定理

概率无向图模型的联合概率分布P(Y)可以表示如下：

$$P(Y) = \frac{1}{Z}{\prod_{C}{\Phi_C(Y_C)}}$$ $$Z = \sum_Y{\prod_C{\Phi_C(Y_C)}}$$

通常

$$\Phi_C(Y_C) = exp[-E(Y_C)]$$

其中，C是无向图G中的所有团构成的集合。

条件随机场

定义

设X与Y是随机变量，$P(Y|X)$是在给定X条件下Y的条件概率分布。若随机变量Y构成一个由无向图$G=(V,E)$表示的马尔科夫随机场，即

$$P(Y_v | X, Y_w, w\neq{v}) = P(Y_v | X, Y_w, w~v)$$

对任意结点v成立，则称条件概率分布$P(Y|X)$为条件随机场。

线性链条件随机场
设X，Y均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布$P(Y|X)$构成条件随机场，即满足马尔可夫性

$$P(Y_i|X,Y_1,...,Y_{i-1},Y_{i+1},...,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})$$

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

形式

参数化形式

设$P(Y|X)$为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率有如下形式：

$$P(y|x)=\frac{1}{Z(x)}{exp(\sum_{i,k}{\lambda_k t_k(y_{i-1},y_i,x,i)} + \sum_{i,l}{\mu_l s_l(y_i,x,i)})}$$

其中

$$Z(x)=\sum_y{exp(\sum_{i,k}{\lambda_k t_k(y_{i-1}, y_i, x, i)} + \sum_{i,l}{\mu_l s_l(y_i,x,i)})}$$

简化形式

$$P_w(y|x) = \frac{exp(w\cdot{F(y,x)})}{Z_w(x)}$$

其中，

$$Z_w(x)=\sum_y{exp(w\cdot{F(y,x)})}$$

矩阵形式

$$P_w(y|x)=\frac{1}{Z_w(x)}\prod_{i=1}^{n+1}{M_i(y_{i-1},y_i|x)}$$

其中

$$Z_w(x)=(M_1(x)M_2(x)...M_{n+1}(x))_{start,stop}$$

概率计算问题

给定条件随机场$P(Y|X)$输入序列x和输出序列y，计算条件概率$P(Yi=y_i|x)$，$P(Y{i-1}=y_{i-1},Y_i=y_i|x)$

前向-后向算法

前向向量

$$\alpha_0(y|x) = \begin{cases} 1, & y=start \\ 0, & otherwise \end{cases}$$

则递推公式为：

$$\alpha^T(y_i|x) = \alpha_{i-1}^{T}(y_{i-1}|x)M_i(y_{i-1},y_i|x), i=1,2,...,n+1$$

或者

$$\alpha_i^T(x) = \alpha_{i-1}^T(x)M_i(x)$$

后向向量

$$\beta_{n+1}(y_{n+1}|x) = \begin{cases} 1, & y_{n+1} = stop \\ 0, & otherwise \end{cases}$$

则递推公式为

$$\beta_i(y_i|x) = M_i(y_i,y_{i+1}|x)\beta_{i-1}(y_{i+1}|x)$$

或者

$$\beta_i(x) = M_{i+1}(x)\beta_{i+1}(x)$$

概率计算

$$P(Y_i=y_i|x) = \frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{Z(x)}$$ $$P(Y_{i-1}=y_{i-1},Y_i=y_i|x) = \frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}$$

其中

$$Z(x) = \alpha_n^T(x)\cdot{\mathbf{1}}$$

期望值的计算

利用前向-后向向量，可以计算联合分布和条件分布的数学期望
特征函数$f_k$关于条件分布$P(Y|X)$的数学期望是

$$\begin{equation}\begin{split} E_{P(Y|X)}[f_k] &= \sum_yP(y|x)f_k(y,x)\\ &= \sum_{i=1}^{n+1}\sum_{y_{i-1}y_i}f_k(y_{i-1},y_i,x,i)\frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1}, y_i|x)\beta_i(y_i|x)}{Z(x)} \end{split}\end{equation}$$

其中

$$Z(x) = \alpha_n^T(x)\cdot{\mathbf{1}}$$

特征函数$f_k$关于联合分布$P(X，Y)$的数学期望是

$$\begin{equation}\begin{split} E_{P(X,Y)}[f_k] &= \sum_{x,y}P(x,y)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\ &= \sum_x\hat{P}(x)\sum_yP(y|x)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\ &= \sum_x\hat{P}(x)\sum_{i=1}^{n+1}\sum_{y_{i-1}y_i}f_k(y_{i-1},y_i,x,i)\frac{\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} \end{split}\end{equation}$$

其中

$$Z(x) = \alpha_n^T(x)\cdot{\mathbf{1}}$$

学习算法

迭代尺度法

算法
输入：特征函数$t1$, $t_2$,…,$t{K1}$, $s_1$, $s_2$, …, $s{K2}$；经验分布$\hat{P}(X,Y)$
输出：参数估计值$\hat w$; 模型$P{\hat w}$

1. 对所有$k\in {1,2,…,K}$, 取初值$w_k=0$
2. 对所有$k\in {1,2,…,K}$, 取初值$w_k=0$
3. 对每一个$k\in {1,2,..K}$:
   当k=1,2,…,$K_1$时，令$\delta_k$是方程 $$\sum_{x,y}\tilde{P}(x)P(y|x)\sum_{i=1}^{n+1}{t_k(y_{i-1},y_i,x,i)}exp(\delta_kT(x,y)) = E_{\tilde{P}[t_k]}$$ 的解
   当$k=K1 + l, l=1,2,…,K_2$时，令$\delta{K_1+l}$是方程 $$\sum_{x,y}\hat{P}(x)P(y|x)\sum_{i=1}^{n}{s_l(y_i,x,i)}exp(\delta_{K_1+l}T(x,y)) = E_{\tilde{P}}[s_l]$$ 的解
   更新$w_k$的值: $w_k = w_k + \delta$
4. 如果不是所有$w_k$都收敛，就重复第二步

拟牛顿法

输入：特征函数$f1$, $f_2$, …, $f_n$；经验分布$\tilde{P}(X,Y)$
输出：最优参数值$\hat w$，最优模型$P{\hat w}(Y|X)$

1. 选定初始值$w^{(0)}$，取$B_0$为正定对称矩阵，置k=0
2. 计算$g_k=g(w^{(k)})$。若$g_k=0$，则停止计算；否则转第三步
3. 由$B_kp_k=-g_k$求出$p_k$
4. 一维搜索：求$\lambda_k$使得 $$f(w^{(k)} + \lambda_kp_k) = \min_{\lambda \ge 0}f(w_{(k)} + \lambda p_k)$$
5. 置$w^{(k-1)} = w^{(k)} + \lambda_kp_k$
6. 计算$g{k-1}=g(w^{(k-1)})$，若$g_k=0$，则停止计算；否则，按下式求出$B{k-1}$: $$B_{k+1} = B_k + \frac{y_ky_k^T}{y_k^T\delta_k} - \frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}$$ 其中， $$y_k=g_{k+1} - g_k, \delta_k=w^{(k+1)} - w{(k)}$$
7. 置k=k+1，转第三步

预测算法

维特比算法
输入：模型特征向量F(y,x)和权值向量w，观测序列$x=(x_1,x_2,…,x_n)$
输出：最优路径$y=(y_1^*,y_2^*,…,y_n^*)$

1. 初始化 $$\delta_1(j)=w\cdot F_1(y_0=start,y_1=j,x), j=1,2,...,m$$
2. 递推。对i=1,2,…,n $$\delta_i(l)=\max_{1\le{j}\le{m}}\{\delta_{i-1}(j) + w\cdot{F_i}(y_{i-1}=j,y_i=l,x)\}, l=1,2,...,m$$ $$\phi_i(l) = arg\,\max_{1\le{j}\le{m}}\{\delta_{i-1}(j) + w\cdot{F_i}(y_{i-1}=j,y_i=l,x)\}, l=1,2,...,m$$
3. 终止 $$\max_y(w\cdot{F(y,x)}) = \max_{1\le{j}\le{m}}\delta_n(j)$$ $$y_n^* = arg\,\max{1\le{j}\le{m}}\delta_n(j)$$
4. 返回路径 $$y_i^* = \phi_{i+1}(y_{i+1}^*), i=n-1,n-2,...,1$$ 获得最优路径 $ y = (y_1^*, y_2^*, …, y_n^*)$