条件随机场的简单理解

什么是条件随机场

条件随机场长怎么样

如何构建特征函数

前向—后向算法

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

条件随机场的预测问题

什么是条件随机场

条件随机场的定义

条件随机场总的来说就是只要满足“条件随机场”这个条件，就可以根据定义的模型去求解我们需要求解的问题，而我们时长需要解决的问题以线性的居多，所谓线性就是满足“线性链条件随机场”，本文也只涉及对“线性链条件随机场”的讲解。

定义(线性链条件随机场) 设 $X=(X_1,X_2,...,X_n)$ 与 $Y=(Y_1,Y_2,...,Y_n)$ 均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布 $P(Y|X)$ 构成条件随机场，即满足马尔可夫性：

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

$i=1,2,...,n$ 当 $i=1,n$ 时，只考虑单边

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

所谓线性简单的来说就是随机变量序列X各个节点之间的关系是呈线性的，序列Y也一一对应着各个节点的X，而不是其他乱七八糟的关系，也就是满足马尔可夫性。

回忆一下马尔可夫链的两个假设

(1)齐次马尔可夫假设：	即t时刻的状态只受t-1时刻状态的影响
(2)观测独立性假设：	即任意时刻的观测只受该时刻所处状态的影响

在线性条件随机场里面t时刻的状态往往受到前后两个状态的相互影响从而有(条件概率分布)：

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

假设线性条件随机场的应用

它的应用场景与HMM隐马尔科夫模型的类似，因此我们要解决的问题也对应了前面HMM模型的三个问题：

1.概率计算问题：给定参数，计算观测序列出现的概率，如 $P(Y_i=y_i|x)$ , $P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$ 等为后面做准备。

2.学习问题：极大化训练数据的对数函数P，求满足P的参数。

3.预测问题：不用说肯定是输出最大的隐藏序列(标注序列)。

条件随机场长怎么样

条件随机场的参数化形式

我们上面给出了了条件随机场的条件分布函数：

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

但是我们又应该如何得到 $P(Y_i|X,Y{i-1},Y_{i+1})$ 的表达呢？更近一步地，整个序列Y的条件概率分布 $P(Y|X)$ 又应该怎么表达呢？

我们先来看教科书式的表达(参数化表达)：

$p(y|x)=\frac{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)}$

$Z(x)=\sum_y exp(\sum_{i,k}\lambda _kt_k(y_{i-1},y_{i},x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i))$

假设参数化形式的内部理解

1. $t_k(y_{i-1},y_{i},x,i),s_l(y_i,x,i)$ 称为特征函数，其中 $t_k(y_{i-1},y_{i},x,i)$ 是对状态序列的特征提取，表示 $y_{i}$ 的特征受 $y_{i-1}$ 状态的影响。 $s_l(y_i,x,i)$ 是对观测序列的特征提取，表示 $y_{i}$ 受 $x_{i}$ 的影响，说到这里是不是很熟悉，没错，它跟HMM很相似，也体现了马尔可夫的两个假设(至于特征又是怎么提取的下面将会以一个例子来介绍)。特征函数的取值为0或1，满足某个特征就取1，不满足就取0。

2. $\lambda _k,\mu_l$ 表示特征函数的一个权值，表示某个特征的重要程度或者是正负方向。

3. 我们对求和项 $\sum_{i,k}\lambda _kt_k(y_{i-1},y_{i},x,i)+\sum_{i,l}\mu_ls_l(y_i,x,i)$ 做一个合并

得到 $\sum_{k=1}^{K}w _k\sum_{i=1}^nf_k(y_{i-1},y_i,x,i)$ 其中 $K=k+l$ 。

令 $f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i)$ ，

则 $\sum_{k=1}^{K}w _k\sum_{i=1}^nf_k(y_{i-1},y_i,x,i)=\sum_{k=1}^{K}w _kf_k(y,x)$

求和项 $\sum_{k=1}^{K}w _kf_k(y,x)$ 表示对序列 $y=(y_1,y_2,...,y_n)$ 所有的特征求和的一个综合评分

4. 指数化 $e^{\varphi }$ 的意义：数据的大小之于某种结果的贡献往往表现出自然指数的增长性，或者是说采用指数化往往比线性对某种目的的拟合性能更好，比如一个女生选男朋友，有三个对象，身高为(170，175，180)，100分制的评分，似乎(80,85,100)比(80,90,100)更贴合女生的要求，指数化也是这样，用于拉开线性情况下高分与低分的距离。

5. $Z(x)$ 是对所有可能的状态序列 $y$ 求和，其作用是归一化各种情况，以总和为1的形式给出每种情况的概率大小。

如何构建特征函数

OK，那到这里条件随机场的参数化形式就只剩下特征函数怎么求了

一个例子——词性标注问题 ：（转自：http://www.jianshu.com/p/55755fc649b1 ）

词性标注就是给一个句子中的每个单词注明词性。比如这句话：“Bob drank coffee at Starbucks”，注明每个单词的词性后是这样的：“Bob (名词) drank(动词) coffee(名词) at(介词) Starbucks(名词)”。

