NLP 手册

条件随机场 CRF

Posted by Pelhans on August 26, 2019

条件随机场

马尔科夫随机场

有向图模型表示将一组变量上的联合概率分布分解为局部条件概率分布的乘积. 有向图也定义了一组条件独立性质, 根据图进行分解的任何概率分布都必须满足这些条件独立性质. 例如, 下图中贝叶斯网络(有向图)的联合概率分布(出自百面机器学习)为:

因为 在给定A的条件下B和C是条件独立, 因此:

同理,在给定B和C的条件下 A 和D 是条件独立的:

因此联合概率为:

无向图也表示一个分解方式, 一组条件独立关系.一个马尔科夫随机场, 也被称为马尔科夫网络或者无向图模型,包含一组节点,每个节点都对应着一个变量或者一组变量.链接是无向的,不含有箭头.

条件独立性质

假设我们有三个节点集合, 记作 A,B,C. 我们考虑条件独立性 在给定C的情况下 A独立于B的性质.如果所有这些路径都通过了集合C中的一个或者多个节点, 那么所有这样的滤镜都被”阻隔”, 因此条件独立性质成立.

条件独立性的一种比较简单的检测方法是假设从图中把集合 C中的节点以及与这些节点相连的链接全部删除.而后看是否存在一条从A 到B中任意节点的路径.如果没有,则条件独立性质一定成立.

分解性质

我们现在需要将图上得的联合概率分布$p(x)$分解为在图的局部范围内得变量集合上定义的函数的乘积. 因为 , 这个局部范围要求为我们的分解一定要让 A 和B 不出现在同一因子中, 从而让属于这个图的所有可能的概率分布都满足条件独立的性质.

因此需要团块的概念, 它的定义是图中节点的一个子集, 团块中的节点集合是全连接的.最大团快定义为将图中得任何一个其他节点加入到这个团块中都会破坏团的定义.现在我们可以将联合概率分布分解的因子定义为团块中变量的函数.为了方便,我们可以采用最大团块的函数而不是一般性,这是因为其他团块一定是最大团块的子集.

现在我们将团块定义为 C, 将团块中的变量定义为 $x_{C}$, 这样联合概率分布可以写成图的最大团块的势函数 $\psi_{C}$ 的乘积形式:

其中 Z 被定义为 划分函数, 是一个归一化常数, 等于:

它确保了上式给出的概率分布被正确的归一化.它的精确计算是非常困难的,不过好在很多任务都不需要Z的精确值. 同时势函数我们只考虑值大于等于零的, 确保概率大于等于0. 势函数通常也不具有具体的概率含义.

因为势函数被限制为严格非负, 因此将势函数表示为指数的形式更方便, 即:

势函数可以看作一种度量,它表示了局部变量的哪种配置优于其他的配置.

其中 $E(x_{C})$ 被称为能量函数, 指数表示被称为玻尔兹曼分布. 联合概率分布被定义为势函数的乘积.因此总的能量可以通过将各个团块的能量相加的方法得到.

常见的能量函数的形式为:

其中 $ \beta_{v}, \alpha_{u,v}$ 表示系数. $ t_{u,v}(u,v), s_{v}(v)$ 表示约束条件, 如CRF中的特征函数. 第一项考虑每一对节点之间的关系, 第二项考虑单个节点.

例子: 图像去噪

取一张图片, 它的每个像素点是二值的{+1, -1}, 作为原始图像, 噪声图像是在原始图像基础上, 随机翻转10%像素点的值. 现在我们的目标是恢复噪声图像.

假设原始图像为 $X = {x_{1}, x_{2}\dots, x_{n}}$, 噪声图像为 $Y = {y_{1}, y_{2},\dots,y_{n}}$. 我们知道 $x_{i}$与 $y_{i}$ 间存在强烈的相关性, $x_{i}$, $x_{j}$ 间也存在强烈相关性. 因此我们假设团块包含两种:

  • ${x_{i}, y_{i}}$, 对应一种能量函数, 我们取一个简单得形式 $-\eta x_{i}y_{i}$,$\eta$为正, 即 x,y 符号相同时, 能量低.
  • ${x_{i}, x_{j}}$, 形式 $-\beta x_{i}x_{j}$, $\beta$为正,表示 $x_{i}, x_{j}$相同时能量低.

