统计机器学习-条件随机场

2020-07-08 本文已影响0人又双叒叕苟了一天

条件随机场是给定一组输入随机变量条件下另一组随机变量的条件概率分布模型 $P(Y|X)$ ，其特点是假设输出随机变量构成马尔可夫随机场。类似隐马尔可夫模型，条件随机场也有概率计算问题，学习问题和预测问题，后面会给出解决这些问题的算法。首先定义马尔可夫随机场。

概率无向图模型（马尔可夫随机场）

概率无向图模型又叫做马尔可夫随机场。如下图所示

概率无向图

$Y_1,Y_2,\cdots,Y_5$ 是五个随机变量，是概率无向图的结点，结点的集合记做 $V$ 。连线代表随机变量之间的依赖关系，是概率无向图的边，边的集合记做 $E$ ，如果两个变量之间没有连线，说明这两个随机变量独立。整个概率无向图可以记做 $G=(V,E)$ 。

概率无向图可以通过以下方式定义，首先描述成对马尔可夫性、局部马尔可夫性、全局马尔可夫性：

成对马尔可夫性：设 $u$ 和 $v$ 是无向图 $G$ 中任意两个没有边连接的结点，结点 $u$ 和 $v$ 分别对应随机变量 $Y_u$ 和 $Y_v$ ，其他所有结点为 $O$ ，对应的随机变量为 $Y_O$ ，这些随机变量满足：
$P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_u|Y_O)$
即随机变量 $Y_u$ 和 $Y_v$ 条件独立。

可以看出，上述成对的、局部的、全局的马尔可夫性定义是等价的。

概率无向图模型的定义

设有联合概率分布 $P(Y)$ ，由无向图 $G=(V,E)$ 表示，在图 $G$ 中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布 $P(Y)$ 满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型，或马尔可夫随机场。

有了如上定义，重要的是如何求联合 $P(Y)$ 。事实上，联合概率可以写成若干子联合概率的乘积形式，也就是将联合概率进行因子分解。

概率无向图模型的因子分解

首先定义图与最大团。

团与最大团的定义

无向图 $G$ 中任何两个结点均有边连接的结点子集称为团。若 $C$ 是无向图 $G$ 的一个团，并且不能再加进任何一个 $G$ 的结点使其成为一个更大的团，则称 $C$ 为最大团。

如下图

团与最大团

上图有7个团， $\{Y_1,Y_2\}, \{Y_2,Y_3\}, \{Y_3,Y_4\}, \{Y_4,Y_2\}, \{Y_1,Y_3\}, \{Y_1,Y_2,Y_3\}, \{Y_2,Y_3,Y_4\}$ ，其中 $\{Y_1,Y_2,Y_3\}, \{Y_2,Y_3,Y_4\}$ 是最大团。

Hammersley-Clifford定理

概率无向图模型的联合概率分布 $P(Y)$ 可以表示为如下形式：
$P(Y)=\frac1Z\prod_C\Psi_C(Y_C)$

$Z=\sum_Y\prod_C\Psi_C(Y_C)$

其中， $C$ 是无向图的最大团， $Y_C$ 是 $C$ 的结点对应的随机变量， $\Psi_C(Y_C)$ 是 $C$ 上定义的严格正函数（通常定义为指数函数 $\Psi_C(Y_C)=\exp\{-E(Y_C)\}$ ），乘积是在无向图所有的最大团上进行的。规范化因子 $Z$ 是对 $Y$ 所有可能的取值情况求和，使其符合概率分布。

条件随机场的定义与形式

条件随机场是在给定随机变量 $X$ 的条件下，随机变量 $Y$ 的马尔可夫随机场 $P(Y|X)$ 。其中 $X$ 是输入变量，表示需要标注的观测序列。 $Y$ 是输出变量，表示标记序列，也称为状态序列（类似隐马尔可夫模型，是没有标注的隐变量）。可以用下图表示：

条件随机场

某个随机变量 $Y_v$ 依赖于 $X$ 和有边相连接的随机变量 $Y_W$ 。于是有如下定义

条件随机场的定义

设 $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\sim v)$
对任意结点 $v$ 成立，则称条件随机概率分布 $P(Y|X)$ 为条件随机场。式中 $w\sim v$ 表示在图 $G=(V,E)$ 中与结点 $v$ 有边连接的所有结点 $w$ ， $w\neq v$ 表示结点 $v$ 以外的所有结点， $Y_v$ ， $Y_w$ 为结点 $v,w$ 对应的随机变量。