下面，就用条件随机场来解决这个问题。

以上面的话为例，有5个单词，我们将：(名词，动词，名词，介词，名词)作为一个标注序列，称为l，可选的标注序列有很多种，比如l还可以是这样：（名词，动词，动词，介词，名词），我们要在这么多的可选标注序列中，挑选出一个最靠谱的作为我们对这句话的标注。

怎么判断一个标注序列靠谱不靠谱呢？

就我们上面展示的两个标注序列来说，第二个显然不如第一个靠谱，因为它把第二、第三个单词都标注成了动词，动词后面接动词，这在一个句子中通常是说不通的。

假如我们给每一个标注序列打分，打分越高代表这个标注序列越靠谱，我们至少可以说，凡是标注中出现了动词后面还是动词的标注序列，要给它负分！！

上面所说的动词后面还是动词就是一个特征函数，我们可以定义一个特征函数集合，用这个特征函数集合来为一个标注序列打分，并据此选出最靠谱的标注序列。也就是说，每一个特征函数都可以用来为一个标注序列评分，把集合中所有特征函数对同一个标注序列的评分综合起来，就是这个标注序列最终的评分值。

定义CRF中的特征函数
现在，我们正式地定义一下什么是CRF中的特征函数，所谓特征函数，就是这样的函数，它接受四个参数：
1. 句子 $x=(x_1,x_2,...,x_n)$ （就是我们要标注词性的句子）
2. $i$ ，用来表示句子 $x$ 中第 $i$ 个单词
3. $y_i$ ，表示要评分的标注序列给第i个单词标注的词性
4. $y_{i-1}$ ，表示要评分的标注序列给第i-1个单词标注的词性

它的输出值是0或者1,0表示要评分的标注序列不符合这个特征，1表示要评分的标注序列符合这个特征。

几个特征函数的例子
1. $f_1(y_{i-1},y_i,x,i)$ 当 $y_{i}$ 是“副词”并且第 $i$ 个单词以“ly”结尾时，我们就让 $f_1=1$ ，其他情况 $f_1=0$ 。不难想到， $f_1$ 特征函数的权重 $\lambda_1$ 应当是正的。而且 $\lambda_1$ 越大，表示我们越倾向于采用那些把以“ly”结尾的单词标注为“副词”的标注序列

2. $f_2(y_{i-1},y_i,x,i)$ 如果 $i=1$ ， $l_i$ 为动词，并且句子 $x$ 是以“？”结尾时， $f_2=1$ ，其他情况 $f_2=0$ 。同样， $\lambda_2$ 应当是正的，并且 $\lambda_2$ 越大，表示我们越倾向于采用那些把问句的第一个单词标注为“动词”的标注序列。

3. $f_3(y_{i-1},y_i,x,i)$ 当 $l_{i-1}$ 是介词， $l_{i}$ 是名词时， $f_3=1$ ，其他情况 $f_3=0$ 。 $\lambda_3$ 也应当是正的，并且 $\lambda_3$ 越大，说明我们越认为介词后面应当跟一个名词。

4. $f_4(y_{i-1},y_i,x,i)$ 如果 $l_{i}$ 和 $l_{i-1}$ 都是介词，那么 $f_4=1$ ，其他情况 $f_4=0$ 。这里，我们应当可以想到 $\lambda_4$ 是负的，并且 $\lambda_4$ 的绝对值越大，表示我们越不认可介词后面还是介词的标注序列。

.................一系列的特征函数对序列 $y$ 的每个节点进行评分求和，最后归一化就可以得到当前序列 $y$ 的概率大小。

$p(y|x)=\frac{exp(\sum_{k=1}^{K}w _kf_k(y,x))}{Z(x)}$

$Z(x)=\sum_y exp(\sum_{k=1}^{K}w _kf_k(y,x))$

前向—后向算法

细看一下分子

先回顾一下条件概率分布函数 $p(y|x)=\frac{exp(\sum_{k=1}^{K}w _kf_k(y,x))}{Z(x)}$ 的分子部分 $exp(\sum_{k=1}^{K}w _kf_k(y,x))$

如果根据 $i$ 展开应该是这样的： $exp(\sum_{i=1}^{n+1} \sum_{k=1}^{K}w _kf_k(y_{i-1},y_i,x,i))=\prod _{i=1}^{n+1} (exp(\sum_{k=1}^{K}w _kf_k(y_{i-1},y_i,x,i)))$

定义一个函数

$M_i(y_{i-1},y_i|x)=exp(\sum_{k=1}^{K}w _kf_k(y_{i-1},y_i,x,i))$ 表示在x的条件下取得状态 $y_{i-1},y_i$ 时所有特征的得分

定义一个M阶矩阵

$M_i(x)=[M_i(y_{i-1},y_i|x)]$ 不同的状态 $y_{i-1},y_i$ ，对应不同的值，m表示 $y_i$ 有m种状态

分布函数的新形式

$p(y|x)=\frac{\prod _{i=1}^{n+1}M_i(y_{i-1},y_i|x)}{Z(x)}$ ，

