Последовательности, токены и предсказание

Языковая модель не получает ни слов, ни букв — только номера токенов. Токенизатор решает, сколько шагов займёт фраза, какие части слов разделят один вектор и сколько вычислений достанется разным языкам. Это первый обучаемый блок системы, и обучается он раньше всех остальных — на корпусе, который потом уже не изменишь.

Строка, которую модель никогда не видит

Между текстом и нейронной сетью стоит переводчик. Он превращает строку в последовательность целых чисел:

$$T:\ \text{строка}\longrightarrow(i_1,i_2,\ldots,i_n),\qquad i_t\in\{0,1,\ldots,V-1\}.$$

Обратный переводчик восстанавливает строку:

$$T^{-1}(i_1,\ldots,i_n)=\text{строка}.$$

От пары $(T,T^{-1})$ требуют одного жёсткого свойства — обратимости на любых данных:

$$T^{-1}\bigl(T(s)\bigr)=s\quad\text{для всякой строки }s.$$

Дальше модель видит только индексы, каждому из которых сопоставлен обучаемый вектор $e_{i}\in\mathbb R^{d}$. Ни буква, ни морфема, ни слово в вычислениях не участвуют: участвует номер строки в таблице.

Отсюда странное на первый взгляд следствие. Фраза стоит столько-то шагов вычисления не потому, что она сложная, а потому, что токенизатор так решил. Сложность мысли и цена её обработки связаны только через статистику того корпуса, на котором обучали словарь.

Все числа этого урока измерены здесь

Прежде чем считать, договоримся об источнике. Все цифры ниже получены на реальных текстах, которые лежат в этом самом репозитории: русская проза — это уроки нашего учебника (первые сорок восемь файлов), английская проза — открытый корпус SMS Spam Collection, знакомый по уроку про наивный Байес, программный код — Python-скрипты, которыми построены рисунки книги. Мини-BPE обучен здесь же, с нуля, ровно по правилу «сливай самую частую пару», детерминированно. Ничего не взято «из литературы»: каждое число можно пересчитать.

Обучающая часть и проверочная часть текста не пересекаются — иначе токенизатор хвалили бы за запоминание, а не за сжатие. Это та же гигиена, что в уроке про train/val/test, просто применённая к словарю.

Четыре разбиения одной фразы

Возьмём фразу « нейросеть учится» — 17 символов, 32 байта в UTF-8. Её можно подать модели минимум четырьмя способами.

Байты. Алфавит ровно из 256 символов, любая строка представима, ни одного «неизвестного слова». Цена: 32 шага на 17 символов.

Символы Unicode. Алфавит в десятки тысяч знаков, длина 17.

Слова. Два шага — и полная беспомощность перед формой, которой не было в словаре.

Подслова. Компромисс, который и победил: частые куски становятся одним токеном, редкие распадаются, но не исчезают.

На нашем словаре, обученном на русской прозе, эта фраза стоит 32 токена без слияний, 10 токенов после сотни слияний, 6 после восьмисот и 5 после трёх тысяч. Одна и та же мысль — от 32 до 5 шагов вычисления.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Байт не нейтрален

Первый неприятный факт: UTF-8 не одинаково добр к языкам. Латинская буква занимает один байт, кириллическая — два. На реальном тексте наших уроков получается 1,727 байта на символ (71,8% символов — кириллица, каждая ровно по два байта), на английских SMS — 1,002. Ещё до всякой токенизации русский текст «тяжелее» примерно в 1,7 раза:

$$\frac{\text{байт}}{\text{символ}}\bigg|_{\text{рус}}=1{,}727, \qquad \frac{\text{байт}}{\text{символ}}\bigg|_{\text{англ}}=1{,}002.$$

Именно поэтому байтовое разбиение фразы дало 32 шага на 17 символов: почти по два на знак.

BPE: алгоритм сжатия, ставший токенизатором

