条件随机场模型和训练方法条件随机场模型是由[7]首先提出的，这个模型在自然语言处理和生物信息学中得到了广泛的应用，这一章我们简要介绍了条件随机场模型极其训练方法。

更详尽的介绍参见[2],[3],[4]。

2.1训练的定义考虑这样一个问题：给定一个模型，这个模型有很多参数，如何找出模型的最佳参数？训练是解决这个问题的一个方法。

给定一组训练数据和一组模型，按照某个衡量标准，选出最符合训练数据的模型，这个过程叫做训练。

只有选取的训练数据符合现实情况时，选择的模型才能符合现实，因此训练数据的选取是一个重要的问题。

衡量模型的标准有许多个，下面介绍两个衡量标准。

2.1.1极大似然估计(x;)P ω是随机变量X 的概率密度分布函数，ω是其中的参数。

12{x ,x ,...,x }n 是一组随机变量12,,...,X n X X 的观测值，12,,...,X n X X 是一组独立同分布的随机变量，分布与X 相同。

极大似然估计：12'arg max (x ,x ,...,x ;)arg max (x ;)n i iP P ωωωωω==∏ 极大似然估计是一个非常自然的想法，就是选择使训练数据发生概率最大的参数，但极大似然估计的一个缺点是对训练数据的假设太强，不容易满足。

下面介绍的条件似然估计可以克服这个缺点。

2.1.2条件似然估计假设每一个训练数据由两部分组成，形如(x,y)；其中x 是已知的观测值，y 的概率分布由x 和ω唯一确定。

为了判断y 的取值，我们只需要刻画条件概率分布(y |x;)ωP 。

我们不用联合概率分布(y,x;)ωP 的原因是x 的取值是已知的，我们不需要刻画x 的概率分布，何况我们很难准确的刻画x 的概率分布。

假设给定一组训练集：1122{(x ,y ),(x ,y ),...,(x ,y )}n n 。

条件似然估计：1212'arg max (y ,y ,...,y |x ,x ,...,x ;)arg max (y |x ;)n n i i iP P ωωωωω==∏ 这里所做的假设是y i 的概率分布仅由x i 和ω决定，即：111(y |x ,...,x ,y ,...,y ;)(y |x ;)i n i i i P P ωω-=下文中将要介绍的条件随机场模型的训练方法就是根据这个思想。

例6.（英文单词划分问题）在一些排版软件中，为了保持美观，有时会需要对一些长的单词按照音节划分、断行，因此需要考虑如何对单词按音节进行划分这个问题。

我们可以把英文单词按照音节分为一些小的部分，比如说单词hyphenation 可以划分为hy-phen-a-tion 。

在这个问题中x 所在的集合是所有单词组成的集合，y 的取值集合是所有0、1序列组成的集合。

y 与单词长度相同，0表示对应字母后面不断开，1表示对应字母后面断开，默认y 的最后一位是0。

例如x=hyphenation 对应的y 是010*******。

显然Y 的取值完全由x 和模型参数决定，因此这个问题可以采用条件似然估计来训练模型。

2.2条件随机场模型x 是给定的观察值，y 的分布由x 和参数ω唯一确定，y 的结构可以由无向图G 表出，y 中的每个随机变量可以取值的集合称为标签集，例如在单词划分问题中，标签集为{0，1}。

x 可以称为观测序列，y 可以称为标记序列。

条件随机场模型是指所有条件概率分布可以表示成如下形式的模型：exp((x,y))(y |x;)(x,)j j jF P Z ωωω=∑ (2.1)其中(x,y)j F 称为特征函数，特征函数分为两类：一类是定义在边上的特征函数，表示为 ,e 遍历图G 中所有边，一类是定义在节点上的特征函数，表示为 , n 遍历图G 中所有节点，两类特征函数可以统一的写为 ；(x,)Z ω称为划分函数， 。

图12. 线性条件随机场模型例7. 单词划分问题中y 的结构如图12所示，这个问题可以用条件随机场模型求解。

下面给出这个问题的一组特征函数模板：2i 1i i 1i I (x x "",y 0,y 1)--=== 3i 2i 1i i 1i I (x x x "",y 0,y 1)---=== 4i 3i 2i 1i i 1i I (x x x x "",y 0,y 1)----===其中代表任意字母，I 为指示函数。

有些单词组合容易组成一个音节，比如说edge edge [1][2]e e e F (x,y)f (y ,y ,x,e)=∑(,)(,,)=∑node noden n F x y f y x n i[1]i[2](x,y)(y ,y ,x,i)=∑j j i F f '(x,)exp((x,y'))ωω=∑∑j j y j Z F“re”、“non”、“tion”，因此这些字母组合对应的特征函数：2i 1i i 1i I (x x "re",y 0,y 1)--===3i 2i 1i i 1i I (x x x "non",y 0,y 1)---===4i 3i 2i 1i i 1i I (x x x x "tion",y 0,y 1)----===的权重比较高。

