HMM->MEMM->CRF以及BiLSTM+CRF中的CRF层

哔哩哔哩《机器学习-白板推导系列》第十七集https://www.bilibili.com/video/av34444816>
官方中文翻译版本https://zhuanlan.zhihu.com/p/44042528 （中文学术平台版本）；https://createmomo.github.io/2017/09/12/CRF_Layer_on_the_Top_of_BiLSTM_1/（英文原文）此处仅提供了该系列的第一章链接
官方中文翻译版本https://www.jianshu.com/p/55755fc649b1；https://blog.echen.me/2012/01/03/introduction-to-conditional-random-fields/（英文原文）

前言

在进行命名实体识别时会发现目前最为流行且稳定的方案主要是通过BiLSTM+CRF模型实现的。然而由于CRF模型的公式看上去让人望而却步一直难以理解为此我花了一些时间阅读了许多专家分享的文章从中获得了一些体会但目前的理解仍然停留在表面水平不够深入

分类算法

监督学习的核心目标是建立一个能够基于输入数据预测输出结果的模型；这些方法主要可分为两类：生成方法与判别方法；所得到的模型分别被称作生成模型与判别模型。在监督学习中，生成型分析通过建模联合概率分布P(X,Y)，进而推导出条件概率分布P(Y|X)作为预测的基础；而判别分析则直接基于输入数据预测输出类别或值；典型的生成型算法包括朴素贝叶斯分类器以及上回我们介绍过的隐马尔可夫模式；相比之下，则是以决策树、k近邻法等为代表的一系列判别型算法。

HMM

HMM即是隐马尔可夫模型；还记得之前介绍的朴素贝叶斯模型吗？它的标签通常被视为0/1值，在进行二分类任务时尤其常见；例如，在垃圾邮件识别任务中；实际上，在将朴素贝叶斯的二值标签序列化后（即将每个输入对应一个标签），该模型便转化为隐马尔可夫模型；

隐马尔可夫模型由三个核心要素共同决定：初始状态概率向量π、状态转移概率矩阵A以及观测概率矩阵B组成。其中矩阵A描述了系统中各个状态之间的转移规律；矩阵B则表征了各个状态下可能产生的观测值类型及其概率分布。

该模型基于以下两个关键假设：

该模型包含以下三个基本研究方向：

MEMM

HMM模型用到了两个比较强的假设，分别是齐次马尔可夫假设和观测独立性假设，这两个假设都属于比较强的假设，方便了建模计算的同时也丢掉了一些信息，并且HMM属于生成模型，是对联合概率分布进行的建模，而对于我们的序列标注问题，其实要求的是条件概率，所以用判别模型更好，于是就有了MEMM，最大熵马尔可夫模型，它打破了观测独立性假设（更加合理），并且属于判别式模型。
最大熵马尔科夫模型利用判别式模型的特点，直接对每一个时刻的状态建立一个分类器，然后将所有的分类器的概率值连乘起来。为了实现是对整个序列进行的分类，在每个时刻t时，它的特征不仅来自当前观测值x_{t}，而且还来自前一状态值y_{t-1}。

MEMM基于最大熵模型，在每个时间点对各个前一个状态的变化进行归一化处理。这种局部的归一化操作会导致标注偏置问题： MEMM存在标注偏置问题，并偏好选择拥有较少转移的状态（具体可见下图）。根本原因在于该模型的局部归一化机制无法实现全局最优解。

我关于标注偏置问题的理解就是由于MEMM是局部归一化即每一次状态转移都要计算归一化概率，所以当一个状态拥有更少的转移状态的时候，他的概率相对就会大一些，MEMM更倾向于选择转移状态少的路径。
如上图，状态一永远更加倾向于转向状态二，而状态二总是倾向于保留在状态二，然而通过维特比算法解码可以得出：
P(1-> 1-> 1-> 1)= 0.4 x 0.45 x 0.5 = 0.09 ，
P(2->2->2->2)= 0.2 X 0.3 X 0.3 = 0.018，
P(1->2->1->2)= 0.6 X 0.2 X 0.5 = 0.06，
P(1->1->2->2)= 0.4 X 0.55 X 0.3 = 0.066
最佳路径是1->1->1->1，从状态2可能转移出去的概率包括1、2、3、4、5，概率在可能的状态上分散了，而状态1转移出去的可能状态仅仅为状态1和2，概率更加集中。正是由于局部归一化的影响，隐藏状态会倾向于转移到那些后续状态可能更少的状态上，以提高整体的后验概率，这就是标注偏置问题产生的根本原因。CRF解决了这个问题

CRF

从图结构分析可知，在移除了Y标签间的单向箭头后形成了双向连接这一操作实际上相当于打破了HMM模型中的齐次马尔可夫假设。

在命名实体识别（NER）任务中这一发现提示着我们必须遵循一定的标注规则因为如果不遵循这些规则就容易导致标注结果可能出现偏差例如在标注序列中如果出现B-PER后紧跟I-ORG这样的情况这种组合通常是不允许存在的。

例如在一个合理的标注序列中如果出现B-PER之后紧跟的是I-ORG这可能暗示着某种特定的关系模式但这种组合本身并不符合标准的语言规范因此需要通过构建特征函数集合来对每条标注序列进行评分标准的设计并在此基础上确定最优的标注方案。

