©PaperWeekly 原创 · 作者|苏剑林
单位|追一科技
研究方向|NLP、神经网络
从 MEMM 全称 Maximum Entropy Markov Model,中文名可译为“最大熵马尔可夫模型”。不得不说,这个名字可能会吓退 80% 的初学者:最大熵还没搞懂,马尔可夫也不认识,这两个合起来怕不是天书?而事实上,不管是 MEMM 还是 CRF,它们的模型都远比它们的名字来得简单,它们的概念和设计都非常朴素自然,并不难理解。
回顾 CRF
作为对比,我们还是来回顾一下 CRF。说是“回顾”,是因为笔者之前已经撰文介绍过 CRF 了,如果对 CRF 还不是很了解的读者,可以先去阅读旧作简明条件随机场CRF介绍 | 附带纯Keras实现。简单起见,本文介绍的 CRF 和 MEMM 都是最简单的“线性链”版本。
本文都是以序列标注为例,即输入序列 x=(x1,x2,…,xn),希望输出同样长度的标签序列 y=(y1,y2,…,yn),那么建模的就是概率分布:
CRF 把 y 看成一个整体,算一个总得分,计算公式如下:
这个打分函数的特点就是显式地考虑了相邻标签的关联,其实 g(yk−1,yk) 被称为转移矩阵。现在得分算出来了,概率就是得分的 softmax,所以最终概率分布的形式设为:
如果仅局限于概念的话,那么 CRF 的介绍到此就结束了。总的来说,就是将目标序列当成一个整体,先给目标设计一个打分函数,然后对打分函数进行整体的 softmax,这个建模理念跟普通的分类问题是一致的。CRF 的困难之处在于代码实现,因为上式的分母项包含了所有路径的求和,这并不是一件容易的事情,但在概念理解上,笔者相信并没有什么特别困难之处。
更朴素的 MEMM
现在我们来介绍 MEMM,它可以看成一个极度简化的 seq2seq 模型。对于目标 (1) ,它考虑分解:
然后假设标签的依赖只发生在相邻位置,所以:
接着仿照线性链 CRF 的设计,我们可以设:
至此,这就得到了 MEMM 了。由于 MEMM 已经将整体的概率分布分解为逐步的分布之积了,所以算 loss 只需要把每一步的交叉熵求和。
两者的关系
将式 (6) 代回式 (5) ,我们可以得到:
对比式 (7) 和式 (3),我们可以发现,MEMM 跟 CRF 的区别仅在于分母(也就是归一化因子)的计算方式不同,CRF 的式 (3) 我们称之为是全局归一化的,而 MEMM 的式 (7) 我们称之为是局部归一化的。
这一节我们来分析 MEMM 的优劣、改进与效果。
MEMM 的优劣
MEMM 的一个明显的特点是实现简单、速度快,因为它只需要每一步单独执行 softmax,所以 MEMM 是完全可以并行的,速度跟直接逐步 Softmax 基本一样。
而对于 CRF,式 (3) 的分母并不是那么容易算的,它最终转化为一个递归计算,可以在 O(n) 的时间内算出来(具体细节还请参考简明条件随机场CRF介绍 | 附带纯Keras实现),递归就意味着是串行的,因此当我们模型的主体部分是高度可并行的架构(比如纯 CNN 或纯 Attention 架构)时,CRF 会严重拖慢模型的训练速度。后面我们有比较 MEMM 和 CRF 的训练速度(当然,仅仅是训练慢了,预测阶段 MEMM 和 CRF 的速度都一样)。
至于劣势,自然也是有的。前面我们提到过,MEMM 可以看成是一个极度简化的 seq2seq 模型。既然是这样,那么普通 seq2seq 模型有的弊端它都有。seq2seq 中有一个明显的问题是 exposure bias,对应到 MEMM 中,它被称之为 label bias,大概意思是:在训练 MEMM 的时候,对于当前步的预测,都是假设前一步的真实标签已知。
这样一来,如果某个标签 A 后面只能接标签 B ,那么模型只需要通过优化转移矩阵就可以实现这一点,而不需要优化输入 x 对 B 的影响(即没有优化好 f(B;x));然而,在预测阶段,真实标签是不知道的,我们可能无法以较高的置信度预测前一步的标签 A ,而由于在训练阶段,当前步的 f(B;x) 也没有得到强化,所以当前步 B 也无法准确预测,这就有可能导致错误的预测结果。
双向 MEMM
label bias可能不好理解,但我们可以从另外一个视角看 MEMM 的不足:事实上,相比 CRF,MEMM 明显的一个不够漂亮的地方就是它的不对称性——它是从左往右进行概率分解的。
笔者的实验表明,如果能解决这个不对称性,能够稍微提高 MEMM 的效果。笔者的思路是:将 MEMM 也从右往左做一遍,这时候对应的概率分布是:
然后也算一个交叉熵,跟从左往右的式 (7) 的交叉熵平均,作为最终的 loss。这样一来,模型同时考虑了从左往右和从右往左两个方向,并且也不用增加参数,弥补了不对称性的缺陷。作为区分,笔者类比 Bi-LSTM 的命名,将其称为 Bi-MEMM。
注:Bi-MEMM 这个名词并不是在此处首次出现,据笔者所查,首次提出 Bi-MEMM 这个概念的,是论文 Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data [1],里边的 Bi-MEMM 是指一种 MEMM 的双向解码策略,跟本文的 Bi-MEMM 含义并不相同。
根据上面的结论,在深度学习时代,MEMM 的“没落”似乎就可以理解了——MEMM 除了训练速度快点之外,相比 CRF 似乎也就没什么好处了,两者的预测速度是一样的,而很多时候我们主要关心预测速度和效果,训练速度稍微慢点也无妨。
这两个模型的比较结果是有代表性的,可以说这正是所有全局归一化和局部归一化模型的差异:全局归一化模型效果通常好些,但实现通常相对困难一些;局部归一化模型效果通常不超过全局归一化模型,但胜在易于实现,并与易于拓展。
如何易于拓展?这里举两个方向的例子。
第一个例子,假如标签数很大的时候,比如用序列标注的方式做文本纠错或者文本生成时(相关例子可以参考论文 Fast Structured Decoding for Sequence Models [5]),标签的数目就是词表里边的词汇数 |V| ,就算用了 subword 方法,词汇数少说也有一两万,这时候转移矩阵的参数量就达到数亿(),难以训练。
读者可能会想到低秩分解,不错,低秩分解可以将转移矩阵的参数量控制为 2d|V| ,其中 d 是分解的中间层维度。不幸的是,对于 CRF 来说,低秩分解不能改变归一化因子计算量大的事实,因为 CRF 的归一化因子依然需要恢复为 |V| × |V| 的转移矩阵才能计算下去,所以对于标签数目巨大的场景,CRF 无法直接使用。
但幸运的是,对于 MEMM 来说,低秩分解可以有效低降低训练时的计算量,从而依然能够有效的使用。bert4keras 里边所带的 MaximumEntropyMarkovModel 已经把低秩序分解集成进去了,有兴趣的读者可以查看源码了解细节。
第二个例子,上述介绍的 CRF 和 MEMM 都只考虑相邻标签之间的关联,如果我要考虑更复杂的邻接关联呢?比如同时考虑 跟 的关联?
这时候 CRF 的全局归一化思路就很难操作了,归根结底还是归一化因子难算;但如果是 MEMM 的局部归一化思路就容易进行。事实上,笔者之前设计的信息抽取分层标注思路,也可以说是一种跟 MEMM 类似的局部归一化的概率图模型,它考虑的关联就更复杂化了。
本文介绍并简单推广了跟 CRF 一样同为概率图经典案例的 MEMM,它与 CRF 的区别主要是归一化方式上的不一样,接着笔者从实验上对两者做了简单的比较,得出 MEMM 训练更快但效果不优于 CRF 的结论。尽管如此,笔者认为 MEMM 仍有可取之处,所以最后构思了 MEMM 的一些拓展。
[1] https://www.aclweb.org/anthology/H05-1059/
[2] https://github.com/bojone/bert4keras
[3] https://github.com/bojone/bert4keras/blob/master/examples/task_sequence_labeling_cws_crf.py
[4] https://github.com/bojone/bert4keras/blob/master/examples/task_sequence_labeling_ner_crf.py
[5] https://arxiv.org/abs/1910.11555
点击以下标题查看更多往期内容:
#投 稿 通 道#
让你的论文被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢?答案就是:你不认识的人。
总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学习心得或技术干货。我们的目的只有一个,让知识真正流动起来。
📝 来稿标准:
• 稿件确系个人原创作品,来稿需注明作者个人信息(姓名+学校/工作单位+学历/职位+研究方向)
• 如果文章并非首发,请在投稿时提醒并附上所有已发布链接
• PaperWeekly 默认每篇文章都是首发,均会添加“原创”标志
📬 投稿邮箱:
• 投稿邮箱:hr@paperweekly.site
• 所有文章配图,请单独在附件中发送
• 请留下即时联系方式(微信或手机),以便我们在编辑发布时和作者沟通
🔍
现在,在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域,欢迎在公众号后台点击「交流群」,小助手将把你带入 PaperWeekly 的交流群里。
▽ 点击 | 阅读原文 | 查看作者博客