CRF学习——基础学习

CRF是NLP中很常用且经典的模型,今天就复习一下CRF模型。

参考:
https://arxiv.org/abs/1011.4088
http://cseweb.ucsd.edu/~elkan/250Bwinter2012/loglinearCRFs.pdf

前言

生成模型 VS 判别模型

下面这张图展示了生成模型和判别模型的联系和区别:这两种模型都是用极大似然估计来估计概率,只是两个估计的概率公式不同,生成模型是$p(x, y)$,判别模型是$p(y|x)$。为什么生成模型能生成数据呢,因为$p(x, y) = p(y) * p(x|y)$,我们可以学习到$p(x|y)$,那么当我们采样y时,就可以根据它生成x了。

图片

生成模型可以用于生成,也可以用于判别。但判别模型只能用于判别。生成模型需要学习到更多有关数据的细节。比如有很多猫和狗的图片,对于生成模型,它就会学到很多猫和狗的长什么样的细节(因为学不到的话它也生成不出来);但对于判别模型,主要学习到猫和狗的区别,如下图:

图片

生成模型的目标函数是P(x, y),而判别函数是P(y|x)。转化$P(x,y)=P(y)P(x|y)$,也就是生成模型学习到的一个是$P(x|y)$,比如对于y=猫来说,能学习到一个x的分布(即猫的特征分布,有时这个分布用高斯分布去模拟),如下图:

图片

那怎么生成呢?事实上我们可以从$P(x|y=猫)$这个分布中去采样一个x(比如对于图片来说,x就是像素矩阵),而这个x就是一个猫的图片了。下面再以预测男、女身高为例,做一个生成模型,过程如下图(当需要生成时,直接从正太分布x~$N(\mu, \sigma^2$)中采样即可):

图片

那么在判别问题上,哪个模型效果更好呢?从生成视角看,生成式建模的是$P(x,y)=P(y)P(x|y)$,从判别视角看,生成式建模的是$P(x,y)=P(x)P(y|x)$。而判别式建模的就是$P(y|x)$。也就是两类模型都去做了判别$P(y|x)$,而生成模型同时学习了$P(x)$(可以理解成一个prior)。从直观上感觉,只做一件事情的判别模型会更好。因为生成模型要同时兼顾$P(x)$和$P(y|x)$,它要找到这两者之间的一个平衡点。因此,我们可以得出以下结论:

  • 当数据量大时,使用判别模型会优于生成模型
  • 当数据量小时,生成模型有可能比判别模型要好(因为生成模型有prior,即p(x),有时为了防止过拟合,会在模型中加入正则项,其实这个正则项就是一个prior)

【注】:上面提到的p(x, y)、p(x|y)其实是所有概率的乘积,即图片

Directed Model VS Undirected Model

有明确依赖关系的叫有向图。比如做金融风控,如下图:

图片

没有依赖关系的叫无向图。比如在做Image Segmentation时,需要对每个点进行分类。如果把每个点看成时独立的话,缺少了像素点之间的联系。因此可以把它看成一个graphic model。因为点之间很难有方向的关系,因此使用无向图:

图片

Joint Probability

使用联合概率来建模图模型(后续可以用这个联合概率进行分类)。有向图的联合概率很好写:

图片

在生成模型HMM中,其概率公式如下图:

图片

无向图有两种方法建模:

  • Maximal Clique方法:先分成团,每个团用score function计算一个契合度。而这个契合度和团里的元素的联合概率是正相关的,因此这个score function也可以用联合概率表示,如下图:

图片

  • Pair-wise

图片

【注】:

  • 因为score function得出的是一个相对值,不同feature、不同算法得出的结果不一样。但最后我们是想得到P(1,2,3,4,5)这个联合概率的绝对值的(后续做判别时会用到),因此我们除以了一个归一化项z。这个z要考虑所有可能的情况,在实际情况中我们可以使用维特比来简化计算量。
  • z是一个global normalization,使用这种全局的归一化有一个好处,就是图中的结点是有一个偏好的,但是z是一个全局的量,可以修正结点的偏好,使得模型考虑得更加全面。
  • 在有向图中使用的是local normalization,比如P(4|2,5)只需要关注P(2,5),因此有向图是从局部角度考虑的
  • z的计算量比较大,如果变量是离散型的,则可以使用维特比算法;如果变量是连续型的,则只能使用一些近似算法(partition funciton,比如MCMC)

接下来有一个问题,这个score function究竟是怎么计算出来的呢?

首先,我们假设score function计算的是变量之间的compatability。所以,变量之间关系越紧密,则score function结果越大。例如,假设a、b、c是三位学生,他们在一起做项目。则score function可以表示三位学生合作的结果。他们关系越好,合作越紧密,则得分越高。紧接着,我们要考虑这三位学生的一些特征。我们要选择一些特征,能刻画出三位学生是否能合作好。比如三个学生是否来自同一个班级(f1),以及他们之前是否合作过(f2),以及他们之间的能力是否互补(f3)等等。我们可以把这些特征做一个线性组合来得到score(linear model)。当然也可以使用非线性的方式构造score function,这个时候就是log-linear crf。下图概括了这个过程:

