华人科学家团队再获ACL最佳论文：以数学方法生成最优词表

北京时间8月5日进行的ACL 2021大会上，主办方为“最佳论文”正式颁奖，字节跳动AI Lab的论文《Vocabulary Learning via Optimal Transport for Neural Machine Translation》获此殊荣。该研究提出了一种新的词表学习方案 VOLT，在多种翻译任务上取得了优秀的结果。

这是ACL成立59年以来，华人科学家团队第二次摘得最高奖项。ACL大会由国际计算语言学协会主办，是自然语言处理与计算语言学领域最高级别的学术会议。自2010年百度投中ACL开始，越来越多华人面孔出现在ACL上，并不断斩获荣誉：

2012年，清华大学获得“最佳学生论文”奖；

2019年，中科院计算所、腾讯微信AI与华为诺亚方舟实验室等单位合作获得“最佳长论文”奖，南京理工大学和香港科技大学也分别获得“杰出论文”奖；

来到2021年，不仅字节跳动摘得“最佳论文”荣誉，香港中文大学与腾讯AI Lab合作论文也被评为“杰出论文”。

根据ACL 2021 官方发布的信息，本届大会共计收到 3350 篇论文投稿，最终有 21.3% 的论文录用到主会（Main Conference），并接收了14.9%的论文到Findings子刊，综合录用率为 36.2%。字节跳动AI Lab的VOLT为何能在3350篇论文中脱颖而出？

ACL官方评审意见认为：字节跳动的VOLT方案对机器翻译中一个重要问题提出了有效且新颖的解决方案，能显著减少词表的学习和搜索时间，相信其不仅会在研究界产生重要影响，在工业应用方面也有着巨大潜力。

VOLT尝试解决自然语言处理（NLP）的两个基本问题：什么是最优词表，如何生成最优词表。

什么是最优词表：以边际收益定义词表评价指标MUV

对如何定义最优词表，首先要考虑词表的什么属性比较重要。以下图为例，以下的词表哪个较好一些？

目前为止，子词级别的词表使用比较多并且已经在多个任务上被验证效果。因此，在目前的认知条件下，我们可以认定子词为较好的选择。相比于传统的词为基础单位的词表，子词规模小不会面临稀疏标记（token）的问题。稀疏标记是指在语言中出现概率比较小的子词。相比于字结构的词表，子词也不会面临熵太大语义无法区分的问题。作者也是主要考虑了信息熵和词表大小两个主要因素来涉及评价指标。

【信息熵】信息熵也可以理解成为蕴含在每个字中的平均语义含量。直观上理解信息熵越小表示每个字或者词表示的信息越简单，那么更加利于模型学习。作者使用基于字的熵计算方式来评估该属性，其中v为词表，i为词表中的标记，P为标记在训练集出现的频率：

【词表大小】词表越大，稀疏标记出现的概率也变大。众所周知，机器学习对训练数据的数量要求很高，稀疏标记的出现概率较低，因此稀疏标记越多，需要的训练数据往往也就越多。因此，在基于频率的方法下，词表越小，稀疏标记越少，参数也越少。因此从词表大小角度来看，我们期望词表大小越小越好。

总的来说，信息熵和词表大小不可以兼得。一般来说，词表越大，所需参数越大，稀疏标记越多，但是信息熵在减小。

论文作者为了建模这种平衡，引入了边际收益的概念。边际收益衡量了付出单位代价所能获得的利益的数量。边际收益越大，那么投入产出比越高。作者将信息熵看成是边际收益中的利益，词表大小看成是边际收益中的代价。随着词表的增加，不同大小的词表的信息熵收益是不同的，作者使用边际收益的概念定义了衡量词表质量的指标MUV，并且观测到了MUV指标和下游任务的相关性。

如何生成最优词表：将词表搜索变为最优运输问题

给定词表评价指标MUV之后，学习最优词表的问题可以粗略地等价为寻找具有最大MUV的词表问题，但是词表搜索空间不仅庞大，而且是离散空间，如何去高效地学到相应的词表呢？作者此处巧妙地将词表搜索变成了最优运输的过程。为了便于大家更容易理解最优运输，这里对最优运输先做一个简单地回顾。