为了简化问题，通常假设随机变量 $Y$ 的概率无向图是一条线性链，叫做线性链条件随机场，这种假设虽然简化了问题，但是依然可以取得比较好的效果，并大大降低了计算的复杂度。如下图

线性链条件随机场

此时，相邻的两个随机变量构成一个最大团。但是这种情况依然很复杂，在此假设上，再假设随机变量 $X$ 有着和 $Y$ 相同的图结构，如下图

XY相同图结构的线性链条件随机场

此时每个随机变量 $Y_i$ 只依赖于有边相连接的随机变量 $Y_{i-1}$ ， $Y_{i+1}$ 和 $X_i$ 。线性链条件随机场有如下定义

线性链条件随机场的定义

设 $X=(X_1,X_2,\cdots,X_n)$ ， $Y=(Y_1,Y_2,\cdots,Y_n)$ 均为线性链表示的随机变量序列，若在给定随机变量序列 $X$ 的条件下，随机变量序列 $Y$ 的条件概率分布 $P(Y|X)$ 构成条件随机场，即满足马尔可夫性
$P(Y_i|X,Y_i,\cdots,Y_{i-1},Y_{i+1},\cdots,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})\\ i=1,2,\cdots,n\ \ (在i=1和n时只考虑单边)\tag1$
则称 $P(Y|X)$ 为线性链条件随机场。在标注问题中， $X$ 表示输入观测序列， $Y$ 表示对应的输出标记序列或状态序列。

条件随机场的参数化形式

根据Hammersley-Clifford定理，可以给出线性链条件随机场的参数化形式。

线性链条件随机场的参数化形式

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

值得注意的是，特征函数 $t_k$ 依赖于输入 $x$ ，当前位置 $y_i$ 和上个位置 $y_{i-1}$ ，称为转移特征。特征函数 $s_l$ 依赖于输入 $x$ 和当前位置 $y_i$ ，称为状态特征。特征函数 $t_k$ 和 $s_l$ 取值通常为0或1，当满足特征时，取1。

条件随机场的简化形式

将转移特征 $t_k$ 和状态特征 $s_l$ 用统一的方式表示，对上述参数化形式进行简化。假设有 $K_1$ 个转移特征， $K_2$ 个状态特征，则共有 $K=K_1+K_2$ 个特征函数，记
$f_k(y_{i-1},y_i,x,i)= \begin{cases} t_k(y_{i-1},y_i,x,i),\ \ k=1,2,\cdots,K_1\\ s_l(y_i,x,i),\ \ k=K_1+l;l=1,2,\cdots,K_2 \end{cases}$
使用特征函数对各个位置 $i$ 求和，记为
$f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i),\ \ k=1,2,\cdots,K$
各个特征的权值记为
$w_k= \begin{cases} \lambda_k,\ \ k=1,2,\cdots,K_1\\ \mu_l,\ \ k=K_1+l;l=1,2,\cdots,K_2 \end{cases}$
则线性链条件随机场的参数形式可以简化为
$P(y|x)=\frac1{Z(x)}\exp{\sum_{k=1}^Kw_kf_k(y,x)}\tag4$

$Z(x)=\sum_y\exp\sum_{k=1}^Kw_kf_k(y,x)\tag5$

回顾最大熵模型：
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

可以看出两者有着非常类似的形式，并且线性链条件随机场也是对数线性模型。

若以 $w$ 表示权值向量，即
$w=(w_1,w_2,\cdots,w_K)^T$
以 $F(y,x)$ 表示全局特征向量，即
$F(y,x)=(f_1(y,x),f_2(y,x),\cdots,f_K(y,x))^T$
则线性链条件随机场还有以下内积形式：
$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))$

条件随机场的矩阵形式

在标记（状态）序列 $y$ 引入特殊的起点和终点状态标记 $y_0=\mathrm{start}$ ， $y_{n+1}=\mathrm{stop}$ ，这时 $P_w(y|x)$ 可以通过矩阵形式表示。

对观测序列 $x$ 的每一个位置 $i=1,2,\cdots,n+1$ ，定义一个 $m$ 阶矩阵（ $m$ 是标记 $y_i$ 取值的个数，因为 $y_0$ 和 $y_{n+1}$ 只有是不是start或是不是stop两个取值，所以在起点和终点 $m=2$ ，其余位置正常）
$M_i(x)=[M_i(y_{i-1},y_i|x)]_{m_{y_{i-1}}\times m_{y_i}}$

