Метод токенизации BPE
Материал из MachineLearning.
Byte-Pair Encoding (BPE) — алгоритм субсловной токенизации, изначально предложенный для сжатия данных, а позднее адаптированный для обработки естественного языка. В контексте машинного обучения и обработки естественного языка BPE используется для разбиения текста на подслова (субтокены) на основе частотности пар символов. Этот метод позволяет строить словарь фиксированного размера, покрывающий открытое множество слов, и является одним из доминирующих подходов в современных больших языковых моделях (LLM).
Содержание |
История
Алгоритм BPE был изначально предложен Филипом Гейджем в 1994 году как метод сжатия данных, который итеративно заменяет наиболее частую пару байтов на новый символ.
В 2016 году Рико Сеннрих, Барри Хэддоу и Александра Бёрч адаптировали BPE для задачи нейросетевого машинного перевода (NMT). В своей работе «Neural Machine Translation of Rare Words with Subword Units» они предложили использовать BPE для сегментации слов на подслова, чтобы решить проблему неизвестных слов (OOV, out-of-vocabulary) и представить открытый словарь через фиксированный набор символов. Эта работа стала поворотным моментом, после которого BPE и его вариации получили широкое распространение в NLP.
Постановка задачи
Вход: корпус текстов (обучающая выборка) и целевой размер словаря (гиперпараметр).
Выход: упорядоченный список правил слияния (merge rules) и итоговый словарь токенов, включающий отдельные символы, слитые подслова и специальные токены.
В процессе обучения алгоритм строит словарь, начиная с базового набора символов, и итеративно добавляет в него новые токены, образованные слиянием наиболее частых пар. При кодировании нового текста выученные правила слияния применяются к последовательности символов для получения последовательности идентификаторов токенов.
Алгоритм
Обучение (построение словаря)
- Инициализация. Словарь инициализируется всеми уникальными символами (или байтами) в корпусе, а также специальными токенами (например,
<PAD>,<UNK>,<BOS>,<EOS>). Каждое слово в корпусе представляется как последовательность символов с маркером конца слова (например,</w>). - Подсчёт пар. Для каждой пары соседних символов (или уже слитых токенов) во всех словах корпуса подсчитывается взвешенная частота: частота пары умножается на частоту слова, в котором она встречается.
- Слияние. Выбирается пара с максимальной частотой. Все вхождения этой пары в корпусе заменяются на новый объединённый токен. Новый токен добавляется в словарь, а правило слияния сохраняется в упорядоченном списке.
- Итерация. Шаги 2–3 повторяются до достижения целевого размера словаря
или до исчерпания пар для слияния.
Псевдокод (обучение):
ВХОД: корпус, целевой_размер_словаря V
ВЫХОД: словарь, список_правил_слияния
1. инициализировать словарь всеми уникальными символами корпуса
2. для каждого слова в корпусе:
представить слово как последовательность символов + маркер конца слова
3. пока размер словаря < V:
подсчитать частоты всех соседних пар символов (взвешенно по частоте слов)
если пар не найдено: прервать
выбрать пару с наибольшей частотой
заменить все вхождения этой пары на новый объединённый токен
добавить новый токен в словарь
сохранить правило слияния в список
4. вернуть словарь и список правил слияния
Кодирование (применение к новому тексту)
- Новый текст разбивается на слова (по пробелам или с помощью предварительной токенизации).
- Каждое слово разбивается на символы с добавлением маркера конца слова.
- К последовательности символов последовательно применяются выученные правила слияния в том порядке, в котором они были изучены.
- Полученные токены сопоставляются с идентификаторами из словаря.
Псевдокод (кодирование):
ВХОД: текст, словарь, список_правил_слияния
ВЫХОД: список_идентификаторов_токенов
1. разбить текст на слова
2. для каждого слова:
разбить на символы + маркер конца слова
для каждого правила слияния (в порядке обучения):
применить правило к текущей последовательности (слить совпадающие пары)
сопоставить полученные токены с идентификаторами
3. вернуть объединённый список идентификаторов
Байтовый BPE (Byte-Level BPE)
В 2019 году OpenAI представила вариацию BPE, работающую на уровне байтов (Byte-Level BPE), в модели GPT-2. В этом подходе текст сначала кодируется в последовательность байтов (обычно UTF-8), и BPE применяется к байтам, а не к символам Юникода. Это гарантирует, что любая строка может быть представлена без использования токена <UNK>, поскольку базовый словарь содержит все 256 возможных байтов. Байтовый BPE стал стандартом де-факто для многих современных LLM, включая RoBERTa и модели семейства LLaMA (начиная с LLaMA 3).
Достоинства и слабые стороны
Достоинства
- Открытый словарь. BPE позволяет представить любое слово, включая редкие и неизвестные, через последовательность подслов. Это решает проблему OOV, которая была серьёзным ограничением для пословных моделей.
- Фиксированный размер словаря. BPE обеспечивает компромисс между размером словаря и длиной последовательностей, что важно для эффективности вычислений и использования памяти.
- Простота и скорость. Алгоритм концептуально прост и вычислительно эффективен: он многократно сливает наиболее частые пары символов.
- Сохранение морфологической информации. Разбиение на подслова позволяет модели улавливать общие корни и аффиксы, что особенно полезно для морфологически богатых языков.
Слабые стороны и ограничения
- Зависимость от предварительной токенизации. Классический BPE предполагает, что слова разделены пробелами. Это плохо работает для языков без явных пробелов (например, китайского или японского), хотя байтовый BPE и SentencePiece смягчают эту проблему.
- Неоптимальное сжатие. Исследования показывают, что даже продвинутые реализации BPE могут быть менее эффективны в сжатии последовательностей, чем простые эвристики, особенно при обработке пробелов и общих фрагментов слов.
- Проблемы с символическими языками. Токенизаторы BPE, обученные на естественном языке, могут быть неэффективны для кода и других формальных языков, где важна точная структура.
- Артефакты токенизации. BPE может порождать «странные» токены для редких символов или последовательностей, что приводит к нестабильности модели при работе с подсчётом букв, арифметикой и т.п.
Использование в языковых моделях
BPE и его вариации лежат в основе токенизации многих ключевых архитектур LLM:
- GPT-2 и RoBERTa используют байтовый BPE (Byte-Level BPE).
- LLaMA (1 и 2) используют SentencePiece с байтовым BPE и механизмом byte-fallback.
- LLaMA 3 перешла на 128k байтовый BPE (в стиле tiktoken).
- XLM-RoBERTa использует BPE-подход.
- CLIP использует байтовый BPE.
Важно отметить, что BERT использует не BPE, а алгоритм WordPiece, хотя эти методы концептуально близки.
Другие методы токенизации в LLM
Помимо BPE, в современных LLM применяются следующие подходы:
- WordPiece. Используется в BERT и его производных (DistilBERT, ELECTRA). В отличие от BPE, WordPiece выбирает для слияния пару, которая максимизирует правдоподобие корпуса, а не просто частоту. Продолжения слов помечаются префиксом
##. - Unigram. Реализуется в рамках фреймворка SentencePiece. Начинает с большого словаря-кандидата и итеративно удаляет токены, которые вносят наименьший вклад в правдоподобие корпуса. Используется в T5 и Gemma.
- SentencePiece. Это не столько отдельный алгоритм, сколько библиотека, которая работает с «сырым» текстом (включая пробелы как символы) и может использовать внутри себя либо BPE, либо Unigram. Применяется в XLNet, ALBERT, T5, LLaMA.
- Символьная токенизация (Character-level). Разбивает текст на отдельные символы. Используется реже из-за длинных последовательностей, но находит применение в некоторых специализированных моделях.
Список литературы
- Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL 2016). arXiv:1508.07909.
- Gage, P. (1994). A New Algorithm for Data Compression. The C Users Journal, 12(2), 23–38.
- Kudo, T., & Richardson, J. (2018). SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP 2018).
- Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. In Proceedings of ACL 2018.
- Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners (GPT-2 Technical Report). OpenAI.
- Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of NAACL-HLT 2019.
- Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., & Stoyanov, V. (2019). RoBERTa: A Robustly Optimized BERT Pretraining Approach. arXiv:1907.11692.

