Neural Machine Translation of Rare Words with Subword Units

3.2 Byte Pair Encoding (BPE)

1. How does BPE learn a subword vocabulary?
   Start with the character vocabulary, each word a character sequence plus an end-of-word symbol. Repeatedly count all adjacent symbol pairs (weighted by word frequency, not crossing word boundaries) and merge the most frequent pair (A, B) into a new symbol AB. The number of merges is the only hyperparameter.
   • Sennrich et al., 2016, Neural Machine Translation of Rare Words with Subword Units (Proceedings of the 54th Annual Meeting of ACL (Volume 1: Long Papers)), §3.2, pp. 1717–1718
2. Learn BPE merges from the word counts {low: 5, lower: 2, newest: 6, widest: 3}.
   Pairs are counted with word frequencies; ties go to the first pair found. The first five merges:

   #	merge	count	effect
   1	e + s	9	n e w es t·, w i d es t·
   2	es + t	9	…est·
   3	est + ·	9	…est·
   4	l + o	7	lo w·, lo w e r·
   5	lo + w	7	low·, low e r·

   (· marks the end of a word.)
   • Sennrich et al., 2016, Neural Machine Translation of Rare Words with Subword Units (Proceedings of the 54th Annual Meeting of ACL (Volume 1: Long Papers)), §3.2, pp. 1717–1718
3. How is a learned BPE model applied to a new word?
   Split the word into characters (plus end-of-word marker), then apply the learned merges in order. Any word can be segmented into known symbols, so the vocabulary is open but fixed in size: with the merges above, the unseen lowest becomes low est·.
   • Sennrich et al., 2016, Neural Machine Translation of Rare Words with Subword Units (Proceedings of the 54th Annual Meeting of ACL (Volume 1: Long Papers)), §3.2, pp. 1717–1718
4. What does the BPE vocabulary size equal, and what happens to frequent words?
   Initial characters plus the number of merge operations. Frequent words end up as single symbols (no shortlist of unsegmented words is needed), while rare words are split into frequent subword units.
   • Sennrich et al., 2016, Neural Machine Translation of Rare Words with Subword Units (Proceedings of the 54th Annual Meeting of ACL (Volume 1: Long Papers)), §3.2, pp. 1717–1718
5. How does BPE differ from Huffman-style variable-length word encodings proposed for NMT?
   BPE symbols remain interpretable subword units (character n-grams), so the network can learn to translate and generate new, unseen words from them.
   • Sennrich et al., 2016, Neural Machine Translation of Rare Words with Subword Units (Proceedings of the 54th Annual Meeting of ACL (Volume 1: Long Papers)), §3.2, pp. 1717–1718
6. What is joint BPE, and why did it help?
   Learning one set of merges on the union of source and target vocabularies, instead of separate encodings. It segments names and cognates consistently in both languages, making mappings easier to learn; for English–Russian the Russian side was transliterated to Latin script to learn the merges, then transliterated back.
   • Sennrich et al., 2016, Neural Machine Translation of Rare Words with Subword Units (Proceedings of the 54th Annual Meeting of ACL (Volume 1: Long Papers)), §3.2, pp. 1717–1718