干货|理解机器学习必学算法条件随机场CRF

点击上方“AI遇见机器学习”，选择“星标”公众号
重磅干货，第一时间送达

一、概率图模型

概率图模型又叫做马尔可夫随机场，是一个可以用无线图表示的联合概率分布。在这个无线图中结点表示随机变量，边表示两个随机变量依赖关系。给定一个概率分布及其无向图，首先定义无向图表示随机变量之间存在的马尔可夫性。

成对马尔可夫性

成对马尔可夫性是指概率无向图中任意两个结点 u 和 v ，如果这两个结点没有边向量，则该这两个结点对应的随机变量在给定其余结点（对应其余随机变量）的前提下条件独立。

局部马尔可夫性

局部马尔可夫性是指概率无向图中的任一结点 v，W表示与之相连结点的集合，O表示没有与v直接连接的结点的集合，v与O在给定结点集合W的前提下独立。

全局马尔可夫性

全局马尔可夫性是指对于结点集

和

，如果存在结点集

使得两个结点集

A B

没有边相连，则结点集

对应的随机变量与结点集

对应的随机变量是独立的。

因此概率无向图的定义为，设有联合概率分布P(Y)，如果一个无向图的结点表示随机变量，边表示随机变量之间的依赖关系，如果联合概率分布P(Y)满足成对马尔可夫性、局部马尔可夫性、全局马尔可夫性，则该无向图为概率无向图模型，又称条件随机场。概率无向图最大的特点就是易于因子分解。

团与最大团

在无向图，一个团表示的是一个结点集，并且结点集任意两个结点有边相连。如果一个团不可再增加一个结点，则该团为最大团。{Y1，Y2}{Y1，Y3}{Y2，Y3}{Y2，Y4}

如上图所示，上面可以分解为多个团{Y1,Y2} {Y1,Y3} {Y2,Y3} {Y2,Y4} {Y3,Y4} ，最大团有两个{Y1,Y2,Y3} {Y2,Y3,Y4} 。

将概率无向图模型的联合概率分布表示为其最大团上随机变量的函数的乘积形式的操作，称为概率无向图模型的因式分解。定义Yc是最大团C对应的随机变量，因此联合概率分布可以写为

其中，Z是规范化因子

为势函数，且严格正。

二、条件随机场

简介

条件随机场是一种判别式无向图模型，即条件随机场是对条件概率分布建模（隐马尔可夫和马尔可夫随机场都是对联合概率分布建模，是生成模型）。条件随机场对输入的观测序列

和标记序列

建立条件概率模型

。

例子

假设你有许多小明同学一天内不同时段的照片，从小明提裤子起床到脱裤子睡觉各个时间段都有（小明是照片控！）。现在的任务是对这些照片进行分类。比如有的照片是吃饭，那就给它打上吃饭的标签；有的照片是跑步时拍的，那就打上跑步的标签；有的照片是开会时拍的，那就打上开会的标签。问题来了，你准备怎么干？

一个简单直观的办法就是，不管这些照片之间的时间顺序，想办法训练出一个多元分类器。就是用一些打好标签的照片作为训练数据，训练出一个模型，直接根据照片的特征来分类。例如，如果照片是早上6:00拍的，且画面是黑暗的，那就给它打上睡觉的标签;如果照片上有车，那就给它打上开车的标签。

但实际上，由于我们忽略了这些照片之间的时间顺序这一重要信息，我们的分类器会有缺陷的。举个例子，假如有一张小明闭着嘴的照片，怎么分类？显然难以直接判断，需要参考闭嘴之前的照片，如果之前的照片显示小明在吃饭，那这个闭嘴的照片很可能是小明在咀嚼食物准备下咽，可以给它打上吃饭的标签；如果之前的照片显示小明在唱歌，那这个闭嘴的照片很可能是小明唱歌瞬间的抓拍，可以给它打上唱歌的标签。

所以，为了让我们的分类器能够有更好的表现，在为一张照片分类时，我们必须将与它相邻的照片的标签信息考虑进来。（本例子摘自《如何轻松愉快地理解条件随机场》—milter）

为了更好的介绍条件随机场，在这里仅介绍线性链条件随机场。

如上图所示，线性链条件随机场与隐马尔可夫模型的结构很相似，但隐马尔可夫模型仅仅只考虑先前状态对当前的影响，而条件随机场考虑了属于变量X以及前后状态的影响。由于满足马尔可夫性，以下等式成立。

给定一个句子：我爱学习。现在要把该句子划分为若干个词语。分词的过程相当于给某个字打上标签，即分别是：词头(Begin)、词中(Middle)、词尾(End)、单字成词(Single)，简称B,M,E,S。显然每一字对应的标签和上下文是有关的，（不可能连续有两个词头的出现等等），因此要将前后字的标签考虑进来。这里条件随机场的预测问题同样是使用维特比算法，计算一条最优的路径。

条件随机场参数化形式

现在定义P(Y|X)为线性链条件随机场

其中Z(x)为归一化因子，tk和si为特征函数，μ λ是对应的权重。tk是依赖于边的特征函数，称为转移特征，si是定义在结点上的特征函数，称为状态特征。转移特征和状态特征只有满足条件时取值为1，否则取值为0。为了简便起见，用统一的符号表示特征函数和权值。设转移特征有K1个，状态特征K2个，K = K1+K2。