条件随机场(四)

对所有类型的CRF模型,包括最大熵模型,都是采用极大似然估计的方法来进行参数估计,也就是说在训练数据集$\mathcal T$上进行对数似然函数$\mathcal L$的极大化。根据上一篇《条件随机场(三)》,我们知道线性链CRF的模型为

\begin{equation} p_{\vec {\lambda}}(\vec y | \vec x) = \frac 1 {Z_{\vec {\lambda}} (\vec x)} exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y_{j-1}, y_j, \vec x, j)) \end{equation}

\begin{equation} Z_{\vec {\lambda}}(\vec x) =  \sum_{\vec {y} \in \mathcal Y} exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y_{j-1}, y_j, \vec x, j)) \end{equation}

所以对数似然函数为,

\begin{equation} \begin{aligned} \overline {\mathcal L} (\mathcal T)  & = \sum_{(\vec x, \vec y) \in \mathcal T} log p(\vec y | \vec x) \\ & = \sum_{(\vec x, \vec y) \in \mathcal T} [log (\frac {exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y_{j-1}, y_j, \vec x, j))} { \sum_{y‘ \in \mathcal Y} exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y‘_{j-1}, y‘_j, \vec x, j))})] \end{aligned} \end{equation}

为了避免过拟合,对数似然函数增加一个惩罚因子$- \sum_{i=1}^m \frac {\lambda_{i}^2} {2 \sigma^2}$,其中$\sigma^2$是平衡因子,于是重新组织对数似然函数并作变换,

\begin{equation} \begin{aligned} \mathcal {L} (\mathcal T) & = \sum_{(\vec x, \vec y) \in \mathcal T} [log (\frac {exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y_{j-1}, y_j, \vec x, j))} { \sum_{y‘ \in \mathcal Y} exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y‘_{j-1}, y‘_j, \vec x, j))})] - \sum_{i=1}^m \frac {\lambda_{i}^2} {2 \sigma^2} \\ & = \sum_{(\vec x, \vec y) \in \mathcal T} [(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y_{j-1}, y_j, \vec x, j)) - log (\sum_{y‘ \in \mathcal Y} exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y‘_{j-1}, y‘_j, \vec x, j)))] - \sum_{i=1}^m \frac {\lambda_{i}^2} {2 \sigma^2} \\ & = \underbrace {\sum_{(\vec x, \vec y) \in \mathcal T} \sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y_{j-1}, y_j, \vec x, j)}_{\mathcal A}  \\ & \quad - \underbrace{\sum_{(\vec x, \vec y) \in \mathcal T} log \underbrace {(\sum_{y‘ \in \mathcal Y} exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y‘_{j-1}, y‘_j, \vec x, j)))}_{Z_{\vec \lambda}(\vec x)}}_{\mathcal B}  - \underbrace{\sum_{i=1}^m \frac {\lambda_{i}^2} {2 \sigma^2}}_{\mathcal C} \end{aligned}\end{equation}

对数似然函数$\mathcal L(\mathcal T)$的各项$\mathcal A, \mathcal B, \mathcal C$分别对$\lambda_i$求偏导,

\begin{equation} \frac \partial {\partial {\lambda_i}} \sum_{(\vec x, \vec y) \in \mathcal T} \sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i (y_{j-1}, y_j, \vec x, j) = \sum_{(\vec x, \vec y) \in \mathcal T} \sum_{j=1}^n f_j(y_{j-1}, y_j, \vec x, j) \end{equation}

上式的求导中,将$\lambda_i$看作变量,而$\lambda_k, k \neq i$看作常数。

