条件随机场在机器学习中的应用与推导（第二十一篇）

时间：11-16 神话故事提交错误

大家好，今天小编来为大家解答条件随机场在机器学习中的应用与推导（第二十一篇）这个问题，很多人还不知道，现在让我们一起来看看吧！

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

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

MEMM的概率图是反转HMM概率图的观测变量和潜在变量的边缘。在这种情况下，HMM 中的观察独立性假设不再有效。因此，对的影响包括局部影响和全局影响。 HMM 的观察独立性假设是一个强假设。如果我们有一个文本样本，那么观察独立性假设意味着样本中的每个单词之间没有关系。这显然不合理，所以打破这个假设。是比较合理的。

HMM的概率图如下：

HMMHMM是概率生成模型，其建模对象为。 HMM可以看作是由图中虚线绘制的部分组成。结合其两个假设，其概率公式可写为：

MEMM的概率图中，、、是头对头结构。它们不是独立的，因此打破了观察独立性假设。的角色分为全局和本地。 MEMM是概率判别模型，建模对象为。其概率图可以认为是由图中虚线绘制的部分组成，因此其概率公式为：

MEMM的缺陷在于它必须满足局部概率归一化（即标签偏差问题）。对于这个问题，我们将之间的箭头转换成直线，得到无向图（线性链条件随机场）。这样，只满足全局归一化（破坏齐次马尔可夫假设）。

标签偏差问题（Label Bias Problem）标签偏差问题（Label Bias Problem）是MEMM的一个局限性，这也是它不受欢迎的主要原因。条件随机场（CRF）通过使用无向图解决了这个问题。

根本原因MEMM 对于MEMM，由于齐次马尔可夫假设，上面的概率图可以被认为是由框中的部分组成。因此，概率公式如下：

对于框中的每个组件，我们可以将其视为称为质量分数的函数。这个函数对外来有一定的能量，但是这个质量分数也必然是一个概率，所以对其进行归一化，称为Local归一化，这就是标签偏差问题的根本原因。

CRF采用无向图结构，自然满足全局归一化，从而打破了齐次马尔可夫假设，从而解决了标签偏差问题。

现象局部标准化导致注释偏差问题。由这个问题引起的现象可以用下面的例子来解释。

现象：对于上图中训练的MEMM模型，节点代表时间的状态，边代表观测值。可以看出，上述状态1到2、2到3、4到5、5到3都只有一种状态转换选择，这意味着无论有多少个观测值，都没有不在乎。仅转移特定状态。上述情况显然说明训练出来的模型是不合理的。更具体的例子，如果“小明爱中国”被标注了词性，那么模型会根据“小明”和“小明”的词性直接标注“中国”的词性。爱”。根本不关心观察“中国”本身。

上述MEMM模型是根据训练数据进行训练的。例如，训练数据中有3 块罗布和1 根肋骨。由这样的训练数据得到的模型概率如下图所示：

现象可以看到，由于局部归一化，从1到2、2到3、4到5、5到3的状态转移概率均为1，这在解决解码问题时会产生标注偏差问题，即，在观测值为rib 的情况下，求解最可能的标准序列时，会得到如下结果：

换句话说，解的结果是，这是由于概率造成的。

二、条件随机场

条件随机场CRF的概率密度函数中的条件代表它是一个判别模型，随机场代表它是一个无向图模型。 CRF的概率图如下：

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

简单地说，无向图的概率分布可以分解为图中所有最大团的势函数的乘积。给定一个概率无向图模型，是无向图模型上的最大派，那么的联合概率分布可以写为：

是归一化因子，通常使用势函数（这里称为能量函数），也就是说：

为了方便起见，这里将写成只是为了简化形式，不同最大组之间使用相同的功能。在CRF中，还有：：

为了方便起见，在之前添加了节点。因此，对于CRF的线性链来说，最大簇总共有个。

对于函数，我们可以将其写成三部分：

其中，和称为状态函数，称为传递函数。由于每个在中出现了两次，我们还需要进行归一化，所以我们可以省略每个中的这一项，这意味着我们使用是：

