End2End

今天介绍的内容是指代消解（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打分分布，最后加权平均起来。 ...

今天介绍大名鼎鼎的Transformer，它于2017年出自谷歌的论文《Attention Is All You Need》（https://arxiv.org/pdf/1706.03762.pdf），用Attention实现机器翻译模型，并取得了新的SOTA性能。 传统的机器翻译模型一般是结合RNN和Attention，可以看我之前的博客介绍：CS224N（1.31）Translation, Seq2Seq, Attention。虽然RNN+Attention的组合取得了不错的效果，但依然存在一些问题。由于RNN是序列依赖的模型，难以并行化，训练时间较长；且当句子很长时由于梯度消失难以捕捉长距离依赖关系。虽然相继推出的LSTM和GRU能一定程度上缓解梯度消失的问题，但这个问题依然存在。而且LSTM和GRU难以解释，我们根本不知道当前timestep依赖远的词多一点还是近的词多一点。 Transformer的思想很激进，它完全抛弃了RNN，只保留Attention，从其论文标题可见一斑。RNN无法并行化的根本原因是它的正向和反向传播是沿着句子方向（即水平方向），要想实现并行化，肯定不能再走水平方向了。于是，Transformer完全抛弃水平方向的RNN，而是在垂直方向上不断叠加Attention。由于每一层的Attention计算只和其前一层的Attention输出有关，所以当前层的所有词的Attention可以并行计算，互不干扰，这就使得Transformer可以利用GPU进行并行训练。 具体来说，Transformer的结构如下图所示。我们知道end2end的机器翻译模型一般都是Encoder+Decoder的组合，Encoder对源句子进行编码，将编码信息传给Decoder，Decoder翻译出目标句子。Transformer也不例外，下图左边即为Encoder，右边即为Decoder。 Encoder的每一层有两个子层组成，包括Self-Attention和Feed-forward neural network (FFNN)。FFNN就是常规的全连接网络，没什么可说的，下面重点介绍Self-Attention。 Encoder Self-Attention的结构如下图所示，由于此时是Encoder阶段，对于每个词，都能看到句子中所有其他的词（对应到RNN里面就是可以用双向的RNN）。假设我们想要抽取第二个词”represent”的特征表示。首先，对第二个词的词向量\(e_2\)进行线性变换，即乘以矩阵\(matmul_Q\)，得到Query，这就是标准Attention中的Query。其次，对周围所有的其他词，比如\(e_1\)，也进行线性变换，变换矩阵为\(matmul_K\)，得到很多的Key。然后，Query和所有Key做点积，并用softmax归一化，得到了Query在周围词上的Attention score distribution。接着，周围词乘以另一个线性变换矩阵\(matmul_V\)，变换为Value。最后，Value和Attention score distribution进行加权求和，并加上\(e_2\)自己，送给FFNN。图中右下角的公式中的分母只是个缩放因子。 回顾一下，一个标准的Attention包括三个向量：Q、K、V，其中Q为用来查询的Query，K表示被查询的Key，V表示被查询的Value。其中的K和V来源相同，只是经过了不同的变换。形象描述就是：计算Q在K上分配的注意力\(QK^T\)，然后从V中取出这部分注意力的值\(softmax(\frac{QK^T}{\sqrt{d_k}})V\)。 Self-Attention的优点。因为每个词都和周围所有词做attention，所以任意两个位置都相当于有直连线路，可捕获长距离依赖。而且Attention的可解释性更好，根据Attention score可以知道一个词和哪些词的关系比较大。易于并行化，当前层的Attention计算只和前一层的值有关，所以一层的所有节点可并行执行self-attention操作。计算效率高，一次Self-Attention只需要两次矩阵运算，速度很快。 Transformer的Decoder部分每一层有三个子层组成，包括Self-Attention、Encoder-Decoder Attention和FFNN。Decoder的Self-Attention如下图所示，和Encoder的Self-Attentoin非常像，只不过当要Decoder第二个词时，用黑框蒙住了第三、四个词的运算（设置值为-1e9）。因为对于机器翻译来说，Encoder时能看到源句子所有的词，但是翻译成目标句子的过程中，Decoder只能看到当前要翻译的词之前的所有词，看不到之后的所有词，所以要把之后的所有词都遮住。所以这个Attention也叫Masked Self-Attention。这也说明Transformer只是在Encoder阶段可以并行化，Decoder阶段依然要一个个词顺序翻译，依然是串行的。 不要忘了我们的任务是机器翻译，Decoder Self-Attention只用到了翻译出来的目标句子的前缀信息，还没用到源句子的信息，这部分就在Encoder-Decoder Attention中。前面说了对于源句子，通过Encoder的Self-Attention+FFNN，源句子的每个词都有一个输出向量，这些输出向量作为Encoder-Decoder Attention的Keys和Values，而从目标句子当前要翻译的词的Decoder Self-Attention出来的向量就是Encoder-Decoder Attention的Query。从下图可以看到，Encoder上面出来指向右边Multi-Head Attention的两个箭头就是Keys和Values，而从下面出来指向Multi-Head Attention的一个箭头就是Query。Encoder-Decoder Attention的作用就是看看当前要翻译的词在源句子中各个词上的注意力情况。 我们知道Attention机制是位置无关的，因为对于每个词，它都和句子中的所有词直连求Attention score，跟词在句子中的位置没有关系。但是句子作为一种线性结构，词在句子中的顺序对句子的含义至关重要。为了考虑词的位置信息，词在输入Attention前，把词向量和词在句子中的位置Positional Encoding加起来，得到一个新的向量，输入到Attention中，如上图所示。这个Positional Encoding可通过公式计算得到，这里不展开。 上图的Attention前面都有一个修饰词Multi-Head，也就是下图的Parallel attention heads。前面提到一个标准的Attention包括三个向量Q、K、V，它们分别由原始的查询向量和特征向量乘以矩阵\(matmul_Q\)、\(matmul_K\)、\(matmul_V\)得到。如果一个词在计算Attention时，选用多个不同的\(matmul_Q\)、\(matmul_K\)、\(matmul_V\)，得到的Attention输出向量也就不同了，这正好可以用来表示一个词在句子中的不同作用。比如句子“华为是一家中国的公司”中的“华为”，它的语义是一家公司，它在句子中的成分是主语，也就是说一个词至少有其语义信息和句法信息，如果只用一套\(matmul_Q\)、\(matmul_K\)、\(matmul_V\)，则只能得到一种含义，如果设置多套\(matmul_Q\)、\(matmul_K\)、\(matmul_V\)，则能提取到这个词更多的信息。于是，在对每个词进行Attention时，都会设置多套\(matmul_Q\)、\(matmul_K\)、\(matmul_V\)，提取多个Attention输出向量，然后拼接起来，这就是Multi-Head Attention，或者说Parallel attention heads。我个人理解多套\(matmul_Q\)、\(matmul_K\)、\(matmul_V\)相当于CNN中不同的kernal，相当于不同的特征提取器。 课上还介绍了利用Transformer生成图片和音乐的应用，感兴趣的同学可以搜索相关论文看一看。 有关Transformer的介绍，还可参考如下三个链接： http://jalammar.github.io/illustrated-transformer/ https://zhuanlan.zhihu.com/p/48508221 https://zhuanlan.zhihu.com/p/44121378