\begin{equation} \begin{aligned} \frac \partial {\partial {\lambda_i}} \sum_{(\vec x, \vec y) \in \mathcal T} log Z_{\vec \lambda}(\vec x) & = \sum_{(\vec x, \vec y) \in \mathcal T} \frac 1 {Z_{\vec \lambda}(\vec x)} \frac {\partial {Z_{\vec \lambda}(\vec x)}} {\partial \lambda_j} \\ & = \sum_{(\vec x, \vec y) \in \mathcal T} \frac 1 {Z_{\vec \lambda}(\vec x)} \sum_{\vec {y}‘ \in \mathcal Y} exp (\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i ( y‘_{j-1}, y‘_j, \vec x , j)) \cdot \sum_{j=1}^n f_i(y‘_{j-1}, y‘_j, \vec x , j) \\ & = \sum_{(\vec x, \vec y) \in \mathcal T} \sum_{{\vec y}‘ \in \mathcal Y} \underbrace{\frac 1 {Z_{\vec \lambda}(\vec x)} exp(\sum_{j=1}^n \sum_{i=1}^m \lambda_i f_i ( y‘_{j-1}, y‘_j, \vec x , j))}_{=p_{\vec \lambda}(\vec y | \vec x)} \cdot \sum_{j=1}^n f_i(y‘_{j-1}, y‘_j, \vec x , j) \\ & = \sum_{(\vec x, \vec y) \in \mathcal T} \left( \sum_{{\vec y}‘ \in \mathcal Y} p_{\vec \lambda}({\vec y}‘ | \vec x) \sum_{j=1}^n f_i(y‘_{j-1}, y‘_j, \vec x , j) \right) \end{aligned} \end{equation}

\begin{equation} \frac \partial {\partial{\lambda_k}} (- \sum_{i=1}^m \frac {\lambda_{i}^2} {2 \sigma^2}) = - \frac {\lambda_k} {\sigma^2} \end{equation}

上面的对数似然函数(4)式是凹函数:其中第一项是线性的,因为关于$\lambda_i$求导后的表达式不包含$\lambda_i$了,第二项求导后的表达式中有一个归一化项,自然也与$\lambda_i$无关了,所以第二项也可以看成$\lambda_i$的线性项,而第三项明显是$\lambda_i$的凹函数,所以对数似然函数整体也是凹函数。

对数似然函数的$\mathcal A$项其实就是特征函数$f_i$在经验分布下的期望值(我怎么觉得要除以$| \mathcal T |$,然而这个对计算值没影响,后文会解释),

\begin{equation} \tilde{E}(f_i) = \sum_{(\vec x, \vec y) \in \mathcal T} \sum_{j=1}^n f_i (y_{j-1},y_j, \vec x, j) \end{equation}

$\mathcal B$项的求导则是CRF模型下的$f_i$的期望,

\begin{equation} \begin{aligned}  E(f_i) & = \sum_{(\vec x, \vec y) \in \mathcal Z} p(\vec x, \vec y) \sum_{j=1}^n f_i ({y_{j-1}}‘ , {y_j}‘ , \vec x, j)  \\ & =  \sum_{(\vec x, \vec y) \in \mathcal Z} p(\vec x) p(\vec y | \vec x) \sum_{j=1}^n f_i ({y_{j-1}}‘ , {y_j}‘ , \vec x, j) \\ & =  \sum_{(\vec x, \vec y) \in \mathcal Z} \tilde{p}(\vec x) p(\vec y | \vec x) \sum_{j=1}^n f_i ({y_{j-1}}‘ ,{y_j}‘ , \vec x, j) \\ & \propto \sum_{(\vec x, \vec y) \in \mathcal T} \sum_{{\vec y}‘ \in \mathcal Y} p_{\vec \lambda}({\vec y}‘ | \vec x) \sum_{j=1}^n f_i ({y_{j-1}}‘, {y_j}‘, \vec x, j) \end{aligned} \end{equation}

上式推导中使用经验概率$\tilde{p}(\vec x)$代替$p(\vec x)$,最后一步的正比其实就是乘以了训练集的数量$| \mathcal T|$,这与(8)式也是一致的,(8)中也是经验期望乘以了$| \mathcal T |$,而第三项也可以认为是经过了乘以$| \mathcal T |$ 这一步,