Byte Pair Encoding придумали не для нейросетей. В 1994 году Филип Гейдж описал простой приём сжатия: найти самую частую пару соседних байтов и заменить её одним неиспользованным символом; повторять, пока выгодно.

Через двадцать два года тот же алгоритм вернулся с другой стороны — как способ избавиться от неизвестных слов в машинном переводе.

Формально. Пусть корпус разбит на слова, каждое слово представлено последовательностью базовых единиц. Обозначим через $c(a,b)$ число вхождений пары соседних единиц $(a,b)$ во всём корпусе. Шаг обучения выбирает

$$(a^\star,b^\star)=\arg\max_{(a,b)}c(a,b),$$

после чего в словарь добавляется новая единица $a^\star b^\star$, а все её вхождения в корпусе схлопываются. Ничьи разрешаются фиксированным правилом (у нас — лексикографически), иначе алгоритм перестанет быть воспроизводимым.

Пусть до слияния корпус состоял из $N$ единиц. После слияния

$$N_{\text{new}}=N-c(a^\star,b^\star),$$

то есть выигрыш ровно равен частоте слитой пары. А словарь вырос на единицу:

$$V_{\text{new}}=V+1.$$

Вот и весь обмен: одна строка таблицы эмбеддингов покупает $c(a^\star,b^\star)$ шагов вычисления. Жадность здесь настоящая: раннее слияние меняет частоты всех последующих, и глобально оптимальный словарь никто не обещает.

Отдача падает, и это видно

Обучим словарь на русской прозе и проследим, как длина текста зависит от числа слияний. Без единого слияния текст стоит 171,7 токена на 100 символов (это просто байты). После 200 слияний — 63,7. После 3000 — 34,0:

$$171{,}7\ \xrightarrow{\ +200\ \text{слияний}\ }\ 63{,}7 \ \xrightarrow{\ +2800\ \text{слияний}\ }\ 34{,}0.$$

Первые 200 правил убирают 62,9% длины; последние 1400 — только 13,2%. Кривая экономии выпукла и быстро выполаживается: язык устроен так, что немногие частые куски объясняют большую часть текста.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Первые тридцать слияний собирают алфавит

Если базовые единицы — байты, то первое, чем занят BPE на русском тексте, — восстановление букв. Кириллическая буква записана двумя байтами, и самая частая пара байтов — это просто самая частая буква. Первые декодируемые слияния нашего словаря идут в таком порядке: о, е, а, т, и, р, н, с. Из первых ста правил ровно 30 дают токен длиной в один символ.

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

Пробел — часть токена, а корень — не обязательно

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

Теперь неприятное. Мы привыкли думать, что подслова — это морфемы. Посмотрим, что выучил алгоритм на самом деле:

$$\text{лес}\to\ \texttt{ л|ес},\qquad \text{лесной}\to\ \texttt{ л|ес|ной},\qquad \text{лесник}\to\ \texttt{ л|ес|ник}.$$

Общая часть есть — но это л и ес, а не корень «лес». Слово « электромагнитный» (33 байта) распадается на восемь кусков: э|лек|тр|ом|аг|н|ит|ный — ни один из них не морфема. BPE не знает морфологии; он знает частоты.

Unicode: одинаковый вид — разные данные

Буква й бывает одним code point (U+0439) и сочетанием и с комбинируемым знаком U+0306. Выглядят одинаково, байты разные, токены разные. Нормализация NFC приводит их к общей форме — и её обязательно применять одинаково при обучении словаря, при обучении модели и при выводе. Расхождение нормализации между обучением и продакшеном — классическая, тихая и трудноуловимая ошибка.

Эмодзи усложняют картину ещё сильнее: один видимый знак может состоять из нескольких code points, соединённых zero-width joiner. Правило «один видимый знак — один токен» не выполняется ни в каком словаре.

Словарь стоит параметров

Увеличение $V$ укорачивает текст — и утяжеляет модель с двух концов. Только таблица эмбеддингов содержит

