Метод токенизации BPE

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск

Vokov (Обсуждение | вклад)
(Новая: '''Byte-Pair Encoding (BPE)''' — алгоритм субсловной токенизации, изначально предложенный для сжат...)
К следующему изменению →

Текущая версия

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.

Постановка задачи

Вход: корпус текстов (обучающая выборка) и целевой размер словаря V (гиперпараметр).

Выход: упорядоченный список правил слияния (merge rules) и итоговый словарь токенов, включающий отдельные символы, слитые подслова и специальные токены.

В процессе обучения алгоритм строит словарь, начиная с базового набора символов, и итеративно добавляет в него новые токены, образованные слиянием наиболее частых пар. При кодировании нового текста выученные правила слияния применяются к последовательности символов для получения последовательности идентификаторов токенов.

Алгоритм

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

  1. Инициализация. Словарь инициализируется всеми уникальными символами (или байтами) в корпусе, а также специальными токенами (например, <PAD>, <UNK>, <BOS>, <EOS>). Каждое слово в корпусе представляется как последовательность символов с маркером конца слова (например, </w>).
  2. Подсчёт пар. Для каждой пары соседних символов (или уже слитых токенов) во всех словах корпуса подсчитывается взвешенная частота: частота пары умножается на частоту слова, в котором она встречается.
  3. Слияние. Выбирается пара с максимальной частотой. Все вхождения этой пары в корпусе заменяются на новый объединённый токен. Новый токен добавляется в словарь, а правило слияния сохраняется в упорядоченном списке.
  4. Итерация. Шаги 2–3 повторяются до достижения целевого размера словаря V или до исчерпания пар для слияния.

Псевдокод (обучение):

ВХОД: корпус, целевой_размер_словаря V
ВЫХОД: словарь, список_правил_слияния

1. инициализировать словарь всеми уникальными символами корпуса
2. для каждого слова в корпусе:
       представить слово как последовательность символов + маркер конца слова
3. пока размер словаря < V:
       подсчитать частоты всех соседних пар символов (взвешенно по частоте слов)
       если пар не найдено: прервать
       выбрать пару с наибольшей частотой
       заменить все вхождения этой пары на новый объединённый токен
       добавить новый токен в словарь
       сохранить правило слияния в список
4. вернуть словарь и список правил слияния

Кодирование (применение к новому тексту)

  1. Новый текст разбивается на слова (по пробелам или с помощью предварительной токенизации).
  2. Каждое слово разбивается на символы с добавлением маркера конца слова.
  3. К последовательности символов последовательно применяются выученные правила слияния в том порядке, в котором они были изучены.
  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). Разбивает текст на отдельные символы. Используется реже из-за длинных последовательностей, но находит применение в некоторых специализированных моделях.

Список литературы

  1. 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.
  2. Gage, P. (1994). A New Algorithm for Data Compression. The C Users Journal, 12(2), 23–38.
  3. 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).
  4. Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. In Proceedings of ACL 2018.
  5. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners (GPT-2 Technical Report). OpenAI.
  6. 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.
  7. 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.