于是对数似然函数的偏导为,

\begin{equation} \frac {\partial {\mathcal {L} (\mathcal T)}} {\partial {\lambda_i}} = \tilde{E}(f_i) - E(f_i) - \frac {\lambda_i} {\sigma^2} \end{equation}

(8)和(9)式与最大熵模型(见条件随机场二中的(12)~(16)式)类似,令上式等于0,于是乘以的$| \mathcal T |$这一项就可以忽略了。

计算$f_i$的经验期望是很容易的,只要找出特征$f_i$在训练数据集中出现次数(按道理,应该除以$| \mathcal T |$,但是上文解释过了,可以忽略这一常数因子),计算$E(f_i)$则没那么容易了,因为分类序列的情况比较多,即$| \mathcal Y |$值比较大。而在最大熵模型中可以计算$E(f_i)$的原因是因为其分类输出为单个,而非一个序列,显然序列排序的情况比单个的情况多很多,比如分类总共有J个,则单个分类的情况就是J个,而n长度的序列的可能情况理论上则是 $J^n$个。在CRF中,由于计算的复杂,我们采用动态规划的方法,与HMM中一样,即前向-后向算法。如下图

我们令$T_{j}(s)$表示从位置j,状态为s的节点出发可以到达下一个位置上所有状态对应的节点,$T{j}^{-1}(s)$表示位置 j 且状态为s的节点可以由上一个位置上所有可能的状态节点转换而来,根据前面HMM的介绍内容不难知道,对于线性链CRF模型,前向$\alpha$和后向$\beta$分别为,

\begin{equation} \alpha_{j}(s| \vec x) = \sum_{s‘ \in T_{j}^{-1}(s)} \alpha_{j-1}(s‘ | \vec x) \cdot \Psi_{j}(\vec x, s‘, s) \end{equation}

\begin{equation} \beta_{j}(s | \vec x) = \sum_{s‘ \in T_{j}(s)}(s‘ | \vec x) \cdot \Psi_{j}(\vec x, s, s‘) \end{equation}

其中势函数$\Psi_{j}(\vec x, s‘, s)$可以根据条件随机场(三)中的(3)式和(5)式很容易得到:$\Psi_{j}(\vec x, s, s‘) = \exp (\sum_{i=1}^m \lambda_i f_i (y_{j-1} = s, y_{j} = s‘ , \vec x , j)) $

这里,前向概率 $\alpha_{j}(s | \vec x)$表示输入为$\vec x$的条件下,位置 j 处的状态为 s 并且到位置 j 的前部分标记序列的非规范化条件概率,而后向概率 $\beta_{j}(s | \vec x)$ 表示输入为 $\vec x$的条件下,位置 j 的状态为s 且 j 位置到最后的那一部分标记序列的非规范化条件概率,一定要注意是非规范化的,因为没有考虑因子$Z_{\vec {\lambda}}(\vec x)$。

定义第一个位置 j = 1 之前的起始位置 j = 0 的状态记为 $\bot$,最后一个位置 j = n 之后的一个位置 j = n + 1 的状态记为 $\top$,于是有

\begin{equation} \alpha_{0} (\bot | \vec x) = 1 \end{equation}

\begin{equation} \beta_{|\vec x| + 1}(\top | \vec x) = 1 \end{equation}

有了上述信息,计算$f_i$的期望就可以有效地实现了,根据(9)式,

条件概率$\sum_{{\vec y}‘ \in \mathcal T} p_{\vec {\lambda}}({\vec y}‘ | \vec x)$表示给定输入$\vec x$的条件下,所有可能的输出$\vec y$的条件概率之和,易知

