Investigating the Effectiveness of BPE: The Power of Shorter Sequences

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 1375–1381, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 1375 Investigating the Effectiveness of BPE: The Power of Shorter Sequences Matthias Gall´e NAVER LABS Europe matthias.galle@naverlabs.com Abstract Byte-Pair Encoding (BPE) is an unsupervised sub-word tokenization technique, commonly used in neural machine translation and other NLP tasks. Its effectiveness makes it a de facto standard, but the reasons for this are not well understood. We link BPE to the broader family of dictionary-based compression algo- rithms and compare it with other members of this family. Our experiments across datasets, language pairs, translation models, and vocab- ulary size show that – given a fixed vocabu- lary size budget – the fewer tokens an algo- rithm needs to cover the test set, the better the translation (as measured by BLEU). 1 Introduction It is common practice in modern NLP to represent text in a continuous space. However, the inter- face between the discrete world of language and the continuous representation persists and is ar- guably nowhere so important as in deciding what should be the atomic symbols that will be used as input and/or output. While using words as to- kens seems to be the most natural encoding, it has two major drawbacks: first it suffers from the out-of-vocabulary problems at inference time, and secondly the large number of words (which can easily reach the hundred of thousands) cre- ates additional constraints on the memory and time that is required to train and infer with these mod- els. On the other extreme, working at the charac- ter level has the advantage of a small and closed set. While current performance of character-level Neural Machine Translation (NMT) is competi- tive, its computational cost are much higher (up to 8 times (Cherry et al., 2018)). The commonly used intermediate approach is to pre-process the dataset by inferring sub-word tokens, which are then used as the atomic symbols to be translated. The most popular such method is known as byte-pair en- coding (BPE), which merges iteratively the most frequent pair of symbols. Starting with characters as individual symbols, BPE creates new symbols representing bigrams and eventually higher-level order grams. Such an approach has the advantage of incor- porating some dataset-wide information in the lo- cal decision of what should be a token. It is however not linguistically motivated, and intents to create sub-word tokens based on morpholog- ical analyzer have failed to consistently improve the performance of the resulting translation (Zhou, 2018; Domingo et al., 2018), or do so only in spe- cial cases (morphological rich cases, target side only) (Huck et al., 2017; Pinnis et al., 2017). While this is unsatisfactory, to our knowledge the reasons for the effectivenesses of BPE has not been studied in the literature. In this paper we hypothesize that the reason lies in the compression capacity of BPE: this is, that for two token …

Content truncated to 500 words