在这个问题中，由于y 的结构是线形的，我们称这类条件随机场模型为线性条件随机场模型。

2.3条件随机场模型的三个基本问题我们这一节考虑条件随机场模型的三个基本问题，第一个问题是如何对模型进行推断，第二个问题是如何求边际概率，第三个问题是如何训练模型。

条件随机场模型可以看作是无向图模型的一种变形，它与无向图模型的差别在于条件随机场模型中x 是给定的，因此我们可以用1.4节介绍的无向图模型的算法来求解这个问题。

定义： 。

对于推理和求边际概率问题，我们是在一个固定x 上进行操作，因此我们把i i 1i g (y ,y ,x)-简记为i i 1i g (y ,y )-。

由式(2.1)可以看出，x 不同，只会使(x,y)j F 取值不同，因此我们可以把x 的取值信息完全可以通过(x,y)j F 表出，然后不考虑节点x 。

对于不同的x ，我们只需更新(x,y)j F 的取值，如图13所示。

图13. x 的取值信息完全包含在特征函数中对于因式图非树情况，我们可以采用带圈置信传播算法求解模型。

2.3.1 推断下面我们通过对无向图模型的max-sum 算法导出对线性条件随机场模型的Viterbi 算法：i i 1i j i 1i j g (y ,y ,x)f (y ,y ,x,i)--=∑y 的结构如图12所示，我们以n y 为根节点，由公式(1.9)(1.10)我们可以得到：1(v)max[(u)g (u,v)]g y y g k uk k k k μμ→→-=+ 111(u)(u)y g g y k k k k μμ→→---=将上面两式合并后得：11(v)max[(u)g (u,v)]g y y g k uk k k k μμ→→--=+ 初始条件为 这个算法就是著名的Viterbi 算法。

Viterbi 算法的计算复杂性：假设标签集合有m 个元素，模型有n 个节点，由1.4.2中的分析知算法的时间复杂性为2O(n )m ⋅。

2.3.2边际概率对线性（树状）条件随机场模型的sum-product 算法：由公式(1.7)(1.8)我们可以得到：1(v)[(u)exp (u,v)]g y y g k uk k k k g μμ→→-=∑，111(u)(u)yg g y k k k k μμ→→---= 1111(u)[(v)exp (u,v)]g y y g k v k k k k g μμ→→++++=∑，1121(v)(v)yg g y k k k k μμ→→++++= 将上面式子合并化简后得： 11(v)[(u)exp (u,v)]g y g y k uk k k k g μμ→→--=∑1121(u)[(v)exp (u,v)]g y g y k vk k k k g μμ→→++++=∑初始条件为1(v)exp (START,)g y k k g v μ→=采用记号：(k,v)(v)g y k k αμ→=，1(u,k)(v)g y k k βμ→+=。

我们有：(k,v)[(k 1,u)exp (u,v)]k ug αα=-∑1(u,k)[(v,k 1)exp (u,v)]k vg ββ+=+∑(x,)(k,u)(u,k)uZ ωαβ=∑(k,u)(u,k)(y u |x;)(x,)k P Z αβωω== 1(v)(START,)μ→=g y k k g v)图14. 计算线性条件随机场模型的边际分布2.3.3条件随机场模型的训练训练数据集：1122{(f(x ),y ),(f(x ),y ),...,(f(x ),y )}n n ，其中f(x )i 表示第i 个训练数据的所有特征函数，x i 的信息完全包含在f(x )i 中，因此我们可以用f(x )i 代替x i 。

为了避免数值下溢，我们计算log-likelihood:log (y |x ;)((y ,x )log (x ,)k k k w k k i i k ik L P w F Z θω==-∑∑∏(y|x )(y,x )exp((y,x ))((y ,x ))(x ,)((y ,x )(y,x )P(y |x ))((y ,x )[F (y,x )])k k k j m m y m k k w j k kj k k k k j j k y k k k j p j kF F L F w Z F F F E ωω∂=-∂=-=-∑∑∑∑∑∑ 对线性条件随机场模型，我们有：(y|x )(y|x )1(y|x )1,'[F (y,x )][(y ,y ,x ,i)][f (y ,y ,x ,i)](i 1,)f (y,y',x ,i)exp((y,y',x ,i))(y',i)/Z(x,)k k k k k p j p j i i ik p j i i ik k j j j i y y jE E f E y f αωβω++===-∑∑∑∑∑其中第三个等号利用了:1P(y y,y y'|x;)(i 1,)exp((y,y',x ,i))(y',i)/Z(x,)k i i j j jy f ωαωβω-===-∑我们可以把条件随机场的训练问题看成一个无约束最优化问题，目标函数是w L ，计算w L ∇后，可以利用L-BFGS 算法进行优化，关于L-BFGS 算法介绍参见[8]。