CRF模型

您所在的位置：网站首页 › crf算法 › CRF模型

CRF模型

#CRF模型| 来源: 网络整理| 查看: 265

CRF概念

随机场是由若干个位置组成的整体，当给每一个位置中按照某种分布随机赋予一个值之后，其全体就叫做随机场。

马尔科夫随机场是随机场的特例，它假设随机场中某一个位置的赋值仅仅与和它相邻的位置的赋值有关，和与其不相邻的位置的赋值无关。

CRF是马尔科夫随机场的特例，它假设马尔科夫随机场中只有X和Y两种变量，X一般是给定的，而Y一般是在给定X的条件下我们的输出。

X和Y有相同的结构的CRF就构成了线性链条件随机场。

CRF的数学语言描述：设X与Y是随机变量， $P(Y|X)$ 是给定X时Y的条件概率分布，若随机变量Y构成的是一个马尔可夫随机场，则称条件概率分布 $P(Y|X)$ 是条件随机场。(判别式模型)

linear-CRF的数学定义：设 $X=(X_1,X_2,...,X_n)$ ， $Y=(Y_1,Y_2,...,Y_n)$ 均为线性链表示的随机变量序列，在给定随机变量序列X的情况下，随机变量Y的条件概率分布 $P(Y|X)$ 构成条件随机场，即满足马尔可夫性： $P(Y_i|X,Y_1,Y_2,...,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})$ ，则称 $P(Y|X)$ 为线性链条件随机场。

linear-CRF模型：给定训练数据集X和对应的标记序列，K个特征函数 $f_k(x,y)$ ，需要学习linear-CRF的模型参数wk。

应用：条件概率 $P_w(y|x)=\frac{1}{Z_w(x)} \exp \sum_{k=1}^K w_kf_k(x,y)=\frac{\exp \sum_{k=1}^K w_kf_k(x,y)}{\sum_y {\exp \sum_{k=1}^K w_kf_k(x,y)}}$

优化目标： $l(w)=-\log \prod _{i=1}^n p_w(x_i,y_i)\equiv -\log \prod _{x,y} p_w(x,y)^{\bar{P} (x,y)}=-\sum_{x,y} \bar{P} (x,y) \log p_w(y|x)$

【注】使用了本人文章“最大熵模型”记录的一个结论。

得： $l(w)=\sum_{x} \bar{P}(x) \log (\sum_{y} \exp \sum_{k=1}^K w_kf_k(x,y))-\sum_{x,y}{\bar{P} }(x,y) \sum_{k=1}^K w_kf_k(x,y)$

求导：

$\frac{\partial l(w)}{\partial w_k}=\sum_{x,y} \bar{P}(x,y)P_w(x|y)f_k(x,y) -\sum_{x,y} \bar{P}(x,y) f_k(x,y)$

更新参数： $w_k:=w_k-\eta \cdot \frac{\partial l(w)}{\partial w_k}$ ，其中η为学习率

特征分为2类，第一类是定义在Y节点上的节点特征函数，这类特征函数只和当前节点有关，记为： $s_l(y_i,x,i)$ ，l=1,2,..,L

第二类是定义在Y上下文的局部特征函数，这类特征只和当前节点和上一节点有关，记为： $t_k(y_{t-1},y_t,x,i)$ ，k=1,2,..,K

维特比解码：

维特比算法是一个动态规划算法

$\delta _{i}(l)$ 代表在位置i处标记为 $l\in {1,2,...,m}$ ；其中m代表标记的总类数。

$\delta _{i+1}(l)=\max_{1\leq j\leq m} \{ \delta _i(j)+ \sum_{k=1}^K w_kf_k(y_i=j,y_{j+1}=l,x,i) \}$

$\Psi _{i+1}(l)=\arg \max_{1\leq j\leq m} \{ \delta _i(j)+ \sum_{k=1}^K w_kf_k(y_i=j,y_{j+1}=l,x,i) \}$

其中 $\Psi _{i+1}(l)$ 代表在位置i+1处标记为l时，经过位置i是哪个路径；这个序列的值也就是最佳路径。

参考：http://www.cnblogs.com/pinard/p/7048333.html

HMM模型

HMM有2个假设：一阶马尔可夫假设，即任意时刻的状态只依赖前一时刻的状态，与其他时刻无关；观测独立性假设。任意时刻的观测只依赖于该时刻的状态，与其他状态无关。

学习联合概率 $P(X,Y)=\prod_{t=1}^T p(y_t|y_{t-1})p(x_t|y_t)$

$P(Y|X)=\frac{P(X,Y)}{P(X)}$ ，p(X)是已知的，可忽略

MEMM最大熵马尔可夫模型

有别于HMM，MEMM的当前状态依赖于前一状态与当前观测

学习条件概率 $P(Y|X)=\prod_{i=1}^n P(y_i|Y_{i-1},x_{1:n})=\prod_{i=1}^n \frac{\exp (w \cdot f(y_i,y_{i-1},x_{1:n}))}{\sum_{\tilde{s}\in S } \exp(w \cdot f(\tilde{s} ,y_{i-1},x_{1:n})) }$

其中S代表状态集合，i代表当前被标记的位置；

可以注意到MEMM在每个节点对所有可能的状态y求和然后用做局部归一化的分母。所以MEMM中节点状态转移的概率都是归一化的概率。

缺点：标注偏置问题

标注偏置问题示例

从全局的角度分析：

无论观测值，State 1 总是更倾向于转移到State 2；

无论观测值，State 2 总是更倾向于转移到State 2.

可以看出MEMM所做的是本地归一化，导致有更少转移的状态拥有的转移概率普遍偏高，概率最大路径更容易出现转移少的状态。因MEMM存在着标注偏置问题，故全局归一化的CRF被提了出来。

HMM和CRF区别

1)HMM是生成式模型，CRF是判别式模型

https://www.cnblogs.com/hellochennan/p/6624509.html

两者都是用了马尔科夫链作为隐含变量的概率转移模型,只不过HMM使用隐含变量生成可观测状态，其生成概率有标注集统计得到，是一个生成模型；而CRF反过来通过可观测状态判别隐含变量，其概率亦通过标注集统计得来，是一个判别模型。

2)HMM是概率有向图，CRF是概率无向图

3)HMM求解过程可能是局部最优，CRF可以全局最优

4)CRF概率归一化较合理，HMM则会导致label bias 问题

5)CRF和HMM都假设隐变量是满足马尔科夫性的，即当前状态仅和上一个状态有概率转移关系而与其它位置的状态无关。

6)CRF优于HMM的地方在于，它可以引入更多的特征，包括词语本身特征和词语所在上下文的特征，而非单词本身。

https://www.zhihu.com/question/53458773

判别式模型：直接对 $P(Y|X)$ 建模；

生成式模型：训练阶段对 $P(X,Y)$ 建模，inference再对新的sample计算 $P(Y|X)$

完毕。

【本文地址】

公司简介

联系我们