竹子建站官网,免费开源网站,公司网站招聘模板,制作免费网站CRF基本介绍
在机器学习中#xff0c;建模线性序列结构的方法#xff0c;除了HMM算法#xff0c;另一个重要的模型就是CRF。HMM为了降低模型复杂性#xff0c;对观测变量做了独立假设(即隐状态之间有相关性#xff0c;而观测变量之间没有相关性)#xff0c;这在某种程度…CRF基本介绍
在机器学习中建模线性序列结构的方法除了HMM算法另一个重要的模型就是CRF。HMM为了降低模型复杂性对观测变量做了独立假设(即隐状态之间有相关性而观测变量之间没有相关性)这在某种程度上损害了模型的准确性CRF弥补了这个缺陷它同样假设类别变量之间有相关性但没有对观测变量之间做出任何假设(即可能有相关性也可能没有相关性)。
CRF除了和HMM形成对比前者是判别式模型后者是生成式模型另一方面CRF还可看成是对最大熵模型的扩展即它是一个结构化学习模型而不是单个位置的分类模型。CRF如何被因子化CRF公式如何推导如何建立最大熵模型和CRF的公式联系以及如何得到CRF图表示结构是本文的几个重点。本文还会提到一些算法刚开始被用于HMM稍作修改也能用于线性链CRF比如前向-后向算法、维特比算法。另外需要指出用于线性链CRF的训练和推理算法不能直接用于任意结构的CRF。
背景知识条件熵(Conditional entropy)
信息论中条件熵用于量化描述随机变量Y所需的信息量在另一个随机变量X已知的情况下写作H(Y|X)具体形式如下 公式1
其中和表示随机变量X和Y的样本集。注意这里有可能出现可以认为等于0因为
直觉上可以把看成是某个函数的期望即其中是条件概率被定义为
它是公式1中负号放到求和里面后的右半部分。函数可看成当给定变量时为描述变量需要的额外信息量。因此通过计算所有的数据对的期望值条件熵就能测量出要想通过变量解码出变量平均意义上需要多少信息。
现在进一步要问以上具体怎么来的首先假设Y的概率密度函数为那么Y的熵就是具体为
公式2
其中是当Y取的互信息。因此已知X为某个取值x时求Y的熵根据条件期望即代入公式2有
公式3
注意表示对求关于所有不同x取值的平均。换言之是对关于每个x的加权求和其中权重就是概率具体如下
公式4
上式第1个等号根据定义第2个等号使用了公式3第3个等号调整将两个合并简化第4个等号利用贝叶斯公式。公式4最后得到公式1。
一些基本属性当且仅当Y完全被X控制。当且仅当Y和X是两个独立的随机变量。
条件熵的链式规则即当X的熵已知那么Y的条件熵可通过联合熵减去得到。它的推导过程如下
公式5
上式第1步来自公式4第2步把log拆成相减的两项第3步把拆成两项第4步对第一项套用熵的公式得到对第二项消去y变量对y求和第5步继续套用熵的公式得到
把公式5扩展到多个随机变量得到
公式6
可以发现公式6和概率中的链式法则类似只不过把乘法变为了加法。
条件熵的贝叶斯规则证明如下因为有以及别忘了得证。特别的当Y条件独立于Z当给定X那么有
最大熵模型(Maximum Entropy Model)
最大熵模型是一个条件概率模型它基于最大熵原则意思是当我们不具备对一个概率分布的完整信息时唯一的无偏估计假设就是均匀分布。在该假设下最恰当的概率分布就是在给定约束下的最大化熵的分布。根据公式1对于条件模型对应的条件熵为
公式一
其中Z X ×Y 包含了所有可能的输入x和输出y。注意Z不仅包括所有训练数据的样本也包括所有可能出现的组合。最大熵模型的基本原理是找到使得条件熵取得最大值但仍然符合训练数据中的约束信息。目标函数也叫主问题即primal problem如下
公式二
其中P是满足训练数据约束条件的所有模型的集合。
我们假设训练样本体现为特征。现在定义二值特征函数(其中)它既依赖输入变量x也依赖类别变量y一种可能的函数形式如下
公式三
每个特征的期望值是从经验分布估计得到而经验分布是通过对训练集中不同值的频率进行简单计数得到具体表达式如下
公式四
注意所有可能的数据对都被统计在内。考虑到所有不被包含在训练集中的数据对的经验概率为0公式四可以改写为
公式五
其中N是训练集的大小即。因此可通过对训练数据()统计为1的频率计算得到当然要除以训练集大小N。
类似于经验分布的特征期望值(即公式四)模型分布的特征期望值为
公式六
注意由于所有可能的取值非常大可能无法简单计算。因此可对重写
公式七
以上把联合概率变为了条件概率乘积。进一步我们把替换为经验分布就得到了的近似值
公式八
类比公式五上式可进一步转化为
公式九
注意上式只有出现在训练集中的x被考虑()以及所有的y取值都被考虑()。很多应用中y的取值只有很少几个可能值因此对所有y求和是可行的可以被高效计算。
公式二假设最优模型和训练数据一致这意味着每个特征在经验分布上的期望值和在特定模型分布上的期望值等价即有
公式十
另一个约束是对于条件概率恒有
公式十一
在特定约束下的最优化问题可以用拉格朗日乘子法解决对每个约束引入得到如下拉格朗日函数
公式十二
求解过程如下
首先与公式八的期望值近似求解类似公式一的的近似求解为
公式十三
上式对的偏导为
公式十四
说明把看成变量把看成常量相当于对xlogx的形式求导数比较简单。
公式十二的第二部分即前m个约束对的偏导为 公式十五
以上分别将和的表达式即公式八和公式四代入注意减号右边不包含因此偏导为0而左边是的线性函数只需保留其余系数即可。
公式十二的第三部分更简单它对的偏导就是系数因此完整的偏导如下
公式十六
令上式为0来求解得到 移动右边第一项到左边得到 等式两边除以得到 把上式的1移到右边得到 把log消除得到的表达式
公式十七
考虑到公式十一有个概率加和约束
公式十八
我们把公式十七代入公式十八得到 等式两边除以左边第一项得到
公式十九
把公式十九重新代入公式十七得到
公式二十
对上式简单改写就得到著名的最大熵模型
公式二十一
其中就是公式二十的分母即
公式二十二
条件随机场(Conditional Random Fields)
条件随机场(即CRF)可看成最大熵模型的序列版本(sequence version)这意味着它们都是判别式模型。CRF与HMM对比除了后者是生成式模型之外二者另一个重要的不同点是CRF不再局限于线性序列结构而可以是任意结构当然线性结构是最常见的。
CRF基本原则
CRF是一种计算的概率模型其中输出向量对应的输入向量(也叫做观测值)。要知道在无向图中概率分布可以用称为最大团的非负函数的乘积表示其中每个因子包含来自不同团的节点这意味着条件独立的节点不会出现在同一个因子中作为一种无向图CRF推导的起点一般是以下公式
(式1)
其中是CRF结构图中对应于不同最大团的因子每个因子对应一个随机变量的势函数其中势函数一般由观测值的不同特征组合而成。当然势函数可以是任意的函数甚至可以不必是概率函数因此势函数乘积的归一化必不可少这是为了保证最终得到有意义的概率值。这是通过归一化因子Z来实现的。Z的表达式为
(式2)
在参数学习(或模型训练)中对Z的计算是非常重要且具有挑战性的因为这需要对所有可能的变量进行求和。需要指出最大熵模型(公式二十一、二十二)也符合式1和式2其中非负势函数取指数函数而取观测值的不同特征的加权求和。
CRF的条件概率可进行如下推导
(式3)
其中第一步是贝叶斯公式第二步把展开成对求和的形式故需引入变量从而变为联合概率第三步对分子和分母分别套用式1其中随机变量用输入变量和输出变量分开表示。
当然也可以直接把式1表示成如下形式
(式4)
其中归一化因子的表达式可参考式3的第三步的分母为
(式5)
注意到目前为止都是CRF的通用形式而不只表示线性结构。
线性链CRF(Linear-chain CRFs)
作为CRF的特例线性链CRF把输出变量建模成序列数据我们把式4写成如下形式
(式6)
其中也作相应调整
(式7)
我们假设每个因子符合如下形式(和最大熵模型类似但更为复杂)
(式8)
假设观测序列的长度为n1即有n1个y节点那么因子数就是n(因为相邻的两个位置变量和被合并为一个因子)那么线性链CRF可重写为
(式9)
上式通过结合式6和式8把对指数函数的累乘改写成对其肩上数字的累加得到。与最大熵模型最大的区别是式9比公式二十一多了一层对j的累加这是因为CRF不再只是预测单标签而是要预测标签序列。在式9中j指定了输入序列的位置下标。而权重完全不依赖位置下标j。
类似的为了归一化条件概率到[0,1]区间对应的分母为
(式10)
上式是对所有可能的标签序列求和目的是最终得到可行的概率值。
对式9可以进行三种变形分别是
1) 将代表序列位置的j求和移动到exp前面如下所示
(式11)
2) 将代表不同特征的i求和移动到exp前面如下所示
(式12)
对于式12因子不再在序列中流动构造而是在特征中流动构造。
3) 同时将i和j的求和移动到exp前面如下所示
(式13)
需要指出式11的因子一般基于最大团而式12和式13不需要满足这个要求。一般来说因子化时如果不是用最大团会导致某种程度的不准确因为并不是所有的依赖都被正确考虑到有时会导致冗余计算。后面会基于式11进行分析。
和HMM的三个基本问题相似线性链CRF也有两个基本问题分别是
1. 给定观测值和CRF模型M求最有可能的标签序列
2. 给定标签序列和观测序列求CRF模型M的参数使得最大
其中问题1是CRF最常见的应用而问题2是如何训练来调整模型参数尤其是特征权重。注意在判别式模型中概率不需要建模而HMM中是需要的。
训练过程
在训练集上进行最大似然估计目标函数为
(式14)
为了避免过拟合一般要加上惩罚项注意这个技术细节也能用在最大熵模型中。
推导过程如下
(式15)
第1步对式14加上惩罚项第2步将log的分子分母转化成相减的形式并把第一项的log和exp抵消掉但保留第二项第3步将第一项不必要的括号省略并记做A将第二项记做B其中log的内容记为将第三项(即惩罚项)记做C。注意A项、B项、C项都包含特征权重
A项、B项、C项对权重(或)的偏导可以分开计算。其中A项的偏导计算很简单如下
(式16)
B项的偏导计算过程较为复杂如下
(式17)
其中第一步是对求偏导利用链式求导法则第二步继续求对的偏导利用链式求导法则以及exp指数的导数是它自己第三步将移动到第二层求和以内并与exp项一起合并为具体见式9第四步就是最终结果。
C项的偏导计算很简单如下
(式18)
注意式15所示的似然函数是凹函数这是因为第一项关于(或)是线性的见式16第二项由于log是凹函数而内部的是线性的不改变凹凸性所以还是凹函数第三项是开口向下的二次函数也是凹函数所以整体还是凹函数。
式16(A项的偏导)从含义上其实就是特征的经验分布的期望值(可类比公式五)具体如下
(式19)
式17(B项的偏导)从含义上是模型分布的期望值(可类比公式九)具体如下
(式20)
因此对权重(或)的偏导可看成
(式21)
式19和式20分别与最大熵模型的公式五和公式九对应其中最大区别是因子的消失而这一点对于通过近似推导找最大值是不相关的。需要注意线性链CRF中直接计算是不可行的因为存在大量可能的序列标注而在最大熵模型中这点是可行的因为输出变量y的不同值比较少。CRF中输出序列存在巨大的组合复杂性因此需要一个DP算法也就是HMM中的前向-后向算法只需要简单的修改即可。
首先定义一个函数用于将输入位置为j的单个状态s映射到位置为j1的下一个状态的集合再定义一个逆函数将所有可能的下一个状态的集合映射回s。特殊状态和分别表示序列的开始和结束。前向和后向分别用和表示可看成线性链CRF中的消息传递递推公式如下 和式8的势函数定义一致特征被定义在特定状态(如和)之上例如 函数将消息从链头传递到链尾相反。二者初始化如下 有了和的初始值和递推关系就能非常高效的计算模型分布的期望值具体如下
(式26)
其中下划线部分可看成在计算状态序列的所有组合构成的势函数。一个可视化的网格图如下
(图1)
其中每一列表示一个序列位置j的多个状态s每一行表示不同序列位置所有可能的消息传递路径被描绘出来。每个和一次迭代计算后被保存因此只需要计算一次。归一化因子的公式为
(式27)
前向-后向算法时间复杂度为即与序列长度线性相关而与状态数是二次相关。
推理过程
推理是为了找到给定观测序列对应的最有可能的状态序列与HMM的解码类似这里不是为了找到每个单独最有可能的状态而是为了最大化预测正确的状态数。所以这里同样要用维特比算法(Viterbi algorithm)。维特比算法和前向-后向算法类似只不过将求和改为最大化。
定义一个函数表示在位置j以状态s结束的序列概率的最高分即有
(式28)
它的递推关系表示为
(式29)
用函数用来跟踪j和s的值整个算法流程如下
1. 初始化。将起始状态到所有可能的第一个状态s的函数值设为对应的因子值并将起始状态保存到函数中具体如下
(式30)
2. 迭代过程。下一步的值通过当前值计算得到具体如下
(式31)
3. 终止结果 4. 路径回溯利用重新计算最优路径找到状态序列
(式34)
仔细观察前3步非常像前向-后向算法。总的来说维特比算法先在网格中填充最优值然后第4步在网格中读取最优路径。
任意结构CRF(Arbitrarily structured CRFs)
任意结构CRF指的是树或者网格结构从线性链结构CRF转到任意结构CRF需要丢掉一些团构建的约束条件因此需要更通用的训练和推理算法。比如有文献提出了Skip Chain结构如下图b
(图2)
可以看到b图和a图的区别是相邻的位置可能没有连接而不相邻的节点可能有连接有点像深度学习的残差网络(也许比它更早出现)。
对于线性链CRF(图2a)它的势函数来自以下团模板(clique templates)
(式35)
这个单一的模板意味着线性链CRF只能连接两个相邻的位置j和j-1.
对于跳跃链CRF(图2b)它的势函数来自两个团模板
(式36)
可以看到C1模板和式35一样而C2模板的两个节点和可以不相邻即它们都只要满足在全域范围内即可当然也可以另外规定b是a的整数倍等等。注意C1和C2模板是或的关系即只需满足一个就要建立连接。比如有5个节点的跳跃链CRF输入序列根据C1模板2和3、3和4、4和5、5和6都要建立连接而根据C2模板(即b是a的整数倍)就有2和4、2和6、3和6建立连接那么就得到如下结构图和因子图
(图3)
在训练和推理时序列结构(无论HMM还是线性链CRF)都采用前向-后向算法和维特比算法即通过往链上的两个方向发送消息来实现。而对于树结构的CRF甚至任意结构CRF一般采用最大和(max-sum)算法和sum-product算法。具体见《PRML》的8.4节。
参考资料 条件熵维基百科。
《Classical Probabilistic Models and Conditional Random Fields》2007 年。
《模式识别与机器学习》2006 年。
《统计学习方法》2012年。
