干货 | 条件随机场详解之模型篇
干货 | 条件随机场详解之模型篇
昱良 机器学习算法与Python学习
条件随机场部分分为两篇讲解，今天这一篇主要简单的讲述什么是条件随机场以及在这之前的概率无向图模型，下一次将从优化算法的层面上论述如何优化这个问题。（理解本篇文章需要对数理统计和图论有一定的基础）
条件随机场（Conditional Random Fields），简称 CRF，是一种判别式的概率图模型。条件随机场是在给定随机变量X条件下，随机变量Y的马尔科夫随机场。原则上，条件随机场的图模型布局是可以任意给定的，但比较常用的是定义在线性链上的特殊的条件随机场，称为线性链条件随机场。因为其不论在训练、推论或是解码上，都存在效率较高的算法可供演算。
CRF最早由John D. Lafferty等在2001年提出，结合了最大熵模型和隐马尔可夫模型（生成式模型）的特点，是一种概率无向图模型。它常用于序列标注、词性标注，语义分析等自然语言处理问题，比如可以用于分词（Segmentation）、词性标注（Part of Speech）和命名实体识别（Named Entity Recognition）任务。一般序列分类问题常常采用隐马尔可夫模型（HMM），但隐马尔可夫模型中存在两个假设：输出独立性假设和马尔可夫性假设。其中，输出独立性假设要求序列数据严格相互独立才能保证推导的正确性，而事实上大多数序列数据不能被表示成一系列独立事件。而条件随机场则使用一种概率图模型，具有表达长距离依赖性和交叠性特征的能力，能够较好地解决标注（分类）偏置等问题的优点，而且所有特征可以进行全局归一化，能够求得全局的最优解。
概率无向图模型
由于条件随机场是在给定一组输入随机变量条件下，另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔科夫随机场。因此在本节首先介绍马尔科夫随机场，即概率无向图模型。
概率无向图模型定义
图是由结点及连接结点的边组成的集合。结点和边分别记作v和e，结点和边的集合分别记作V和E，图记作G=（V,E）。无向图是指图的边是没有方向的。
概率图模型是由图表示的概率分布。设有联合概率分布P(Y)，Y∈Y是一组随机变量。由无向图G=（V,E）表示概率分布P(Y)，即在图G中，结点v∈V表示一个随机变量Yv，Y=(Yv)v∈V;边e∈E表示随机变量之间的概率依赖关系。
给定一个联合概率分布P(Y)和表示它的无向图G.首先定义无向图表示的随机变量之间存在的成对马尔科夫性、局部马尔科夫兴和全句马尔科夫性。概率无向图模型的定义：设有联合概率分布P(Y)，由无向图G=(V,E)表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布P(Y)满足成对、局部或全局马尔科夫性，就称此联合概率分布为概率无向图模型或马尔科夫随机场模型。
概率无向图模型的因子分解
团与最大团： 无向图G中 任何两个结点均有边连接的结点子集称为团。若C是无向图G的一个团，并且不能再加进任何一个G的结点使其称为一个更大的团，则称此C为最大团。
将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解。给定概率 模型，舍弃无向图为G，C表示G上的最大团，Yc表示C对应的随机变量。那么概率无向图模型的联合概率分布P(Y)可写作图中所有最大团上的函数的乘积形式，即
其中，Z是规范化因子，由下式给出：
规范化因子保证P(Y)构成了一个概率分布。这里要求势函数是严格正的，通常定义为指数函数：
条件随机场
一般的条件随机场定义：设X与Y是随机变量，P(X|Y)是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由 G=(V,E)表示的马尔科夫随机场，即
P(Yv|X,Yw,w≠v) = P(Yv|Yw,w－v)，对任意的节点v成立，则称条件概率分布P(Y|X)为条件随机场。式中w—v表示在图G中与结点v有变连接的所有节点w，w≠v表示节点v以外的所有结点，Yv，Yu与Yw为结点v,u,与w对应的随机变量。在定义中并没有要求X与Y具有相同的结构。但是在实际中，一般假设X和Y具有相同的图结构。
下面主要介绍一种特殊的条件随机场模型，即无向图为如图1所示的线性链的情况。即G=(V={1,2,…,n}, E={(i,i+1)}), i=1,2,…,n-1.在此情况下，X=(X1,X2,…,Xn) , Y=(Y1,Y2,…,Yn),最大团是相邻两个结点的集合。线性链条件随机场有下面的定义。
线性链条件随机场：
设X=(X1,X2,…,Xn),Y=(Y1,Y2,…,Yn)均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔科夫性P(Yi|X,Y1,…,Yi-1,Yi+1,…,Yn)=P(Yi|X,Yi-1,Yi+1), i=1,2,…n,(在i=1和n时只考虑单边)。则称P(Y|X)为线性链条件随机场。在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。
参数化形式
设P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率具有如下的形式：
其中
式中，tk和sl是特征函数，λk和μl是对应的权值。Z(X)是规范因子，求和是在所有可能的输出序列上进行的。上面的两个式子是线性链条件随机场模型的基本形式，表示给定输入序列x，对输出序列y预测的条件率。tk是定义在边上的特征函数，称为转移特征。依赖于当前和前一个位置。sl是定义在结点上的特征函数，称为状态特征，依赖于当前位置。tk和sl都依赖于位置，是局部特征函数。通常，特征函数tk和sl取值为1和0；当满足特征条件时取值为1，否则为0.条件随机场完全由特征函数tk，sl和对应的权值λk和μl确定。线性链条件随机场也是对数线性模型。
条件随机场的对数模型可以做相应的简化，以使它的形式看起来比较简洁。设有K1个转移特征，K2个状态特征，K=K1+K2，记
然后对转移与状态特征在各个位置i求和，记作：
用wk表示特征fk(y,x)的权值，即
于是条件随机场可以表示为:
其中
若以w表示权值向量，即
F(y,x)表示全局特征向量,即
则，条件随机场可以写成向量w与F(y,x)的内积形式：
其中，
为了以后计算方便，下面将给出条件随机场的矩阵形式。引入特殊的起点和y0=start，yn-1=stop，这时pw(y|x)可以通过矩阵形式表示。对于观测序列x的每一个位置i=1,2,…,n+1，定义一个m阶矩阵（m是标记yi取值的个数）。
这样，给定观测序列x，标记序列y的非规范化概率可以通过n+1个矩阵的乘积表示，于是，条件概率Pw(y|x)是
其中