概述
对于从业者来说，大家无时无刻不在使用词表对语言进行向量化表示。在深度学习时代，词表构建基本上是所有自然语言处理任务的第一步工作。尽管现今也有了一些比较通用的词表处理方法，但是仍然没有办法回答最基础的问题：什么是最优词表，如何生成最优词表？为了回答该问题，本论文尝试提出一种无需训练的词表评价指标和针对该评价指标的词表学习方案VOLT。该方案在常用的英德翻译、英法翻译、低资源翻译、多语言翻译上都取得了相比传统词表解决方案更好的结果。
简介
据资料记载，全世界目前已有5651种语言。尽管这些语言在书写、发音、词汇量等层面各不相同，在计算语言领域，从业者们有一套统一的框架去表示这些语言输入。
目前自然语言的通用做法为：1）先为语言构建词表，2）使用词表将输入文本分块。较常用的词表构建方法为子词（sub-word）构建法。该方法先将连续的字按照频率进行切块。频率最高的切块们将构成最后的词表。下图是使用子词词表切割的输入样例。每个方块对应一个单独的表示。
【词表：重要的第一步】 现在基本上所有的自然语言处理任务都需要词表作为第一步。这些任务不仅仅包括实验室研究任务，比如命名实体识别、阅读理解等，也包括大规模商用任务，比如机器翻译，搜索推荐等等。也就是说，每一分钟都有百万千万的自然语言处理程序运行在这些词表之上。尽管词表如此重要，相比于深度模型的研究工作数量而言，词表的研究工作仍旧是凤毛麟角。而且尽管现在已经有了一些还不错的词表构建方法，但是我们好像仍旧无法回答“最优的词表长什么样子？如何生成最优词表？”等问题。
【如何生成最优词表？】 为了弄清楚什么是最优词表，第一个问题是如何评价词表。尽管可以使用最直接的方案：将所有的词表在任务上都进行测试。但考虑到计算资源的有限性和庞大的词表搜索空间，这种方案基本属于理论上可行但实践不可行。那么一个自然而言的问题便是，如何在不进行下游任务训练的情况下去评价一个词表的好坏？第二个问题是假设我们有了该评价方法，考虑到词表的离散特性，如何从庞大的离散空间搜索最优词表。针对这两个问题，作者们尝试在本工作中给出了一个全新的解决方案，该方案在多样化的翻译任务上都取得了不错的效果。接下来，本论文将详细介绍该工作是如何解决这两大问题的。
问题一：什么是最优词表
如果我们要考虑这个问题，那么就要考虑词表的什么属性比较重要？为了带领大家思考这个问题，可以先看一个简单的问题：以下的词表哪个较好一些？
目前为止，子词级别的词表使用比较多并且已经在多个任务上被验证效果。因此，在目前的认知条件下，我们可以认定子词为较好的选择。相比于传统的词为基础单位的词表，子词不会面临稀疏标记（token）的问题。稀疏标记（token）是指在语言中出现概率比较小的子词。相比于字结构的词表，子词也不会面临熵太大语义无法区分的问题。作者也是主要考虑了信息熵和词表大小两个主要因素来涉及评价指标。
【信息熵】信息熵也可以理解成为蕴含在每个字中的平均语义含量。直观上理解信息熵越小表示每个字或者词表示的信息越简单，那么更加利于模型学习。作者使用基于字的熵计算方式来评估该属性，其中v为词表，i为词表中的token，P为token在训练集出现的频率：
【词表大小】词表越大，稀疏标记（token）出现的概率也变大。众所周知，机器学习对训练数据的数量要求很高，稀疏标记（token）的出现概率较低，因此稀疏标记（token）越多，需要的训练数据往往也就越多。因此，在基于频率的方法下，词表越小，稀疏标记（token）越少，参数也越少，那么更加有利于模型学习。
总的来说，信息熵和词表大小不可以兼得。一般来说，词表越大，所需参数越大，稀疏标记（token）越多，但是信息熵在减小。因此，作者为了建模这种平衡，引入了边际收益的概念。边际收益衡量了付出单位代价所能获得的利益的数量。边际收益越大，那么投入产出比越高。作者将信息熵看成是边际收益中的利益，词表大小看成是边际收益中的代价。随着词表的增加，不同大小的词表的信息熵收益是不同的，作者使用边际收益的概念定义了衡量词表质量的指标MUV，并且观测到了MUV指标和下游任务的相关性。
问题二：怎么学习最优词表
给定词表评价指标MUV之后，学习最优词表的问题可以粗略地等价为寻找具有最大MUV的词表问题，但是词表搜索空间不仅庞大，而且是离散空间，如何去高效地学到相应的词表呢？作者此处巧妙地将词表搜索变成了最优运输的过程。为了便于大家更方便地理解最优运输，这里对最优运输先做一个简单地回顾。
【最优运输】最优运输是大约250年前，法国数学家蒙日在其作品中第一次对这类问题进行了严格分析，下面是一个比较直观的例子。假设在第二次世界大战中，我方有一些前线发出了需要增兵的信号，而我们的士兵分散在不同的后方根据地。不同的前线需要的士兵个数不同，后方根据地的士兵个数也不同，前线距离后方根据地的距离也不同。问如何设计转移方案，使得总转移代价最低？这就是最优运输想要回答的问题。
最优运输问题示意图
【词表搜索】作者在新的定义框架下，将字表示为士兵，将所有的标记（token）候选表示为前线，不同字的数量为在训练集中出现的频次，不同标记（token）候选需要字的数量为该标记（token）在训练集中出现的频次。比如cat在训练集中出现了20次，那么cat需要20个c，20个a，和20个t来组成该单词。为了避免不合法的搬运，作者将不合法的搬运设为无穷大（比如字e搬运给词cat是不合法的）。由于字的个数是有限的，肯定有一些标记（token）候选无法拿到对应的字，那么这些标记（token）将会从最终的词表中踢出去。最后，得到搬运的词组合成最后的词表。也就是说，每次搬运方式都对应一种词表，只需要将搬运的代价对应成词表学习问题的目标，即可使用高效的最优运输的解法去解决。那么如何将词表学习的问题转化成为最优运输的代价呢，此处本文做了一些重构操作：
首先，MUV可以理解成为熵对词表大小的一阶导数，为了建模连续的导数，本文引入了相对分数来模拟导数：
这里的H代表的是信息熵，分子是信息熵的相对变化量，而分母中的i代表size的变化量，S是一个递增序列，每个元素代表以该时刻大小的所有词表组合。因此对于每个step来说，都存在一个具有最大MUV分数的词表，只要对所有的step做遍历，就可找到最优词表。为了进一步降低求解难度，作者对每一步的求解公式做了一个近似，提出最优该公式的下届，也就是：
那么这每个step的问题就转化成了每个step寻找熵最大词表的问题。作者紧接着使用了基于熵的最优运输解法就可以将最优运输的目标定义成为寻找熵最大词表的问题。具体求解公式如下，最小化公式的左边为转移矩阵的熵，可以近似理解为词表的熵，后边的项为避免不合法搬运的正则化项。如此以来，就可以使用标准的求解算法去求解该公式：
总的来说，对于每个step，作者都是用如上算法找到词表的最大熵并且计算出当前的最大MUI分数，最后遍历所有的step即可找到具有最优的MUV的词表。需要说明的是在得到标记（token）候选集的时候，作者为了简单，借用了字节对编码（BPE：byte pair encoder）学到的标记组合。具体VOLT方法伪代码见如下所示：
方法不需要任务的下游任务训练，因此非常简单高效。
结果
以下是VOLT生成的词表在单语翻译的结果，可以看出新方法学到的词表比经常使用的词表大小小很多，效果也很有竞争力。
以下是在多语翻译的结果，总体来看，在三分之二的数据集上效果也是较好的。
简单思考
古往今来，大家在做机器翻译的时候一直都比较习惯用同样的一套词表大小，比如双语翻译中的32K。但是看本文的实验可以发现，有很多比32K更好的选择，尤其是低资源翻译上。这篇文章除了介绍VOLT提供一个更好的词表学习工具外，还分析了词表大小对表现的影响。作者使用VOLT搜索出的词表大小生成了BPE的词表，发现也可以得到相似的结果，因此作者也推荐使用VOLT作为一种词表size学习方式。除此之外，实验中也发现简单的基线模型在使用了VOLT生成的词表之后也达到了和最优结果匹配的分数，或许也可以引发大家对基线模型效果的进一步思考。
参考文献
[1] Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. 2019. Character-level language modeling with deeper self-attention.
[2] Wenhu Chen, Yu Su, Yilin Shen, Zhiyu Chen, Xifeng Yan, and William Yang Wang. 2019. How large a vocabulary does text classification need?
[3] Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport.
[4] Taku Kudo and John Richardson. 2018. Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.
[5] Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural machine translation of rare words with subword units
