CS224N(2.26)Coreference Resolution

今天介绍的内容是指代消解(Coreference Resolution)。指代(mention)是指句子中出现的名词、名词短语、代词等,指代消解就是把指向同一实体(entity)的指代聚类到一起的过程。比如下面的两句话,蓝色的词就是很多的指代,需要找出来哪些指代是指向同一个实体。比如Barack Obama、his、He都是指奥巴马。

下面的例子是比较简单的情况,事实上,在真实的语言中,情况更加复杂,比如有些指代可能表示多个实体。比如“他们”,可能同时指代了“小明”和“小王”,这种指代对于现在的NLP模型来说比较难,暂时不考虑。

指代消解有很多应用场景,比如知道代词的含义之后,能更好地理解全文,进而能更准确的进行机器翻译,另外,在对话系统中进行指代消解能产生更正确的回答句子。


指代消解主要有两个步骤。第一步是指代识别(mention detection),即找出句子中所有的指代,这一步相对简单。第二步才是进行真正的指代消解(coreference resolution),这一步比较难,也是本节课的主要内容。

指代(Mention)是指句子中的一个短语(span),它可以是代词、也可以是命名实体、还可以是名词短语。指代识别的方法有多种,比如词性标注(POS)、命名实体识别(NER)、语法分析器(parser)等。

指代识别虽然相比于指代消解更简单,但也不是那么简单,它也有它自己的一些难题。比如下面列出的几个例子其实就不是指代,但用POS、NER等方法有可能把它们找出来,导致找出过多的指代(over-generates)。

一个简单的方法是,指代识别阶段尽量保召回率,保留所有找到的可能是指代的词,都参与后期的指代消解。如果一个指代没有找到它的共同指代(coreference),则说明这个指代是孤立的(singleton mention),有可能是指代识别阶段找到的不是指代的词,直接把它扔掉即可。


指代消解发展至今,经历了四种不同的方法,分别是Rule-based、Mention pair、Mention Ranking和Clustering。下面分别介绍每一种方法。

1976年Hobbs提出了基于规则的朴素算法,被后人称为Hobbs算法。该方法有9个步骤,包含了很多规则,非常繁琐,这里就不具体介绍了。Hobbs算法虽然是基于规则的,但在当时取得了不错的效果,现在也常常作为该领域的baseline模型。但是因为该方法是基于规则的,有很多指代消解没法解决。比如下图的两组例子,它们的句子结构完全相同,但指代不同,基于规则的Hobbs算法如果正确消解了第一个句子的指代,则肯定无法正确消解第二个句子的指代。

很明显,要想同时正确消解两个句子的指代,必须像人一样理解句子的含义。所以,指代消解也可以作为图灵测试之外的实验,用来测试AI的智力。如果AI能100%准确完成指代消解,AI的智力也就达到了人类的水平。


比较简单的Mention pair的方法。该方法把指代消解问题转化为一个二分类问题。从左到右遍历句子,每找到一个指代,就把它和前面找到的每个指代作为一个pair,问分类器这个pair是否指代同一个实体,如果是的话,就把它们连起来。二分类的损失就是交叉熵。很简单的一个模型。

该模型在测试的时候,设定一个概率阈值,比如把所有概率超过0.5的指代pair都连起来,然后所有连在一起的指代作为一个聚类。如果一个指代不与任何其他指代连接,则它可能不是一个指代。这种方法有over-cluster的风险,即万一有一根线连错了,则会导致原本属于两个cluster的所有指代归为一个类。

Mention pair模型的不足:对于很长的句子,可能会找到很多指代,而一个指代的先行词(antecedent)往往只有一个,但mention pair方法却把它和它前面的所有指代都pair进行指代消解。比如下面的例子,最后的he明确的指代是紧邻它的前一个Nader,但却需要把he和前面的4个指代都pair进行消解,无形中增加了计算量。可能的解决方法是只让模型预测一个先行词,也就是mention ranking方法。


Mention ranking的方法。每个指代同时和前面所有指代打分,用softmax归一化,找出概率最大的先行词,添加一条连边。注意需要添加一个NA节点,因为有的指代可能第一次出现,前面没有先行词,或者这个指代根本就不是一个真正的指代。

Mention ranking在训练时的损失函数如下:i:对于每一个指代;j:看看其前面的所有指代,最大化i所指代的j的概率$1(y_{ij}=1)p(m_j,m_i)$。

测试的时候与mention pair类似,把有边连的指代聚类到一起。


前面的内容都是假设我们计算好了任意两个指代是coreference的概率,那么,如何来计算这个概率呢?主要有三种方法,分别是Non-neural statistical classifier、Simple neural network和More advanced model using LSTMs, attention。下面分别介绍这三种方法。