今天介绍另一个NLP任务——机器翻译，以及神经网络机器翻译模型seq2seq和一个改进技巧attention。 机器翻译最早可追溯至1950s，由于冷战的需要，美国开始研制由俄语到英语的翻译机器。当时的机器翻译很简单，就是自动从词典中把对应的词逐个翻译出来。 后来在1990s~2010s，统计机器翻译（Statistical Machine Translation, SMT）大行其道。假设源语言是法语\(x\)，目标语言是英语\(y\)，机器翻译的目标就是寻找\(y\)，使得\(P(y|x)\)最大，也就是下图的公式。进一步，通过贝叶斯公式可拆分成两个概率的乘积：其中\(P(y)\)就是之前介绍过的语言模型，最简单的可以用n-gram的方法；\(P(x|y)\)是由目标语言到源语言的翻译模型。为什么要把\(P(y|x)\)的求解变成\(P(x|y)*P(y)\)？逐个击破的意思，\(P(x|y)\)专注于翻译模型，翻译好局部的短语或者单词；而\(P(y)\)就是之前学习的语言模型，用来学习整个句子\(y\)的概率，专注于翻译出来的句子从整体上看起来更加通顺、符合语法与逻辑。所以问题就转化为怎样求解\(P(x|y)\)。 SMT进一步把\(P(x|y)\)分解成\(P(x,a|y)\)，其中\(a\)表示一个对齐alignment，可以认为是两种语言之间单词和单词或短语和短语的一个对齐关系。如下图所示是一个英语和法语的alignment。对齐本身就很复杂，存在1对1，1对多，多对1，多对多等情况，所以\(P(x,a|y)\)的求解在给定\(y\)的情况下，不但要考虑对齐方案\(a\)的情况\(P(a|y)\)，还需要考虑对齐之后词与词的翻译情况\(P(x|a,y)\)，可能的情况非常多。 那么，SMT怎样找到\(\arg max_y\)呢？穷举所有情况是不可能的，启发式搜索是可行的。形象描述就是在搜索过程中，对概率较低的路径进行剪枝，只保留概率较大的翻译情况。如下图的搜索树，对于概率较低的路径就不往下搜索了。 总之，统计机器翻译非常复杂，有很多的子模块，需要很多的人工干预和特征工程。 2014年，seq2seq模型横空出世，神经网络机器翻译（Neural Machine Translation, NMT）方兴未艾。seq2seq顾名思义，就是从序列到序列的模型，因为机器翻译的源语言和目标语言都是seq。 seq2seq的NMT如下图所示，它由两个RNN组成，左边的红色部分称为Encoder RNN，它负责对源语言进行编码（Encode）；右边的绿色部分称为Decoder RNN，它负责对目标语言进行解码（Decode）。首先，Encoder RNN可以是任意一个RNN，比如朴素RNN、LSTM或者GRU。Encoder RNN负责对源语言进行编码，学习源语言的隐含特征。Encoder RNN的最后一个神经元的隐状态作为Decoder RNN的初始隐状态。Decoder RNN是一个条件语言模型，一方面它是一个语言模型，即用来生成目标语言的；另一方面，它的初始隐状态是基于Encoder RNN的输出，所以称Decoder RNN是条件语言模型。Decoder RNN在预测的时候，需要把上一个神经元的输出作为下一个神经元的输入，不断的预测下一个词，直到预测输出了结束标志符<END>，预测结束。Encoder RNN的输入是源语言的word embeding，Decoder RNN的输入是目标语言的word embeding。 seq2seq是一个很强大的模型，不但可以用来做机器翻译，还可以用来做很多NLP任务，比如自动摘要、对话系统等。 seq2seq作为一个条件语言模型，形式化来说，它直接对\(P(y|x)\)进行建模，在生成\(y\)的过程中，始终有\(x\)作为条件，正如下图的条件概率所示。 上面介绍了seq2seq的预测过程，seq2seq的训练过程如下图所示。训练的时候，我们同时需要源语言和翻译好的目标语言，分别作为Encoder RNN和Deocder RNN的输入。对于Encoder RNN没什么好说的。Decoder RNN在训练阶段，每一个时间步的输入是提供的正确翻译词，输出是预测的下一个时间步的词的概率分布，比如在\(t=4\)，预测输出是\(\hat y_4\)，而正确答案是“with”，根据交叉熵损失函数，\(J_4=-\log P(“with”)\)。总的损失函数就是所有时间步的损失均值。 seq2seq的训练过程是end2end的，即把Encoder RNN和Decoder RNN作为一个整体进行训练，不会像SMT一样有很多的子模块单独训练。当然seq2seq也可以单独对encoder和deconder进行训练优化，再组合，但是这个效果不一定会比整体优化encoder和deconder更好。 上上张图介绍的seq2seq的预测过程，实际上是一个贪心的预测过程，即在Decoder RNN的每一步都贪心选择\(\hat y_t\)概率最大的那个词。但是贪心只能保证每一步是最优的，无法保证预测出来的句子整体是最优的。特别是如果在\(t\)时刻贪心选择的词不是全局最优，会导致\(t\)时刻往后的所有预测词都是错误的，没有回头路了。但是如果每个时间步都穷举所有可能的情况的话，时间复杂度\(O(V^T)\)又太高了。 Beam search搜索策略是贪心策略和穷举策略的一个折中方案，它在预测的每一步，都保留Top-k高概率的词，作为下一个时间步的输入。k称为beam size，k越大，得到更好结果的可能性更大，但计算消耗也越大。请注意，这里的Top-k高概率不仅仅指当前时刻的\(\hat y_t\)的最高概率，而是截止目前这条路径上的累计概率之和，如下图的公式所示。 举例如下，假设\(k=2\)，第一个时间步保留Top-2的词为”he”和”I”，他们分别作为下一个时间步的输入。”he”输入预测输出前两名是”hit”和”struck”，则”hit”这条路的累加概率是”he”的概率加上”hit”的概率=-1.7，类似的可以算出其他几个词对应路径的概率打分。最后在这4条路上保留\(k=2\)条路，所以”hit”和”was”对应路径保留，作为下一个时间步的输入；”struck”和”got”对应路径被剪枝。 最终的搜索树如下图所示，可以看到在每个时间步都只保留了\(k=2\)个节点往下继续搜索。最后”pie”对应的路径打分最高，通过回溯法得到概率最高的翻译句子。请注意，beam search作为一种剪枝策略，并不能保证得到全局最优解，但它能以较大的概率得到全局最优解，同时相比于穷举搜索极大的提高了搜索效率。 在beam search的过程中，不同路径预测输出结束标志符<END>的时间点可能不一样，有些路径可能提前结束了，称为完全路径，暂时把这些完全路径放一边，其他路径接着beam search。beam search的停止条件有很多种，可以设置一个最大的搜索时间步数，也可以设置收集到的最多的完全路径数。 当beam search结束时，需要从n条完全路径中选一个打分最高的路径作为最终结果。由于不同路径的长度不一样，而beam search打分是累加项，累加越多打分越低，所以需要用长度对打分进行归一化，如下图所示。那么，为什么不在beam search的过程中就直接用下面的归一化打分来比较呢？因为在树搜索的过程中，每一时刻比较的两条路径的长度是一样的，即分母是一样的，所以归一化打分和非归一化打分的大小关系是一样的，即在beam search的过程中就没必要对打分进行归一化了。 ...