$Z(x)=(\sum_y\prod _{i=1}^{n+1}M_i(y_{i-1},y_i|x))$ 表示对所有序列的非规范化得分的总和

前向—后向算法

对每个指标 $i=0,1,2,...,n+1$ ，定义前向向量 $a_i(x)$ ：

起始单元：

$a_0(y|x)=\left\{\begin{matrix} 1,\ \ \ y=start \\ 0,\ \ \ y\neq start \end{matrix}\right.$

递推单元：

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

可表示为：

$a_i^{T}(x)=a_{i-1}^{T}(x)M_i(x)$

$a_i^{T}(y_i|x)$ 表示在已知序列y的情况下从位置0到i的得分，或叫非规范化概率

用图表示

同样，定义后向向量

$\beta_{n+1}(y_{n+1}|x)=\left\{\begin{matrix} 1,\ \ \ y_{n+1}=stop \\ 0,\ \ \ y_{n+1}\neq stop\end{matrix}\right.$

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

$\beta_i^{T}(y_i|x)$ 表示在已知序列y的情况下从末尾位置反向到i的得分，或叫非规范化概率

由前向后向算法不难得到

$Z(x)=a_{n}^{T}(x)\cdot 1=1^T\cdot \beta_1^{T}(x)$ ，1为m维的单位向量。

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

状态i为yi的概率

$P(Y_i=y_i|x)=\frac{a_i^T(y_i|x)\beta_i(y_i|x))}{Z(x)},Z(x)=a_{n}^T(x)\cdot1=1^T\cdot\beta_1(x)$

状态i-1为yi-1，状态i为yi的概率

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

期望值的计算

条件随机场的预测问题

预测问题就是给定条件随机场 $P(Y|X)$ 和输入序列 $x$ ，求条件概率最大的标记序列 $y^*$ ，即对观测序列进行标注

$y^*=arg\ max_y\ p_w(y|x)$

$=arg\ max_y\ \frac{exp(w\cdot F(y,x))}{Z(x)}$

$=arg\ max_y\ exp(w\cdot F(y,x))$

$=arg\ max_y\ (w\cdot F(y,x))$

其中

$w=(w_1,w_2,..,w_k)$

$F(y,x)=(f_1(y,x),f_2(y,x),...,f_k(y,x))^T$

$f_k(y,x)=\sum_{i=1}^nf_k(y_{i-1},y_i,x,i),k=1,2,...,K$

故 $w\cdot F(y,x)$ 表示根据指定序列的 $y$ ，对每一个节点 $i=1,2,...,n$ 中的每一个特征函数与权重的成绩乘积求和

是条件随机场预测问题成为非规范化概率(得分)最大的最优化路径问题。

维比特算法

曾记否，在讲HMM时我们也用了维比特算法求最优路径的，大概就是在每个节点 $i$ 求使 $P(y_i=j|y_1,y_2,...,y_i-1,x)$ 最大的 $y_{i-1}$ 的标注是什么，在遍历完 $i$ 后返向求取上一个标注，最终得到最优路径在这里也是一样。

为了对每一个节点进行展开计算，我们需要定义

$F_i(y_{i-1},y_i,x)=(f_1(y_{i-1},y_i,x),f_2(y_{i-1},y_i,x),...,f_k(y_{i-1},y_i,x))^T$ ,表示在节点i处各特征得分和的向量

令

$\delta _1=w\cdot F_1(y_{0}=start,y_1,x)$ ,表示i=1节点处乘以权重向量后的得分和的向量

$\delta _1(j)=w\cdot F_i(y_{i-1},y_i=j,x),j=1,2,...m$ 可以表示 $\delta _i$ 的每个分量，m表示状态的个数

$\delta _i(l)=\underset{1\leq j\leq m}{max}(\delta _{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)),l=1,2,...m$ 表示在节点i-1处取得最大值的项连接到i处各个标注的得分

$\varphi_i(l)=arg\underset{1\leq j\leq m}{max}(\delta _{i-1}(j)+w\cdot F_i(y_{i-1}=j,y_i=l,x)),l=1,2,...m$ 记录上一个节点的最大位置

当i=n时 $\underset{1\leq j\leq m}{max}\delta _n(j)$ 就是非规范化概率的最大值

而 $\varphi_n(j)=arg\underset{1\leq j\leq m}{max}(\delta _{n}(l))$ 就是最优路径的终点 $y^*_n$

将后一个节点的最优值作为当前节点的指针便可以得到当前节点的最优值得

所以 $y^*_i=\varphi _{i+1}(y^*_{i+1}),i=n-1,n-1,...,1$

则 $y^*=(y^*_1,y^*_2,...,y^*_n)$ 就是使得概率最大化的最优标注序列。

到最优的标注序列 $y^*=()$

未完待续

[1] 李航.统计学习方法[M].北京：清华大学出版社，2012：155-184

[2] 如何轻松愉快地理解条件随机场（CRF）？[Online]. https://www.jianshu.com/p/55755fc649b1