1294人阅读
数据挖掘/机器学习（11）
条件随机场模型是Lafferty于2001年，在最大熵模型和隐马尔科夫模型的基础上，提出的一种判别式概率无向图学习模型，是一种用于标注和切分有序数据的条件概率模型；
条件随机场模型作为一个整句联合标定的判别式概率模型，同时具有很强的特征融入能力，是目前解决自然语言序列标注问题最好的统计模型之一。条件随机场的缺点是训练的时间比较长。
条件随机场定义
设G=（V，E）是一个无向图，Y=(Yv)，，Y表示图中顶点的结合。如果在观察变量X的条件下，在图G中随机变量Yv服从马尔科夫属性，即：表示在图G中，v，w是邻居，那么（X,Y）就表示一个条件随机场。
即它是在给定需要标记的观察序列 X的条件下计算整个标记序列 Y的联合概率分布，而不是在给定当前状态条件下定义下一个状态的分布。公式如下所示：
HMM.vs MEMM .vs CRF
隐马尔可夫模型中存在两个假设：输出独立性假设和马尔可夫性假设。其中，输出独立性假设要求序列数据严格相互独立才能保证推导的正确性，而事实上大多数序列数据不能被表示成一系列独立事件。而条件随机场则使用一种概率图模型，条件随机场没有隐马尔可夫模型那样严格的独立性假设条件，因而可以容纳任意的上下文信息，可以灵活地设计特征。同时，条件随机场具有表达长距离依赖性和交叠性特征的能力，而且所有特征可以进行全局归一化，能够求得全局的最优解，还克服了最大熵马尔可夫模型标记偏置的缺点。
下图是用图的形式描述HMM（左），MEMM（中），链式的CRF（右）表示序列时的区别。注（空心圆表示此变量是不用于描述模型的）。其中HMM中，Yi只与Yi-1有关，而Xi输出只与Yi有关。在MEMM中，Yi 是由Xi和Yi-1确定的，在CRF中，确定某个Yi，它会考虑整个Y及Xi的。
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：16521次
排名：千里之外
原创：13篇
(1)(5)(5)(2)(2)(6)(1)利用条件随机场模型进行中文分词-爱编程
利用条件随机场模型进行中文分词
&&&&& 中文分词的方法非常多，基于词库是最基本的，但是当前各大互联网公司基本上不会仅仅依赖于词库的分词，一般以机器学习的分词为主，词库分词的方式为辅。在很久以前，我提过利用，条件随机场其实是隐马尔科夫模型的一次升级版本，网上有很多关于条件随机场模型的分词，但是基本上很难看懂，也许是论文的缘故，那些作者习惯了一上来就是一堆复杂的公式，我也看了一些，获取有些作者自己都没搞懂，就弄了一篇论文。本文从实践的角度，提供一种基于条件随机场模型的中文分词解决方案。
&&&&& 第一步：准备语料库。
&&&&& 首先，你必须得准备一个已经分好词的语料库，用于机器学习，如下图所示：
&&&&& 如果你没有，可以在这里。
&&&&& 第二步：初步语料库特征学习
&&&&& 和隐马尔科夫模型一样，条件随机场也是基于学习字的状态来进行状态分析的，对于一个字来说，它有4个状态，分别是：词头(Begin)、词中(Middle)、词尾(End)、单字成词(Single)，简称B,M,E,S。
&&&&& 因此需要把第一步的语料库，分析出每一个字的状态，例如：&收益&需要改进为：&收|B 益|E&, 通过将语料库的每一个分好的词，添加其状态信息，如下图所示：
&&&&& 当然，如果你比较懒，也没有关系，我这里提供好已经分析完毕的数据，可以在。
&&&&& 第三步：特征学习
&&&&& 有了第二步的初步学习，第三步就相对容易多了，特征学习是整个过程中非常重要的部分，在进行特征学习之前，必须弄清楚一个问题，要学习哪些特征？如下：
&&&&& 1. 这一个字一共在语料库中出现的次数是多少？例如&我&字一共出现了256次。
&&&&& 2. 这一个字，出现为词头（B）、词中（M）、词尾（E）、单字成词（S）的概率是多少？即为在256出现&我&字的时候，&我&作为词头的概率是多少，词中的概率是多少，依次类推。
&&&&& 3. 这一个字，当为词头（B）的时候，它转移到下一个词的状态概率是多少？每一个字都有属于自己的状态，但是这个字的后面一个字，也有属于自己的状态，那么当前字的状态，到下一个字的状态（或许是B、M、E、S之一）的概率是多少。例&我&字，当&我&的状态为B的时候，后面跟的字中，状态为B的为0个，状态为M的为10个，状态为E的为20个，状态为S的0个。依次统计&我&的状态为M、E、S的时候，下一字的状态。此过程俗称：状态转移概率计算。此项会形成一个4X4的矩阵。
&&&&& 截至前面三个特征学习，也许你会感觉与隐马尔科夫模型的方式没有太大区别，但是从理论上研究，条件随机场的准确率一定是高于隐马尔科夫模型的。是因为条件随机场会学习上下文关系，也就是多计算了，当一个字出现的时候，它的前一个字是什么，后一个字是什么，这个概率是多少，也就是我们第四个特征学习。
&&&& 4. 这一个字出现的时候，后面字出现的是什么，概率为多少？例如当状态为B的&我&，下一个字是&们&的概率为67.9%，例如状态为S的&我&，上一个字是&的&的概率为21%，下一个字是&爱&的概率为17.8%等等，记录每一个字在四种状态下上下文关系，是非常重要的一步。这一步中，我们仅仅记录了上一个字和下一个字的上下文关系，条件允许的情况下，我们可以记录上两个字和下两个字的上下文关系。
&&&& 利用代码，就是如下示例：
* Feature for each word.
* @author liufanping
private static class Feature {
* The State transition matrix
private Double[][]
* The observation sequence transition matrix
private Double[]
* The predecessor State
private TreeMap&Integer, Double& preS
* The next status
private TreeMap&Integer, Double& nextS
* Total count.
private int
&&&& 上面代码中需要注意两个事项：
&&&& 1. 每一个字都会有这样一个特征类，可以利用一个哈希表，key存字，value存其特征。
&&&& 2. 记录前后上下文的preStatus ，key是上一个字和当前字状态的组合，nextStatus，key是下一个字和当前字状态的组合，例如当前字是&我&，当前字的状态是B，下一个字可能是&们&，在nextStatus中，key就是&们_B&的哈希值，value均是出现这种情况的概率。
&&&& 我相信从语料库中学习这四个特征，应该不是一件很难的事情，自己根据描述完善代码即可。
&&&& 第四步：开始分词
&&&& 既然特征已经训练好了，怎么去给一个句子分词呢？例如用户输入&希腊的经济结构较特殊&，怎么就可以进行分词了呢？其实很简单，下面就是数学计算了。
&&&& 1. 将&希腊的经济结构较特殊&变成字符数组。即&希&、&腊&、&的&、&经&、&济&、&结&、&构&、&较&、&特&、&殊&。
&&&& 2. 取出每一个字对应特征（第三步产生的内容）。
&&&& 现在每一个字的特征以及取出来了，后面怎么办呢？我们先分析下，我们其实就是在给每一个字确定它是B、M、E、S四个状态中的哪一种，因此可以绘制一个矩阵。
&&&& 到这里，既然是矩阵，而且是求矩阵里面的一个路径，那么很容易想到维特比算法。到这里，我们只需要计算出&希&字在B、M、E、S的状态值，后面就游刃而解。
&&&& 我们设定矩阵中的值为S， S[字][当前状态]=MAX(P[上一个字任何状态][当前状态]*S[上一个字][任何一个状态])+W[前(后)一个字_当前状态][当前字]+R[当前状态概率]& (备注：R是特征二，P是特征三，W前是特征四的上文部分，W后是特征四的下文部分)
&&&& 例如&腊&字，在为状态B上的值为：S[腊][B]=MAX(P[B][B]*S[希][B],P[M][B]*S[希][M],P[E][B]*S[希][E],P[S][B]*S[希][S])+W前[希_B][腊]+W后[的_B][腊]+R[B]，同理可以计算S[腊][M],S[腊][E],S[腊][S]。
&&&& 依次类推，可以计算出后面其它字的情况。由于&希&字出现在首字，不存在其它状态转移到其状态的概率，因此，S[希][B]=W前[_B][希]+W后[腊_B][希]+R[B]，依次计算出&希&字其它值。
&&&& 上面过程，希望反复用研究下，研究透后，你会发现很简单，通过计算会得到如下矩阵：
&&& 看到这里，你似乎已经看到分词的结果了，在矩阵中所有值的后面，都有一个小括号，里面存放的是路径，也就是这个值是通过上一个的哪一个值过来的（因为有计算max的过程，就会有路径选择），记录下来之后，以便于路径回溯。
&&& 当得到这个矩阵之后，我们只需要将&殊&中的最大值取出，即为1.1867对应状态是End，来自上一字的状态0，也就是&特&字的Begin，再次查看&特&字来自于上一个字&较&的Single。因此，判别状态如下
&&& &希/B 腊/E 的/S 经/B 济/E 结/B 构/E 较/S 特/B 殊/E&
&&& 翻译成分词结果就是&希腊 的 经济 结构 较 特殊&。
&&& 完成的实现分词过程，如果你对此项有点模糊，建议看下维特比算法。
&&& 写到最后，我也要感谢您能够看到最后，这是比较简单的一种利用条件随机场进行分词的方式，复杂的，可以在这个基础上进行优化升级。
&&& 诚挚的谢意！
版权所有 爱编程 (C) Copyright 2012. . All Rights Reserved.
闽ICP备号-3
微信扫一扫关注爱编程，每天为您推送一篇经典技术文章。2289人阅读
机器学习（3）
条件随机场（CRF）是给定一组输入随机变量的条件下另一组输出随机变量的条件概率分布。
1.概念引入
概率图模型
概率图模型是由图表示的概率分布。无向图G=(V,E)表示概率分布P(Y)，节点v∈V表示一个随机变量YV；边e∈E表示随机变量之间的概率依存关系。
成对马尔科夫性
u和v是G中任意两个没有边连接的节点，其他所有节点为O。成对马尔科夫性是指给定随机变量组YO的条件下随机变量Yu和Yv是条件独立的，即
P(Yu,Yv|YO)=P(Yu|YO)P(Yv|YO)
局部马尔科夫性
v是G中任意一点，W是与v有边连接的所有节点，O是v,W以外的其他所有节点。局部马尔科夫性是指给定YW的条件下Yv与YO是独立的，即
P(Yv,YO|YW)=P(Yv|YW)P(YO|YW)
全局马尔科夫性
A,B是G中被C分开的任意节点集合。全局马尔科夫性是指给定YC条件下YA和YB是条件独立的，即
P(YA,YB|YC)=P(YA|YC)P(YB|YC)
概率无向图模型
如果联合概率P(Y)满足成对、局部或者全局马尔科夫性，就称该联合概率分布为无向图模型，或者马尔科夫随机场。最大特点：易于因子分解。
团与最大团
无向图G中任何两个节点都有边连接的节点子集称为团（clique）。若不能再加进一个节点使团更大，称该团为最大团。
无向图模型的因子分解（factorization）
C为G上最大团，P(Y)可以写作图中所有最大团C上的函数ΨC(YC)的乘积形式，即
P(Y)=1Z∏cΨC(YC)
其中，Z是归一化因子，Z=∑r∏cΨC(YC)。ΨC(YC)称为势函数，通常定义为指数函数：
ΨC(YC)=exp{-E(YC)}
Hammersley-Clifford定理
概率无向图模型的联合概率分布P(Y)可以表示为：
P(Y)=1Z∏cΨC(YC)
Z=∑r∏cΨC(YC)
条件随机场
条件随机场是给定随机变量X的条件下，随机变量Y的马尔科夫随机场。主要介绍定义在线性链想的线性链条件随机场（用于标注等问题）
P(Yv|X,Yw,w≠v)=P(Yv|X,Yw,w连v)对于任何节点v都成立，成条件概率分布P(Y|X)为条件随机场。w连v表示所有与v相连的节点w，w≠v表示所有除v外的节点w。也就是说，对于点v来说，只有与它相连的点会对它产生影响。
线性链条件随机场
设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)
相当于是说，线性的模型只考虑两边的节点对它的影响，因为只有两边的节点与它相邻。
1.3 条件随机场的参数化形式
线性链条件随机场的参数化形式
P(Y|X)为线性链条件随机场，则在X取x的条件下，Y取y的条件概率：
P(y|x)=1Z(x)exp(∑i,kλktk(yi-1,yi,x,i)+∑i,lμlsl(yi,x,i))
其中Z(x)是归一化因子tk和sl 是特征函数 λk和μl 是对应的权值。tk 是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置。sl 是定义在节点上的特征函数，称为状态特征。特征函数的取值当满足特征条件时取1，否则取0。
1.4 条件随机场的矩阵形式
引入特殊的起点和终点状态标记y0=start,yN+1=stop,这时Pw(Y|X) 可以通过矩阵形式表示。对x的每一个位置i=1,2,3,…,n+1，定义一个m阶矩阵（m是标记yi 取值的个数）。
Mi(x)=[Mi(Yi-1,Yi|x)]
Mi(yi-1,yi|x)=exp(Wi(yi-1,yi|x))
Wi(yi-1,yi|x)=∑k=1Kwkfk(yi-1,yi,x,i)
这样，给定观测序列x，y的非规范化概率可以通过n+1个矩阵的乘积来表示:
∏i=1n+1Mi(Yi-1,Yi|x)
2. 条件随机场的概率计算问题
问题描述：给定条件随机场P(Y|X)，输入序列x，和输出序列y，计算条件概率P(Yi=yi|xi) 和P(Yi-1=yi-1,Yi=yi|xi) 以及相应的数学期望。
2.1 前向-后向算法
前向向量αi(x)
α0(y|x)={1,y=start0,否则
递推公式：
αTi(yi|x)=αTi-1(yi-1|x)Mi(yi-1,yi|x)
αTi(yi|x) 表示在位置i的标记是yi 并且到位置i的前部分标记序列的非关规范化概率。yi可取的值有m个，所以αi(x) 是m维列向量。
后向向量βi(x) ：
βn+1(yn+1|x)={1,yn+1=stop0,否则
递推公式：
βi(yi|x)=Mi(yi,yi+1|x)βi-1(yi+1|x)
βi(yi|x) 表示在位置i的标记为yi 并且从i+1到n的后部分标记序列的非规范化概率。
可知Z(x)=αTn(x)?1=1T?β1(x)
P(Yi=yi|x)=αTi(yi|x)βi(yi|x)Z(x)
P(Yi-1=yi-1,Yi=yi|x)=αTi-1(yi-1|x)Mi(yi-1,yi|x)βi(yi|x)Z(x)
期望值的计算
特征函数fk 关于条件分布P(Y|X)的数学期望：
EP(Y|X)[fk]=∑yP(y|x)fk(y,x)=∑i=1n+1∑yi-1,yifk(yi-1,yi,x,i)αTi(yi|x)Mi(yi-1,yi|x)βi(yi|x)Z(x)
特征函数fk 关于联合分布P(X,Y)的数学期望：
EP(X,Y)[fk]=∑yP(x,y)fk(y,x)=∑P^(x)∑i=1n+1∑yi-1,yifk(yi-1,yi,x,i)αTi(yi|x)Mi(yi-1,yi|x)βi(yi|x)Z(x)
其中，P^(x) 是经验分布。
3. 条件随机场的学习算法
问题描述：
给定训练集，估计条件随机场模型参数。
学习方法包括：极大似然估计、正则化的极大似然估计。
具体的优化实现算法：改进的迭代尺度法IIS、梯度下降法以及拟牛顿法。
4. 条件随机场的预测算法
问题描述：
给定条件随机场P(Y|X)和输入序列x，求条件概率最大输出序列y*
维特比算法
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：22468次
排名：千里之外
原创：23篇
评论：12条
(4)(4)(2)(13)(1)(2)}