网站经营性备案多少钱,学做网站能赚多少,厦门人才网最新招聘信息,南宁关键词排名公司文章目录1 前言2 Log-linear model3 MEMM3.1 模型概述3.2 label bias问题4 CRF4.1 模型概述4.2 模型训练4.3 模型解码4.4 小结参考资料1 前言
条件随机场(conditional random field, CRF)是在建立序列模型时的常用模块#xff0c;它的本质就是描述观测到的序列xˉ\bar{x}xˉ对…
文章目录1 前言2 Log-linear model3 MEMM3.1 模型概述3.2 label bias问题4 CRF4.1 模型概述4.2 模型训练4.3 模型解码4.4 小结参考资料1 前言
条件随机场(conditional random field, CRF)是在建立序列模型时的常用模块它的本质就是描述观测到的序列xˉ\bar{x}xˉ对应的状态序列yˉ\bar{y}yˉ的概率记作P(yˉ∣xˉ)P(\bar{y}|\bar{x})P(yˉ∣xˉ)。这里字符上的横线表示这是一个序列下文中所有的序列都会带这个横线不带横线就不是序列。
它是HMM的升级版如果不熟悉HMM的话建议看我的搞懂HMM这篇文章不看那篇直接看这篇关系也不大。
提出CRF是为了改进MEMM(maximum-entropy Markov model)的label bias问题而提出MEMM是为了打破HMM的观测独立性假设。这些在下文中会进一步说明。
本文主要是参考了Log-Linear Models, MEMMs, and CRFs其中会额外补充一些东西并加入自己的一些理解。
2 Log-linear model
CRF的源头就是Log-linear model是由它一点点改进过来的。
我们先假设观测变量为xxx观测集合为XXX有x∈Xx \in Xx∈X比如xxx是一个单词状态变量为yyy状态集合为YYY有y∈Yy \in Yy∈Y比如yyy是某种词性提取特征的函数向量为ϕˉ(x,y)\bar{\phi}(x, y)ϕˉ(x,y)这里带了横线表示有多个函数函数之间的权重为wˉ\bar{w}wˉ。那么在给定xxx的情况下yyy的概率为比如单词xxx是词性yyy的概率
p(y∣x;wˉ)exp(wˉ⋅ϕˉ(x,y))∑y′∈Yexp(wˉ⋅ϕˉ(x,y′))(2-1)p(y|x;\bar{w}) \frac{exp(\bar{w} \cdot \bar{\phi}(x, y))}{\sum_{y \in Y} exp(\bar{w} \cdot \bar{\phi}(x, y))} \tag{2-1} p(y∣x;wˉ)∑y′∈Yexp(wˉ⋅ϕˉ(x,y′))exp(wˉ⋅ϕˉ(x,y))(2-1)
式(2−1)(2-1)(2−1)的分子表示给定xxx时yyy取某个值时的指数计算式分母表示表示给定xxx时yyy取所有情况的指数计算式之和。说白了就是一个归一化的操作。
使用指数expexpexp是为了保证概率都是正的wˉ⋅ϕˉ(x,y)\bar{w} \cdot \bar{\phi}(x, y)wˉ⋅ϕˉ(x,y)可正可负。
显而易见在这种定义下可以保证
∑y∈Yp(y∣x;wˉ)1(2-2)\sum_{y \in Y} p(y|x;\bar{w}) 1 \tag{2-2} y∈Y∑p(y∣x;wˉ)1(2-2)
假设我们有nnn组有标签的数据{(xi,yi)}i1n\{(x_i, y_i)\}_{i1}^{n}{(xi,yi)}i1n这里还没有涉及到序列可以理解为一个单词xix_ixi对应一个词性yiy_iyi的数据集。
我们的目的是调整模型的参数wˉ\bar{w}wˉ使得出现数据集这样的标签对应情况的可能性最大也就是
wˉ∗argmaxwˉ∏i1np(yi∣xi;wˉ)(2-3)\bar{w}^* arg \max_{\bar{w}} \prod_{i1}^n p(y_i|x_i;\bar{w}) \tag{2-3} wˉ∗argwˉmaxi1∏np(yi∣xi;wˉ)(2-3)
为了方便计算通常会取对数即
wˉ∗argmaxwˉ∑i1nlog(p(yi∣xi;wˉ))(2-4)\bar{w}^* arg \max_{\bar{w}} \sum_{i1}^n log(p(y_i|x_i;\bar{w})) \tag{2-4} wˉ∗argwˉmaxi1∑nlog(p(yi∣xi;wˉ))(2-4)
通常为了不让模型学偏把wˉ\bar{w}wˉ学的特别大来糊弄过去还会加一个正则项
wˉ∗argmaxwˉ∑i1nlog(p(yi∣xi;wˉ))−λ2∣∣wˉ∣∣2(2-5)\bar{w}^* arg \max_{\bar{w}} \sum_{i1}^n log(p(y_i|x_i;\bar{w})) - \frac{\lambda}{2}||\bar{w}||^2\tag{2-5} wˉ∗argwˉmaxi1∑nlog(p(yi∣xi;wˉ))−2λ∣∣wˉ∣∣2(2-5)
这也就是损失函数有了损失函数之后就可以用梯度下降的方法求参数wˉ∗\bar{w}^*wˉ∗了。
这只是针对于非序列的数据集。
3 MEMM
3.1 模型概述
MEMM(maximum-entropy Markov model)进一步将问题从p(y∣x)p(y|x)p(y∣x)转变为p(yˉ∣xˉ)p(\bar{y}|\bar{x})p(yˉ∣xˉ)也可以写成
p(y1,y2,...,ym∣x1,x2,...,xm)(3-1)p(y^1, y^2, ..., y^m|x^1, x^2, ..., x^m) \tag{3-1} p(y1,y2,...,ym∣x1,x2,...,xm)(3-1)
其中xjx^jxj表示序列中的第jjj个token比如一句话中的第jjj个单词yjy^jyj表示序列中的第jjj个标签比如一句话中的第jjj个单词的词性mmm表示序列的长度。
用YYY表示所有可能的标签集合这是一个有限的集合yj∈Yy^j \in Yyj∈Y。
将式(3−1)(3-1)(3−1)用条件概率进行变换就有
p(y1,y2,...,ym∣x1,x2,...,xm)∏j1mp(yj∣y1,...,yj−1,x1,...,xm)(3-2)p(y^1, y^2, ..., y^m|x^1, x^2, ..., x^m) \prod_{j1}^m p(y^j|y^1, ..., y^{j-1}, x^1, ..., x^m) \tag{3-2} p(y1,y2,...,ym∣x1,x2,...,xm)j1∏mp(yj∣y1,...,yj−1,x1,...,xm)(3-2)
式(3−2)(3-2)(3−2)仅仅是一堆条件概率这是必然成立的没有任何假设。我们如果把HMM中的齐次马尔可夫假设放到这里来认为yjy^jyj只受yj−1y^{j-1}yj−1的影响那么就有
p(y1,y2,...,ym∣x1,x2,...,xm)∏j1mp(yj∣yj−1,x1,...,xm)(3-3)p(y^1, y^2, ..., y^m|x^1, x^2, ..., x^m) \prod_{j1}^m p(y^j|y^{j-1}, x^1, ..., x^m) \tag{3-3} p(y1,y2,...,ym∣x1,x2,...,xm)j1∏mp(yj∣yj−1,x1,...,xm)(3-3)
这里仍旧认为yjy^jyj受所有xjx^jxj的影响这就打破了HMM中的观测独立假设。这是一个在很多任务中不合理的假设所以MEMM算是对HMM做了改进。画成概率图就是 图3-1 MEMM概率图有很多的CRF的文章都是从概率图开始讲的但其实根本没有必要不是先有了图3-1才有了式(3−3)(3-3)(3−3)而是先有了式(3−3)(3-3)(3−3)才有了图3-1图3-1仅仅只是让式(3−1)(3-1)(3−1)看起来更方便了。不知道概率图一点关系都没有。
不过既然画了概率图也顺嘴说一句MEMM的概率图和HMM的概率图的区别就在于xxx的箭头方向反了从生成模型变成了判别式模型以及MEMM是所有的xxx指向每一个yjy^jyj而HMM是xjx^jxj指向yjy^jyj打破了观测独立假设。
好回到式(3−3)(3-3)(3−3)利用log-linear model进行建模就有 p(yj∣yj−1,x1,...,xm)exp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,yj))∑y′∈Yexp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,y′))(3-4)p(y^j|y^{j-1}, x_1, ..., x_m) \frac{exp(\bar{w} \cdot \bar{\phi}(x^1,...,x^m, j, y^{j-1}, y^{j}))}{\sum_{y \in Y} exp(\bar{w} \cdot \bar{\phi}(x^1,...,x^m, j, y^{j-1}, y))} \tag{3-4} p(yj∣yj−1,x1,...,xm)∑y′∈Yexp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,y′))exp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,yj))(3-4)
注意对比一下式(3−4)(3-4)(3−4)和式(2−1)(2-1)(2−1)的区别就是条件概率中的条件变了。
将式(3−4)(3-4)(3−4)代入式(3−3)(3-3)(3−3)就有
p(y1,y2,...,ym∣x1,x2,...,xm)∏j1mexp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,yj))∑y′∈Yexp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,y′))(3-5)p(y^1, y^2, ..., y^m|x^1, x^2, ..., x^m) \\ \prod_{j1}^m \frac{exp(\bar{w} \cdot \bar{\phi}(x^1,...,x^m, j, y^{j-1}, y^{j}))}{\sum_{y \in Y} exp(\bar{w} \cdot \bar{\phi}(x^1,...,x^m, j, y^{j-1}, y))} \tag{3-5} p(y1,y2,...,ym∣x1,x2,...,xm)j1∏m∑y′∈Yexp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,y′))exp(wˉ⋅ϕˉ(x1,...,xm,j,yj−1,yj))(3-5)
这里在训练模型的时候不是拿式(3−5)(3-5)(3−5)这个大家伙去训练的而是训练p(yj∣yj−1,x1,...,xm)p(y^j|y^{j-1}, x_1, ..., x_m)p(yj∣yj−1,x1,...,xm)这个模型。
有了p(yj∣yj−1,x1,...,xm)p(y^j|y^{j-1}, x_1, ..., x_m)p(yj∣yj−1,x1,...,xm)之后任何的xxx和yj−1y^{j-1}yj−1yjy^jyj进来都可以输出一个概率值问题就变成了如何decoding如何推理即求
argmaxy1,..,ymp(y1,..,ym∣x1,...,xm)(3-6)arg\max_{y^1, .., y^m} p(y_1, .., y^m | x^1, ..., x^m) \tag{3-6} argy1,..,ymmaxp(y1,..,ym∣x1,...,xm)(3-6)
如果我们假设YYY集合中有kkk个元素的话那么y1,...,ymy^1, ..., y^my1,...,ym就有kmk^mkm种组合这样的计算量就太大了。这个时候就要用动态规划了这里的动态规划有一个自己的名字叫做viterbi算法其实就是动态规划。
我们会建立一个矩阵π[j,y]\pi [j, y]π[j,y]j1,...,mj1,...,mj1,...,m并且y∈Yy \in Yy∈Y。π[j,y]\pi [j, y]π[j,y]存储了在第jjj个位置状态取yyy时的最大概率值和得到该概率值的序列y1,..,yjy^1, .., y^jy1,..,yj。可以表示为
π[j,y]maxy1,...,yj−1(p(y∣yj−1,x1,...,xm)∏k1j−1p(yk∣yk−1,x1,...,xm))(3-7)\pi[j, y] \max_{y^1, ..., y^{j-1}}(p(y|y^{j-1}, x^1, ..., x^m) \prod_{k1}^{j-1}p(y^k|y^{k-1}, x^1, ..., x^m)) \tag{3-7} π[j,y]y1,...,yj−1max(p(y∣yj−1,x1,...,xm)k1∏j−1p(yk∣yk−1,x1,...,xm))(3-7)
其中最开始的为初始变量相当于HMM中的初始概率
π[1,y]p(y∣y0,x1,...,xm)(3-8)\pi[1, y] p(y | y^0, x^1, ..., x^m) \tag{3-8} π[1,y]p(y∣y0,x1,...,xm)(3-8)
y0y^0y0就是START这样的起始token。
之后是通过迭代得到的
π[j,y]maxy′∈Y(π[j−1,y′]⋅p(y∣y′,x1,...,xm))(3-9)\pi[j, y] \max_{y \in Y}(\pi[j-1, y] \cdot p(y|y, x^1, ..., x^m)) \tag{3-9} π[j,y]y′∈Ymax(π[j−1,y′]⋅p(y∣y′,x1,...,xm))(3-9)
将π[j,y]\pi[j, y]π[j,y]这个矩阵填满之后就有
maxy1,...,ymp(y1,...,ym∣x1,...,xm)maxyπ[m,y](3-10)\max_{y^1, ..., y^m}p(y^1, ..., y^m | x^1, ..., x^m) \max_{y} \pi[m, y] \tag{3-10} y1,...,ymmaxp(y1,...,ym∣x1,...,xm)ymaxπ[m,y](3-10)
MEMM相比于HMM的优势在于
观测变量不再独立可以自行设计ϕˉ\bar{\phi}ϕˉ对结果更可控
3.2 label bias问题
MEMM也存在自身的问题这个问题被称为label bias问题故名思义这是由于训练数据标签的不平衡所导致的如果训练数据足够大标签足够平衡就没有这个问题。出现这个问题的根本原因就是p(yj∣yj−1,x1,...,xm)p(y^j|y^{j-1}, x^1, ..., x^m)p(yj∣yj−1,x1,...,xm)是在每个时间节点都做了一次归一化丢失了一些信息。
下面举个例子来试着说明一下只要有一个直观的理解就可以了不要太纠结例子的合理性。
假设我们通过训练得到了下图3-2这样的一张概率值推理图我们输入[“the”, “cat”, “sat”]可以发现[“ARTICLE”, “NOUN”, “VERB”]这样的概率是最高的有1.0∗0.9∗1.00.91.0*0.9*1.00.91.0∗0.9∗1.00.9。
图3-2 概率值推理图但是当我们的输入是[“cat”, “sat”]的时候就会发现[“NOUN”, “VERB”]的概率只有0.1∗1.00.10.1*1.00.10.1∗1.00.1而[“ARTICLE”, “NOUN”]的概率有0.9∗0.30.270.9*0.30.270.9∗0.30.27。这是因为以cat为开头的句子模型见的很少。如果可以在计算当中把模型见的很少这个信息也带上的就可以避免这个问题了。
下面来看下图3-2对应的逻辑图如下图3-3所示就是没有归一化的图。
图3-3 逻辑值推理图归一化是exe^xex这样的指数归一化可以动手算下看是和图3-2的概率值对应上的。这里[“cat”, “sat”]这个例子的[“NOUN”, “VERB”]就是310010331001033100103而[“ARTICLE”, “NOUN”]就变成了521265212652126。用加法是因为这里都是log值。
这里就说这么多只是给个直观的理解想要细究的可以看下The Label Bias Problem或是自行搜一下其他大佬是怎么说的。
4 CRF
4.1 模型概述
有了前面那么多的铺垫CRF(conditional random filed)就很容易理解了。MEMM是对式(3−4)(3-4)(3−4)进行建模而CRF是对式(4−1)(4-1)(4−1)进行建模
p(y1,...,ym∣x1,...,xm)p(yˉ∣xˉ)(4-1)p(y^1, ..., y^m|x^1, ..., x^m) p(\bar{y}|\bar{x}) \tag{4-1} p(y1,...,ym∣x1,...,xm)p(yˉ∣xˉ)(4-1)
注意式(2−1)(2-1)(2−1)式(3−4)(3-4)(3−4)和式(4−1)(4-1)(4−1)的区别。CRF没有局部的归一化了只有全局的归一化说白了就是一个考虑序列的log-linear模型。
p(yˉ∣xˉ;wˉ)exp(wˉ⋅Φˉ(xˉ,yˉ))∑yˉ′∈Ymexp(wˉ⋅Φˉ(xˉ,yˉ′))(4-2)p(\bar{y}|\bar{x};\bar{w}) \frac{exp(\bar{w} \cdot \bar{\Phi}(\bar{x}, \bar{y}))}{\sum_{\bar{y} \in Y^m} exp(\bar{w} \cdot \bar{\Phi}(\bar{x}, \bar{y}))} \tag{4-2} p(yˉ∣xˉ;wˉ)∑yˉ′∈Ymexp(wˉ⋅Φˉ(xˉ,yˉ′))exp(wˉ⋅Φˉ(xˉ,yˉ))(4-2)
其中YmY^mYm表示用YYY中的元素组成长度为mmm的序列的所有可能的序列集合。
这里还把ϕˉ\bar{\phi}ϕˉ变成了Φˉ\bar{\Phi}ΦˉΦˉ\bar{\Phi}Φˉ的定义为
Φˉ(xˉ,yˉ)∑j1mϕˉ(xˉ,j,yj−1,yj)(4-3)\bar{\Phi}(\bar{x}, \bar{y}) \sum_{j1}^{m} \bar{\phi}(\bar{x}, j, y^{j-1}, y^{j}) \tag{4-3} Φˉ(xˉ,yˉ)j1∑mϕˉ(xˉ,j,yj−1,yj)(4-3)
这里的ϕˉ(xˉ,j,yj−1,yj)\bar{\phi}(\bar{x}, j, y_{j-1}, y^{j})ϕˉ(xˉ,j,yj−1,yj)和MEMM中的是一模一样的都是人为定义的特征函数。只不过是把整个序列的都加到了一起。
CRF的概率图模型如下图4-1所示它和图3-1的区别是yjy^jyj之间变成了无向图。还是那句话不看这个图也没问题。
图4-1 CRF概率图4.2 模型训练
CRF的模型训练和log-linear模型的方法基本一致。简而言之就是我们有nnn条训练样本{(xˉi,yˉi)}i1n\{(\bar{x}_i, \bar{y}_i)\}_{i1}^n{(xˉi,yˉi)}i1n每个xˉi\bar{x}_ixˉi都是序列xi1,...,ximx_i^{1}, ..., x_i^{m}xi1,...,xim每个yˉi\bar{y}_iyˉi也都是序列yi1,...,yimy_i^{1}, ..., y_i^{m}yi1,...,yim。
其目标函数为
wˉ∗argmaxwˉ∑i1nlog(p(yˉi∣xˉi;wˉ))−λ2∣∣wˉ∣∣2(4-4)\bar{w}^* arg \max_{\bar{w}} \sum_{i1}^n log(p(\bar{y}_i|\bar{x}_i;\bar{w})) - \frac{\lambda}{2}||\bar{w}||^2 \tag{4-4} wˉ∗argwˉmaxi1∑nlog(p(yˉi∣xˉi;wˉ))−2λ∣∣wˉ∣∣2(4-4)
接下来的任务就交给梯度下降就可以了。
4.3 模型解码
CRF进行decoding目标是
argmaxyˉ∈Ymp(yˉ∣xˉ;wˉ)argmaxyˉ∈Ymexp(wˉ⋅Φˉ(xˉ,yˉ))∑y′∈Yexp(wˉ⋅Φˉ(xˉ,yˉ′))argmaxyˉ∈Ymexp(wˉ⋅Φˉ(xˉ,yˉ))argmaxyˉ∈Ymwˉ⋅Φˉ(xˉ,yˉ)argmaxyˉ∈Ym∑j1mwˉ⋅ϕˉ(xˉ,j,yj−1,yj)(4-5)\begin{aligned} arg\max_{\bar{y} \in Y^m} p(\bar{y}|\bar{x};\bar{w}) arg\max_{\bar{y} \in Y^m} \frac{exp(\bar{w} \cdot \bar{\Phi}(\bar{x}, \bar{y}))}{\sum_{y \in Y} exp(\bar{w} \cdot \bar{\Phi}(\bar{x}, \bar{y}))} \\ arg\max_{\bar{y} \in Y^m} exp(\bar{w} \cdot \bar{\Phi}(\bar{x}, \bar{y}))\\ arg\max_{\bar{y} \in Y^m} \bar{w} \cdot \bar{\Phi}(\bar{x}, \bar{y}) \\ arg\max_{\bar{y} \in Y^m} \sum_{j1}^{m} \bar{w} \cdot \bar{\phi}(\bar{x}, j, y^{j-1}, y^{j}) \end{aligned} \tag{4-5} argyˉ∈Ymmaxp(yˉ∣xˉ;wˉ)argyˉ∈Ymmax∑y′∈Yexp(wˉ⋅Φˉ(xˉ,yˉ′))exp(wˉ⋅Φˉ(xˉ,yˉ))argyˉ∈Ymmaxexp(wˉ⋅Φˉ(xˉ,yˉ))argyˉ∈Ymmaxwˉ⋅Φˉ(xˉ,yˉ)argyˉ∈Ymmaxj1∑mwˉ⋅ϕˉ(xˉ,j,yj−1,yj)(4-5)
ϕˉ(xˉ,j,yj−1,yj)\bar{\phi}(\bar{x}, j, y^{j-1}, y^{j})ϕˉ(xˉ,j,yj−1,yj)有一部分是和yj−1y^{j-1}yj−1有关的称为转移特征还有一部分是和yj−1y^{j-1}yj−1无关的称为状态特征。这里杂到一起了可以不用关心。
解码的方法还是用的动态规划同样定义一个π[j,s]\pi[j, s]π[j,s]。
初始概率为
π[1,y]wˉ⋅ϕˉ(xˉ,1,y0,y)(4-6)\pi[1, y] \bar{w} \cdot \bar{\phi}(\bar{x}, 1, y^{0}, y) \tag{4-6} π[1,y]wˉ⋅ϕˉ(xˉ,1,y0,y)(4-6)
概率的迭代式为
π[j,y]maxy′∈Y(π[j−1,y′]wˉ⋅ϕˉ(xˉ,j,y′,y))(4-6)\pi[j, y] \max_{y \in Y} (\pi [j-1, y] \bar{w} \cdot \bar{\phi}(\bar{x}, j, y, y)) \tag{4-6} π[j,y]y′∈Ymax(π[j−1,y′]wˉ⋅ϕˉ(xˉ,j,y′,y))(4-6)
求出所有的π[j,y]\pi[j, y]π[j,y]之后就可以得到概率最大的那条路径
maxy1,...,ym∑j1mwˉ⋅ϕ(xˉ,j,yj−1,yj)maxyπ[m,s](4-7)\max_{y^1, ..., y^m} \sum_{j1}^{m} \bar{w} \cdot \phi (\bar{x}, j, y^{j-1}, y^j) \max_{y} \pi[m, s] \tag{4-7} y1,...,ymmaxj1∑mwˉ⋅ϕ(xˉ,j,yj−1,yj)ymaxπ[m,s](4-7)
4.4 小结
CRF既解决了HMM观测独立不合理的问题也解决的MEMM中label bias的问题并且可以手动加入特征函数来干预模型的输出有些不可能的情况可以手动把转移概率设得很小即可。
一般会把CRF加在Bi-LSTM之后让序列模型的输出更可控。如果数据够多且够均衡的话CRF也是可以不加的。
参考资料
[1] Log-Linear Models, MEMMs, and CRFs [2] https://anxiang1836.github.io/2019/11/05/NLP_From_HMM_to_CRF/ [3] https://pytorch.org/tutorials/beginner/nlp/advanced_tutorial.html [4] https://www.bilibili.com/video/BV19t411R7QU?p4share_sourcecopy_web [5] The Label Bias Problem