$M_i(y_{i-1},y_i|x)=\exp(W_i(y_{i-1},y_i|x))$

$W_i(y_{i-1},y_i|x)=\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)$

$M_i(y_{i-1},y_i|x)=\exp[\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)]$ 可以看做各个位置 $i$ 上特征函数的加权和再求 $\exp$ ，得到输入 $x$ 条件下，未规范化的状态 $y_{i-1}$ 到状态 $y_i$ 之间的状态转移概率。

这样，给定观测序列 $x$ ，相应标记序列 $y$ 的非规范概率可以通过该序列 $n+1$ 个矩阵适当元素的乘积 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 表示。于是，条件概率 $P_w(y|x)$ 是
$P_w(y|x)=\frac1{Z_w(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)\tag6$
其中 $Z_w(x)$ 为规范化因子，是 $n+1$ 个矩阵的乘积的下标为 $(\mathrm{start},\mathrm{stop})$ 的元素
$Z_w(x)=(M_1(x)M_2(x)\cdots M_{n+1}(x))_{\mathrm{start},\mathrm{stop}}\tag7$
$y_0=\mathrm{start}$ ， $y_{n+1}=\mathrm{stop}$ ，表示开始状态与终止状态，规范化因子 $Z_w(x)$ 是以 $\mathrm{start}$ 为起点 $\mathrm{stop}$ 为终点通过状态的所有路径 $y_1,y_2,\cdots,y_n$ 的非规范化概率 $\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$ 之和。可以通过矩阵计算公式得到，过程略。

条件随机场的概率计算问题

条件随机场的概率计算问题是给定条件随机场 $P(Y|X)$ ，输入序列 $x$ 和输出序列 $y$ ，计算条件概率 $P(Y_i=y_i|x)$ ， $P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ 以及相应的数学期望的问题。类似隐马尔可夫模型，使用前向-后向算法。

前向-后向算法

对每个指标 $i=0,1,\cdots,n+1$ ，定义前向向量 $\alpha_i(x)$ ：
$\alpha_0(y|x)= \begin{cases} 1,\ \ y=\mathrm{start}\\ 0,\ \ 否则 \end{cases}$
递推公式为
$\alpha_i^T(y_i|x)=\alpha_{i-1}^T(y_{i-1}|x)[M_i(y_{i-1},y_i|x)],\ \ i=1,2,\cdots,n+1\tag8$
又可表示为
$\alpha_i^T(x)=\alpha_{i-1}^T(x)M_i(x)$
$\alpha_i(y_i|x)$ 表示在位置 $i$ 的标记是 $y_i$ 并且到位置 $i$ 的前部分标记序列的非规范化概率， $y$ 的取值有 $m$ 个，所以 $\alpha_i(x)$ 是 $m$ 维列向量。

同样，对每个指标 $i=0,1,\cdots,n+1$ ，定义后向向量 $\beta_i(x)$ ：
$\beta_{n+1}(y_{n+1}|x)= \begin{cases} 1,\ \ y_{n+1}=\mathrm{stop}\\ 0,\ \ 否则 \end{cases}$
递推公式
$\beta_i(y_i|x)=[M_i(y_i,y_{i+1}|x)]\beta_{i+1}(y_{i+1}|x)\tag9$
又可表示为
$\beta_i(x)=M_{i+1}(x)\beta_{i+1}(x)$
$\beta_i(y_i|x)$ 表示在位置 $i$ 的标记为 $y_i$ 并且从 $i+1$ 到 $n$ 的后部分标记序列的非规范化概率， $y$ 的取值有 $m$ 个，所以 $\beta_i(y_i|x)$ 是 $m$ 维列向量。

由前向-后向向量的定义不难得到：
$Z(x)=\alpha_n^T(x)\cdot\textbf1=\textbf1^T\beta_1(x)\tag{10}$
这里， $\textbf1$ 是元素均为1的 $m$ 维列向量。

概率计算

$P(Y_i=y_i|x)=\frac{\alpha_i^T(y_i|x)\beta_i(y_i|x)}{Z(x)}\tag{11}$

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

其中，
$Z(x)=\alpha_n^T(x)\cdot\textbf1\tag{13}$

期望值计算

$\begin{align} 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)P(Y_{i-1}=y_{i-1},Y_i=y_i|x)\\ &=\sum_{i=1}^{n+1}\sum_{y_{i-1},y_i}f_k(y_{i-1},y_i,x,i)\frac{\alpha_i^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} \end{align}\\ k=1,2,\cdots,K\tag{14}$

