CRF

2019-01-15

Words= 2.4k | Time≈ 10min

NLP-序列标注三大模型HMM、MEMM、CRF

对于HMM，MEMM，CRF需要结合概率图的层面上理解和记忆，这几个模型主要用在了序列标注上，这篇笔记针对这三个模型进行公式推导，加深理解。

生成模型 & 判别模型

生成模型

生成模型学习的是联合概率$p(x,y)=p(x|y)p(y)$，然后利用贝叶斯定理来求解后验概率$p(y|x)$

$$p(y|x) = \frac{p(x|y)p(y)}{\sum_{y{}’ \epsilon \gamma} p(x|y{}’)p(y{}’)}$$

常见的生成模型有：朴素贝叶斯（NB），HMM

判别式模型

直接学习$p(y|x)$，判别式模型根据所提供的feature直接学习一个分类边界

常见的判别式模型：神经网络，SVM，CRF

1579078407329

对数线性模型（log-linear model）

对于有一系列输入数据$χ$ ，和一系列标签数据 $γ$，如何通过这些标注数据来求解 p(y|x)p(y|x) 呢？一般可以用对数线性模型来求解，也就是判别模型一般可以通过对数线性模型来建模，常见的最大熵模型、softmax、MEMM、CRF都使用了对数线性模型。

对数线性模型形如：

$$p(y|x) = \frac{p(x|y)p(y)}{\sum_{y{}’ \epsilon \gamma} p(x|y{}’)p(y{}’)}$$

其中有：

输入集合 $χ$
标签集合 $γ$
$wϵRdwϵRd$ 是模型的参数
$x$, $yϵγ$
特征函数 $f:χ×γ→Rd$
$f(x,y)$ 可认为对输入输出同时抽取特征

对数线性模型表示的意义为：在条件$x$以及参数$w$下发生$y$的概率，一般$w$是要学习的参数

分类问题和序列标注问题

分类问题

分类问题一般是对输入进行建模得到语义编码（如可以使用RNN，CNN进行编码）然后经过分类器将空间映射到分类空间上，最后可通过softmax将权重归一化得到映射到各个分类空间的概率，取概率最大的作为分类。

序列标注问题

序列标注问题的重点在于学习序列位置之间的关系，然后解码出最大概率标签路径，比如有$K$个标签，当输入序列长度为$m$时，那么就有$K^m$条概率路径，序列标注问题是要从$K^m$条概率路径中寻找到概率最大的那条路径。NLP中常见的任务，如分词，词性标注，命名体识别都属于序列标注问题。

HMM

之前已经说了HMM是生成模型，它引入了一阶马尔科夫假设：当前状态只与上一状态有关。结合这两点可以得到联合概率

$$p(x1…xm,s1…sn)=∏tp(st|st−1)p(xt|st)$$

$p(st|st−1)p(st|st−1)$称为状态间的转移概率，称为发射概率（由隐状态发射成显状态的概率）

由图可知HMM是一个有向图。

HMM的解码部分是求解：$argmaxs1…sm p(x1…xm,s1…sm)$, 通常采用Viterbi算法解码

HMM的特点

HMM有两个独立性假设：

观测序列之间是独立的
当前状态仅依赖于先前的状态

MEMM

Max Entropy Markov Model最大熵马尔可夫模型，在最大熵的基础上引入了一阶马尔科夫假设。 MEMM属于判别式模型，它要学习条件概率

$$p(s_{1}…s_{m}|x_{1}…x_{m}) = \prod_{i=1}^{m}p(s_{i}|s_{1}…s_{i-1}, x_{1}…x_{m}) $$

由于引入了一阶马尔科夫假设，故当前状态仅于前一状态有关

$$p(s_{1}…s_{m}|x_{1}…x_{m}) = \prod_{i=1}^{m}p(s_{i}|s_{i-1}, x_{1}…x_{m})$$

而最大熵模型是对数线性模型从而得到MEMM的模型表达式

$$p(s_{i}|s_{i-1}, x_{1}…x_{m}; w) = \frac{exp(w \cdot \phi (x_{1}…x_{m}, i, s_{i-1}, s_{i}))}{ \sum {s{}’ \epsilon S} exp(w \cdot \phi (x{1}…x_{m}, i, s_{i-1}, s{}’) ) }$$

$\phi (x_{1}…x_{m}, i, s_{i-1}, s{}’)$ 是一个特征函数，其中有：

ii 代表当前被标记的位置
ss 先前的状态
s′s′ 当前的状态

故有

$$\begin{align} p(s_{1}…s_{m}|x_{1}…x_{m}) &= \prod_{i=1}^{m} p(s_{i}|s_{i-1}, x_{1}…x_{m}) \ &= \prod_{i=1}^{m}\frac{exp(w\cdot \phi (x_{1}…x_{m}, i, s_{i-1}, s_{i}))}{\sum {s{}’\epsilon S}exp(w\cdot \phi (x{1}…x_{m}, i, s_{i-1}, s{}’))} \ &= \frac{exp(\sum {i} w\cdot \phi (x{1}…x_{m}, i, s_{i-1}, s_{i}))}{\sum {s{}’\epsilon S}exp(w\cdot \phi (x{1}…x_{m}, i, s_{i-1}, s{}’))} \tag{1} \end{align}$$

