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