Vocabulary Learning via Optimal Transport for Neural Machine Translation
ACL2021 Best paper Code: link
这篇也就是被ICLR2021拒了后被评为ACL2021 best paper的文章，来自字节跳动的AI Lab。
Related Work
Subword model
英文中传统分词方法基于空格进行tokenization。但这一方法面临OOV (Out Of Vocabulary)问题和同一单词的不同形态造成的冗余。因此如今BERT等模型多使用Subword模型，它的划分粒度介于词与字符之间。主流的(指某些中文网站上有博客介绍的）Subword model有Byte Pair Encoding (BPE), WordPiece和Unigram Language Model。
Byte-Pair-Encoding(BPE)
"Neural machine translation of rare words with subword units."arXiv preprint arXiv:1508.07909(2015).
BPE算法被用于处理NMT (Neural Machine Translation)任务中的OOV问题。
BPE是一种自下而上的压缩算法。将单词作为单词片段处理（word pieces），以便于处理未出现单词。
we adopt BPE generated tokens as the token candidates.
论文提出的算法要先用BPE...
概要
机器翻译中，token vocabulary对最终结果会产生很大的影响。论文研究了词表的评价指标以及如何不通过训练直接找到最优的词表。文章的主要内容包括 1. 从信息论角度分析词表的作用 2.借助Optimal transport来找到最佳token词典 3. 更小的词表but更高的BLEU。
Intro
词汇量（vocabulary size）会影响机器翻译任务的绩效，而通过遍历搜索来寻找最优的词汇量需要极高的计算开销，因此现有的研究大多采用统一的大小，如30k-40k。BPE通过选择频率最高的sub-words做为词典的token以进行数据压缩，以此减少熵。
语料熵随着词汇量的增加而减少，有利于模型学习。另一方面，过多的字符会导致字符稀疏化，这会损害模型学习。本文通过同时考虑熵和词汇量大小来探索自动词汇化，需要找到一个合适的目标函数来同时优化它们。其次，假设给出了适当的度量，由于指数搜索空间（\(2^N\))，解决这种离散优化问题仍然具有挑战性。
针对上述问题，论文提出VOcabulary Learning approach via optimal Transport, VOLT——最优传输的词汇学习方法
总的来说，论文的目标是1.得到“简洁而不臃肿”的词汇表 —— entropy-size trade off 2. 优化搜索过程。
Marginal Utility of Vocabularization (MUV)
借用经济学中的边际效应的概念，以词汇的边际效应（MUV）作为衡量标准， 然后将目标转向在可处理的时间复杂度中最大化 MUV。 
在经济学中，边际效应用于平衡收益和成本，因此论文使用 MUV 来平衡熵（收益）和词汇量（成本）。也就是从成本（大小）的增加中获得多大的收益（熵）。
Definition of MUV
MUV 表示熵对大小的负导数 \[ \mathcal{M}_{v(k+m)}=\frac{-\left(\mathcal{H}_{v(k+m)}-\mathcal{H}_{v(k)}\right)}{m} \] 其中 \(v(k), v(k+m)\) 是两个分别带有 \(k\) 和 \(k+m\) 个字符的词汇。\(\mathcal{H}_{v}\) 表示词汇表 \(v\) 语料库的樀，它由字符樀的总和定义。用字符的平均长度对熵进行归一化来避免字符长度的影响。最终的熵定义为： \[ \mathcal{H}_{v}=-\frac{1}{l_{v}} \sum_{j \in v} P(j) \log P(j) \] \(P(i)\) 是训练语料库中token \(i\) 的相对频率, \(l_{v}\) 是词汇表 \(v\) 中token的平均长度。
Preliminary Results
为了验证 MUV 作为词汇化衡量标准的有效性，作者对来自 TED 的 45 个语言对进行了实验，并计算了 MUV 和 BLEU 分数之间的Spearman相关系数(\(\rho\))。Spearman 得分为 0.4。
We believe that it is a good signal to show MUV matters
有了MUV作为评价指标，我们有两个选择来获得最终词表：搜索和学习。作者认为基于学习是更高效的，因此进一步探索了一种基于学习的解决方案 VOLT。（当然最终借助实验比较了 MUV-Search 和 VOLT的性能。）
Maximizing MUV via Optimal Transport
优化问题
首先引入一个辅助变量\(S\)，\(\boldsymbol{S}=\{k, 2 \cdot k, \ldots,(t-1) \cdot k, \cdots\}\)。 \(S\)是一个递增序列，对于每个时间戳t，\(S[t]\)代表不多于\(S[t]\)个词条的词表集合。引入这一变量，根据递推关系来计算任意一个词表的MUV（借助前一个时间戳s[t-1]上的词表递进计算）
\(k\)代表前后两个词表\(v(t)\)和\(v(t-1)\)之间的大小差（size gap）。我们的目标是找到MUV最高的\(v[t]\) \[ \begin{array}{l} \underset{t}{\arg \max } \underset{v(t-1) \in \mathbb{V}_{\boldsymbol{S}[t-1]}, v(t) \in \mathbb{V}_{S[t]}}{\arg \max } \mathcal{M}_{v(t)}= \\ \underset{t}{\arg \max } \underset{v(t-1) \in \mathbb{V}_{\boldsymbol{S}[t-1]}, v(t) \in \mathbb{V}_{S[t]}}{\arg \max }-\frac{1}{k}\left[\mathcal{H}_{v(t)}-\mathcal{H}_{v(t-1)}\right] \end{array} \] \(\mathbb{V}_{\boldsymbol{S}[t-1]}\)和 \(\mathbb{V}_{\boldsymbol{S}[t]}\)表示两个词表的集合，其中每个词表大小的上界为\(s[t-1]\)和\(s[t]\)
The inner arg max represents that the target is to find the vocabulary from \(\mathbb{V}_{\boldsymbol{S}[t]}\) with the maximum MUV scores. The outer arg max means that the target is to enumerate all timesteps and find the vocabulary with the maximum MUV scores.
遍历t，遍历\(\mathbb{V}_{\boldsymbol{S}[t-1]}\)。
（词表越大熵越小）上述公式意味着从v(t-1)这个词表，增加i个词/tokens之后，期望新得到的v(t)词表的熵降低的最多。即两个词表对应的熵的差值越大越好。
Due to exponential search space, we propose to optimize its upper bound: \[ \underset{t}{\arg \max } \frac{1}{k}\left[\underset{v(t) \in \mathbb{V}_{S[t]}}{\arg \max } \mathcal{H}_{v(t)}-\underset{v(t-1) \in \mathbb{V}_{S[t-11}}{\arg \max } \mathcal{H}_{v(t-1)}\right] \]
(论文ArXiv上的前一版本中写的还是lower bound...而最新版放的是upper bound...)
anyway至此整个方法可以分成两个步骤：
- 每个时间步t上，寻找最优的词表（按照最大化熵来寻找）
- 枚举每个时间步t，并输出满足上一个公式的词表（对应的就是时间步t的”最优词表“）
step1的目标就是最大化： \[ \underset{v(t) \in \mathbb{V}_{\boldsymbol{S}[t]}}{\arg \max }-\frac{1}{l_{v(t)}} \sum_{j \in v(t)} P(j) \log P(j) \] \(l_{v}\)是每个token的平均字符长度，\(P(j)\)是token j的概率（频率）
However, notice that this problem is in general intractable due to the extensive vocabulary size. Therefore, we instead propose a relaxation in the formulation of discrete optimal transport, which can then be solved efficiently via the Sinkhorn algorithm
借助最优传输OT的思想，松弛原优化问题，进而用信息论中的Sinkhorn algorithm求解。
Optimal Transport （不太懂）
- 每个transport matrix对应一个词表；
- transport matrix决定有多少chars被“运输”到token候选（词条候选）；
- 长度为0的tokens（包含0个chars)，不会被增加到词表。
不同的”运输矩阵“会带来不同的”运输开销”。而最优化运输（路径）问题的目标就是寻找一个“运输矩阵“，使得”运输开销“(即，负熵)最小化。
目标函数： \[ \begin{array}{c} \min _{v \in \mathbb{V}_{S[t]}} \frac{1}{l_{v}} \sum_{j \in v} P(j) \log P(j) \\ \text { s.t. } \quad P(j)=\frac{\operatorname{Token}(j)}{\sum_{j \in v} \operatorname{Token}(j)}, l_{v}=\frac{\sum_{j \in v} \operatorname{len}(j)}{|v|} \end{array} \]
近似(obtain a tractable lower bound of entropy) - 启发式规则(最长词条匹配原则) - 变换为两部分损失
复杂的推导后得到： \[ \min _{\boldsymbol{P} \in \mathbb{R}^{m \times n}}\langle\boldsymbol{P}, \boldsymbol{D}\rangle-\gamma H(\boldsymbol{P}) \]
\[ \boldsymbol{D}(j, i)=\left\{\begin{array}{ll} -\log P(i \mid j)=+\infty, & \text { if } i \notin j \\ -\log P(i \mid j)=-\log \frac{1}{\operatorname{len}(j)}, & \text { otherwise } \end{array}\right. \]
实验
3个数据集上NMT任务的BLEU比较（双语语料、多语语料等）
VOLT对比BPE、MUV search更加高效
最后，全论文的核心应该是MUV的提出以及用OT进行优化这一trick，实验结果也比较solid，虽然最终的算法并不复杂，但是OT部分Sinkhorn算法需要较强的信息论背景，本CS专业看了半年仍是一脸懵。
指路一篇介绍Sinkhorn算法的链接： https://arxiv.org/pdf/1803.00567.pdf
