果壳中的条件随机场(CRF In A Nutshell)
By 苏剑林 | 2017-11-25 | 108326位读者 |本文希望用尽可能简短的语言把CRF(条件随机场,Conditional Random Field)的原理讲清楚,这里In A Nutshell在英文中其实有“导论”、“科普”等意思(霍金写过一本《果壳中的宇宙》,这里东施效颦一下)。
网上介绍CRF的文章,不管中文英文的,基本上都是先说一些概率图的概念,然后引入特征的指数公式,然后就说这是CRF。所谓“概率图”,只是一个形象理解的说法,然而如果原理上说不到点上,你说太多形象的比喻,反而让人糊里糊涂,以为你只是在装逼。(说到这里我又想怼一下了,求解神经网络,明明就是求一下梯度,然后迭代一下,这多好理解,偏偏还弄个装逼的名字叫“反向传播”,如果不说清楚它的本质是求导和迭代求解,一下子就说反向传播,有多少读者会懂?)
好了,废话说完了,来进入正题。
逐标签Softmax #
CRF常见于序列标注相关的任务中。假如我们的模型输入为$Q$,输出目标是一个序列$a_1,a_2,\dots,a_n$,那么按照我们通常的建模逻辑,我们当然是希望目标序列的概率最大
$$P(a_1,a_2,\dots,a_n|Q)$$
不管用传统方法还是用深度学习方法,直接对完整的序列建模是比较艰难的,因此我们通常会使用一些假设来简化它,比如直接使用朴素假设,就得到
$$P(a_1,a_2,\dots,a_n|Q)=P(a_1|Q)P(a_2|Q)\dots P(a_n|Q)$$
注意这里的Q不一定是原始输入,比如它可能是经过多层LSTM之后的隐藏输出$q_1,q_2,\dots,q_n$,并且我们认为全局的关联已经由前面的模型捕捉完成了,因此在最后一步,我们可以认为特征之间互不相关,那么
$$\begin{aligned}P(a_1|Q)=&P(a_1|q_1,q_2,\dots,q_n)=P(a_1|q_1)\\
P(a_2|Q)=&P(a_2|q_1,q_2,\dots,q_n)=P(a_2|q_2)\\
&\quad\vdots\\
P(a_n|Q)=&P(a_n|q_1,q_2,\dots,q_n)=P(a_n|q_n)\\
\end{aligned}$$
从而
$$P(a_1,a_2,\dots,a_n|Q)=P(a_1|q_1)P(a_2|q_2)\dots P(a_n|q_n)$$
这就得到了我们最常用的方案:直接逐标签输出最大概率的那个标签。而前面的模型通常是多层的双向LSTM。
条件随机场 #
逐标签softmax是一种简单有效的方法,但有时候会出现不合理的结果。比如我们用sbme来做4标签分词时,逐标签softmax无法排除出现bbbb这样的序列的可能性,但这个序列是违反了我们的解码规则(b后面只能接m或e)。因此,有人说逐标签softmax不需要动态规划,那是不对的,这种情况下,我们至少需要一个“非0即1”的转移矩阵,直接把不合理的转移概率设为0(如$P(b|b)=0$),然后通过动态规划保证得到合理的序列。
上述方案会出问题,归根结底就是我们在建模的时候,使用了输出完全独立的朴素假设(一元模型),但我们真实的输出序列又是上下文有关的,因此造成了优化目标与模型假设不吻合。能不能直接把上下文考虑进去呢?很简单,使用二元模型即可。
$$\begin{aligned}P_Q(a_1,a_2,\dots,a_n)=&P_Q(a_1) P_Q(a_2|a_1) P_Q(a_3|a_1,a_2)\dots P_Q(a_n|a_1,\dots,a_{n-1})\\
=&P_Q(a_1) P_Q(a_2|a_1) P_Q(a_3|a_2)\dots P_Q(a_n|a_{n-1})
\end{aligned}$$
这里为了使得表达式更好看一些,我把输入$Q$放到了下标中。这已经很接近CRF了!
继续观察上式,上面是一个转移概率的乘积,然而我们为什么非要定义每一项都是转移概率呢?于是,CRF的做法非常一般,首先它定义了一个函数$f(x,y;Q)$(它可能是一些简单的特征函数之和,但具体的形式其实不重要),然后直接令
$$P_Q(a_1,a_2,\dots,a_n) = \frac{1}{Z}\exp\left(\sum_k f(a_{k-1},a_k;Q)\right)$$
其中$Z$是归一化因子。跟前一式相比,两者的区别在于,$P_Q(a_k|a_{k-1})$是有概率意义的(条件概率),而单项的$e^{f(a_{k-1},a_k;Q)}/Z$是没有概率意义的,所以CRF是更一般的形式。
这就是CRF的全部了。
一个更完整的参考链接:https://zhuanlan.zhihu.com/p/28465510
线性链CRF #
What?你在逗我?这就是CRF?这一个个$P_Q(a_k|a_{k-1})$是什么鬼?还有$f(x,y;Q)$呢?
这位读者,你可问倒我了,我也不知道是什么鬼呀。不信您到再看看网上的一些教程,它们给出的公式大概是这样的(直接抄自这里):
$$\begin{aligned}p(l | s) =& \frac{\exp[score(l|s)]}{\sum_{l’} \exp[score(l’|s)]} \\
=& \frac{\exp[\sum_{j = 1}^m \sum_{i = 1}^n \lambda_j f_j(s, i, l_i, l_{i-1})]}{\sum_{l’} \exp[\sum_{j = 1}^m \sum_{i = 1}^n \lambda_j f_j(s, i, l’_i, l’_{i-1})]}\end{aligned}$$
这里的$f$都是未知的“特征函数”,需要根据具体问题具体设计,那还不是等价于说是未知的$f(a_{k-1},a_k;Q)$。所以,我确实不知道是什么鬼呀。
好吧,就算你是对的,你好歹也教教我怎么用吧?
这里介绍一个经常用的版本——线性链CRF,它就是tensorflow自带的版本。我们先写出
$$\begin{aligned}&P_Q(a_1,a_2,\dots,a_n)\\
=&P_Q(a_1) P_Q(a_2|a_1) P_Q(a_3|a_2)\dots P_Q(a_n|a_{n-1})\\
=&P_Q(a_1) \frac{P_Q(a_1, a_2)}{P_Q(a_1) P_Q(a_2)} P_Q(a_2) \frac{P_Q(a_2, a_3)}{P_Q(a_2) P_Q(a_3)}P_Q(a_3) \dots \frac{P_Q(a_{n-1}, a_n)}{P_Q(a_{n-1}) P_Q(a_n)} P_Q(a_n)
\end{aligned}$$
是不是感觉还挺好看的?根据CRF的一般思路,我们放弃每一项的概率意义,直接写出
$$\begin{aligned}&P_Q(a_1,a_2,\dots,a_n)\\
=&\frac{1}{Z} \exp \Big[f(a_1;Q)+g(a_1, a_2;Q) + f(a_2;Q) +\dots + g(a_{n-1}, a_n;Q) + f(a_n;Q)\Big]
\end{aligned}$$
所谓线性链,就是直接认为函数$g$实际上跟$Q$没关系,任何情况都共用一个$g(a_{k-1},a_k)$,这样它不过是个待确定的矩阵而已。剩下的则跟逐标签softmax的情形差不多了,认为$f(a_k;Q)\equiv f(a_k;q_k)$。按照极大似然的思想,loss应该取为:
$$\begin{aligned} &-\log P_Q(a_1,a_2,\dots,a_n)\\
=& - \sum_{k=1}^n f(a_k;q_k) - \sum_{k=2}^n g(a_{k-1},a_k) + \log Z
\end{aligned}$$
如果前面模型用双向LSTM来得到特征$q_k$,那么就得到了序列标注任务中最经典的BiLSTM-CRF了。
所以,现在也就不难理解tensorflow中自带的CRF的函数了:
https://github.com/tensorflow/tensorflow/tree/master/tensorflow/contrib/crf
相对于逐标签softmax,CRF不过是换了一个loss罢了,当然,还多了一个互信息矩阵,并且解码的时候需要用到viterbi算法。但这都不重要,因为tensorflow都帮我们写好了。
再设计? #
线性链CRF可以说是一个化简的模版,我们是不是可能参照这个模版,设计一个改进的CRF?比如,用模型生成一个跟Q有关的互信息矩阵?也许是可能的。
剥开nutshell,才能更好地品尝nut,这就是果壳中的味道了。知其然,知其所以然,一切就没那么神秘了。
(新介绍:https://kexue.fm/archives/5542)
转载到请包括本文地址:https://www.spaces.ac.cn/archives/4695
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Nov. 25, 2017). 《果壳中的条件随机场(CRF In A Nutshell) 》[Blog post]. Retrieved from https://www.spaces.ac.cn/archives/4695
@online{kexuefm-4695,
title={果壳中的条件随机场(CRF In A Nutshell)},
author={苏剑林},
year={2017},
month={Nov},
url={\url{https://www.spaces.ac.cn/archives/4695}},
}
November 25th, 2017
无向图模型中单个特征函数不具有概率意义。
私以为,第II节中标签序列的概率公式,其实是直接根据一阶马尔科夫假设得到的HMM模型。
实际在编写条件随机场时最简化的形式就是直接将HMM的参数对数化,但直接认为这是条件随机场是不是有失偏颇?
病句,最后一个词用错了
是我的认识不足,已经根据你的建议做了一些修改,非常感谢。
November 27th, 2017
最后一个公式中,只有Z需要带log吧,前面两项应该都不需要的
笔误,已修正,非常感谢~
December 28th, 2017
III节中讲到tensorflow自带的CRF,引入公式=P(a1|Q)*P(a2|a1, Q)*... = p(a1|Q)*P(a2,a1|Q)/(P(a1|Q) * P(a2|Q)) * P(a2|Q) ...
由于qi只和ai有关,于是可不可以写成P(a1|q1)*P(a2|a1, q2) = p(a1|q1)*P(a2|a1)*P(a2|q2) 这样比上式少除一个P(a2|q2).....?
另外单从公式来看,也可以用来表达HMM,那么g(a1,a2|Q)应该是不对称的
而P(a2,a1|Q)/(P(a1|Q) * P(a2|Q)) 是对称的。不知道有没有说清楚。。。
从形式看,线性链CRF跟HMM是没有区别的。它们的区别在于,CRF去掉了每一项的概率意义,直接定义了$f(a_1;Q),g(a_2,a_1;Q)$这些函数表示它们的关系(你可以认为是某种得分),然后最后再整体归一化。
这样子操作的话,HMM实际上就是描述每个点的概率分布,而CRF则直接描述每条路径的概率,由于它的建模对象是一条路径而不是逐点,而已在全局规划上效果会更好。
这点同意。然而公式的推导这块,如果有
P(a1|Q)*P(a2|a1, Q)*... = p(a1|Q)*P(a2,a1|Q)/(P(a1|Q) * P(a2|Q)) * P(a2|Q) ...
g(a1,a2;Q) = P(a2,a1|Q)/(P(a1|Q) * P(a2|Q))
则 g(a1,a2;Q) = g(a2,a1;Q)
这里不应该得到这样的结论,g不一定是对称的
不大理解你的逻辑,我没说$g$关于$a_1,a_2$对称呀。就算是$\frac{P_Q(a_1, a_2)}{P_Q(a_1) P_Q(a_2)}$这个量关于$a_1,a_2$也不一定是对称的。
这样啊,求教为什么这个量关于a1,a2不一定是对称的?
因为$p(a_1,a_2)$不是对称的呀。比如$p(a_1,a_2)$表示左边是$a_1$右边是$a_2$的概率,那么$p(a_2,a_1)$就表示左边是$a_2$右边是$a_1$的概率,$p(a_1,a_2)$不一定等于$p(a_2,a_1)$的呀。
哦 明白了 谢谢楼主~
February 24th, 2018
真是有趣,这两天搜三个不同的问题都找到了这个blog
哈哈,欢迎多多关注。
记得很久之前就来过了,这个blog的样式比较特别,有印象。还跟博主一样都住在广州呢
May 20th, 2018
请问第3节中的函数g是具体是什么含义?来的太突然有点懵
任意函数。(就是指可以写成那样的形式。)
August 23rd, 2018
"我们认为全局的关联意境由前面的模型捕捉完成了"应为“我们认为全局的关联已经由前面的模型捕捉完成了”
嗯嗯,感谢指出~
July 24th, 2019
你的crf讲解系列很赞,注册了个账号夸下你,我算是终于懂了看二天。
March 13th, 2023
[...]笔者去年曾写过博文《果壳中的条件随机场(CRF In A Nutshell)》,以一种比较粗糙的方式介绍了一下条件随机场(CRF)模型。然而那篇文章显然有很多不足的地方,比如介绍不够清晰,也不够完整,还没有实现,在这里我们重提这个模型,将相关内容补充完成。[...]
March 16th, 2023
您好,请问下第三部分 线性链CRF 公式这一步是怎么变化来的:
\begin{aligned}
=&P_Q(a_1) P_Q(a_2|a_1) P_Q(a_3|a_2)\dots P_Q(a_n|a_{n-1})\\
=&P_Q(a_1) \frac{P_Q(a_1, a_2)}{P_Q(a_1) P_Q(a_2)} P_Q(a_2) \frac{P_Q(a_2, a_3)}{P_Q(a_2) P_Q(a_3)}P_Q(a_3) \dots \frac{P_Q(a_{n-1}, a_n)}{P_Q(a_{n-1}) P_Q(a_n)} P_Q(a_n)
\end{aligned}
为什么:
\begin{aligned} P_Q(a_2|a_1) = \frac{P_Q(a_1, a_2)}{P_Q(a_1) P_Q(a_2)} P_Q(a_2)
\end{aligned}
贝叶斯公式