其中，
$Z(x)=\alpha_n^T(x)\cdot\textbf1$

$\begin{align} 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\tilde P(x)\sum_yP(y|x)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\ &=\sum_x\tilde P(x)\sum_y\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\frac{\alpha_i^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)} \end{align}\\ k=1,2,\cdots,K\tag{15}$

其中 $\tilde P(x)$ 是 $x$ 的经验分布。

$f_k(y_{i-1},y_i,x,i)$ 在 $1\leq k\leq K_1$ 时，是转移特征函数，对应概率 $P(y|x)=P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ ，在 $K_1\lt k\leq K_1+K_2$ 时，是状态特征函数，对应概率 $P(y|x)=P(Y_i=y_i|x)$ 。可以通过一次前向扫描得到 $\alpha_i$ 和 $Z(x)$ ，通过一次后向扫描计算 $\beta_i$ ，从而计算所有的概率和特征的期望。

条件随机场的学习算法

条件随机场模型实际上是定义在时序数据上的对数线性模型，类似最大熵模型，所以也可以用IIS法，梯度下降法以及拟牛顿法。

改进的迭代尺度法（IIS）法

IIS法的思路是找到特征函数权值参数 $w$ 的更新量 $\delta$ ，使得极大似然函数改变量 $L(w+\delta)-L(\delta)$ 的下界在每次迭代时提高，达到极大似然估计的效果，具体推导参考最大熵模型。

条件随机场模型学习的改进的迭代尺度法

输入：特征函数 $t_1,t_2,\cdots,t_{K_1}$ ， $s_1,s_2,\cdots,s_{K_2}$ ；经验分布 $\tilde P(x,y)$ ；

输出：参数估计值 $\hat w$ ；模型 $P_{\hat w}$ 。

（1）对所有 $k\in \{1,2,\cdots,K\}$ ，取初值 $w_k=0$

（2）对每一 $k\in \{1,2,\cdots,K\}$ ：

（a）当 $k=1,2,\cdots,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=K_1+l$ ， $l=1,2,\cdots,K_2$ 时，令 $\delta_{K_1+l}$ 是方程
$\sum_{x,y}\tilde P(x)P(y|x)\sum_{i=1}^ns_l(y_i,x,i)\exp(\delta_{K_1+l}T(x,y))=E_{\tilde P}[s_l]$
的解，其中
$T(x,y)=\sum_kf_k(y,x)=\sum_{k=1}^K\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)$
是在数据 $(x,y)$ 中出现所有特征的总和。

（b）更新 $w_k$ 值： $w_k\leftarrow w_k+\delta_k$

（3）如果不是所有 $w_k$ 都收敛，重复步骤（2）

当 $T(x,y)$ 是常数时，方程比较容易求解，当 $T(x,y)$ 不是常数时，方程比较难求解，在《统计机器学习》条件随机场部分有其他相关解决方法的描述。

拟牛顿法

对于条件随机场模型
$P_w(y|x)=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(y,x)\bigg)}$
学习的优化目标函数是对数似然函数的相反数：
$\min_{w\in\textbf R^n}f(w)=\sum_x\tilde P(x)\log\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)-\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)$
其梯度函数是
$g(w)=\sum_{x,y}\tilde P(x)P_w(y|x)f(x,y)-E_{\tilde P}(f)$

条件随机场模型学习的BFGS算法

输入：特征函数 $t_1,t_2,\cdots,t_{K_1}$ ， $s_1,s_2,\cdots,s_{K_2}$ ；经验分布 $\tilde P(x,y)$ ；

输出：参数估计值 $\hat w$ ；模型 $P_{\hat w}$ 。

（1）选定初始点 $w^{(0)}$ ，取 $B_0$ 为正定对称矩阵，置 $k=0$

（2）计算 $g_k=g(w^{(k)})$ 。若 $g_k=0$ ，则停止计算，否则转（3）

（3）由 $B_kp_k=-g_k$ 求出 $p_k$

（4）一维搜索：求 $\lambda_k$ 使得
$f(w^{(k)}+\lambda_kp_k)=\min_{\lambda\geq0}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+1}=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$ ，转（3）