MEMM解码部分是计算 $arg \underset{s_{1}…s_{m}}{max}\ p( s_{1}…s_{m}|x_{1}…x_{m})$，为了好理解我做了一步步简化

$$\begin{align} arg \underset{s_{1}…s_{m}}{max}\ p( s_{1}…s_{m}|x_{1}…x_{m}) &= arg \underset{s_{1}…s_{m}}{max}\ \prod_{i=1}^{m}p( s_{i}|s_{i-1} ,x_{1}…x_{m}) \ &= arg \underset{s_{1}…s_{m}}{max}\ p( s_{i}|s_{i-1}, x_{1}…x_{m} ) \ &= arg \underset{s_{1}…s_{m}}{max}\frac{exp(w\cdot \phi (x_{1}…x_{m}, i, s_{i-1}, s_{i}))}{\sum {s{}’\epsilon S}exp(w\cdot \phi (x{1}…x_{m}, i, s_{i-1}, s{}’))} \ &= arg \underset{s_{1}…s_{m}}{max}\ exp(w\cdot \phi (x_{1}…x_{m}, i, s_{i-1}, s_{i})) \ &= arg \underset{s_{1}…s_{m}}{max}\ w\cdot \phi (x_{1}…x_{m}, i, s_{i-1}, s_{i}) \tag{2} \end{align}$$

也即是编码等价于求解公式(2)(2)，通常用viterbi算法求解，如果不采用viterbi求解它的算法复杂度是O(Km)O(Km) ，采用了viterbi算法可以降到O(mK2)O(mK2)，(KK 为隐状态数目, mm为观测序列长度)

[

如图，MEMM也是有向图模型。

MEMM的优点

克服了HMM输出独立性问题，通过引入特征函数使得模型比HMM拥有更多信息，而且最大熵则从全局角度来建模，它“保留尽可能多的不确定性，在没有更多的信息时，不擅自做假设”

MEMM的缺点

标签偏置(labeling bias)问题，由于MEMM的当前状态只与当前观测以及上一状态有关，导致隐状态中有更少转移的状态拥有的转移概率普遍偏高（是不是一头雾水，再没有更好的解释之前只能继续一头雾水了）简单的说就是MEMM中概率最大路径更容易出现在转移少的状态中。如何解决这个问题呢？引入全局化特征可以解决标签偏置问题，下文的CRF其实就在MEMM上加入全局化特征从而解决标签偏置问题

CRF

Conditional Random Forest条件随机场，这里主要讲解线性链（linear-chain）,这里不会牵扯太多概率图的东西（因为我也不会啊:<）还是从对数线性模型出发。首先要明确的一点是CRF也属于判别模型，所以和MEMM一样需要对

$$p(s1…sm|x1…xm)p(s1…sm|x1…xm)$$

建模，CRF也和MEMM一样做了一阶马尔科夫假设，即当前状态只与上一状态有关，但是区别在于CRF的特征采用了全局特征，它把观测序列当做整体来看所以它的特征函数是全局的，它的特征函数为：

$$φ(x1…xm,s1…sm)=∑j=1mϕ(x1…xm,j,sj−1,sj)φ(x1…xm,s1…sm)=∑j=1mϕ(x1…xm,j,sj−1,sj)$$

其中 ϕϕ 和MEMM的特征函数是一致的，接下来的步骤和MEMM差不多了，只是特征函数变为了φφ，为了连续性在此再走一遍流程。

CRF的模型表达式为：

$$p(si|si−1,x1…xm;w)=exp(w⋅φ(x1…xm,i,si−1,si))∑s′ϵSexp(w⋅φ(x1…xm,i,si−1,s′))p(si|si−1,x1…xm;w)=exp(w⋅φ(x1…xm,i,si−1,si))∑s′ϵSexp(w⋅φ(x1…xm,i,si−1,s′))$$

CRF的解码部分是计算 $argmaxs1…sm p(s1…sm|x1…xm)argmaxs1…sm p(s1…sm|x1…xm)$，一步步进行简化

$$argmaxs1…sm p(s1…sm|x1…xm)=argmaxs1…sm∏i=1mp(si|si−1,x1…xm)=argmaxs1…sm p(si|si−1,x1…xm)=argmaxs1…smexp(w⋅φ(x1…xm,i,si−1,si))∑s′ϵSexp(w⋅φ(x1…xm,i,si−1,s′))=argmaxs1…sm exp(w⋅φ(x1…xm,i,si−1,si))=argmaxs1…sm w⋅φ(x1…xm,i,si−1,si)=argmaxs1…sm ∑jmw⋅ϕ(x1…xm,i,si−1,si)(3)argmaxs1…sm p(s1…sm|x1…xm)=argmaxs1…sm∏i=1mp(si|si−1,x1…xm)=argmaxs1…sm p(si|si−1,x1…xm)=argmaxs1…smexp(w⋅φ(x1…xm,i,si−1,si))∑s′ϵSexp(w⋅φ(x1…xm,i,si−1,s′))=argmaxs1…sm exp(w⋅φ(x1…xm,i,si−1,si))=argmaxs1…sm w⋅φ(x1…xm,i,si−1,si)(3)=argmaxs1…sm ∑jmw⋅ϕ(x1…xm,i,si−1,si)$$

对比一下(2)和(3)可知道CRF和MEMM的区别。和MEMM一样，一般采用viterbi算法来进行解码。