一、背景

1. 概述

如上所示，分类问题分为硬分类和软分类两种。硬分类问题指的是分类结果非此即彼的模型，包括SVM、PLA、LDA等。软分类问题将概率作为分类的依据，分为概率判别模型和概率生成模型两种。其中概率判别模型对概率 进行建模，代表算法有逻辑回归（Logistic Regression，LR）。LR的损失函数为交叉熵损失函数，这类模型也叫做对数线性模型，一般地，又叫做最大熵模型（Max Entropy Model），这类模型和指数族分布的概率假设是一致的。朴素贝叶斯算法（Naive Bayes）为概率生成模型的一种，如果将其单元素的条件独立性推广到一系列隐变量，由此得到的模型就是动态模型，如隐马尔可夫模型（Hidden Markov Model，HMM），从概率意义上，HMM也可以看做高斯混合模型（Gaussian Mixture Model，GMM）在时序上的推广。

2. HMM vs. MEMM

如果将最大熵模型和HMM相结合，就得到了最大熵马尔可夫模型（Max Entropy Markov Model）。MEMM的概率图如下：

                                                MEMM

这个概率图就是将HMM的概率图观测变量和隐变量的边反向，这样的话HMM中的观测独立假设就不成立了，也因此 的影响包括局部和全局两种。HMM的观测独立假设是一个很强的假设，如果我们有一个文本样本，那么观测独立假设就意味着样本之中的每个词之间没有任何关系，这显然是不合理的，因此打破这个假设是更加合理的。

HMM的概率图如下：

                                              HMM

HMM是一个概率生成模型，其建模对象 是，可以将HMM的看做是由图中画虚线的部分所组成的，结合其两个假设，可以写出其概率公式为：

MEMM的缺陷是其必须满足局部的概率归一化（也就是Label Bias Problem），对于这个问题，我们将 之间的箭头转为直线从而得到无向图（线性链条件随机场），这样就只要满足全局归一化了（破坏了齐次马尔可夫假设）。

3. 标注偏置问题

标注偏置问题（Label Bias Problem）是MEMM存在的一个局限性，这也是决定它不流行的主要原因，条件随机场（Conditional Random Field，CRF）通过使用无向图解决了这个问题。

• 根因

                                                  MEMM

对于MEMM，上面的概率图由于存在齐次马尔可夫假设可以认为是由一个个方框中的部分组成的，因此有概率公式如下：

对于每一个方框中的组件，我们可以看做一个函数，叫做mass score，这个函数对外是有一定能量的，但这个mass score同时必须是一个概率 ，因此被归一化了，叫做局部归一化，这就是导致标注偏置问题的根本原因所在。

而CRF采用无向图的结构，其天然地满足全局归一化，也就打破了齐次马尔可夫假设，从而解决了标注偏置问题。

• 现象

局部归一化造成了标注偏置问题，这一问题造成的现象可以通过以下例子来解释。

                                                  现象

对于上图中训练得到的MEMM模型，节点表示时刻的状态 ，边表示观测 。可以看出，上述状态从1到2，2到3，4到5，5到3全部都只有一个状态转移的选择，这也就导致无论观测 是多少， 都不关心而只会向确定的一个状态进行转移。上述状况显然表明训练得到的模型是不合理的，举个更具体的例子，如果对“小明 爱 中国”进行词性标注，模型会根据“小明”和“爱”的词性直接标注“中国”的词性，根本不关心观测“中国”本身。

上述MEMM模型是根据训练数据训练得到的，比如在训练数据中一共有3个rob，1个rib，这样的训练数据得到的模型概率如下图所示：

 

                                                现象

可以看出由于局部归一化从1到2，2到3，4到5，5到3的状态转移概率全部都是1，这样会造成求解Decoding问题时的标注偏置问题，也就是在观测为rib的条件下，求解最可能的标准序列 时会得到以下结果：

二、条件随机场

1. 条件随机场的概率密度函数

CRF中条件代表这是一个判别式模型，随机场表示其是一个无向图模型。CRF的概率图如下：

                                                           CRF

对于无向图的因子分解，可以参考以前的文章中的讲解：概率图模型-表示|机器学习推导系列（十）。

2. 概率密度函数的向量形式

为了更方便地使用概率密度函数进行后续求导等一系列操作，我们需要对上述概率密度函数进行整理和简化，从而取得其向量的表示形式。

三、参数估计和推断

1. 条件随机场要解决的问题

Inference：

2. 求解边缘概率

这个方法类似于HMM中的前向后向算法，其实也就是概率图模型中精确推断的变量消除法（信念传播），相关参考链接为：概率图模型-推断|机器学习推导系列（十一）。

3. 参数估计

对于概率密度函数的以下形式：

这里可以看出这个概率密度函数就是一个指数族分布，其中参数向量就是上面的 ，充分统计量也就是 。有关指数族分布的讲解可以参考这个链接：指数族分布|机器学习推导系列（九）。

CRF的参数估计问题就是在似然上做梯度上升来求得最优解，而我们用来求导的概率密度函数使用以下形式：

按照极大似然估计的思路，写出公式如下：

这个结论和指数族分布|机器学习推导系列（九）中第三部分的推导过程类似，这里我们就不再重复。

对于上述式子，我们可以调整加和符号的位置：

4. Decoding问题

Decoding问题和HMM中的Viterbi算法类似，同样采样动态规划的思想⼀层⼀层求解最大值，求解方法很类似，这里就不再重复，参考链接：隐马尔可夫模型|机器学习推导系列（十七），更具体的可以参考李航老师的《统计学习方法》中关于CRF的讲解。