$$P_{\text{emb}}=V\cdot d$$

параметров, а выходной слой, предсказывающий следующий токен, ещё столько же. При $d=768$ это

$$V=32\,768\ \Rightarrow\ 25{,}2\ \text{млн},\qquad V=128\,000\ \Rightarrow\ 98{,}3\ \text{млн}.$$

Рост словаря в 3,91 раза даёт во столько же раз более тяжёлые вход и выход. Есть и статистическая цена: редкий токен получает мало градиентных обновлений, поэтому его вектор остаётся почти случайным. Это ровно та ситуация малой выборки, ради которой в уроке о сглаживании добавляли псевдосчётчики.

Лаборатория слияний

Начните с нуля слияний: проверочная строка разложена по буквам. Добавляйте правила по одному и смотрите на две вещи сразу — какое слияние выиграло на этом шаге и насколько укоротилась строка. Первые десять правил дадут почти всю экономию, дальше отдача пойдёт по капле; это та же кривая, что на рис. 75.2, но собранная у вас на глазах.

Затем главный опыт урока: обучите словарь на русском корпусе и подайте английскую строку (или наоборот). Число токенов почти не изменится — выученные пары в чужом тексте не встречаются. Ошибки нет, <UNK> нет, всё представимо, но дорого. Именно различие между «может» и «дёшево» и есть содержание следующего раздела.

Свой словарь дешевле чужого

Обучим три словаря — на русской прозе, на английских SMS и на Python-коде — и измерим цену каждого из трёх текстов каждым из трёх словарей. Мера — токенов на байт, чем меньше, тем лучше.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Переведём в человеческие единицы. Своим словарём русское слово стоит в среднем 2,38 токена, английское слово своим словарём — 1,61. А русское слово чужим, английским словарём — 11,77 токена: почти по токену на букву.

$$F=\frac{\text{число токенов}}{\text{число слов}},\qquad F_{\text{рус, свой}}=2{,}38,\qquad F_{\text{рус, чужой}}=11{,}77.$$

Величину $F$ называют fertility — «плодовитостью» токенизатора. Высокая fertility не доказывает, что модель хуже понимает язык. Она доказывает измеримую инфраструктурную асимметрию: тот же смысл стоит дороже.

Бюджет контекста как языковая величина

Пусть контекстное окно равно 512 токенам. Сколько символов русского текста туда поместится? Своим словарём — 1505 символов, чужим — 304. Английского текста своим словарём — 1656:

$$L_{\text{симв}}=\frac{n_{\text{ток}}}{F_{\text{симв}}},\qquad \frac{1505}{304}\approx4{,}95.$$

Одно и то же окно вмещает почти в пять раз меньше содержания. Если дальше идёт суммаризация, вторая система получила пятикратно меньше текста ещё до того, как началось «понимание».

Хуже того, цена внимания квадратична по длине. Если в механизме внимания число элементов карты растёт как

$$\text{work}\propto n^{2},$$

то пятикратное удлинение последовательности превращается в

$$4{,}95^{2}\approx24{,}5$$

раза больше работы на тот же смысл. Токенизация — не лингвистическая деталь, а множитель перед счётом за вычисления.

Числа: где ломается арифметика

Отдельная драма — числа. Наш словарь обучен на прозе, где числа редки, и результат таков: из чисел от 0 до 999 лишь 4,3% занимают один токен, 60,8% — два, 34,9% — три; в среднем 2,31 токена на число. Но интереснее не среднее, а границы:

$$512\to\texttt{5|12},\qquad 2024\to\texttt{20|24},\qquad 1917\to\texttt{1|9|1|7}.$$

Разряды разрезаны в разных местах у разных чисел. Модель, которой предъявили 512 + 1917, видит не «сотни, десятки, единицы», а куски 5, 12, 1, 9, 1, 7. Позиционная система, которую человек читает справа налево, для неё перемешана.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Хвост словаря: кто работает, а кто спит