A. Non-neural statistical classifier。统计机器学习方法,抽取每个指代的各种特征,然后用机器学习分类器来计算两个指代是coreference的概率。这里面的特征包括人称、性别一致性,语义相容性等等,如下图所示。


B. Neural Coref Model。输入是候选先行词和当前指代词的词向量,还需要加入一些额外的特征(Additional Feature),也就是上面统计机器学习方法里用到的一些特征。中间是FFNN,即全连接网络,最后输出两个指代是coreference的概率。


C. End-to-end Model。end2end模型是目前指代消解的SOTA模型,它把指代识别和指代消解两个任务融合到一起,用一个模型来解决。

它的网络结构如下左图所示。由于该模型同时完成了指代识别和指代消解两个任务,所以它需要枚举句子中任意两个词之间的span是否是一个指代,以及这个指代与其他指代是否是coreference的关系。

具体来说,对于每个词i,输入网络中的是这个词的词向量以及charCNN词向量拼接起来的向量。然后送入bi-LSTM中,提取bi-LSTM两个LSTM的隐藏层向量,拼接起来作为词i的特征向量$x^*$。枚举包含词i的起始位置START(i)和终止位置END(i),由起始位置到终止位置构成一个span,假设这个span可能是一个指代。一个span由向量$g_i$表示,它包含4个部分,分别是:span的起始和终止位置的特征向量$x^*_{START(i)}$和$x^*_{END(i)}$,包含这个span的起始和终止位置的特征;这个span的attention表示向量$\hat{x_i}$,提取这个span表示的核心信息,比如the black cat中cat是核心信息;以及一些额外的特征$\phi(i)$。

一个span的attention表示向量$\hat{x_i}$计算公式如下右图。span中每个词的特征向量经过全连接网络FFNN,得到一个attention打分,softmax归一化得到归一化的attention打分分布,最后加权平均起来。

抽取了所有span的特征向量$g_i$后,需要完成两个任务,一是判断这个span是否是一个指代,二是判断任意两个span是否是coreference的关系。对于任意两个span i和j,它们的打分公式如下图所示,包含三部分,分别表示三个意思:span i是一个指代吗、span j是一个指代吗、span i和span j是coreference关系吗。三部分的概率计算方法也是全连接网络FFNN的方法。

这个模型虽然是一个end2end的方法,看起来比较漂亮,同时完成了指代识别和指代消除两个任务,但它的复杂度太高了。假设句子中有T个词,枚举所有span需要O(T^2)的复杂度,然后枚举任意两个span又需要span^T的复杂度,综合起来就是O(T^4)的复杂度。由于复杂度太高,这个模型需要一个剪枝过程,其实就相当于需要一个指代识别器提前把指代找出来,这样就省去了枚举span的O(T^2)的复杂度。


最后,介绍一种层次聚类的方法,是Manning老师提出来的。该方法的核心思想是说,在找到指代的情况下,指代消解的过程本质上是一个聚类的过程,所以我们对所有指代做一个聚类,一个类中的所有指代就表示同一个实体,是coreference的关系。那么,使用哪种聚类方法呢,使用自底向上的层次聚类方法agglomerative clustering。

以下图为例,对于找到的4个指代,我们发现Google和the company的关系比较近,Google Plus和the product的关系也比较近,首先把它们各自聚到一类。注意,此时对计算机来说,Google和Google Plus的关系无法判断,一方面它们在字面上有n-gram的overlap,但另一方面在句子中的含义可能不一样,这个时候还比较难判断它们是否有coreference的关系。但是,当cluster 1和cluster 2都形成之后,要判断{Google, the company}和{Google Plus, the product}的关系时,就比较容易了,因为the company和the product是比较容易区分的,由于它们在不同的类中,也就区分了Google和Google Plus。

层次聚类的方法相比于mention-pair的方法更简单,因为是类与类之间计算指代关系,一个类中有多个词,可以增加类之间的辨识度。

下面是对两个类进行相似度打分的模型,也是基于神经网络的方法,具体不介绍了。


最后,介绍下指代消除的评价指标。上面提到,指代消除的过程本质上是聚类的过程,所以所有可用于评价聚类效果的指标都可以用来评价指代消除,比如指标MUC, CEAF, LEA, B-CUBED, BLANC等。

下图是一个B-cubed指标的例子,对于每个System cluster,计算其中的Gold cluster的Precision和Recall,然后取平均。如果欠聚类,则Precision很高,但Recall低;如果过聚类,则Recall很高,但Precision低,所以可以对P和R再求个F1。


最后,指代消解领域目前的进展如下表所示,在OntoNotes数据集上,目前的SOTA就是上面介绍的end2end模型,该模型虽然比开始的Rule-based方法高了不少,但是本身的绝对性能其实还有很大的提升空间。

2 thoughts on “CS224N(2.26)Coreference Resolution

Leave a Reply

Your email address will not be published. Required fields are marked *