$$\sum_{{\vec y}‘ \in \mathcal T} p_{\vec {\lambda}}({\vec y}‘ | \vec x) = \frac 1 {Z_{\vec {\lambda}}(\vec x)}  \sum_{s \in S}  \alpha_{j}(s | \vec x) \beta_{j}(s|\vec x) $$

代入(9)式得,

\begin{equation} \begin{aligned} E(f_i) & = \sum_{(\vec x, \vec y) \in \mathcal T} \frac 1 {Z_{\vec {\lambda}}(\vec x)}  \sum_{s \in S}  \alpha_{j}(s | \vec x) \beta_{j}(s|\vec x) \cdot \sum_{j=1}^n f_i({y_{j-1}}‘, {y_j}‘, \vec x, j)  \\ & =  \sum_{(\vec x, \vec y) \in \mathcal T} \frac 1 {Z_{\vec {\lambda}}(\vec x)} \sum_{j=1}^n \sum_{s \in S}   f_i({y_{j-1}}‘, {y_j}‘, \vec x, j) \alpha_{j}(s | \vec x) \beta_{j}(s|\vec x) \\ & = \sum_{(\vec x, \vec y) \in \mathcal T} \frac 1 {Z_{\vec {\lambda}}(\vec x)} \sum_{j=1}^n \sum_{s \in S} \sum_{s‘ \in T_{j}(s)} f_i((s, s‘, \vec x, j) \alpha_{j}(s | \vec x) \Psi_{j}(\vec x, s, s‘) \beta_{j+1}(s‘|\vec x) \end{aligned} \end{equation}

上式计算过程可以用下图形象的表示出来

此外,归一化因子可以表示为

$$Z_{\vec {\lambda}}(\vec x) = \beta_{0}(\bot | \vec x) $$

于是解(10)式方程即可。

(未完待续,后面将持续统计学习相关的文章,鄙人也是边学边记录)

ref

Classical Probabilistic Models and Conditional Random Fields

时间: 06-30

条件随机场(四)的相关文章

条件随机场入门(四) 条件随机场的预测算法

CRF 的预测问题是给定模型参数和输入序列(观测序列)x, 求条件概率最大的输出序列(标记序列)$y^*$,即对观测序列进行标注.条件随机场的预测算法同 HMM 还是维特比算法,根据 CRF模型可得: \begin{aligned}y^* &= \arg \max_yP_w(y|x) \\&=  \arg \max_y\frac{ \exp \left \{w \cdot F(y,x) \right\}}{Z_w(x)} \\&=  \arg \max_y \exp \left \

条件随机场入门(四) 条件随机场的训练

本节讨论给定训练数据集估计条件随机场模型参数的问题,即条件随机场的学习问题.条件随机场模型实际上是定义在时序数据上的对数线形模型,其学习方法包括极大似然估计和正则化的极大似然估计.具体的优化实现算法有改进的迭代尺度法IIS.梯度下降法以及 L-BFGS 算法.(crf++ 采用了 L-BFGS 优化的方式,所以着重看这种训练方法即可) L-BFGS算法 对于条件随机场模型: \[P_w(y|x) = \frac{\exp \left \{ \sum_{k=1}^K w_kf_k(x,y)\rig

条件随机场(CRF) - 4 - 学习方法和预测算法(维特比算法)

声明: 1,本篇为个人对<2012.李航.统计学习方法.pdf>的学习总结,不得用作商用,欢迎转载,但请注明出处(即:本帖地址). 2,由于本人在学习初始时有很多数学知识都已忘记,所以为了弄懂其中的内容查阅了很多资料,所以里面应该会有引用其他帖子的小部分内容,如果原作者看到可以私信我,我会将您的帖子的地址付到下面. 3,如果有内容错误或不准确欢迎大家指正. 4,如果能帮到你,那真是太好了. 学习方法 条件随机场模型实际上是定义在时序数据上的对数线性模型,其学习方法包括极大似然估计和正则化的极大

条件随机场(CRF) - 2 - 定义和形式

声明: 1,本篇为个人对<2012.李航.统计学习方法.pdf>的学习总结,不得用作商用,欢迎转载,但请注明出处(即:本帖地址). 2,由于本人在学习初始时有很多数学知识都已忘记,所以为了弄懂其中的内容查阅了很多资料,所以里面应该会有引用其他帖子的小部分内容,如果原作者看到可以私信我,我会将您的帖子的地址付到下面. 3,如果有内容错误或不准确欢迎大家指正. 4,如果能帮到你,那真是太好了. 书上首先介绍概率无向图模型,然后叙述条件随机场的定义和各种表示方法,那这里也按照这个顺序来. 概率无向图

猪猪的机器学习笔记(十八)条件随机场

条件随机场 作者:樱花猪 摘要: 本文为七月算法(julyedu.com)12月机器学习第十八次课在线笔记.条件随机场是一种判别式概率模型,是随机场的一种,常用于标注或分析序列资料,如自然语言文字或是生物序列. 引言: “条件随机场”被用于中文分词和词性标注等词法分析工作,一般序列分类模型常常采用隐马尔科夫模型(HMM),像基于类的中文分词.但隐马尔可夫模型中存在两个假设:输出独立性假设和马尔可夫性假设.其中,输出独立性假设要求序列数据严格相互独立才能保证推导的正确性,而事实上大多数序列数据不能

NLP —— 图模型(二)条件随机场(Conditional random field,CRF)

本文简单整理了以下内容: (一)马尔可夫随机场(Markov random field,无向图模型)简单回顾 (二)条件随机场(Conditional random field,CRF) 这篇写的非常浅,基于 [1] 和 [5] 梳理.感觉 [1] 的讲解很适合完全不知道什么是CRF的人来入门.如果有需要深入理解CRF的需求的话,还是应该仔细读一下几个英文的tutorial,比如 [4] . (一)马尔可夫随机场简单回顾 概率图模型(Probabilistic graphical model,P

【NLP】条件随机场知识扩展延伸

条件随机场知识扩展延伸 作者:白宁超 2016年8月3日19:47:55 [摘要]:条件随机场用于序列标注,数据分割等自然语言处理中,表现出很好的效果.在中文分词.中文人名识别和歧义消解等任务中都有应用.本文源于笔者做语句识别序列标注过程中,对条件随机场的了解,逐步研究基于自然语言处理方面的应用.成文主要源于自然语言处理.机器学习.统计学习方法和部分网上资料对CRF介绍的相关的相关,最后进行大量研究整理汇总成体系知识.文章布局如下:第一节介绍CRF相关的基础统计知识:第二节介绍基于自然语言角度的

理解条件随机场(转)

理解条件随机场最好的办法就是用一个现实的例子来说明它.但是目前中文的条件随机场文章鲜有这样干的,可能写文章的人都是大牛,不屑于举例子吧.于是乎,我翻译了这篇文章.希望对其他伙伴有所帮助.原文在这里[http://blog.echen.me/2012/01/03/introduction-to-conditional-random-fields/] 想直接看英文的朋友可以直接点进去了.我在翻译时并没有拘泥于原文,许多地方都加入了自己的理解,用学术点的话说就是意译.(画外音:装什么装,快点开始吧.)

条件随机场(CRF) - 2 - 定义和形式(转载)

转载自:http://www.68idc.cn/help/jiabenmake/qita/20160530618218.html 参考书本: <2012.李航.统计学习方法.pdf> 书上首先介绍概率无向图模型,然后叙述条件随机场的定义和各种表示方法,那这里也按照这个顺序来. 概率无向图模型(马尔可夫随机场) 其实这个又叫做马尔可夫随机场(MRF),而这里需要讲解的条件随机场就和其有脱不开的关系. 模型定义 首先是无向图.那什么是无向图呢? 其实无向图就是指没有方向的图....我没有开玩笑,无