Токенизатор BPE

Алгоритм BPE (Byte-Pair Encoding, [1]) является одним из самых популярных методов подсловной токенизации в современных задачах обработки естественного языка. Изначально предложенный как алгоритм сжатия данных, он был успешно адаптирован для машинного перевода, а затем стал стандартом для обучения языковых моделей.

Алгоритм BPE состоит из двух этапов:

1. Этап обучения, на котором строится словарь токенов и определяются правила слияния подряд идущих токенов в более крупные по большому корпусу обучающих текстов.

2. Этап кодирования, при котором выученные правила применяются для перевода новых текстов в последовательности токенов из словаря.

Обучение токенизатора BPE

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

Рассмотрим процесс обучения на простом примере.

Пусть наша исходная строка - _AB_ABC_AB_ABAB.

Базовый словарь на старте состоит из уникальных символов: A, B, C, _.

Процесс обучения выглядит следующим образом:

1. Алгоритм сканирует строку и находит самую частую пару соседних символов. Это пара A и B (встречается 5 раз).

   • Формируется новое правило слияния: A + B = [AB].
   • В словарь добавляется новый токен: [AB].
   • Строка перезаписывается с учетом слияния: _[AB]_[AB]C_[AB]_[AB][AB].

2. Теперь самая частая пара в обновленной строке - это символ _ и новый токен [AB] (встречаются вместе 4 раза).

   • Добавляем следующее правило: _ + [AB] = [_AB].
   • В словарь добавляется токен: [_AB].
   • Строка перезаписывается: [_AB][_AB]C[_AB][_AB][AB].

3. Далее самая частая пара — два подряд идущих токена [_AB] (встречается 2 раза).

   • Правило: [_AB] + [_AB] = [_AB_AB]
   • В словарь добавляется токен: [_AB_AB]
   • Строка перезаписывается: [_AB_AB]C[_AB_AB][AB]

А общем случае алгоритм повторяет этот процесс до тех пор, пока не будет достигнут заранее заданный целевой размер словаря (гиперпараметр) или пока частота самых популярных пар не упадет ниже заданного порога.

В результате обучения мы получаем:

1. Базовый словарь (A, B, C, _) + новые токены ([AB], [_AB], [_AB_AB]).
2. Упорядоченный список правил слияния, который будет использоваться для токенизации новых текстов.

Кодирование новых текстов

На этапе применения токенизатор берет новый текст и применяет к нему выученные правила слияния в порядке их создания при обучении.

Возьмем новую строку: _AB_ABAB_AB.

1. Сначала строка разбивается на базовые символы: _ A B _ A B A B _ A B.
2. Применяем правило 1 (A + B $\to$ [AB]): получаем _ [AB] _ [AB] [AB] _ [AB].
3. Применяем правило 2 (_ + [AB] $\to$ [_AB]): получаем [_AB] [_AB] [AB] [_AB].
4. Применяем правило 3 ([_AB] + [_AB] $\to$ [_AB_AB]): получаем итоговую последовательность [_AB_AB] [AB] [_AB].

Эффективность алгоритма

В данном примере исходная строка из 11 символов превратилась в последовательность всего из 3 токенов, то есть мы сжали текст почти в 4 раза! Это повышает скорость обработки текста моделью, повышает её эффективный контекст и улучшает качество самой обработки, так как крупные токены несут в себе семантический смысл более высокого уровня, чем отдельные буквы.

Декодирование

Декодирование — это процесс обратного превращения последовательности токенов, сгенерированных моделью, в читаемый текст. Логически этот процесс представляет собой последовательную «распаковку» сложных токенов обратно в базовые символы путем применения правил слияния в обратном порядке.

Например, для сгенерированной строки [_AB_AB][AB][_AB]:

1. [_AB_AB] распадается на [_AB] + [_AB].
2. [_AB] распадается на _ + [AB].
3. [AB] распадается на A + B. В итоге восстанавливается строка _AB_ABAB_AB.

На практике токенизатор не выполняет поэтапное расщепление токенов. Вместо этого он хранит прямой словарь соответствий токенов и их символьных расшифровок (например, [_AB_AB] $\to$ "_AB_AB"). Благодаря этому распаковка даже самых длинных токенов в символы происходит за одну итерацию!

Пре-токенизация в BPE

Если запустить алгоритм BPE сразу на сыром тексте, возникнет серьезная проблема. Алгоритм начнет сливать слова со знаками препинания.

Например, если слово "кот" часто встречается в конце предложений, алгоритм может создать правило: кот + . $\to$ кот.. В итоге в словаре появятся отдельные токены для кот., кот,, кот!, кот? вместо того, чтобы хранить один токен кот и отдельные токены для знаков препинания.

Это приводит к разрастанию словаря, лишённому семантического смысла.

Для решения этой проблемы применяется пре-токенизация (pre-tokenization). Перед тем как запустить алгоритм BPE, текст разбивается на изолированные фрагменты на основе простых эвристик:

• Отделяются последовательности букв и цифр (слова).
• Отделяются знаки препинания, спецсимволы и пробелы.

Главное правило пре-токенизации: слияниям BPE категорически запрещено пересекать границы этих фрагментов. Также в слияниях не участвуют специальные управляющие токены (такие как [BOS], [EOS]).

Пример пре-токенизации

Возьмем фразу: "Hello, world!!!"

1. Этап разбиения (до BPE): текст разбивается на список изолированных фрагментов: ["Hello", ",", " world", "!!!"].
2. Слияния идут только внутри фрагментов.
   • Возможные слияния: He + llo, wor + ld, ! + !!
   • Невозможные слияния: world + !!!, Hello + ,

Таким образом, символы никогда не будут объединяться со знаками препинания.

А частоты встречаемости пар токенов теперь нужно считать по их встречаемости во всех образованных фрагментах текста.

Разделение слов и проблема суффиксов

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

Например, слово dropout (написанное слитно) и фраза drop out (написанная раздельно) без учета пробелов могут обе токенизироваться как [drop] [out]. В таком случае декодер не будет знать, нужно ли ставить пробел при восстановлении текста, а модель, обрабатывающая токен [out] не будет знать, обрабатывает ли она отдельное слово или часть слова.

Для однозначного декодирования в конец каждого слова перед обучением добавляется специальный маркер * (в оригинальной статье это был </w>):

• Фраза: team dropped out of the competition $\to$ [team*] [drop] [ped*] [out*] [of*] [the*] [competit] [ion*]

• Фраза: we added a dropout layer $\to$ [we*] [add] [ed*] [a*] [drop] [out*] [layer*]

При использование этого маркера декодирование токенов в исходный текст становится однозначным.

Дополнительно прочитать о BPE-токенизации и о её использовании в библиотеке transformers можно в [2].

Литература

1. Sennrich R., Haddow B., Birch A. Neural machine translation of rare words with subword units. – Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. – 2016.

2. Hugging Face LLM course: токенизация Byte-Pair Encoding.