除此之外再添加一个$hx_{i}$作为偏置. 因此模型的能量函数为:

带入势函数得到联合概率分布.我们现在希望找到一个具有较高的概率的图像 x, 因此可以用一个简单的 迭代算法 ICM 或者模拟退火算法等进行求解.

条件随机场

条件随机场是判别模型, 针对条件概率进行建模.被广泛应用到 词性标注, 句法分析等自然语言处理任务中. 它的定义为:

令 G=<V,E> 表示与观测变量序列 X 和 标记变量序列Y 对应的无向图. $Y_{v}$表示与节点 v 对应的标记随机变量, n(v) 表示节点 v 的邻接节点集. 若图G中节点对应的每个变量 $Y_{v}$ 都满足马尔可夫性, 即 $ P(Y_{v}|X, Y_{V-{v}}) = P(Y_{v}|X, Y_{n(v)}) $, 那么 $(Y,X)$ 构成了一个条件随机场.

条件随机场作为无向图的一种, 具有多种形式, 不过最常见的还是链式CRF, 如下图所示:

给定观测变量序列 X, 链式条件随机场主要包含两种关于标记变量的团:

  • 单个标记变量与 X 构成的团: ${Y_{i}, X}$
  • 相邻标记变量与X构成的团: ${Y_{i}, Y_{i-1}, X}$

CRF 对条件概率 $P(Y|X)$ 建模,根据前面无向图的公式形式, 其条件概率公式形式为:

其中 K1 为转移特征函数的个数, K2 为状态特征的个数. t 为转移特征函数,刻画了相邻标记变量间的关系, s 是状态函数,表示观测序列X 对标记变量的影响.

特征函数通常是实值函数, 用来刻画数据的一些很可能成立或者预期成立的经验特性. 如:

转移特征函数表示,当第i个观测值 为 “knock”时, 相应的标记Yi 和 Yi+1 很可能分别是 V和P. 状态特征函数表示 当第i个观测值Xi为单词 “knock”时, 标记很可能为 V.

CRF 的其他表示形式

简化形式

对同一特征在各个位置求和,将局部特征函数转化为一个全局特征函数,将 CRF 表示成权值向量和特征向量的内积形式,即简化形式.

首先将 K1 个 转移特征函数 和 K2 个 状态特征函数 统一起来:

对转移与状态函数在各个位置 i 求和, 得到:

上式可以理解为特征函数在所有位置上的总分. 对于参数部分,我们也这么做:

因此条件随机场的简化形式就可以写作:

CRF 矩阵形式

假设标记变量 $Y_{i}$ 的取值集合为 ${y_{1}, y_{2}, \dots, y_{m}}$, 其中 m 是标记的取值个数.对于观测变量序列和标记变量序列的每个位置 i=1…n,定义一个 m 阶矩阵:

其中:

可以看到,这是一个由各种可能势函数组成的矩阵. 因此条件概率可以表示为:

可以看出, 由于矩阵形式以从开始状态到结束状态转移得到,因此相比于前面的公式, 多了一个对n的求和.

概率计算问题

条件随机场的概率计算问题是,已知条件随机场 $P(X|Y)$, 其中$Y_{i}$ 的取值集合为 $Y = {y_{1}, y_{2}, \dots, y_{m}}$, 给定观测序列 $\tilde{X} = {x_{1}, x_{2}, \dots, x_{n}}$, 给定标记序列 , 其中 $\tilde{y}_{i}\in Y$, 求:

  • 条件概率 $P(Y_{i}=\tilde{y}_{i}|X)$
  • 条件概率

和 HMM 那类似, 可以通过前向-后向算法解决.

首先定义前向算子, $\alpha_{i}(Y_{i}|X)$, 它表示在位置i的标记是 $Y_{i}$, 并且到位置 i 的前半部分标记序列的非规范化概率. 由于 $Y_{i}$ 的取值有 m 个, 因此前向算子是 m 维的:

