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

Максимизация правдоподобия корпуса

Алгоритм WordPiece [1] был первоначально разработан компанией Google для систем голосового поиска, а позднее успешно адаптирован для систем машинного перевода [2] и языковых моделей семейства BERT.

В отличие от алгоритма BPE, который жадно объединяет самые часто встречающиеся пары символов, WordPiece опирается на вероятностную модель. Его главная цель — подобрать такие правила слияния токенов, которые обеспечивают увеличение правдоподобия (likelihood) обучающего корпуса текстов.

Представим обучающий корпус $C$ как последовательность слов $w_1, \dots, w_n$ , где каждое слово $w_i$ разбито на некоторые токены:

w_i = [t_{i,1}, \dots, t_{i,K_i}]

Предполагается статистическая независимость встречи токенов в слове, поэтому вероятность встретить это слово $P(w_i)$ вычисляется как произведение вероятностей составляющих его токенов:

P(w_i) = \prod_{j=1}^{K_i} P(t_{i,j})

Соответственно, правдоподобие всего корпуса $L$ представляет собой произведение вероятностей всех слов и, как следствие, всех токенов в корпусе:

L = P(C) = \prod_{i=1}^N P(w_i) = \prod_{\text{tokens} \in C} P(t) \to \max_{\text{tokens}}

При объединении двух соседних токенов $A$ и $B$ в новый токен $AB$ вероятностная структура корпуса меняется. Чтобы понять, насколько целесообразно именно такое слияние, вводится показатель прироста правдоподобия. Если обозначить количество совместных встреч пары как $N_{AB}$ , то изменение общего правдоподобия после слияния оценивается формулой:

\text{Gain} = \frac{L_{\text{new}}}{L_{\text{old}}} = \left( \frac{P(AB)}{P(A) \cdot P(B)} \right)^{N_{AB}}

Идея и критерий объединения

Основное преимущество алгоритма заключается в том, что он итеративно ищет такие соседние фрагменты, слияние которых дает максимальное значение прироста правдоподобия (Gain). При этом объединяются исключительно символы и группы символов, в то время как знаки препинания и специальные токены в процессе слияния не участвуют.

В современных реализациях (например, в библиотеках от HuggingFace, [3]) для ускорения вычислений степень $N_{AB}$ часто опускается, и алгоритм использует упрощенную метрику оценки (Score):

\text{Gain} \approx \frac{P(AB)}{P(A) \cdot P(B)}

В чем математический смысл упрощенной метрики?

Упрощенная формула в точности совпадает с мерой точечной взаимной информации (Pointwise Mutual Information, PMI), которая также используется в лингвистике для поиска устойчивых словосочетаний (коллокаций).

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

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

Для обеспечения устойчивости алгоритма вводится дополнительное ограничение: пара токенов рассматривается для объединения только в том случае, если количество их совместных появлений превышает заранее заданный порог.

Алгоритм обучения

Процесс обучения токенизатора WordPiece состоит из нескольких этапов:

Подготовка Текст проходит стадию нормализации (приведение к нижнему регистру, удаление диакритических знаков и т.д.) и разбивается на отдельные слова (пре-токенизация).
Инициализация Базовый словарь $V$ заполняется всеми уникальными символами, присутствующими в языке, изолированными знаками препинания, а также системными токенами, такими как [CLS], [SEP], [PAD], [UNK].
Цикл, пока словарь токенов не достигнет целевого размера:
- Вычисляются базовые вероятности всех токенов в текущем разбиении: $P(t) = \frac{\text{количество вхождений } t}{\text{общее число токенов}}$ .
- Для всех соседних пар токенов внутри слов рассчитывается метрика объединения (Score).
- Пара с максимальным значением Score сливается в единый новый токен, который добавляется в словарь.

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

Обратимость токенизации и маркер продолжения

Важной проблемой сабворд-токенизации является неоднозначность восстановления текста. Декодер должен понимать, где заканчивается одно слово и начинается другое. Например, английское слово dropout и фраза из двух слов drop out могут быть токенизированы идентично: [drop] и [out].

В WordPiece эта проблема решается элегантным способом: к началу токена, который является продолжением слова (а не его началом), добавляется специальный маркер # (хотя в популярных реализациях это ##).

