很久之前曾经接触过CRF，但是觉得这东西太晦涩难懂了，看了很多科普博客但很多都是从概率图的层面上解释的，虽然图形能让你很快了解个大概，但是有些地方疑惑时是很难从图形中得到答案的，所以我更喜欢从公式出发。最近重拾CRF，顺便也回顾了HMM MEMM，这几个模型主要用在了序列标注上，故在此形成一个小型知识体系便于以后复习。
前情知识
生成模型 & 判别模型
生成模型
生成模型学习的是联合概率 p(x,y)=p(x|y)p(y)，然后利用贝叶斯定理来求解后验概率 p(y|x)
p(y|x)=p(x|y)p(y)∑y′?γp(x|y′)p(y′)
常见的生成模型有：朴素贝叶斯（NB），HMM
判别式模型
直接学习 p(y|x;w), w 为学习参数，判别式模型根据所提供的 feature 直接学习一个分类边界
常见的判别式模型：神经网络，SVM，CRF
对数线性模型（log-linear model）
对于有一系列输入数据 χ ，和一系列标签数据 γ ，如何通过这些标注数据来求解 p(y|x) 呢？判别式模型建模：
p(y|x),?(x,y)∈χ×γ
对于上述建模一般可以用对数线性模型来求解，常见的最大熵模型、softmax、MEMM、CRF都使用了对数线性模型。
对数线性模型一般包含：
特征函数是需要定义的，比如可以这么定义特征函数：
满足条件fk(x,y)={1,满足条件0,otherwise
其中，特征函数 fk(x,y) 个数可任意制定 (k=1,...,d)
那啥是特征呢？
按照刚刚的描述，特征用向量来表示。特征向量 f(x,y) 的每一维 fk(x,y),(k=1,...,d) 都是一个特征。特征可以表达 x 和 y 的各种性质。每个特征有一个权重参数 wk ，权重的值通过训练数据估计。训练数据由样例 (x(i),y(i)),i=1,..,n 组成。
对于任意的 (x,y)∈χ×γ，判别式模型定义了如下的条件概率：
p(y|x;w)=exp(w?f(x,y))∑y′?γexp(w?f(x,y′))
分母 Z=∑y′?γexp(w?f(x,y′)) 为归一化项，可以保证 ∑y∈γp(y|x;w)=1，对上式两边同时取对数，得到：
$$log p(y|x;w)=log exp(w?f(x,y))∑y′?γexp(w?f(x,y′))=w?f(x,y)?logZ$$
可见第一项 w?f(x,y) 是线性的，而第二项当 x 固定时，logZ 也是固定的。所以当 x 固定时， logp(y|x;w) 是特征的线性函数，因此叫对数线性模型。
对于训练集 (x(i),y(i)),i=1,..,n 样本的损失函数如下：
L(w)=∑inlog p(yi|xi;w)
为了防止过拟合，一般会加上 L2 正则
L′(w)=∑inlog p(yi|xi;w)?λ2∑kwk2
可用梯度上升法来优化损失更新参数。
一般用极大似然估计来估计参数
vw=argmaxw∈RdL′(w)
分类问题和序列标注问题
分类问题
分类问题一般是对输入进行建模得到语义编码（如可以使用RNN，CNN进行编码）然后经过分类器将空间映射到分类空间上，最后可通过softmax将权重归一化得到映射到各个分类空间的概率，取概率最大的作为分类。
序列标注问题
序列标注问题的重点在于学习序列位置之间的关系，然后解码出最大概率标签路径，比如有K个标签，当输入序列长度为m时，那么就有Km条概率路径，序列标注问题是要从Km条概率路径中寻找到概率最大的那条路径。NLP中常见的任务，如分词，词性标注，命名体识别都属于序列标注问题。
HMM
之前已经说了HMM是生成模型，它引入了一阶马尔科夫假设：当前状态只与上一状态有关。结合这两点可以得到联合概率
p(x1...xm,s1...sn)=∏tp(st|st?1)p(xt|st)
p(st|st?1)称为状态间的转移概率，p(xt|st)称为发射概率（由隐状态发射成显状态的概率）
由图可知HMM是一个有向图。
HMM的解码部分是求解：argmaxs1...sm p(x1...xm,s1...sm), 通常采用 Viterbi 算法解码
HMM的特点
HMM有两个独立性假设：
- 观测序列之间是独立的 (A B 独立 有P(A, B) = P(A)P(B)，所以计算联合概率的时候才能用叠乘 )
- 当前状态仅依赖于先前的状态
MEMM
Max Entropy Markov Model 最大熵马尔可夫模型，在最大熵的基础上引入了一阶马尔科夫假设。 MEMM 属于判别式模型，它要学习条件概率
p(s1...sm|x1...xm)=∏i=1mp(si|s1...si?1,x1...xm)
由于引入了一阶马尔科夫假设，故当前状态仅于前一状态有关
p(s1...sm|x1...xm)=∏i=1mp(si|si?1,x1...xm)
而最大熵模型是对数线性模型，由上文可得到 MEMM 的条件概率表达式
p(si|si?1,x1...xm;w)=exp(w??(x1...xm,i,si?1,si))∑s′?Sexp(w??(x1...xm,i,si?1,s′))=1Zexp(w??(x1...xm,i,si?1,si))
?(x1...xm,i,si?1,s′) 是一个特征函数，其中有：
- i 代表当前被标记的位置
- s 先前的状态
- s′ 当前的状态
故有
p(s1...sm|x1...xm)=∏i=1mp(si|si?1,x1...xm)=∏i=1mexp(w??(x1...xm,i,si?1,si))Z(1)=exp(∑iw??(x1...xm,i,si?1,si))Z
MEMM 解码用的是极大似然估计 argmaxs1...sm p(s1...sm|x1...xm)，为了好理解我做了一步步简化
argmaxs1...sm p(s1...sm|x1...xm)=argmaxs1...sm ∏i=1mp(si|si?1,x1...xm)=argmaxs1...sm p(si|si?1,x1...xm)=argmaxs1...smexp(w??(x1...xm,i,si?1,si))∑s′?Sexp(w??(x1...xm,i,si?1,s′))=argmaxs1...sm exp(w??(x1...xm,i,si?1,si))(2)=argmaxs1...sm w??(x1...xm,i,si?1,si)
也即是编码等价于求解公式(2)，通常用 viterbi 算法求解，如果不采用 viterbi 求解它的算法复杂度是 O(Km) ，采用了 viterbi 算法可以降到 O(mK2)，(K 为隐状态数目, m为观测序列长度)
如图，MEMM也是有向图模型。
MEMM的优点
克服了 HMM 输出独立性问题，通过引入特征函数使得模型比 HMM “拥有更多信息” （上下文信息），而且最大熵则从全局角度来建模，它“保留尽可能多的不确定性，在没有更多的信息时，不擅自做假设”。
举个例子：
HMM中，观测节点 xi 仅依赖隐藏状态节点 yi （没有上下文信息）,也就意味着我的观测节点只依赖当前时刻的隐藏状态。但在更多的实际场景下，观测序列是需要很多的特征来刻画的，比如说，在做 NER 时，标注 yi 不仅跟当前状态 xi 相关，而且还跟前后标注 yj,(j≠i) 相关，比如字母大小写、词性等等。
MEMM的缺点
标签偏置(labeling bias)问题，由于MEMM的当前状态只与当前观测以及上一状态有关，导致隐状态中有更少转移的状态拥有的转移概率普遍偏高，简单的说就是MEMM中概率最大路径更容易出现在转移少的状态中。
举个例子：
用 Viterbi 算法解码 MEMM，可见状态 1 倾向于转换到状态 2，同时状态 2 倾向于保留在状态 2，按照这个规律去猜可能会产生最优转换路径就是在状态 1 和 2 之间转换。 解码过程细节（需要会 Viterbi 算法这个前提）：
1 2 3 4 |
P(1->1->1->1) = 0.4 x 0.45 x 0.5 = 0.09 P(2->2->2->2) = 0.2 X 0.3 X 0.3 = 0.018 P(1->2->1->2) = 0.6 X 0.2 X 0.5 = 0.06 P(1->1->2->2) = 0.4 X 0.55 X 0.3 = 0.066 |
但是得到的最优的状态转换路径却是 1->1->1->1，不存在 1 和 2 之间的转换，为什么呢？因为状态 2 可以转换的状态比状态 1 要多（因为转换出去的概率和为1 ，如果转换的状态多了，那么各个转换出去状态分摊的概率可能就小了），从而使转移概率降低, 即 MEMM 倾向于选择拥有更少转移的状态。本例中虽然 1 -> 2 的转换概率比较高，但是 2 -> 1 的就不一定了。
为什么出现这个问题呢？因为 MEMM 当前的状态仅与上一状态和当前的观测状态有关，没有考虑到更多的观测信息，因而可能会存在偏置。
公式 (1) 中 ∑ 求和的作用在概率中是归一化，但是这里归一化放在了指数内部，管这叫局部归一化。 问题来了，viterbi 求解过程，是用动态规划的状态转移公式，因为是局部归一化，所以 MEMM 的 viterbi 的状态转移会出现局部最优的情况，导致 dp 无法正确的递归到全局的最优。
如何解决这个问题呢？引入全局化特征可以解决标签偏置问题，下文的 CRF 其实就在MEMM上加入全局化特征从而解决标签偏置问题。
CRF
Conditional Random Forest条件随机场，这里主要讲解线性链（linear-chain）,这里不会牵扯太多概率图的东西（因为我也不会啊:<）还是从对数线性模型出发。 首先要明确的一点是CRF也属于判别模型，所以和MEMM一样需要进行条件概率建模
p(s1...sm|x1...xm)
CRF 也和 MEMM 一样做了一阶马尔科夫假设，即当前状态只与上一状态有关，但是区别在于CRF的特征采用了全局特征，它把观测序列当做整体来看所以它的特征函数是全局的，它的特征函数为：
φ(x1...xm,s1...sm)=∑j=1m?(x1...xm,i,si?1,si)
其中 ? 和 MEMM 的特征函数是一致的，和 MEMM 的区别是，MEMM 的当前状态与上一状态和当前的输入有关，而 CRF 当前的状态与上一状态和所有的输入有关，这可以缓解标签偏置的问题。接下来的步骤和MEMM差不多了，只是特征函数变为了φ，为了连续性在此再走一遍流程。
CRF的条件概率表达式为：
p(si|si?1,x1...xm;w)=exp(w?φ(x1...xm,i,si?1,si))∑s′?Sexp(w?φ(x1...xm,i,si?1,s′))
对所有状态由：
p(s1...sm|x1...xm)=∏i=1mp(si|si?1,x1...xm)=∏i=1mexp(w?φ(x1...xm,i,si?1,si))Z=exp(∑iw?φ(x1...xm,i,si?1,si))Z(3)=exp(∑i∑jwj??j(x1...xm,i,si?1,si))Z
CRF的解码部分是计算 argmaxs1...sm p(s1...sm|x1...xm)，一步步进行简化
argmaxs1...sm p(s1...sm|x1...xm)=argmaxs1...sm∏i=1mp(si|si?1,x1...xm)=argmaxs1...sm p(si|si?1,x1...xm)=argmaxs1...smexp(w?φ(x1...xm,i,si?1,si))∑s′?Sexp(w?φ(x1...xm,i,si?1,s′))=argmaxs1...sm exp(w?φ(x1...xm,i,si?1,si))=argmaxs1...sm w?φ(x1...xm,i,si?1,si)(4)=argmaxs1...sm ∑jmw??(x1...xm,i,si?1,si)
对比一下(2)和(3)可知道 CRF 和 MEMM 的区别。和 MEMM 一样，一般采用 viterbi 算法来进行解码。
由图可知线性链CRF是无向图模型。
CRF的优点
克服了HMM的输出独立性假设问题以及MEMM的标注偏置问题。
后记
HMM、MEMM属于有向图模型，贝叶斯网络一般属于有向图。而CRF属于马尔科夫网络属于无向图。所以它们本身属于统计概率图（PGM）的一部分，要想真正弄懂之间的原理和区别还需要系统的学习PGM。
另，由Refrence中可知本文大量引用了Michael Collins教授的tutorial,MC的tutorial通俗易懂，但是有些地方做了简化，如果不详细说明有时也会一头雾水，所以本文主要做了些翻译和修补工作。
Refrence
[1] ~mcollins/hmms-spring2013.pdf