前向算子的递归形式为:

即通过算子 $\alpha_{i}$ 和 $M_{i}$ 得到 $\alpha_{i+1}$.

类似地, 我们可以定义后向算子 $\beta_{i}(y_{i}|X)$, 它表示在位置 i 的标记是 $Y_{i}$,并且从位置 i+1 的后半部分标记序列的非规范化概率.它也是 m 维列向量.

后向算子的递归关系为:

即从终点开始, 通过后向算子递推向 i + 1 位置得到非规范化概率.

结合前后向算子, 标记序列在位置 i 处标记 $Y_{i} = \tilde{y}_{i}$ 的条件概率为:

其中 Z 是规范化因子.

参数学习

CRF 可以看作定义在时序数据上的对数线性模型, 学习方法可以像 LR 一样用 极大似然估计.

似然函数

考虑到 观测序列和标记序列 $(X, \tilde{y})$, 根据经验分布 $\tilde{P}(X,Y)$, 该对序列出现的次数为:. 则利用条件概率和 X 的先验分布, 出现如此多次数概率为$(X_{s}, Y_{s})$(这里对这个公式为什么要有 N*P 很不理解):

对于整个数据集 D, 则对上式进行连乘并取对数即可得到对数似然函数:

因为第一项是个常数, 去掉, 同时移除常数倍数 N, 我们有:

把 $P_{\overrightarrow{w}}$ 代入:

其形式与最大熵算法完全一致, 这说明从最大熵算法可以推导出 CRF 的条件概率表示.

从我个人的角度, 也许可以从另一个角度来推导, 不知道对不对.这种推导比较符合我心中似然函数的推导思路.

首先由条件概率, 对于整个数据集进行连乘并取对数转化为求和可以得到似然函数:

将条件概率的公式代入上式, 可以得到:

指标 i 和 t缩减一下,用简化形式表达,则有:

对比现在的似然函数和之前的, 我们发现差别仅仅是计算对联合概率 $\tilde{P}(X,Y)$ 的期望. 加上之后就一样了.而那个联合概率是由一开始不理解得指数那带来的, 等我理解再来看看为什么要计算这个期望吧.

现在还有点问题就是参数太多了, 对应办法是加正则化项.L2 的 正则项是 , L1 的是 .

参数求解

现在参数求解的目标是, 通过数据集获取先验概率分布$\tilde{P}(X,Y)$ 和 $\tilde{P}(X)$ 后, 通过最大化似然函数来求解参数.方法可以用常见的那些, 如IIS, 拟牛顿法等. IIS 的可以见 最大熵模型那里, 这里说一下拟牛顿法.其中F是 -L.

  • 选定初始点 $\overrightarrow{w}^{0}$, 取H 的逆的近似矩阵 $B_{0}$ 为 正定对称矩阵, 置 k=0
  • 计算梯度$ \overrightarrow{g}_{k} = \overrightarrow{g}(\overrightarrow{w}^{k})$:
    • 如果梯度小于预设精度 $\epsilon$, 停止计算, 得到参数
    • 若 $\overrightarrow{g}_{k}$ 的绝对值大于预设精度, 则:
      • 求得 $\overrightarrow{p}_{k}$, 它代表梯度下降的方向
      • 一维搜索, 求出 $\lambda_{k} = \min_{\lambda\geq 0}F(\overrightarrow{w}^{k} + \lambda \overrightarrow{p}_{k})$,即得到步长
      • 更新参数 w: $ \overrightarrow{w}^{k+1} = \overrightarrow{w}^{k} + \lambda_{k}\overrightarrow{p}_{k}$
      • 计算 $\overrightarrow{g}_{k+1} = \overrightarrow{g}(\overrightarrow{w}^{k+1})$. 如果它的绝对值小于预设精度,则停止计算,得到最终参数
      • 计算新的 B: , 其中 .
      • k = k+1, 继续迭代

预测算法

