Байтовое кодирование пар

Byte-Pair Encoding (BPE) — это метод сжатия данных и алгоритм токенизации текста, основанный на итеративной замене наиболее часто встречающейся пары смежных символов (или байтов) на новый, ранее не использовавшийся символ. В контексте обработки естественного языка (NLP) BPE используется для построения словаря подслов (субслов), что позволяет эффективно обрабатывать редкие и незнакомые слова, а также морфологически богатые языки, включая русский.

История и происхождение

Алгоритм BPE был впервые предложен Филипом Гейджем в 1994 году в статье «A New Algorithm for Data Compression». Первоначально он применялся исключительно для сжатия данных, демонстрируя высокую эффективность на текстовых файлах. Идея заключалась в том, чтобы сократить объём данных путём замены повторяющихся последовательностей байтов на более короткие коды.

В 2016 году исследователи Рикардо Семрих, Барри Хэддоу и Александра Бёрч из компании Neural Machine Translation (ныне часть Google) адаптировали BPE для задачи нейронного машинного перевода. В их работе «Neural Machine Translation of Rare Words with Subword Units» было показано, что BPE позволяет разбивать слова на подсловные единицы, что решает проблему обработки слов, отсутствующих в словаре (out-of-vocabulary, OOV). С этого момента BPE стал одним из стандартных методов токенизации в NLP, особенно в архитектурах на основе трансформеров, таких как GPT, BERT и их многочисленные вариации.

Алгоритм работы

Алгоритм BPE работает в два этапа: обучение (построение словаря) и применение (токенизация).

Обучение (построение словаря)

1. Инициализация: Исходный корпус текста разбивается на отдельные символы (или байты). Каждому уникальному символу присваивается свой идентификатор. Начальный словарь состоит из всех этих символов.
2. Подсчёт пар: Алгоритм подсчитывает частоту встречаемости всех возможных пар символов (или байтов) в текущем представлении корпуса.
3. Слияние: Самая часто встречающаяся пара символов объединяется в новый символ (токен). Этот новый токен добавляется в словарь. Все вхождения этой пары в корпусе заменяются на новый токен.
4. Повторение: Шаги 2 и 3 повторяются заданное количество раз (гиперпараметр, обычно от нескольких тысяч до нескольких десятков тысяч). После каждой итерации размер словаря увеличивается на единицу.

Результатом обучения является упорядоченный список правил слияния (merge rules), который определяет, как исходные символы объединяются в подслова.

Применение (токенизация)

1. Исходное слово разбивается на отдельные символы.
2. Алгоритм последовательно применяет правила слияния, полученные на этапе обучения, в том же порядке, в котором они были созданы (от наиболее частого к наименее частому).
3. Если в слове встречается пара символов, для которой существует правило слияния, эта пара объединяется.
4. Процесс продолжается до тех пор, пока не будут применены все возможные правила или слово не будет представлено целиком одним токеном из словаря.

Пример для английского слова «lowest»:

• Начальное разбиение: l, o, w, e, s, t
• Применение правил (гипотетически): (l, o) -> lo; (lo, w) -> low; (e, s) -> es; (low, es) -> lowes; (lowes, t) -> lowest.
• Результат: слово «lowest» может быть представлено одним токеном [lowest] или, если правила не позволяют, несколькими, например [low] и [est].

Варианты и модификации

Byte-level BPE (BBPE)

В классическом BPE токенизация работает на уровне символов (Unicode). Это приводит к тому, что словарь может быть очень большим из-за множества редких символов. В варианте Byte-level BPE (BBPE), популяризированном моделью GPT-2, входной текст сначала кодируется в последовательность байтов (например, в кодировке UTF-8). Алгоритм BPE затем работает с байтами. Это позволяет:

• Гарантировать, что любой символ из любого языка может быть представлен.
• Значительно уменьшить размер начального словаря (до 256 байтовых значений).
• Обеспечить единообразную обработку текстов на разных языках.

SentencePiece

SentencePiece — это библиотека токенизации, разработанная Google, которая реализует как BPE, так и unigram language model. Её ключевое отличие от классического BPE заключается в том, что она работает непосредственно с необработанным текстом, не требуя предварительной сегментации на слова (например, с помощью пробелов). SentencePiece рассматривает текст как последовательность символов и применяет BPE к этой последовательности, что особенно полезно для языков, где границы слов неочевидны (например, японский, китайский).

Применение в NLP

BPE является фундаментальным компонентом большинства современных больших языковых моделей (LLM) и систем машинного перевода.

• Трансформерные модели: BPE используется для токенизации входного текста в моделях семейства GPT (OpenAI), LLaMA (Meta — организация признана экстремистской и запрещена в РФ), BERT (Google), RoBERTa (Facebook) и многих других. Он позволяет моделям обрабатывать слова любой длины, используя ограниченный по размеру словарь.
• Машинный перевод: BPE позволяет системам перевода работать с редкими словами, сложными терминами и именами собственными, разбивая их на знакомые подсловные единицы. Например, немецкое слово «Lebensversicherungsgesellschaft» (страховая компания жизни) может быть разбито на более мелкие части, такие как «Lebens», «versicherungs», «gesellschaft», которые модель уже знает.
• Обработка морфологии: Для флективных языков, таких как русский, BPE эффективно выделяет корни, суффиксы и окончания. Слово «читаю» может быть представлено как [чита] + [ю], а слово «читал» — как [чита] + [л], что позволяет модели учить грамматические закономерности.

Преимущества и недостатки

Преимущества

• Решение проблемы OOV: BPE может представить любое слово, даже если оно не встречалось в обучающем корпусе, разбив его на известные подслова.
• Сбалансированный размер словаря: Позволяет использовать словарь фиксированного размера (например, 32 000 или 50 000 токенов), который является компромиссом между уровнем символов (слишком короткие последовательности) и уровнем слов (слишком большой словарь).
• Компактность: Представление текста в виде подслов часто более компактно, чем посимвольное, и более гибко, чем пословное.
• Независимость от языка: Алгоритм не требует лингвистических знаний и может быть применён к любому языку.

Недостатки

• Неоптимальная сегментация: BPE не учитывает семантику или морфологию. Он может разбивать слова на части, не соответствующие реальным морфемам (например, «un» + «able» вместо «unable»). Это может ухудшить понимание смысла моделью.
• Зависимость от корпуса: Словарь и правила слияния сильно зависят от обучающего корпуса. Если корпус содержит много текстов на определённую тему, BPE будет лучше сегментировать слова этой тематики и хуже — слова из других областей.
• Отсутствие детерминированности (в некоторых реализациях): В классическом BPE результат токенизации одного и того же слова может зависеть от контекста, так как алгоритм применяется ко всей последовательности, а не к отдельным словам.

Критика и альтернативы

Несмотря на широкое распространение, BPE подвергается критике за свою «слепоту» к лингвистической структуре. Альтернативные методы токенизации, такие как Unigram Language Model (используется в SentencePiece) и WordPiece (используется в BERT), предлагают более вероятностный подход к сегментации. WordPiece, например, выбирает слияния не по частоте, а по приросту вероятности языковой модели. В последние годы также ведутся исследования по созданию «морфологических» токенизаторов, которые используют лингвистические правила для более точного выделения морфем.

Источники

• Gage, P. (1994). A New Algorithm for Data Compression. The C Users Journal.
• Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics.
• Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners. OpenAI Blog.
• Kudo, T., & Richardson, J. (2018). SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations.
• Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies.