浅谈嵌套命名实体识别（Nested NER）
©PaperWeekly 原创 · 作者｜张成蹊
单位｜北京大学硕士生
研究方向｜自然语言处理
序
命名实体识别（Named Entity Recognition, 下称 NER）任务，主要目的是从一段话中抽取出其中可能为实体的所有元素。比如：
“Hi Siri, 今天北京天气怎么样？”
如果下游任务要求我们从其中抽取出地点，那我们期望 北京 能被识别成 Location，如果我们希望从中抽取的产品名称，那么 Siri 应该被标记成 Product —— 换言之，能从句子中抽出什么实体，是由我们提前给定的标签集合定义的。
在一个任务型对话系统中，一些可能在后台处理中使用到的实体都应该被抽出来：我们有理由相信，Siri 是真正将 北京 给提取出来了，然后再通过后台查询到了天气~~，而不是找了一个人工客服在后台即时回复~~。
NER 在很多下游任务中都是非常重要的一环。比如在电商行业，我们可能需要从用户的查询中提取出品牌或商品，来针对性地给用户返回内容。金主爸爸可能也希望用户在查指定品牌的时候，将一些商品放在第一位。
在任务型人机对话方面，正如上面所说，一个合格的 Chatbot 需要能够准确地识别时间、地点、事件等元素以回答相关问题或安排日程，同时做到不偷听用户的日常对话。
而嵌套 NER，顾名思义，就是识别的实体中可能会存在嵌套的情况。比如北京大学不仅是一个组织，同时北京也是一个地点；雅诗兰黛小棕瓶是一个产品，同时雅诗兰黛是一个品牌。
准确地识别嵌套内容有什么作用呢？简单来讲，如果一个模型能够识别出北京大学是一个组织，它倾向于将所有出现的北京大学都标记成组织。
但如果它能够在识别前者的同时将北京标记成地点，我们就认为它有能力将所有[地点]大学的模式都识别出来，因为后者的角度，模型学到的是一种 pattern，而非记住了一种具体情况。此外，提取出来的额外信息也能作为辅助特征，增强其他任务的效果。
具体地，我会介绍以下几部分内容：
当前普遍使用的传统 NER 解决方案； 传统 NER 在解决嵌套 NER 任务时存在的问题； 如何解构 NER 任务，从不同的角度解决问题，使模型能够识别嵌套的 NER； 介绍近几年嵌套 NER 领域有代表性的解决方案。
从 NER 到 Nested NER
2.1 NER 任务的解决方案
在进入 Nested NER 之前，我们先来简单谈谈目前普通 NER 任务（下称 Flat NER）的解决方案，即，将实体识别当做序列标注问题。
如果我们希望识别出地点。给定句子：北京市海淀区。我们希望抽取出来两个实体，分别为：北京市+海淀区。然而如果只对每个 token 进行分类，所有的 token 都将被分到 Location 标签中，这样两个相邻的同类型实体边界就无法正确区分开来。
BIO：即 Beginning、Inside、Outside，对于一个实体的第一个 token，标注为 B-[type]，实体其他位置的 token 标注为 I-[type]，不属于任何实体的 token 标注为 O；这样，对于一个标签数 的实体集，使用 BIO 标注将转变为 个标签； BIOES：即 Beginning、Inside、End、Outside、Single。其中 End 用来标识一个实体的结束，而 Single 用来标识仅包含一个 token 的实体。
在给定 BIO 标注 Schema 的前提下，北京市海淀区的标注结果为：B-Location, I-Location, I-Location, B-Location, I-Location, I-Location。能够完整且没有歧义地复原出模型的标注结果。
基于上述表述，我们可以将一个基于序列标注（Sequence Labeling）的 NER 任务解决方案总结为两个简单的步骤：
选择一个有效的标注 Schema； 选择分类模型（常用 CNN/Bi-LSTM/BERT），对每个 token 进行分类；根据分类结果复原出原文中的实体。
2.2 Nested NER
我们现在回头来看嵌套 NER 的解决方式，一步步提出该问题的基础解决方案，并探讨这些方案存在的不足。
很显然，2.1 节中所定义的 Flat NER 解决方案是没有办法解决嵌套情况的，因为在嵌套 NER 中，一个 token 可能分别拥有两个不同的类型。
例如：北京大学中的北同时属于 B-Location，也属于 B-Organization；而京也拥有 I-Location 与 I-Organization 两个标签。
[1] 完全不改变 Schema，只是在输入训练集的时候，训练集中的 label 从原来的 one-hot 编码形式变成一个指定类别的均匀分布；在训练时将损失函数改为 BCE 或 KL-divergence；在进行推理时，给定一个 hard threshold，所有概率超过这个阈值的类别都会被预测出来，当做这个 token 的类。 [2] 修改 Schema，将可能共同出现的所有类别两两组合，产生新的标签（如：将 B-Location与 B-Organization 组合起来，构造一个新的标签 B-Loc|Org）；这样做的好处是最后的分类任务仍然是一个单分类，因为所有可能的分类目标我们都在 Schema 中覆盖了。
我相信在这些年探索中，这个方案是有学者研究过的，因为它简单易行，改动也小；不过除了 NAACL18 与 ACL19 中的两篇文章仔细探讨了这些方案以外，我很少有见到有使用这种思路解决问题的 paper。因为它存在一些比较明显的问题：
（仅针对第一种实现方式）模型学习的目标设置过难，阈值定义比较主观，很难泛化； （仅针对第二种实现方式）指数级增加了标签，导致分布过于稀疏，很难学习；对于多层嵌套，需要定义非常多的复合标签； 以及最初的问题：修改后的 Schema 预测的结果，复原回实体的时候又不再具有唯一性了。
当然，我们仍然能够给模型添加规则与约束，来一一解决这些问题，具体内容在论文中有相应的阐述。
在这里，Decode 过程指的是基于模型输出的 token 表示来给 token 分类的过程，在 Sequence Labeling 中指的是 FFN + Softmax/CRF + Argmax 这一套操作。
严格来说，解决方案 1 的第一个实现方式也算是非常 naive 的修改了 Decode 过程，不过在这里我们讨论一些更加有效的方案。
值得注意的是，修改 Decoder 的目的是为了保证能够给一个 token 同时赋予多个类别，所以我们仍然将下面的方案视作 Sequence Labeling 任务（尽管最后输出的 label list 长度可能与 token 的数量不同，但这是因为由原来的单分类变成了多分类所必然导致的）。
[2] 既然直接使用 FFN 映射做单分类没法解决嵌套问题，做多分类又不容易做work，那是否可以考虑使用生成式的方法，如 seq2seq 中的 Decoder 来逐个生成每个 token 的标签？使用 Decoder 能够将输入的 token 数量与输出的类别数量解绑，允许给token打上超过一个的标签——但是与原来的生成方法不同，除了使用特殊字符 [EOS](end of sentence)来标识整个生成过程结束以外，我们需要引入一个特殊字符[EOW](end of word)来标识接下来生成的是属于下一个 token 的标签。[3] 使用分层的方式对token的表示进行预测也是一个非常有意思的方案：如果一次分类无法解决实体嵌套的问题，那就对第一次的分类结果继续做分类，如是迭代，直到达到最大迭代次数或是不再有新的实体产生为止。这种解决方案存在的问题是对 Decoder 的学习要求较高，如果前面的迭代过程中出现了错判，这个问题可能会传递到后续迭代过程中。
依稀记得之前看过一篇让我印象深刻的知乎文章，名为"丢掉幻想，全面拥抱Transformer"。借由此名，最后一种解决嵌套 NER 问题的方式可以叫做"丢掉序列标注，全面拥抱 Multi-Stage" 。
我们已经在上文中多次提到，序列标注任务是天然不支持给一个 token 赋予多个标签的，尽管我们已经进行了多个层面的修饰，使它能够应用到多标签分类上。
但是既然它应用到 Nested 任务上时效果并不突出，也没有其不可替代性，为什么不直接舍弃掉这个任务形式，尝试其它的解决方案呢？
撇开原来的 NER 解决方案，从头考虑一个实体识别的方案，我们仍然从一个非常 naive 的 proposal 出发：
将句子中所有的子序列全部枚举出来，即得到一个子序列集合：。 训练一个分类器 ，负责将子序列映射到给定的标签集合（即：Location, Organization, ..., O）中：。
当然，我们仍旧可以通过一些人工规则或设定来减弱这些问题，例如：
模型训练困难：给每个类型单独训练一个分类器； 时空复杂度：假设最长的实体长度为 ，全枚举子序列时只枚举长度小于 的所有情况； 负样本很多：在执行分类之前，先训练一个/多个通用的筛选器，或通过人工规则首先筛掉一批负样本；在训练过程中对负样本进行采样，而非使用全部。
非常典型地，我们可以以现有的模型骨架（Bi-LSTM、ELMo 等）来简便地搭建一份上面所描述的模型。[4] 使用了 7 个 Bi-LSTM 与 1 个 ELMo 来提取不同 level 的上下文信息，并使用了一个 Self-Attention 来通过上下文来增强每个子序列的表示。
由于这篇 paper 不会在下面详细讲到，我在这里冒昧做个简单的评价：
尽管是非常典型的上述 proposal 实现模板，这篇 paper 的建模操作总体而言并不算特别 elegant，并且加了一些人工设定，有少部分的操作甚至难以解读，而作者也没有专门去解释一些操作的含义，导致我读完之后小小的脑袋里充满着大大的问号。
这个设定能够 work 超过了我的常识。我能理解 Encode 以后的 token 表示中确实有蕴含整个句子中上下文信息。
但就此判定，并期许它所表示的正好就是该 token 附近特定区域的某一概率，似乎比直接用该区域的表示来做出这个判定要来得牵强些。希望有阅读过这篇 paper 的同学与我讨论，解答我的疑惑。
[5] 给出了思路上与 [4] 相似的解决方案。不过相较于全枚举，[5] 选择从另一个角度来获得候选实体：预测两个 token 之间相连的概率。如果两个 token 之间相连的概率较大（在文中体现为值趋向于 0），认为它们在当前 level 更倾向于在同一个实体中。随后迭代更新实体中每个 token 的表示，就能识别多层的嵌套信息。
[6] 提出了一个假设：在一个实体中，总会存在一个或多个 token 是该实体的锚点（即如果这个 token 出现，则有相当概率该 token 在一个实体之内。作者以
The department of [xxx]中的department为例，阐述它很有可能出现在一个类型为 Organization 的实体中）。由此，我们可以将识别嵌套实体的任务转换为寻找锚点的任务：首先找到锚点并判定它所代表的类别，随后找到该锚点所在实体的边界。[7] 将寻找实体的任务视为阅读理解（Machine Reading Comprehension，下称 MRC）任务，即：查询句子中是否存在指定问句的答案。在这里问句代表了一个指定类别的查询（如：Is there any Location in this sentence?），而作为问句的答案，模型将输出句子中所有对应实体的开始与结束位置。
[8] 受到构造一棵语句解析树过程的启发，将识别嵌套实体视为一个构造解析树的过程：在每一个时间步中，模型将根据当前状态来决定是给指定 token 赋予一个标签，还是给已经赋予标签的两段实体打上一个更高层次的标签（以此实现了标签的嵌套），抑或是跳过当前处理的 token。这样的操作比较像一个内部带着条件语句的 RNN 单元，它能根据当前的情况来以不同的方式处理一个 token：给它打标签，或者不做处理。
相关Paper选读
上面的部分主要是阐述了 Flat NER 与 Nested NER 任务形态上的区别，通过 Sequence Labeling 的缺陷来从各个方面推导出一些可行的解决方案。
由于篇幅与时间所限，接下来我将挑选三篇思路上比较有趣的 paper，来具体阐述研究者是究竟是如何解决 Nested NER 这一任务的。
3.1 逐个token的解析：基于状态转换（Transition）的方法
[8] 基于状态转换的方法在近三年所提出的 Nested NER 解决方案中占据了一席之地。这个方法有些像编译原理中的有穷自动机，而且十分相似的一点是，它们确实都在对某个输入进行解析。
如果对自动机有了解，大家知道自动机的下一个状态依赖于当前状态与当前的输入，而如果从玄学的角度来看待，自动机当前的状态是由从开始到现在所有的状态转换以及所有的输入共同影响达到的，也就是说当前状态中理应 Encode 了从开始为止所有操作的信息。
但是实际上，当前的状态只是一个状态而已，之前的所有操作与信息都随着时间的流逝进入到历史的长河中去了。
现在回头考虑 Nested NER 的问题：如果我们能通过以一个状态转换的形式来解析一个句子，从中提取出所有的嵌套实体，我们首先需要解决的就是如何在当前状态中把之前的信息也放进来，令人高兴的是有一个结构天然带有这样的性质：即 时间序列 模型。
首先我们来看一个带有嵌套实体的句子：
constituency parsing中 shift-reduce 解析方式的启发，作者设计出了一个解析上述句子的体系。在整个过程中，我们需要维护下面三个结构：一个栈（Stack），栈顶元素是当前需要处理的元素。我们需要根据上下文与当前的状态来决定：忽略该元素、给该元素打标签，或是将该元素与前一个元素进行复合，打上更高层次的标签。
一个队列（Buffer）。队列中是句子中待处理的剩余 token。
一个操作器（Action）。这个操作器本质是一个模型，它将根据目前的系统状态来决定执行哪一种解析操作。
SHIFT：将队列头部的一个 token 弹出，移入栈中。值得注意的是，这并不代表我们跳过了当前 token 的处理，由栈的功能定义可知，这一步的目的实际是要开始处理这个 token 了； Unary-X：将栈顶的元素弹出，给它打上标签 [X]，随后重新压入栈中；
Reduce-X：弹出两次栈顶元素，给它们打上标签 [X]，随后重新压入栈中。
从上述操作中容易看到，只有 Reduce 操作是赋予了实体更高层次，也即嵌套的标签。
假设目前输入句子：Indonesian leaders visited him ，一个正确的解析操作序列应该如下图的 Action 列所示：
上述的 Unary+Reduce 操作最终得到的解析树中的每个实体只能是一棵二叉树（可以参照上图的解析过程来辅助理解为什么一定是一棵二叉树）；二叉树意味着一个被识别出来的实体里面只能包含最多两个 token，然而现实中非常多的实体是由超过两个 token 所构成的；
如果不停的进行无意义的操作，会显著加剧栈所占的内存空间，同时得到的结果是不合理的（例如反复连续执行同一个类型的 Unary），需要对操作进行约束；
最后一个问题，同时也是 Deep Learning 大家族灵魂拷问：在完全正确的 Action 操作顺序下，我们确实能完成对嵌套实体的识别，但怎样判断当前应该执行哪一个 Action 呢？
接下来主要讲述的是问题 3，也就是论文的核心部分：如何获得一个尽可能准确地 Action 序列。下面的处理方式堪称万物皆可Embedding的实践典范。
队列中保存的是当前还未处理的所有 token，作者使用了一个反向的 LSTM 来学习这个队列的表示。之所以使用反向（即从队列尾开始到队列头），是由于我们当前下一个待处理 token 是队列头的字符，因此所需要的信息自然是从文本尾部到当前文本的信息； 栈中保存的是目前已经处理的 token 以及处理结果（即目前为止嵌套实体的识别结果），与队列的表示方法相似，从栈底到栈顶使用单向 LSTM 来获得栈顶元素的表示；值得注意的是，由于栈顶的两个元素可能会被修改（或因为下一个 token 的移入而被改变），作者在此使用了 Stack-LSTM 来避免频繁修改带来的时空开销； 当一个新 token 被移入栈顶时，基于该 token 的表示与 Stack-LSTM 特性更新新的栈顶表示； 当栈顶元素被执行 Unary-X 操作时，我们将类型 的表示集成到当前栈顶元素的表示中去，即 ，其中 是新的向量，是栈顶元素当前向量，分别是类型 的权重矩阵与正则项，表示当前执行的是 unary 操作； 当栈顶元素执行Reduce-X操作时，与上面操作相同，更新栈顶元素的表示为 ，其中 分别是次栈顶元素与栈顶元素的表示，即二叉树的左右子节点。 操作器之前所做的历史操作我们也使用一个结构将其保存下来，并使用一个单向 LSTM 来获得整体表示，方向为从第 1 个 Action 一直到离当前最近的 Action。
简单总结一下，作者相当于将待处理的文本内容、已处理的文本结果，与已经进行的 Action 操作视为一个系统，将其 Embed 到一个向量中，以表征当前的整体状态，再基于这个状态使用分类器来判断下一步执行的操作。
这里的每一步都在 Embed 层面进行。当然，这样的做法虽然 work，但这种将一切都看成 Embed，然后使用各种模型结构进行交互的方式，放在自动机体系中或许成立，放在其他应用中，是否仍然可行？
现在我们重新审视句子：***... that his fellow pilot Dabid William had ...*** 及其嵌套标注结果（其中 L=Last=End=E, U=Unit=Single=S）：
值得注意的是，我们需要保证每个 token 至少都有一个 O 标签。这么做的目的是为了能够有效的建模每个新实体的开头的概率。如上图所示，如果一个 token 没有 O 标签，我们需要加一个虚空 O 进去。
我们可以使用一个 Decoder 来实现这个过程。
值得注意的是，虽然这里使用了 Decoder，但是这个 Decode r输出的标签数量与输入的 token 数量是一致的，这也是我在第二章节划分体系时将其分类到多标签任务体系，而非修改了 Decode 过程体系的原因：在该模型中，使用 Decoder 的原因并不是因为 Decoder 能够以生成式的方式产生非等量标签的特性，而是因为 RNN 家族的单元在 Decoder 中能够传递隐层信息以增强当前标签识别结果的特性。在这样的理解上，将这个 Decoder 换成一个表达能力相对较差的 CRF 也是成立的，（虽然效果不会那么好但）大概率也能做 work。 作者在文中提到 we have a decoder-style model 而非直接提出 we apply a decoder，或许也是因为这个原因吧
这个 Decoder 使用的是 LSTM Unit，以下的分析假设读者已经对 LSTM 的内部结构有一定的了解。
上一个时间步的模型输出 是一个概率分布，我们将整个分布通过 softmax 映射到 01 区间，随后将所有概率大于我们预先设定的 hard threshold: 的标签找出来。以上图举例，如果模型得到我们预期的结果，对于当前 token his，模型应该找到两个符合阈值要求的标签 与 。注意，由于这里没有预测出标签 O，我们手动给它加上 O 的标签，即模型最终预测得到 、与 ； 由于上一个时间步模型预测得到了三个可能的标签，我们需要考察这三个标签在当前步分别可能对应哪个标签。所以我们将当前的 复制三份，每一份都通过 LSTM 单元计算当前的隐层输出。特别地，对于上一个时间步的可能标签，当前时间步的隐层结果为： 这样，对于上一个时间步的每一个预测结果，我们都能得到对应的当前时间步的隐层表示。现在我们有了三个隐层表示，将它求平均： 其中 就是上一个时间步中所有满足阈值的标签数量，在当前我们所讲的 case 中取值为 3. 获得当前时间步的输出 ，其中 分别为 FFN 的权重矩阵与正则项。
以上就是使用类似 Decoder 的形式来逐个输出每个 token 所有可能标签的形式，如果上面表述比较难以直接理解，也可以通过 paper 中所给的模型结构图来比较理解。
与我们的讨论过程一致，我们在此给出基于上述思路的损失函数的公式描述：
本质上就是一个多分类交叉熵损失函数，就不再一一讲述其中符号的含义了。
此外，这里对于一些 word embedding 层、multi-layer Bi-LSTM 层也不再进行详述，因为他们的实现方式大同小异，只在于使用了静态 GLoVe 还是动态 ELMo、加 Character LSTM 与否，以及使用了 Bi-LSTM 还是 BERT 作为上下文信息学习框架，亦或在顶层是否添加了一个 Attention 的区别。
据笔者所知，MSRA有位同学应该做了更好的结果出来，不过考虑它要投的顶会时间，保守估计在5月份才会挂到Arxiv上，让我们一起期待吧: )
给定一段信息(passage)与给定一个问题(question)，模型需要从信息中找到回答这个问题的短语(span)。
乍一听这个方法充满了玄学，但当我们拥有一个 BERT 的时候，这个任务就非常好做了。由于预训练时的任务设计，BERT 天生就允许往模型中同时输入两个不同的句子。我们向 BERT 中以下面的形式输入问题与信息：
问题是，怎么拿到这个结果，再将这个结果复原回原来的实体结果呢？
作者训练了三个分类器，分别用于预测模型输出后的：
当前 token 是否为一个实体的开头位置；
当前 token 是否为一个实体的结束位置； 前两个分类器中的两两位置是否匹配（如果开头位置 与结束位置 匹配，我们就认为从 是一个实体。
如果没有完全理清楚整个处理逻辑，你可能会有疑惑：即便我知道了 是一个实体，但是这个实体类型是什么呢？答案是：这个实体类型就是这个问题的类型，如果问题的类型是：这个句子中 PERSON 的实体是什么，那么抽出来的实体类型就是 PERSON。是不是非常有趣？
如此看来，一个问题的优秀程度直接影响了模型抽取实体的效果，那如何设计问题呢？
"head word"（还记得上面所提到的 department 会有很大概率作为 organization 实体的 head word吗？），与此同时这些head word基本不会出现在其他标签的标注指南中。以上就是近几年来 Nested NER 领域的整体研究现状综述，在最后想加点我的个人感想。
在第二部分我着重从我理解的角度出发，来分析为什么 Nested NER 不适用于现在普遍应用的 NER 任务的解决方案。
也从我个人的感受出发，给近几年所有的相关 paper 分了体系，其划分依据主要是撇开整个故事不谈，从模型角度它究竟修改了原来 NER 解决方案中的哪个部分，或者说解决了其中哪个不足。
于是在第三部分，我解读了三篇我觉得非常有意思的解决方案。他们可能不是结果最好的，但都给我以眼前一亮的感觉：原来这个问题还能这么做。
我觉得从接触一个领域，到了解该领域的研究现状，到提出该领域存在的不足，这三个过程是每个研究过程中都不可或缺的，但是最重要的是在此之后针对存在的问题，提出有效的解决方案。
作为全新角度来解决问题的 paper，他们一开始的构思可能比较简单，但之后也能通过人为增加约束的形式将任务做 work，这是研究中不断实验进步的过程。而后面这两个过程，才是研究者能否做出有独创性、有价值成果的决定性因素。
毕竟只会前三步的我，只能写博客，而掌握后两步的大家，就能发顶会了。
点击以下标题查看更多往期内容：
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。
版权声明：以上内容为用户推荐收藏至CareerEngine平台，其内容（含文字、图片、视频、音频等）及知识版权均属用户或用户转发自的第三方网站，如涉嫌侵权，请通知[email protected]进行信息删除。如需查看信息来源，请点击“查看原文”。如需洽谈其它事宜，请联系[email protected]。