一、背景介绍

1、背景算法介绍

HMM，隐马尔可夫模型，是生成模型，基于两个假设，一个是齐次一阶马尔可夫假设，一个是观测独立假设。一阶是指y2只与y1有关系，y3只与y2有关系。在给定y2的时候，y3与y1无关；齐次是指对于正常的马氏链，y1到y2，y2到y3的转移概率是相同的。可以用图中公式数学化表达。

MEMM，最大熵马尔可夫模型，是判别模型，它打破了观测独立假设，在词性标注等应用上更加合理，而且判别模型是对条件概率建模对于标注问题来说也更直接。它的一个缺点是label bias problem，根本原因在于局部归一化。（条件概率分布的熵越小，越不考虑观测变量——可以看下图的例子，从1->2，从4->5只有一条路径，根本不会关注observation是什么。）

CRF，条件随机场，也是判别模型，跟MEMM相比，有向变无向，CRF是全局归一化，克服了label bias problem问题。我们这里讲的主要是线性链条件随机场，它的一个重要应用就是标注序列问题，比如词性标注，命名实体识别等。

2、背景知识介绍

在讲CRF之前，首先介绍一下涉及到的相关知识。概率无向图模型、团与最大团、概率无向图模型的因子分解。

成对马尔可夫性是指，对于任意结点u，v是与u没有边连接的结点，O是除了u、v的其它所有结点，那么在给定Yo的情况下，Yu和Yv是相互独立的。局部马尔可夫性是指，v是任意结点，W是与v有边连接的结点，O是除了v、W的其它所有结点，那么在给定Yw的条件下，Yv和Yw是相互独立的。全局马尔可夫性是指，结点集合A、B是被结点集合C分开的任意集合，那么在给定YC的条件下，YA和YB是相互独立的。

概率无向图模型的联合概率分布可以表示为最大团上随机变量的函数的乘积形式。其中C是最大团，YC是其对应的随机变量，Z是规范化因子，目的是保证P(Y)是概率分布，𝜓𝐶是最大团上的势函数，是严格正的，通常是指数函数。乘积是在无向图所有的最大团上进行的。

二、CRF算法概述

1、条件随机场的定义与形式

X和Y是随机变量，如果对任意结点v，给定X和除v以外的所有结点时Yv的概率分布等于给定X和与v有边连接的所有结点时Yv的概率分布，则条件概率分布P(Y|X)是条件随机场。线性链条件随机场就是X和Y都是线性链表示的随机变量序列。也就是说给定Yi-1和Yi+1之后，Yi和其他的结点是相互独立的。

参数化形式利用了概率无向图模型的因子分解，在条件随机场中y1y2是一个最大团，y2y3是一个最大团，依次类推，那么P(Y|X)就是这些最大团的势函数的乘积。势函数用tk和sl表示。因为加了exp()，所以乘积变成了求和。tk是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置。sl是定义在节点上的特征函数，称为状态特征，依赖于当前位置。tk和sl都依赖于位置，是局部特征函数。通常，特征函数tk和sl的取值为1/0，当满足特征条件时取值为1，否则为0。条件随机场完全由特征函数tk，sl和对应的权值确定。

2、要解决的问题

对于条件随机场，需要解决的问题，主要有以上几个，一个是参数估计的学习问题，前面提到的特征函数tk和sl都是人为设定的，而这些特征函数的权值是需要根据训练数据学习得到的，也就是让N个训练样本出现的概率尽可能的大；一个是推断问题，推断包括求边缘概率，也就是给定X的情况下，求yt为某个值的概率；还包括求最大后验概率，也就是decoding问题，求概率最大的编码序列。下面对这几个问题逐一解决。

（1）参数估计

条件随机场模型实际上是定义在时序数据上的对数线性模型，学习方法是极大似然估计，具体的优化实现算法有改进的迭代尺度法IIS，梯度下降法和拟牛顿法。

（2）边缘概率计算问题

（3）Decoding问题——维特比算法

首先输入时模型的特征向量，也就是特征函数集合(f1(y,x), f2(y,x),…,fk(y,x))，即K1个tk和K2个sl，以及特征函数的权值向量w，待标注的观测序列x。每个位置有m种标记可能。首先初始化，求位置1的各个标记j=1,2…m的非规范化概率，然后递推求位置i的各个标记l=1,2,…m的非规范化概率的最大值，并且记录取得最大值的标记值。直到最后i=n终止，得到最终位置的非规范化概率最大值，和最优路径的终点，最后回溯返回最优路径。

下面是维特比算法的一个示例。

每个位置有0-6种标记选择。给出的待标序列x是 "start 我去北京 end"，e是状态特征，t是转移特征。