Source-linked AI summary
Vocabulary Learning via Optimal Transport for Neural Machine Translation
Jingjing Xu, Hao Zhou, Chun Gan, Zaixiang Zheng, Lei Li
TL;DR
The paper asks how to choose an effective token vocabulary and its size without expensive trial training. It introduces VOLT, which formulates vocabularization as an optimal transport problem balancing entropy and vocabulary size. Across diverse translation settings, VOLT finds well-performing vocabularies while reducing search cost and vocabulary size.
Problem
Existing vocabulary methods emphasize frequency or entropy while insufficiently accounting for vocabulary size, making optimal-size selection dependent on costly trial training.
Method
VOLT measures the entropy benefit relative to vocabulary-size cost with MUV and solves vocabulary selection as an optimal transport problem in polynomial time.
Results
VOLT outperforms widely used vocabularies across diverse translation settings and finds well-performing vocabularies with substantially smaller size and lower search cost.
Takeaways & Limitations
Vocabulary quality and size can be selected without trial training using an entropy–size objective and an efficient optimal-transport solution.
Takeaways & Limitations
The optimal-transport formulation relies on an assumption that smaller vocabularies usually have larger entropy, while the formulation can otherwise include illegal vocabulary-size pairs.
Abstract
from arXiv · showhide
The choice of token vocabulary affects the performance of machine translation. This paper aims to figure out what is a good vocabulary and whether one can find the optimal vocabulary without trial training. To answer these questions, we first provide an alternative understanding of the role of vocabulary from the perspective of information theory. Motivated by this, we formulate the quest of vocabularization -- finding the best token dictionary with a proper size -- as an optimal transport (OT) problem. We propose VOLT, a simple and efficient solution without trial training. Empirical results show that VOLT outperforms widely-used vocabularies in diverse scenarios, including WMT-14 English-German and TED's 52 translation directions. For example, VOLT achieves almost 70% vocabulary size reduction and 0.5 BLEU gain on English-German translation. Also, compared to BPE-search, VOLT reduces the search time from 384 GPU hours to 30 GPU hours on English-German translation. Codes are available at https://github.com/Jingjing-NLP/VOLT .
1 Introduction
Vocabulary construction is necessary for neural machine translation, but frequency-based methods overlook vocabulary size and often require costly trial training. VOLT balances entropy and vocabulary size through marginal utility and optimal transport, achieving strong results with substantially less search cost.
- Vocabularization is a prerequisite for neural machine translation and many other neural NLP tasks.
- Frequency-based vocabulary methods reduce corpus entropy, but vocabulary size also affects downstream performance and is especially important for low-resource tasks.
- Current size selection commonly relies on trial training across possible vocabulary sizes, creating high computation costs.
- VOLT measures the entropy benefit relative to vocabulary-size cost with Marginal Utility of Vocabularization and optimizes it through optimal transport.MUV is defined as the negative derivative of entropy with respect to vocabulary size; the transport formulation is solvable in polynomial time by linear programming.
- VOLT outperforms widely used vocabularies across WMT-14 English-German and TED translation tasks while requiring 30 GPU hours instead of 384 GPU hours for BPE-Search on English-German.
2 Related Work
Vocabulary research has progressed from word-level and character-level methods to subword approaches such as BPE. However, most subword methods prioritize frequency while neglecting vocabulary size, leaving costly trial training for size selection.
- Word-level vocabularies can perform well but commonly fail to handle rare words under limited vocabulary sizes.
- BPE creates subword units by repeatedly merging frequent character sequences, trading off character-level and word-level representations.
- Most existing subword approaches consider frequency while neglecting vocabulary-size effects, so trial training is often required to find the optimal size.
- Figure 2 reports positive MUV–downstream-performance correlations on two-thirds of tasks, with a middle Spearman score of 0.4.
3 Marginal Utility of Vocabularization
The paper introduces MUV to balance the entropy reduction gained from larger vocabularies against their size cost. Preliminary experiments find positive correlations between MUV and BLEU on two-thirds of translation tasks.
- Larger vocabularies decrease corpus entropy and can benefit learning, but they also increase parameter size and token sparsity, which can hurt learning.
- MUV measures the entropy benefit obtained from increasing vocabulary size and serves as the objective for tractable vocabulary selection.It is defined as the negative derivative of entropy with respect to vocabulary size.
- The corpus entropy H_v is based on token entropy and is normalized by the average token length to avoid token-length effects.Token entropy uses relative token frequencies from the training corpus, while l_v denotes average token length.
- Across 45 TED language pairs, two-thirds show positive correlations between MUV and BLEU, with a middle Spearman score of 0.4.The experiments use BPE-generated vocabularies with incremental sizes and shared model and training hyperparameters.
- Enumerating candidate BPE vocabularies can use MUV effectively but still requires substantial time to generate vocabularies and calculate the measure.
4 Maximizing MUV via Optimal Transport
VOLT makes vocabularization tractable by approximating marginal utility across fixed vocabulary sizes and reformulating the search as optimal transport. Transport matrices map character distributions to token candidates, while entropy-based objectives and constraints determine the resulting vocabulary.
- 4.1 Overview: The discrete vocabulary search is intractable because its search space is too large, so VOLT optimizes an upper bound instead.The approach simplifies the problem by considering vocabularies with fixed sizes and using an entropy-based approximation.
- 4.1 Overview: VOLT approximates marginal utility between adjacent vocabulary sizes in an incremental sequence S, then selects the vocabulary with the highest score across timesteps.Each timestep represents vocabularies bounded by S[t], and k estimates the size gap between consecutive vocabulary sizes.
- 4.1 Overview: Optimal transport represents vocabulary construction as moving character mass to token candidates, with each transport matrix defining a vocabulary.Tokens receiving zero transported characters are excluded, and different transport matrices correspond to different transport costs.
- 4.2 Vocabularization via Optimal Transport: The tractable approximation starts from the most frequent tokens and refines this set by searching its subsets using joint token-character probabilities.The resulting objective is the negative entropy of the joint distribution and has the same form as an optimal transport objective.
- 4.2 Vocabularization via Optimal Transport: The relaxed objective combines negative entropy with transport cost and can be solved efficiently using the generalized Sinkhorn algorithm.At each timestep, the transport matrix yields a vocabulary and its entropy score; the final output is selected from these candidates.
- 4.2 Vocabularization via Optimal Transport: The transport distance is infinite for character-token pairs that are invalid and otherwise equals the negative log of the inverse token length.Row and column constraints match transported mass to character and token distributions, with a small ϵ allowing the unbalanced formulation.
5 Experiments
Experiments across bilingual, multilingual, low-resource, and architectural settings show that VOLT finds compact vocabularies with competitive or improved translation quality while reducing search and training costs.
- 5.2 Main Results: VOLT achieves higher BLEU with substantially smaller vocabularies than widely used BPE settings in bilingual translation.Table 1 reports this comparison using vocabulary sizes adopted from the X-to-English setting.
- 5.2 Main Results: VOLT matches heuristically selected BPE-1K vocabularies on low-resource bilingual translation while requiring only one evaluation and 0.5 CPU hours plus 30 GPU hours.BPE-1K was selected through extensive prior experiments, whereas VOLT searches directly.
- 5.2 Main Results: VOLT achieves better BLEU scores on most multilingual translation pairs than BPE-60K, despite searching vocabularies of around 110K tokens.The multilingual evaluation covers language pairs from multiple language families with diverse character sets.
- 5.2 Main Results: VOLT is more efficient than BPE-Search and MUV-Search because it finds competitive vocabularies without enumerating and fully training many candidate vocabularies.BPE-Search sums training time across its candidate set, while VOLT remains the most efficient approach.
- 5.3 Discussion: A simple baseline with a VOLT-generated vocabulary reaches almost the best performance among strong English-German baselines while using a much smaller vocabulary.The results support vocabulary quality as an important contributor to baseline performance.
- 5.3 Discussion: VOLT generalizes across architectures and can slightly speed training, processing 133 versus 101 sentences per second with 11.6K versus 33.6K tokens.The reported speedup mainly comes from larger batch sizes enabled by fewer embedding parameters; the comparison uses the same hardware and beam size.
6 Conclusion
The paper introduces VOLT as an optimal-transport vocabulary search method that avoids trial training and finds well-performing vocabularies across diverse settings.
- VOLT formulates vocabulary search as a two-step discrete optimization objective and solves it with an optimal transport approach.
- VOLT searches for well-performing vocabularies in diverse settings without trial training.
- Experiments show that VOLT can effectively find a well-performing vocabulary across diverse settings.
Appendix A: MUV
The appendix evaluates the relationship between the proposed MUV measurement and BLEU across 45 language pairs from TED.
- The evaluation covers 45 language pairs from TED, using X-En translation directions with most resources.
- The experiments calculate the Spearman correlation between MUV and BLEU scores.
- The evaluation uses the same settings across experiments to examine the relationship between MUV and BLEU.
Appendix B: Experiments
The experiments use Fairseq Transformer-big models with shared embeddings and specified optimization settings across bilingual and multilingual translation tasks.
- The models are Fairseq Transformer-big systems with shared input and output embeddings.
- Training uses Adam with a 5e-4 learning rate, inverse square-root decay, 4,000 warm-up steps, and 0.3 dropout.
- Experiments use 8 GPUs for WMT-14 En-De, 4 for TED bilingual translation, and 16 for TED multilingual translation.
Appendix C: Proofs for Eq. 6
The supplied proof passages contain repeated terms involving the joint probability P(j, i) and its logarithm.
- The displayed terms repeatedly combine P(j, i) with log operations.
- The supplied passages expose fragments of the proof expressions rather than a complete derivation.