Токены распределены крайне неравномерно. На проверочном тексте встретилось 2459 различных токенов; топ-100 покрывает 33,8% всех употреблений, топ-500 — 70,2%. При этом 12,4% встретившихся токенов появились ровно один раз.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Эта картина — старая знакомая: так же ведут себя слова в любом естественном языке. Практический вывод для проектирования: увеличение словаря добавляет почти исключительно редкие токены, то есть строки таблицы, которые почти не учатся. Полезно смотреть не на $V$, а на долю токенов, встретившихся в обучении хотя бы, скажем, тысячу раз.

Следующий токен и честная единица измерения

После токенизации из строки получаются пары «префикс — продолжение»:

$$(i_1,\ldots,i_t)\longrightarrow i_{t+1}.$$

Модель максимизирует правдоподобие — ровно в смысле урока о максимальном правдоподобии, только произведение берётся по позициям:

$$p_\theta(i_1,\ldots,i_n)=\prod_{t=1}^{n}p_\theta(i_t\mid i_{<t}),$$

а минимизируется отрицательный логарифм — та же кросс-энтропия, что в уроке о функции потерь:

$$\mathcal L=-\sum_{t=1}^{n}\log p_\theta(i_t\mid i_{<t}).$$

Обычно сообщают loss на токен и perplexity:

$$\ell=\frac{\mathcal L}{n},\qquad \mathrm{PPL}=\exp(\ell).$$

И вот ловушка: $n$ зависит от токенизатора. Модель с длинными токенами делает меньше шагов, каждый шаг труднее, loss на токен выше — и наоборот. Сравнивать такие числа между моделями с разными словарями бессмысленно. Честная единица — байт исходного текста:

$$\mathrm{BPB}=\frac{\mathcal L}{B\ln2},$$

где $B$ — число байтов текста, а деление на $\ln2$ переводит наты в биты. Величина $\mathcal L$ от разбиения не зависит (это логарифм вероятности одной и той же строки), а $B$ — тем более. Числа становятся сравнимыми.

Пример, который стоит проделать руками. Файл в $B=10\,000$ байт. Модель A: 3000 токенов, $\mathcal L_A=4200$ нат. Модель B: 5000 токенов, $\mathcal L_B=5200$ нат. Тогда

$$\ell_A=1{,}4000,\qquad \ell_B=1{,}0400\ \text{нат/токен},$$ $$\mathrm{BPB}_A=0{,}6059,\qquad \mathrm{BPB}_B=0{,}7502\ \text{бит/байт}.$$

По loss на токен «лучше» B, по битам на байт — A. Порядок моделей перевернулся из-за выбора знаменателя.

Заметьте, что и Шеннон измерял язык в битах на букву, а не в «шагах модели». Языковое моделирование и сжатие — одна и та же задача, записанная разными словами: чем лучше предсказание, тем короче код.

Как выбирать продолжение

Модель выдаёт логиты $z_i$, из которых температурой $\tau$ делают распределение:

$$p_i=\frac{\exp(z_i/\tau)}{\sum_j\exp(z_j/\tau)}.$$

При $\tau\to0$ распределение стягивается в максимум (greedy decoding), при $\tau\to\infty$ — в равномерное. Порядок вариантов температура не меняет никогда: она меняет только резкость. Для логитов $z=(2,1,0,-1)$:

$$\tau=0{,}5:\quad p_1=0{,}8650,\quad H=0{,}657\ \text{бит};$$ $$\tau=1:\quad p_1=0{,}6439,\quad H=1{,}367\ \text{бит};$$ $$\tau=2:\quad p_1=0{,}4551,\quad H=1{,}796\ \text{бит}.$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Top-$k$ оставляет $k$ самых вероятных вариантов, nucleus (top-$p$) — минимальное множество $S$ с условием

$$\sum_{i\in S}p_i\ \ge\ p.$$