Слово dropout (слитно) $\to$ [drop], [#out]
Фраза drop out (раздельно) $\to$ [drop], [out]

Логика такого подхода очевидна: первый токен слова всегда является «чистым», а все последующие части (суффиксы, окончания, части сложных слов) помечаются как «зависимые». Это позволяет модели легко отличать приставки и корни от окончаний.

Пример вычислений при обучении

Рассмотрим механику алгоритма на небольшом примере.

Обучающий корпус playing replayed replaying

Инициализация (разбиение на токены) Слова разбиваются на базовые символы, при этом все символы, кроме первых в слове, получают префикс #:

p, #l, #a, #y, #i, #n, #g (7 токенов)
r, #e, #p, #l, #a, #y, #e, #d (8 токенов)
r, #e, #p, #l, #a, #y, #i, #n, #g (9 токенов)

Общее количество токенов на старте: $N = 7 + 8 + 9 = 24$ .

Пример расчета метрики объединения Сравним две потенциальные пары для слияния: (p, #l) и (#i, #n).

Для пары (p, #l): Токен p встречается 1 раз (в слове playing). $P(p) = 1/24$ . Токен #l встречается 3 раза. $P(\#l) = 3/24$ . Пара встречается вместе 1 раз. $P(p, \#l) = 1/24$ . Расчет метрики:
$\text{Score}(p, \#l) = \frac{1/24}{(1/24) \cdot (3/24)} = \frac{1}{3/24} = 8$
Для пары (#i, #n): Токен #i встречается 2 раза. $P(\#i) = 2/24$ . Токен #n встречается 2 раза. $P(\#n) = 2/24$ . Пара встречается вместе 2 раза. $P(\#i, \#n) = 2/24$ . Расчет метрики:
$\text{Score}(\#i, \#n) = \frac{2/24}{(2/24) \cdot (2/24)} = \frac{1}{2/24} = 12$

Результат: метрика для пары (#i, #n) выше (12 > 8), поэтому эти токены побеждают на текущей итерации и объединяются в новый токен #in.

Применение алгоритма к новым текстам

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

play (токен начала слова)
#play (токен корня в середине слова, как в replaying)
#ing, #ed (популярные суффиксы)
re (популярная приставка)

При применении токенизатора к новому тексту WordPiece использует жадный алгоритм, известный как MaxMatch. Обработка идёт слева направо внутри каждого отдельного слова:

Алгоритм ищет в словаре самый длинный префикс, который совпадает с началом текущего неразобранного остатка слова.
Найденный префикс отщепляется, а к оставшейся части применяется тот же самый поиск самого длинного префикса (с учетом маркера #).
Процесс повторяется, пока слово не будет полностью токенизировано.

Это делает WordPiece очень быстрым на практике, но менее гибким при работе с зашумленными текстовыми данными.

Обработка неизвестных слов

Если на каком-либо шаге алгоритм не может найти ни одного совпадения в словаре для оставшейся части слова, то всё слово целиком отбрасывается и заменяется единым специальным токеном [UNK] (Unknown).

Пример применения

Возьмем гипотетический словарь из примера выше и применим его к новым словам: play, played, playroom.

play $\to$ [play] Алгоритм находит слово целиком в словаре.
played $\to$ [play], [#ed] Самый длинный префикс, который есть в словаре — это play. Остается ed, который сопоставляется с маркером #ed. Оба токена найдены.
playroom $\to$ [UNK] Самый длинный префикс — play. Остается room. Алгоритм ищет префиксы для остатка (то есть токены, начинающиеся с #). Если в словаре есть только #r, то остается #oom. Поскольку элементы #oom, #oo или #o в словаре отсутствуют, нераспознанным объявляется не только суффикс, а всё исходное слово целиком.

Анализ метода

Достоинства

Высокая скорость работы на этапе применения за счет жадного алгоритма поиска MaxMatch.
Математическая логика объединения токенов (увеличение правдоподобия) позволяет выявлять неочевидные, но важные семантические связи. В частности, метод хорошо выделяет реальную морфологию слов (приставки, корни, суффиксы).

Недостатки

Классический WordPiece работает не на уровне байтов, как BBPE, а на уровне символов текста, из-за чего возможна проблема невозможности обработки слов, включающих редкие символы Unicode.
Поскольку каждому символу необходимо иметь как базовую версию, так и версию с префиксом #, стартовый размер словаря равен как минимум удвоенному числу символов алфавита. Из-за этого приходится дополнительно ограничивать множество рассматриваемых символов.

Например, в мультиязычной версии BERT (mBERT) в WordPiece-токенизаторе используется словарь всего на 110 000 токенов, что очень мало для 104 поддерживаемых языков. В результате многие языки с редкими алфавитами страдают от переизбытка токенов [UNK] или разбиения слов на неэффективно мелкие части.

Метод WordPiece является стандартом для таких популярных архитектур энкодеров, как BERT, DistilBERT, ELECTRA.

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

Максимизация правдоподобия корпуса​

Идея и критерий объединения​

Алгоритм обучения​

Обратимость токенизации и маркер продолжения​

Пример вычислений при обучении​

Применение алгоритма к новым текстам​

Пример применения​

Анализ метода​

Литература​