图片

图片

特征工程一般分两种,一种是人工特征,另一种是使用深度学习特征(比如BiLSTM-CRF,卷积核等)。

RoadMap

我们通过对特征函数进行不同假设,可以得到不同模型:

图片

由上图可以看到,假设特征函数是线性函数时,可以产生Log-Linear Model(顾名思义,就是对score funciton先取linear,再取log)。Log-Linear Model的具体模型常见的有逻辑回归和Linear-Chain CRF。那么从另一个角度,有向图模型HMM对于NLP问题有一些缺陷,我们把它从生成模型改造成一个判别模型MEMM,但MEMM有Label Bias的问题,因此我们又把MEMM改成一个无向图模型,就得到了Linear Chain CRF。对于Linear Chain CRF,我们关心的是它的参数估计和Inference算法。因为它也属于Log-Linear Model,所以我们要先学习的是Log-Linear Model的参数估计和Inference。

当然,如果我们假设特征函数是非线性的,会得到Non-linear CRF。

图片

上面这张图是更简明一些的roadmap。对于生成模型,最简单的是朴素贝叶斯,当数据是一条链时,就是HMM,当数据是一个图的时候,就是贝叶斯网络。对于判别模型,最简单的是逻辑回归,当是一条链是就是CRF,当是一个图时就是更general的CRF。

Log-Linear Model

首先我们来看这样一个无向图模型和它的联合概率(用all cliques方法定义联合概率):

图片

那么接下来的问题就是,如何去定义这个score function呢?我们用一个指数函数计算score:

图片

上图式子计算了一个clique的分数,其中$F_j(y_c)$是特征函数。比如$y_1$-$y_2$-$y_3$这个无向图中,我们有2个特征,分别就是$F_1(y_1, y_2, y_3)$、$F_2(y_1, y_2, y_3)$。也就是说,每一个clique里可以抽取出J个特征(每个特征都是一个数)。$w_j*F_j(y_c)$就是一个线性函数,整个模型的参数$\theta={w}$。

那么F特征是什么呢?F主要评估了变量之间的契合度。那为什么这个模型叫Log-Linear呢?看下图就知道了:

图片

下面用文本的一个例子来说明计算这个联合概率的过程:

图片

Multinomial Logistic Regression

我们可以将逻辑回归看成是x、y的一个无向图:

图片

那么逻辑回归的条件概率是什么呢?(这里我们把每个标签作为一个clique)

图片

其中特征函数f_j定义如下,可以看出来我们并没有做特征工程,而是把输入x_j直接看成是特征:

图片

那么一共有多少特征呢?如果标签y有3个(即y={1,2,3}),x的维度为d,则特征总个数为3d,即J=3d。比如,我们分别令y = 1, 2, 3,则$f_j$的具体值如下:

图片

接着,我们把$f_j$的值带入到$P(y|x;\theta)$中:

图片

可以看出来,参数w的维度是3d。我们把上面式子在形式上进行一些简化:

图片

可以看出来这就是一个多元逻辑回归模型(可以用在多分类问题上)。

HMM存在的一些问题

MEMM

假设我们用HMM做词性标注,构建如下模型,会发现有什么问题?

图片

很显然,对于词性标注而言,词性$z_1$不仅仅只依赖于当前词$x_3$,还可能跟其他词有关。那么怎么改进这个模型呢?为了让$z_1$跟所有词相关,我们把它改造成下图:

图片

但上图这个模型又有什么问题呢?我们先写一下上图的联合概率:

图片

可以发现上式中第二项,也就是发射概率,是很难表示的。如果说联合概率很难表示,能不能把它改造成一个判别模型呢,用条件概率去表示呢?下图就是改造后的判别模型:

图片

我们可以看出来上图中$P(z_i|z_{i-1}, x)$是很好表示的(比如用一个线性函数+softmax),那么这个模型就是MEMM模型。下面这张图是MEMM的另一种表示:

图片

但是MEMM有什么问题呢?

Label Bias Problem

首先,我们来看一看什么叫Label Bias。我们先来看下图,哪一条路径的概率最大呢?

图片

很明显,分支比较多的状态的概率概率较小(相对而言不对它们不是很公平),分支较少的路径概率更大。举个例子,做词性分析时,动词的后面可能的词性较少,名词后面的词性就比较多。Label bias的根本原因是local normalization。那么怎么解决这个问题呢?

我们可以把概率换成是score来表示,有了分数,我们就可以用global normalization了。这也就是无向图和有向图的主要区别,如下图:

图片

我们可以将(z1, z2)、(z2, z3)、(z3, z4)看成是clique,计算(z1, z2, x)等的feature function (f1, f2, f3, …f10),再进行加权,就有了score。

