条件随机场是一个马尔科夫网.首先来看一下形如下图所示的马尔科夫网:
回顾马尔科夫网的联合概率计算公式,设与
分别为两个集合:
其中将结果转化为概率:
因为上图马尔科夫网的特殊形式,极大团只有和
,所以还可以进一步简化上述公式:
马尔科夫网是生成式模型,对联合概率进行建模,而条件随机场是辨别式模型,试图对
进行建模.
根据条件概率公式:
我们可以很容易将转化为
:
在马尔科夫网中为了归一化,所以
是所有与
相关的因子总和,而在归一化
时X为已知常量,所以只需累加
:
由于条件随机场定义了Y关于X的一个条件分布,因此可以将其视为一个部分有向图:
既然条件随机场是一个特殊的马尔科夫网,那么也可以用对数线性模型表示:
式中和
是特征函数,
和
是对应的权值,
和
分别为转移特征与状态特征个数.
假设我们在某一节点我们有个局部特征函数和
个节点特征函数,总共有
个特征函数。我们用一个特征函数
来统一表示如下:
对在各个序列位置求和得到:
同时我们也统一对应的权重系数
如下:
这样,我们的linear-CRF的参数化形式简化为:
其中,为规范化因子:
如果将上两式中的与
的用向量表示,即:
则linear-CRF的参数化形式简化为内积形式如下:
我们定义一个的矩阵
,
为
所有可能的状态的取值个数。
定义如下:
我们引入起点和终点标记, 这样,标记序列
的非规范化概率可以通过
个矩阵元素的乘积得到,即:
其中为规范化因子。
当我第一次看到条件随机场使用前向后向算法的时候,我感到非常的亲切,因为在学习隐马尔可夫模型的时候,花了很多时间理解前向后向算法.隐马尔可夫模型是因为有隐变量,所以使用前向后向算法推导概率,而条件随机场虽然没有隐变量,但是却难以直接求解,所以这里也使用前向后向算法.
计算条件概率可以使用如下递推公式:
在起点处,我们定义:
假设我们可能的标记总数是, 则
的取值就有
个,我们用
表示这
个值组成的前向向量如下:
同时用矩阵表示由
形成的
阶矩阵:
这样递推公式可以用矩阵乘积表示:
同样的。我们定义表示序列位置
的标记是
时,在位置
之后的从
到
的部分标记序列的非规范化概率。
这样,我们很容易得到序列位置的标记是
时,在位置
之后的部分标记序列的非规范化概率
的递推公式:
在终点处,我们定义:
如果用向量表示,则有:
由于规范化因子的表达式是:
也可以用向量来表示:
其中,是
维全1向量。
有了前向后向概率的定义和计算方法,我们就很容易计算序列位置的标记是
时的条件概率
:
也容易计算序列位置的标记是
,位置
的标记是
时的条件概率
:
在使用梯度下降法求解模型参数之前,我们需要定义我们的优化函数,一般极大化条件分布的对数似然函数如下:
其中为经验分布,可以从先验知识和训练集样本中得到,这点和最大熵模型类似。为了使用梯度下降法,我们现在极小化
如下:
对求导可以得到:
有了的导数表达书,就可以用梯度下降法来迭代求解最优的
了。注意在迭代过程中,每次更新
后,需要同步更新
,以用于下一次迭代的梯度计算。
条件随机场与隐马尔可夫模型一样使用维特比算法解码.
维特比算法就是将动态规划的一个特例,用来解决上述篱笆网络最优路径问题.现在每个时刻有3种状态,我们每个时刻要取1种状态,有很多种取法:
篱笆网络中每个节点的概率可以根据模型计算出来,现在的问题是如何找出概率最大的那条路径,显然不能用贪心算法,而枚举所有路径复杂度太高,这个问题可以用动态规划算法来解决.
假设我们知道了最优路径,那么最优路径一定会经过第i层的节点,如果求出到第i层所有节点的最优路径,那么全局最优路径一定在这些局部最优路径中.
所以动态规划的求解过程:
我们的第一个局部状态定义为,表示在位置
标记
各个可能取值(1,2…m)对应的非规范化概率的最大值。之所以用非规范化概率是,规范化因子
不影响最大值的比较。根据
的定义,我们递推在位置
标记
的表达式为:
和HMM的维特比算法类似,我们需要用另一个局部状态来记录使
达到最大的位置
的标记取值,这个值用来最终回溯最优解,
的递推表达式为:
参考:
Daphne Koller<概率图模型>