极大团查找做不连续NER
Discontinuous Named Entity Recognition as Maximal Clique Discovery
Abstract
以往的基于转移和基于联合的方法，在训练时都依赖黄金标注的中间结果，使用第一阶段的结果进行预测，产生暴露偏差。
本文提出了一种将不连续NER转换为寻找图的最大团的非参数化过程，避免暴露偏差。
极大团定义：当 G′ 是图 G 的子图，且 G′ 是关于 V′ 的完全图时，子图 G’ 为图 G 的团；当 G’ 是团，且不是其他团的子集时，G’ 为图 G 的极大团；当 G’ 是极大团时，且点数最多，G’ 为图 G 最大团
Introduction
在处理不连续实体识别上，解决overlap问题设计的方法。
目前针对不连续的sota的两个方向：combination-based 和 transition-based.（基于联合和基于转移）
combination-based：首先检测所有重叠的span，然后学习用单独的分类器组合这些段。在训练过程中使用golden段指导分类器，而推理时输入由训练好的模型给出。
transition-based：通过一连串的移位-还原动作对不连续的span进行增量标记。在训练时当前的动作依赖于之前的golden动作，而测试时整个动作序列由模型生成。
尽管这些方法的效果有目共睹，但是存在一个共同的问题：exposure bias
为解决上述问题，本文提出了Mac（Maximal clique）模型:
所有句子的mention实体形成一个segment graph，其中的连续段视为节点，同一实体的各部分连接起来形成边。
那么从这样的segment graph中找到最大团就是问题所在了。
将这个工作抽象为两个不耦合的部分：segment extraction (SE) and edge prediction (EP)（段提取和边预测）
Methodology
下图是抽取过程的一个例子。POB(Part of Body)-身体一部分;ADE(Adverse Drug Event )-不良药物反应
从句子中抽取实体进行标记分类，然后构建成段图(segment graph)。
Grid Tagging Scheme
给定一个n-token句子，通过穷举所有可能token对并根据他们的关系标注标签来构建n*n的标签表。
Segment Extraction
为了提取重叠实体片段，构建一个二维标签表，舍弃下三角区。如图3为一个具体例子。
若ti到tj的一个段属于一个类别，我们将（ti，tj）的一个段分配一组标签。
那么实际上，使用BIS标记方法表示段是连续实体（X-S）、位于X类型的不连续实体开头（X-B）或内部（X-I）。
图中(upper, body)被标记为（POB-S）表示连续实体，类型为“POB”；
(Sever, joint)被标记为（ADE-B）（Sever joint pain的不连续实体）；(Sever, Sever)->（ADE-B）；
( joint, joint)->（POB-S）.可以看到，解决了重叠实体抽取的问题。
Edge Prediction
通过调整同一实体的边界token来构建他们之间的链接进行边预测。
标签模式定义如下：
- head to head(X-H2H)，则有（ti，tj），ti和tj分别表示构成X类型的一个实体的两个段的开始
- tail to tail (X-T2T)，与上述相似但表示尾部
在图4中，“Sever”对于“shoulder”和“pain”有头尾两个标签，是由于不连续实体“Sever shoulder pain”为ADE类型实体。
Model
使用B-K回溯算法寻找图中最大团。
构造三个集合：
- R:记录当前极大团中已加入的点
- P:记录可能还可以加入的点（也就是与R集合中所有点都有边存在的点，这样加入后，才会构成团）
- X:记录已经加入过某极大团的点（作用是判重，因为会从每个结点开始，枚举所有的团，如果不对已经加入某个极大团的点，进行标记，可能会有重复的极大团出现）
那么B-K回溯算法：
- 我们将每一个在P中的点v加入集合R，然后更新P，使P中的点依旧可以和R中的点相连接。
- 回溯时将V从P中移除，加入X中表示当前状态下对包含V的极大团计算结束。
- R为极大团时，必须P与X都为空。P存放可能加入R的点，P空后没有点可以加入R，X中的点必然可以与R构成极大团。因此当且仅当P、X都为空集时R为一个极大团。
对于n个token的句子，进行编码，生产2个表达hs和he分别表示SE和EP的特征：
其中W为参数矩阵，b为偏移量。
Segment Extractor
b和e分别为token的开始和结束，在本模型中固定了行始标记，所以b=ti概率为1只需计算前者。
对于段提取，使用Conditional Layer Normalization(CLN)做归一化：
加入内部信息使用LSTM,以及开始结尾的距离信息：
Edge Predictor
无需距离信息和token内部信息，因此：
实际上，本文模型的网格标记是一种多标签分类方法，使用Sigmoid做全连接。
Datasets
三个数据集：CADEC,ShARe 13，ShARe 14