预测要解决的是在给定条件随机场和观察序列的情况下, 求条件概率最大的标记序列. 与 HMM 一样, 可以用维特比算法来解决, 即用动态规划求解概率最大的路径, 这时一条路径对应着一个标记序列. 这个没什么好说的, 每一步都取概率最优的, 记录下对应的节点. 从头走到尾即可得到非规范概率的最大值, 对应的路径就是最优路径.

HMM, MEMM, CRF, 逻辑回归 间的区别与联系

HMM是基于有向图的生成式模型,直接对联合概率$P(X,Y)$进行建模。它的一个最大的缺点就是由于观测独立性假设,导致它不能考虑上下文的特征,限制了模型的能力;

MEMM是有向图上的判别式模型,直接对条件概率 $P(Y|X)$进行建模。它抛弃了观测独立性假设,可以任意选择特征,但是啊由于MEMM是局部归一化,导致每一节点都要进行归一化,所以只能找到局部的最优值,同时也导致了标注偏置问题,即凡是语料库中未出现的情况全部忽略掉。

CRF是无向图上的判别式模型,直接对条件概率进行建模。它完全抛弃了HMM的两个不合理的假设,直接采用团和势函数进行建模,对所有特征进行全局归一化,因此可以求得全局最优解。

更详细来说, CRF 可以用前一时刻和当前时刻的标签构成的特征函数,加上对应的权重来表示 HMM 中的转移概率,可以用当前时刻的标签和当前时刻对应的词构成的特征函数,加上权重来表示 HMM 中的发射概率。所以 HMM 能做到的,CRF 都能做到。另外,CRF 相比 HMM 能够利用更加丰富的标签分布信息:

  • HMM 只能使用局部特征,转移概率只依赖前一时刻和当前时刻,发射概率只依赖当前时刻,CRF 能使用更加全局的特征,例如词性标注问题中,如果句子末尾出现问号“?”,则句首第一个词是动词的概率更高。
  • HMM 中的概率具有一定的限制条件,如0到1之间、概率和为1等,而 CRF 中特征函数对应的权重大小没有限制,可以为任意值

CRF 实际上是定义在时序数据上的对数线性模型, 因此CRF还可以看成序列化的logistic regression。这点可以从公式上来看, 我们将LR的 概率公式变一下型,可以得到:

其中 Z 是归一化常数, $\theta_{y}$ 时偏置, $\theta_{y,j}$ 是 LR 里的权重参数. 但我们可以看到, 这个公式的形式与 CRF还是一致的, 相当于特殊的形式.

MRF 是生成模型.MRF理论上需要显得出观察变量y和标号变量x的实际概率分布。但是由于计算能力的限制,这一点无法满足,所以目前研究中,采用了近似的方法。假定x的先验分布和y没有关系,只和相邻两节点有关。而y中某一个节点yi的分布只与当前标号变量xi有关,一般假定满足高斯分布。这样的假设是一种妥协,削弱了MRF的能力,但是便于计算实现。

LSTM+CRF 里的 CRF

先放一个介绍的比较好的博客CRF Layer on the Top of BiLSTM. 我去除简单的部分总结一下.

首先介绍两个分数, 发射分数(Emission score, 或状态分数), 它来自于 LSTM 的输出, 比如单词 w1 在 第 j 个标签的分数为0.3. 另一个是转移分数, 即由一个状态转移到另一个状态的得分, 在 lstm 后接的 crf 里,它一开始是一个随即初始化的矩阵, 大小就是标签的数量.随着网络进行训练.

有了两个得分之后就可以定义 CRF 的损失函数, 它由真实路径的分数 和 所有路径的总分数两部分构成,真实路径的分数应该是所有路径分数里最高的.

真实路径的分数 由 状态分数和 转移分数相加得到 Si, 则分数为 $e^{Si}$. 所有路径的总分就是所有路径的分数和. 这样, 损失函数的公式为:

在得到总得损失函数之后,我们会优化模型(包含CRF 里的那个转移矩阵), 使得真实路径的得分所占的比例最高.

解码的话还是用维特比算法.