i代表句子s中的第i个词的位置；其中，
l_{i}表示标注序列对第i个词赋予的词性类别；
l_{i-1}则表示标注序列对前一个词（即i-1位置）赋予的词性类别。
其输出结果为二进制形式，
并为每个特征函数f_j分配一个权重系数\lambda_j。
有了上述定义之后，
在实际应用中我们通常会先选择一个合适的特征函数集合，
并将每个特征函数f_j赋予权重系数\lambda_j。
随后只需提供一个待分析的句子及其对应的标注序列即可。

该公式包含了两个累加操作：内部的累加运算用于计算句子中每个位置单词对应的特征值之和；外部的累加运算则针对每一个特征函数f_{j}进行累加。
对该函数施以指数化处理并使其标准化后，则可获得标注序列的概率值p(l|s)。

我对这一概念进行了阐述。实际上，在机器学习领域中存在三种主要的CRF表示方法：其中一种是基于简化的CRF表示法（Simplified CRF Representation），此外还有两种不同的表示方式：一种是参数化形式（Parametric Form），另一种是矩阵形式（Matrix Representation）。具体而言，在李航所著的相关著作中有详细的阐述。计算概率的问题类似于HMM中所采用的前向-后向算法（Forward-Backward Algorithm），但CRF在模型构建上具有更高的灵活性和表达能力。在学习算法方面，则有改进型迭代尺度法（IIS）、梯度下降法（Gradient Descent）以及拟牛顿法（Quasi-Newton Methods）等多种选择可供使用；而预测阶段则仍然采用维特比算法（Viterbi Algorithm）进行解码。

Bi-LSTM-CRF中的CRF层

BiLSTM-CRF的模型结构如图：

他的输入为已训练好的词向量模型，并经过处理后生成每个单词对应的预测结果。
我们先探讨BiLSTM层的作用及其输出内容是什么？

BiLSTM层的输入表示该单词对应各个类别的分数。如W0，BiLSTM节点的输出是1.5 (B-Person), 0.9 (I-Person), 0.1 (B-Organization), 0.08 (I-Organization) and 0.05 (O)。这些分数将会是CRF层的输入。
其实可以看出来，假如没有CRF层，我们照样也可以标注出来，我们选LSTM层输出的每个节点的最高分数，也可以做出正确的预测，但是有时候会出现问题，就是之前提到过的可能会出现B-PER后跟一个I-ORG这种问题，这时候就需要CRF层了。
预测错误的例子：

CRF层能够提取句子中的限制条件，并参考先前介绍的特征方程来描述这些限制，在训练数据中被CRF层自动提取并建立关系。我们设定两个指标：一是初始评分（Emission Score），其来源于BILSTM输出结果；二是转移评分（Transition Score），后者用于衡量从一个标签到另一个标签的变化程度。观察下述表格可以看出，在训练过程中模型已经习得了一些典型特征：例如从B-PER到I-ORG这类标签之间的转移评分相对较低。

定义损失函数：

该序列有十个可能性的话，则分母等于P₁加至P₁₀。假设第十条路径为真实路径，则其分数应为所有可能路径中得分最高者。每个分数由两部分组成：发射分和转移分之和。我们对损失函数取对数并乘以负号。

前面两项很好求，就是真实路径的分数，我们现在只要求出：

具体迭代过程参考https://zhuanlan.zhihu.com/p/44042528
最后得到结果：

我们最终得到了我们想要的目标，

我们的句子中共有3个单词2个类别，所以共有8条路径。
预测过程：
STEP1：假设我们的句子由3个单词组成X=[w_{0},w_{1},w_{2}]，并且我们已经从训练过程中得到发射分数和转移分数，如下：

STEP2:
你将会看到两类变量：obs 和 previous。Previous存储了上一个步骤的最终结果，obs代表当前单词包含的信息（发射分数）。
Alpha0 是历史最佳的分数 ，alpha1 是最佳分数所对应的类别索引。这两类变量的详细信息待会会做说明。
首先看w_{0}，obs=[x_{01},x_{02}],previous=None
首先观测第一个单词w_{0}，很显然，如果obs=[x_{01}=0.2,x_{02}=0.8]，显然最佳预测结果是L2。
从w_{0}到w_{1}:

然后更新previous的值：

例如

那么我们的previous=[0.5, 0.4]其含义可以这样理解：其中从w_{\! 0}预测w_{\! 1}分别归属于L1的概率为\! 0.2和\! 0.5；最高得分为\! 0.5（即对应路径表现为L\!_2 \rightarrow L\!_1），类推地L\!_2 \rightarrow L\!_2的得分为\! 0.4.
在本次迭代过程中，我们将最高得分赋值给变量\alpha_{{}^:}=\alpha_{{}^:}=

最佳分数对应的类别索引存到alpha1:

(1,1)其实就是代表0.5和0.4都是第（1）行，即L2。
接着w_{0}->w_{1}->w_{2}

上面scores有错误，应该是0.5+x21+t11 等.
假如我们的结果为：

则：

最佳路径为L₁→L₂，在矩阵中最高得分位于第一行第二列位置上，并由此确定路径为L₁→L₂。此外，在每一分类别下最大得分为α₀和α₁赋值

基于这两个数组的数据分析结果表明：我们观察到，在该数据集中最高得分位于第二列（即节点为 L₂），其权重系数为零（即上一阶段的预测结果指向了节点 L₁）。接着我们查看得分值（0.5, 0.4），由于已知 w₁ 的输出结果指向 L₁，则对应 0.5 的索引值为 1（即 w₀ 的输出结果指向 L₂）。综合以上分析可知，在节点序列中最佳路径依次经过的是：从节点 L₂ 出发 → 到达节点 L₁ → 最终返回至节点 L₂。