И всё это применяется к токенам. Частое слово из одного токена выбирается одним решением; редкое слово из пяти токенов имеет пять моментов, где генерация может свернуть не туда. Вероятность строки — произведение по кускам:

$$p(\text{слово})=\prod_{t}p(i_t\mid i_{<t}),$$

и чем на большее число сомножителей разбито слово, тем ниже обычно эта вероятность. Токенизация напрямую влияет на то, какие слова модель «любит» произносить.

Фитингоф: кодировать, не зная статистики

BPE молча предполагает, что статистика будущего текста та же, что у обучающего корпуса. Вопрос «а что делать, если статистика неизвестна или меняется» — классический вопрос советской теории информации.

В 1966 году Борис Михайлович Фитингоф опубликовал в «Проблемах передачи информации» работу «Оптимальное кодирование при неизвестной и меняющейся статистике сообщений». Он показал, что можно строить код, который не знает распределения источника заранее и всё же асимптотически достигает энтропии: избыточность на символ стремится к нулю с ростом длины блока. Это и есть идея универсального кодирования — предшественница адаптивных методов сжатия и, если угодно, идейный антипод BPE: не «выучи таблицу один раз», а «подстраивайся по ходу».

Линию продолжили в Новосибирске: Рафаил Ефимович Кричевский и Виктор Константинович Трофимов в 1981 году предложили оценку вероятностей, известную теперь как KT-оценка, — прибавление $1/2$ к счётчикам,

$$\hat p(x)=\frac{n_x+\tfrac12}{N+\tfrac{|\mathcal A|}{2}},$$

и доказали для неё границу избыточности порядка $\tfrac12\log N$ на параметр. Знакомая конструкция: это ровно сглаживание из урока про псевдосчётчики, только доказанное с точки зрения длины кода, а не байесовского вывода.

Аудит токенизатора: что измерять

Проверять токенизатор надо так же, как модель, — числами на своих данных. Минимальный протокол.

Обратимость. Для каждого текста проверить побайтово: $T^{-1}(T(s))=s$. Любое расхождение — брак, а не мелочь.

Fertility. Токенов на байт, на символ и на слово, отдельно по жанрам: проза, новости, код, термины, таблицы чисел.

Распределение по словам. Доля слов, разбитых на 1, 2, 3 и больше частей. У нас 40,2% слов русского текста укладываются в один токен — эта доля и есть понятная мера «удобства» словаря.

Устойчивость. Редкая фамилия, опечатка, случайный набор букв. Наш словарь даёт И|н|н|ок|ент|ь|ев|ич (8 токенов), ней|рос|еть (3), с опечаткой ней|рос|еть|ь|ь (5) и |q|w|er|ty|u|i|op (8) на латинской абракадабре. Ни одного <UNK> — но и никакой экономии: корректность есть, эффективности нет.

Числа, URL, разметка. Как режутся разряды; сколько стоит https://; не съедаются ли пробелы в отступах кода.

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

До модели уже сделан выбор

Токенизатор — это часть модели, обученная на части датасета и застывшая раньше всех. Он определяет длину последовательности, а с ней — квадратичную цену внимания; он определяет размер таблицы эмбеддингов, а с ней — десятки миллионов параметров; он определяет, увидит ли модель число как разряды или как случайные куски; он определяет, во сколько раз дороже обойдётся один язык по сравнению с другим.

Мы измерили это на настоящем тексте: 171,7 токена на 100 символов без слияний и 34,0 после трёх тысяч; 0,197 токена на байт своим словарём и 0,974 чужим; 1505 символов в окне против 304. Ни одна из этих величин не относится к «интеллекту» модели — все они относятся к переводчику, стоящему перед ней.

Дальше мы посмотрим, что архитектура делает с этой последовательностью индексов: как каждая позиция выбирает, на что смотреть, в уроке про attention, и как из этого собирается трансформер. Но помните: смысл каждого индекса выбран уже сейчас, и выбран статистикой корпуса, а не смыслом языка.

Задачи