t},x_{1:T})=Delta _{y_{t},x_{1:T}}+Delta _{y_{t-1},y_{t},x_{1:T}}" />我们定义和如下：上式中和是给定的特征函数（或者指数函数），和是参数。特征函数的取值是人为给定的，取值只能是或，称为转移特征，称为状态特征，只有在满足特征条件时特征函数取值才为，否则为，比如我们可以规定：总而言之，的概率密度函数可以表示为：概率密度函数的向量形式为了更方便地使用概率密度函数进行后续求导等一系列操作，我们需要对上述概率密度函数进行整理和简化，从而取得其向量的表示形式。对于归一化因子，其只和有关，而与无关，这是因为被积分积掉了，因此可以写成以下形式：接着我们定义以下向量：则此时我们将概率密度函数写作以下向量相乘的形式：此时式子中还剩下一个关于的连加号，而与有关的只有和，于是我们考虑可以将这个连加号放到括号里面：接着继续定义如下两个向量：于是最终可以将概率密度函数写成如下形式：

三、参数估计和推断

条件随机场要解决的问题Learning：也就是参数估计问题，对于给定的训练数据，均是维向量，需要估计参数。 Inference： ①边缘概率：求； ②条件概率：一般在生成模型中较为关注，条件随机场不关注； ③MAP推断：也就是Decoding问题，即。求解边缘概率求解边缘概率的问题就是给定概率分布，求解。对于，其概率分布为：因此我们要求解的概率分布为：假设的取值集合为。上式直接计算的复杂度非常地高，这是由于求和的复杂度是，求积的复杂度是，整体复杂度也就是。因此我们的解决方案是调整求和符号的位置，从而降低复杂度，事实上也就是前面讲过的变量消除法。我们将时刻左右两边的势函数连同积分号拆成两部分和：对于，我们按照变量消除法的思路来调整加和符号的位置：按照从右往左积分的方式可以降低计算的复杂度，也就是一个一个地进行积分，并且上式为了看起来方便省略了括号。这里的是为了表达方便才加上去的一个随机变量，可以认为它的值只能取这一个值。接下来我们将上式写成递推式的形式，我们定义：则递推式为：类似地，对的积分方式为：同样地这里也省略一系列括号，顺序也是从右往左进行积分。我们定义：递推式为：因此，最终的结论也就是：这个方法类似于HMM中的前向后向算法，其实也就是概率图模型中精确推断的变量消除法（信念传播），相关参考链接为：概率图模型-推断|机器学习推导系列（十一）。参数估计对于概率密度函数的以下形式：这里可以看出这个概率密度函数就是一个指数族分布，其中参数向量就是上面的，充分统计量也就是。有关指数族分布的讲解可以参考这个链接：指数族分布|机器学习推导系列（九）。 CRF的参数估计问题就是在似然上做梯度上升来求得最优解，而我们用来求导的概率密度函数使用以下形式：按照极大似然估计的思路，写出公式如下：然后需要对和求导，以为例。等号右边的部分对求导较为简单。从指数族分布的角度来看，就是配分函数，也就是log配分函数。套用指数族分布|机器学习推导系列（九）中第三部分的结论，我们可以知道：类似的对于的一部分进行求导我们可以知道：这个结论和指数族分布|机器学习推导系列（九）中第三部分的推导过程类似，这里我们就不再重复。对于上述式子，我们可以调整加和符号的位置：对于概率，这显然是一个边缘概率，是可以利用上一节的这种前向后向算法来求解这个边缘概率，然后就能得到这个导数。对于边缘概率，上一节的方法是将到的势函数记作，将到的势函数记作。类似的，在求解时就可以将到部分的势函数记作，将到的势函数记作。总而言之，求解的过程是类似的。因此，最终我们得到的log似然对的导数为：然后按照梯度上升的方式来更新参数即可，的处理也类似：

关于条件随机场在机器学习中的应用与推导（第二十一篇），的介绍到此结束，希望对大家有所帮助。