【最优运输】大约250年前，法国数学家蒙日在其作品中对这类问题进行了严格分析，下面是一个比较直观的例子。假设在第二次世界大战中，我方有一些前线发出了需要增兵的信号，而我们的士兵分散在不同的后方根据地。不同的前线需要的士兵个数不同，后方根据地的士兵个数也不同，前线距离后方根据地的距离也不同。问如何设计转移方案，使得总转移代价最低？这就是最优运输想要回答的问题。

【词表搜索】作者在新的定义框架下，将字表示为士兵，将所有的标记候选表示为前线，不同字的数量为在训练集中出现的频次，不同标记候选需要字的数量为该标记在训练集中出现的频次。比如cat在训练集中出现了20次，那么cat需要20个c，20个a，和20个t来组成该标记。为了避免不合法的搬运，作者将不合法的搬运设为无穷大（比如字e搬运给标记cat是不合法的）。由于字的个数是有限的，肯定有一些标记候选无法拿到对应的字，那么这些标记将会从最终的词表中踢出去。最后，得到搬运的标记成最后的词表。也就是说，每次搬运方式都对应一种词表，只需要将搬运的代价对应成词表学习问题的目标，即可使用高效的最优运输的解法去解决。那么如何将词表学习的问题转化成为最优运输的代价呢，此处本文做了一些重构操作：

首先，MUV可以理解成为熵对词表大小的一阶导数，为了建模连续的导数，本文引入了相对分数来模拟导数：

这里的H代表的是信息熵，分子是信息熵的相对变化量，而分母中的i代表词表大小的变化量，S是一个递增序列，每个元素代表以该时刻大小为上届的所有词表组合。因此对于每个步骤来说，都存在一个具有最大MUV分数的词表，只要对所有的步骤做遍历，就可找到最优词表。为了进一步降低求解难度，作者对每一步的求解公式做了一个近似，提出最优该公式的上届，也就是：

那么每个步骤的问题就转化成了每个步骤寻找熵最大词表的问题。作者紧接着使用了基于熵的最优运输解法就可以将最优运输的目标定义成为寻找熵最大词表的问题。具体求解公式如下，最小化公式的左边为转移矩阵的熵，可以近似理解为词表的熵，后边的项为避免不合法搬运的正则化项。如此以来，就可以使用标准的求解算法去求解该公式：

总的来说，对于每个步骤，作者都是用如上算法找到词表的最大熵并且计算出当前的最大MUV分数，最后遍历所有的步骤即可找到具有最优的MUV的词表。需要说明的是在得到标记候选集的时候，作者为了简单，借用了字节对编码（BPE：byte pair encoder）学到的标记组合。具体VOLT方法伪代码见如下所示：

该方法不需要下游任务训练，因此非常简单高效。

测试结果

以下是VOLT生成的词表在双语翻译的结果，可以看出，新方法学到的词表比经常使用的词表小很多，效果也很有竞争力。

以下是在多语翻译的结果，总体来看，在三分之二的数据集上效果也是较好的。

延伸思考

古往今来，大家在做机器翻译的时候都比较习惯用同样的一套词表大小，比如双语翻译中的32000。但是看本文的实验可以发现，有很多比32000更好的选择，尤其是低资源翻译上。

这篇文章除了介绍VOLT提供一个更好的词表学习工具外，还分析了词表大小对表现的影响。作者使用VOLT搜索出的词表大小生成了BPE的词表，发现也可以得到相似的结果，因此作者也推荐使用VOLT作为一种词表大小学习方式。除此之外，实验中也发现简单的基线模型在使用了VOLT生成的词表之后也达到了和最优受限结果（不借助外部资源）匹配的分数，或许也可以引发大家对基线模型效果的进一步思考。

论文地址：https://arxiv.org/abs/2012.15671

项目地址：https://github.com/Jingjing-NLP/VOLT

论文blog：https://jingjing-nlp.github.io/volt-blog/