从Log-linear Model到Log-linear CRF

我们直接从Log-linear的公式进行推导,其实就是把特征函数$f_j(x,y)$表示出来。在无向图中我们把这个特征写成是$F_j(x,y)$(这里的x、y可以看成是一个时间的序列,而不是一个单独的变量)。由于y是一个状态集合,因而(x,y)的特征函数由(y1, y2, x)、(y2, y3, x)、(y3, y4, x)…组成,因此$F_j(x,y)=sum(f_j(y_i, y_{i-1}, x))$。如下图:

图片

$f_j$可以通过人工,或者神经网络的方式得到,接下来就是求解$w_j$。我们的目标是最大化似然函数:图片,因此选择好一个优化方法,就可以求解$w_j$了(比如将loss作为分子对w求偏导)。

【注】:

  • 上式中T是团的个数,在实践序列中,就是timestep-1
  • 上式中exp有两个sum,其中第一个sum是对每个clique的结果求和(因为我们要把所有clique的结果乘起来),第二个sum是对每个clique内部所有特征的加和。?好像写反了
  • $f_j(y_i, y_{i-1}, x)$中的$f_j$在神经网络中常使用softmax
  • $f_j(y_i, y_{i-1}, x)$中的的x可以理解为x1, x2,…,即特征是根据$y_i, y_{i-1}$和所有的x计算出来的,即$f_j(y_i, y_{i-1}, x_1, x_2, …)$

Log-linear CRF

我们的目标是求解:

图片

看上去跟逻辑回归差不多,只不过这里的x、y是时间序列。

Inference Probelm

首先我们来看一下,在x、w已知的情况下,我们怎么求解使得P(y|x;w)最大的y。这看上去和逻辑回归没有区别哈,逻辑回归里y={0,1},这里的y是一个序列。

我们先把式子按照定义展开:

图片

看到上面的形式,我们应首先想到维特比算法,一想到维特比算法,就要想到路径,路径的sum值是最大的,如下图(n是时间长度,m是状态个数):

图片

我们定义的子问题是:$u(k, v)$表示从$t=1$到$t=k$,且t时刻的状态为v的最好的路径的分数。我们最终想求的是$max(u(n, 1)$、$u(n, 2)$… $u(n, m))$为最终答案,如下图:图片

那么我们怎么把$u(k, v)$表示成一个子问题呢?从t=1到t=k一定会经过$u(k-1, 1)$或$u(k-1, 2)$…或$u(k-1, m)$,如下图:

图片

我们用式子表达出来是:图片

看上去,我们把这个二维的矩阵里的score值逐步填充进去就可以了。当想求解最佳状态的路径时,只需要设置好pointer,反向就能从矩阵中找到最佳路径了。整个算法的复杂度是O(mn)O(m)。

【注】:如果score函数是$g_i(y_{i-2}, y_{i-1}, y_{i})$,那么算法复杂度就可能变为$O(m^2n)O(m)$

Parameter Estimation

Log-Linear的w求解

接下来我们来看,在x、y已知的情况下,我们怎么求解w?求导数就好了。我们先来看一下Log-Linear的w是怎么求解的:

图片

上式中最后一项可以看成是$F_j(x, y’)$的期望:

图片

可以看到第一项$F_j(x, y)$是x、y的特征工程,后一项是关于y’的期望。

Log-Linear CRF的w求解

  • 求解partition function z
    • Forward算法:在CRF中,partition function z(x, w)中的x变成了一个序列,我们来看一下这个z怎么计算。我们依然可以使用动态规划算法求解$sum(g_i(y_{i-1}, y_i))$。具体如下图所示:图片

上图中$\alpha(k+1, v)$表示$y_{k+1}=v$的情况下,所有状态的可能性。为了求解$\alpha(k+1, v)$,我们把$y_k$作为一个中介,而$y_k$有1~u种可能。举个栗子,假如有4个状态,3个输出,那么我们最后想求$\alpha(4, 1)+\alpha(4,2)+\alpha(4,3)$的和作为z(x, w)​,且$\alpha(4,1)=\alpha(3,1) + \alpha(3,2) + \alpha(3,3)$,如下图:图片

  • Backward算法:跟Forward相似,只不过是$y_k=u$时考虑${y_k{k+1}, y_n}$的所有可能性,这时候$y_{k+1}$成为了中介。

    图片图片

  • 求解$P(y_k=u|x;w)$

    • $z(x, w)$是考虑所有的可能性,因此可以认为$z(x, w)=p(y_k=1|x;w) + p(y_k=2|x, w) + … + p(y_k=m|x;w)$
    • 根据前向算法和后向算法,可以算出$z(x, w)$
    • $p(y_k=u|x;w)$表示$y_k=u$的情况下,前向和后向的所有可能情况,如下图:

图片

为了求出w,我们需要对$p(y|x;w)$求导,

图片