N-граммные языковые модели

Классификатор на мешке слов отвечает на вопрос «какая тема», а не «что дальше». Чтобы порождать текст, дополнять поисковый запрос или оценивать, правдоподобно ли предложение, нужна модель последовательности: вероятность $P(w_1, \dots, w_T)$ для любой последовательности токенов. Эта заметка строит простейшую такую модель из счётчиков, вводит метрику, которой в курсе измеряется каждая языковая модель, и упирается в то, что модель на счётчиках не умеет обобщать.

Обозначения. Последовательность из $T$ токенов — $w_1, \dots, w_T$, или $w_{1:T}$. $w_{<i}$ означает $w_1, \dots, w_{i-1}$. $c(\cdot)$ считает вхождения последовательности токенов в обучающий корпус. $V$ — словарь.

От совместной вероятности к произведению условных#

Любое совместное распределение последовательности раскладывается по формуле умножения вероятностей (chain rule) без всяких предположений:

$$P(w_1, \dots, w_T) = P(w_1)\,P(w_2 \mid w_1)\,P(w_3 \mid w_1, w_2)\cdots = \prod_{i=1}^T P(w_i \mid w_{<i}).$$

Каждый множитель — вероятность следующего токена при условии всего, что было до него. Эту форму принимает каждая языковая модель курса, от этой заметки до заметки о GPT: языковая модель и есть предсказатель следующего токена, а предсказание следующего токена — задача классификации с $|V|$ классами.

Множители нельзя оценить напрямую. В условии $P(w_i \mid w_{<i})$ стоит префикс, который при $i$ больше нескольких токенов ещё ни разу не встречался ни в одном корпусе. Марковское предположение (Markov assumption) обрезает префикс до последних $n - 1$ токенов:

$$P(w_i \mid w_{<i}) \approx P(w_i \mid w_{i-n+1}, \dots, w_{i-1}).$$

Получается n-граммная языковая модель. При $n = 2$ (биграммы) каждый токен зависит от одного предшественника, при $n = 3$ (триграммы) — от двух. Предположение неверно (местоимение может ссылаться на слово за пятьдесят токенов назад) и полезно (двух токенов контекста уже хватает, чтобы задать бо́льшую часть локальной грамматики).

Отправная точка: оценить условные вероятности подсчётом#

При конечном контексте каждая условная вероятность — категориальное распределение на $V$ при конкретном префиксе, и его оценка максимального правдоподобия — отношение счётчиков:

$$P(w \mid \text{префикс}) = \frac{c(\text{префикс},\, w)}{\sum_{w' \in V} c(\text{префикс},\, w')}.$$

Два специальных токена делают границы последовательности явными. У первых токенов строки нет полного префикса, поэтому строку дополняют слева $n - 1$ копиями символа начала; в конец добавляют символ конца [EOS], чтобы модель могла научиться останавливаться.

Разобранный пример#

Игрушечный корпус из трёх строк и биграммная модель ($n = 2$):

the cat sat
the cat ran
the dog sat

Дополним каждую строку одним символом начала [S] и завершим [EOS]. Счётчики биграмм:

префикс	следующий	счётчик	$P(\text{следующий} \mid \text{префикс})$
[S]	the	3	1
the	cat	2	2/3
the	dog	1	1/3
cat	sat	1	1/2
cat	ran	1	1/2
dog	sat	1	1
sat	[EOS]	2	1
ran	[EOS]	1	1

Вероятность новой строки the dog ran равна

$$P = P(\text{the} \mid \text{[S]})\,P(\text{dog} \mid \text{the})\,P(\text{ran} \mid \text{dog})\,P(\text{[EOS]} \mid \text{ran}) = 1 \cdot \tfrac13 \cdot 0 \cdot 1 = 0.$$

Биграмма dog ran ни разу не встретилась, поэтому вся строка получает нулевую вероятность. Это стоит запомнить: именно этому провалу посвящена оставшаяся часть заметки.

Таблицу проще читать как граф — и именно так модель порождает текст:

Рисунок

Биграммная модель как граф переходов

Порождение#

Раз модель раскладывается слева направо, она так же и порождает текст. Начинаем с дополнения, сэмплируем $w_1 \sim P(\cdot \mid \text{[S]})$, дописываем его, сэмплируем $w_2 \sim P(\cdot \mid w_1)$ и останавливаемся на [EOS]. Выход каждого шага подаётся на вход следующему: порождение авторегрессионное, и этот цикл один и тот же во всех порождающих языковых моделях курса. Альтернатива сэмплированию — брать на каждом шаге самый вероятный токен — одна из стратегий декодирования, которые сравниваются в заметке о GPT.

Триграммная модель, обученная на корпусе коротких русских анекдотов с токенами BPE, порождает строки, грамматичные локально и бессмысленные в целом, например

мужчина должен постро ##ить дом и вот я однажды мгнове ##нно удалил это сообщение , …

Каждые три токена подряд где-то в корпусе встречались; предложение целиком — нет, и связным оно не становится. Двух токенов памяти хватает для согласования соседних слов и ни для чего больше.

Перплексия: от вероятности к числу#

Чтобы сравнить две языковые модели, нужна оценка на отложенном тексте. Сама вероятность последовательности для этого непригодна: она убывает с длиной, так что у длинной тестовой выборки вероятность всегда крошечная, какой бы ни была модель. Возьмём логарифм, который превращает произведение в сумму, и поделим на длину, что даёт среднее на токен:

$$H = -\frac{1}{T}\sum_{i=1}^T \log P(w_i \mid w_{<i}).$$

Это кросс-энтропия тестового текста относительно модели в натах на токен (в битах, если логарифм по основанию 2). Это та же величина, что и функция потерь классификатора из предыдущей заметки, увиденная с четырёх сторон:

1. Как сумма по классам. В позиции $i$ «истинное распределение» — one-hot на наблюдаемом токене $w_i$: $q_i(w) = \mathbb 1[w = w_i]$. Кросс-энтропия между $q_i$ и моделью $P(\cdot \mid w_{<i})$ равна $-\sum_{w \in V} q_i(w)\log P(w \mid w_{<i}) = -\log P(w_i \mid w_{<i})$. Все слагаемые, кроме одного, обращаются в ноль.
2. Как математическое ожидание. Усреднение по позициям — оценка методом Монте-Карло величины $\mathbb E_{w \sim \text{данные}}[-\log P(w \mid \text{контекст})]$, ожидаемой неожиданности модели на тексте из истинного распределения.
3. Как отрицательный логарифм правдоподобия. По формуле умножения вероятностей $T \cdot H = -\log P(w_{1:T})$, поэтому минимизация $H$ — это оценка последовательности методом максимального правдоподобия.
4. Как энтропия плюс дивергенция. Если истинное распределение следующего токена — $p$, то $H(p, P) = H(p) + D_{\mathrm{KL}}(p \,\|\, P)$. Энтропия языка фиксирована; модель может уменьшить только KL-член. Это разложение выведено в курсе по генеративным моделям.

Перплексия (perplexity) — экспонента кросс-энтропии:

$$\mathrm{PPL} = e^{H} = \exp\!\Big(-\frac1T\sum_{i=1}^T \log P(w_i \mid w_{<i})\Big) = P(w_{1:T})^{-1/T}.$$

Последняя форма — среднее геометрическое обратных вероятностей токенов, поэтому перплексию читают как эффективный коэффициент ветвления: модель с перплексией 50 в среднем так же неуверенна, как если бы на каждом шаге выбирала равновероятно из 50 токенов. Масштаб фиксируют две проверки. У модели, которая приписывает каждому токену вероятность 1, $H = 0$ и $\mathrm{PPL} = 1$. У равномерной модели на $|V|$ токенах $H = \log|V|$ и $\mathrm{PPL} = |V|$. Чем меньше, тем лучше, а основание логарифма сокращается, если для $\log$ и $\exp$ взято одно и то же основание.

На игрушечном корпусе у строки the dog ran вероятность 0, поэтому $H = \infty$ и перплексия бесконечна. На обучающих данных происходит обратное: на пяти строках, которые использованы и для обучения, и для оценки, у униграммной модели перплексия 81.7, у триграммной 1.14, а у 10-граммной 1.10. Модели с длинным контекстом запомнили строки, и число ничего не говорит о новом тексте.

Все значения перплексии, измеренные в этой заметке на корпусе анекдотов, — средние по строкам: перплексия каждой строки считается отдельно, и полученные значения усредняются. Так каждая строка весит одинаково, а в формуле выше одинаково весит каждый токен, поэтому значения — не перплексия корпуса. Игрушечный пример показывает разницу: у строки из 2 токенов с NLL на токен 1 перплексия $e \approx 2.72$, у строки из 8 токенов с NLL 3 — $e^3 \approx 20.1$. Их среднее — 11.4, а перплексия корпуса, экспонента суммарного NLL, делённого на общее число токенов, равна $\exp((2 \cdot 1 + 8 \cdot 3)/10) = e^{2.6} \approx 13.5$. Перплексия корпуса — стандартный рецепт, и для новых измерений нужна именно она; средние по строкам приведены здесь потому, что именно они измерены в этой заметке, и сравнивать их можно только в пределах одной таблицы, где все модели оценены одинаково.

Невстреченные n-граммы взрывают перплексию#

Разобьём корпус анекдотов в пропорции 75/25, обучим модель на первой части и оценим отложенную часть на токенах-словах. Перплексии получаются порядка $10^{46}$ для униграммной модели и $10^{48}$ для триграммной. Причина — тот же ноль, что в разобранном примере: у любой тестовой n-граммы, которой не было при обучении, $P = 0$, а $\log 0 = -\infty$. Вероятности ниже $10^{-50}$ поднимаются до $10^{-50}$, чтобы сумма оставалась конечной, и эти поднятые слагаемые доминируют над всем остальным. Чем больше контекста использует модель, тем больше тестовых n-грамм оказываются невстреченными, поэтому триграммы получают оценку хуже униграмм. По этому измерению худшей оказывается модель с самой длинной памятью, и проблема в самом измерении: оно сообщает, сколько тестовых n-грамм не встречалось при обучении, а не насколько хорошо модель предсказывает.

Сглаживание#

Аддитивное сглаживание (сглаживание Лапласа) добавляет псевдосчётчик $\delta$ каждому токену в каждом контексте:

$$P(w \mid \text{префикс}) = \frac{c(\text{префикс},\, w) + \delta}{\sum_{w' \in V}\big(c(\text{префикс},\, w') + \delta\big)} = \frac{c(\text{префикс},\, w) + \delta}{c(\text{префикс}) + \delta\,|V|}.$$

Знаменатель растёт на $\delta|V|$, поэтому масса, отданная невстреченным в данном контексте токенам, равна $\delta(|V| - \text{встреченные})/(c(\text{префикс}) + \delta|V|)$ и делится между ними поровну. При $\delta = 1$ и словаре размером со словарь BPE этого корпуса, 37 580 токенов, контекст, встреченный 10 раз, оставляет действительно наблюдавшимся токенам лишь $10/(10 + 37\,580) \approx 0.03\,\%$ своей массы. Это слишком сильное сглаживание, поэтому добавление единицы — иллюстративный метод, а не практический, но нули оно убирает:

Токены	$n = 1$	$n = 2$	$n = 3$
Слова, $\delta = 1$	39 956	30 058	70 786
BPE, $\delta = 1$	2696	3860	15 598

Таблицу нужно читать внутри строки; две строки между собой не сравнимы. В тексте из токенов BPE токенов больше, чем слов в том же тексте, и каждый предсказать легче, поэтому меньшая перплексия на токен не означает лучшей модели, а в пересчёте на слово порядок может смениться (пересчёт сделан в заметке о токенизации). Внутри строки видны две вещи. Перплексии конечны и лежат в диапазоне, где разница что-то значит. И триграммная модель хуже биграммной: с более длинным контекстом каждый префикс встречается реже, счётчики $c(\text{префикс})$ малы, и сглаживание добавлением единицы сплющивает распределение к равномерному. Лучшее $n$ — компромисс между контекстом и разреженностью данных, и при грубом сглаживании оно маленькое.

Лучшие методы сглаживания исправляют недостаток равномерного распределения массы. Интерполяция смешивает триграммную, биграммную и униграммную оценки с выученными весами, так что редкий триграммный контекст опирается на биграммную статистику, а не на равномерное распределение. Сглаживание Кнезера–Нея (Kneser–Ney smoothing; Kneser and Ney, 1995; Chen and Goodman, 1999) вычитает фиксированную скидку из каждого встреченного счётчика и перераспределяет её пропорционально тому, в скольких различных контекстах встречается токен; это лучший метод для моделей на счётчиках. Хорошая перплексия современной нейросетевой модели на английском веб-тексте — несколько десятков; для маленького корпуса анекдотов разумной целью было бы что угодно ниже нескольких сотен, а сглаживание добавлением единицы до этого не дотягивает.

Что изменилось#

	Классификатор на мешке слов	N-граммная языковая модель
Вопрос	Какая метка?	Что дальше?
Статистика	Счётчики токенов в документе	Счётчики последовательностей из $n$ токенов
Выход	Одно распределение на $K$ метках	Одно распределение на $V$ в каждой позиции
Порядок	Игнорируется	Последние $n - 1$ токенов
Умеет порождать	Нет	Да, авторегрессионно
Метрика	Доля правильных ответов, $F_1$	Перплексия

Ограничения#

• Разреженность растёт с $n$. Число возможных n-грамм равно $|V|^n$. Бо́льшая часть из них никогда не встречается, поэтому модель не может использовать больше нескольких токенов контекста, сколько бы данных у неё ни было.
• Нет обобщения между токенами. the cat sat и the dog sat — не связанные события; то, что встретилось первое, не повышает вероятность второго. Каждый токен — атом, как и в мешке слов. Это ограничение снимает следующая заметка.
• Хранение. Модель — таблица счётчиков для каждого встреченного префикса. Она растёт вместе с корпусом и плохо сжимается.
• Перплексия — внутренняя метрика. Меньшая перплексия не гарантирует лучшей генерации или лучшей прикладной системы; см. заметку об оценке. Кроме того, её нельзя сравнивать между разными токенизаторами: когда меняются токены, меняется и среднее на токен.

Что нужно запомнить#

• Формула умножения вероятностей: $P(w_{1:T}) = \prod_i P(w_i \mid w_{<i})$. Языковая модель — классификатор следующего токена на $V$.
• Марковское предположение: условие только на последние $n-1$ токенов; оценка — отношение счётчиков; строки дополняются символами начала и конца.
• Кросс-энтропия $H = -\frac1T\sum_i \log P(w_i \mid w_{<i})$ — отрицательный логарифм правдоподобия на токен; перплексия равна $e^{H}$, эффективному коэффициенту ветвления; равномерная модель на $V$ даёт $|V|$.
• Невстреченная n-грамма даёт $P = 0$ и бесконечную перплексию. Сглаживание резервирует массу для неувиденного; добавление $\delta$ — простейший вариант, и на больших словарях он сглаживает слишком сильно.
• Порождение авторегрессионное: сэмплировать, дописать, повторить.

Ноутбук#

week03_lm.ipynb. Номера ячеек считают все ячейки, включая текстовые, начиная с 1. Приведённые числа взяты из прогона, сохранённого в курсе; у ячеек, изменённых с тех пор под текущие версии библиотек, сохранённого выхода нет.

• Ячейки 4–5 загружают корпус коротких русских анекдотов, по одному на абзац; ячейки 6–17 строят токенизатор BPE, описанный в заметке о токенизации.
• Ячейки 18–28 формулируют формулу умножения вероятностей и марковское предположение, реализуют count_ngrams (дополнение слева $n - 1$ копиями [UNK], который заменяет символ начала и считается обычным токеном, и добавление [EOS]) и класс NGramLanguageModel, который превращает счётчики в условные вероятности ровно по формуле выше. Ячейки 22–25 показывают триграммные счётчики на пяти строках.
• Ячейки 30–33 обучают триграммную модель с токенами BPE на всём корпусе и сэмплируют анекдот токен за токеном через np.random.choice; приведённая выше строка — сохранённый выход ячейки 33.
• Ячейки 34–36 реализуют перплексию с порогом min_prob, равным $10^{-50}$, как среднее перплексий по строкам и приводят 81.663, 1.142 и 1.103 для $n = 1, 3, 10$ на пяти обучающих строках.
• Ячейка 38 делит корпус в пропорции 75/25 и приводит перплексии отложенной части на токенах-словах порядка от $10^{46}$ до $10^{48}$ для $n = 1, 2, 3$.
• Ячейки 39–43 реализуют LaplaceLanguageModel и приводят сглаженные перплексии отложенной части из таблицы выше, сначала для токенов-слов, затем для токенов BPE. В первой версии метод класса get_tokens_and_probs вызывал метод, которого нет в родительском классе, поэтому сэмплирование из сглаженной модели падало (на оценку, которая использует get_token_prob, это не влияло); текущий ноутбук вызывает get_tokens_and_probs родительского класса, а ячейка 41 проверяет, что сглаженные вероятности по всему словарю в сумме дают 1 для $n = 1, 2, 3$.
• Ячейки 44–55 начинают рекуррентную языковую модель на тех же токенах; её продолжает заметка о RNN.

Дальше#

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

Литература#

• D. Jurafsky, J. H. Martin. Speech and Language Processing, 3rd ed. draft. Глава 3 (n-граммные языковые модели, перплексия, сглаживание).
• R. Kneser, H. Ney. Improved backing-off for M-gram language modeling. ICASSP, 1995.
• S. F. Chen, J. Goodman. An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4), 1999. Сравнение, которое утвердило модифицированное сглаживание Кнезера–Нея.
• C. E. Shannon. Prediction and Entropy of Printed English. Bell System Technical Journal, 30(1), 1951. Энтропия английского текста на символ и n-граммные приближения.
• T. M. Cover, J. A. Thomas. Elements of Information Theory, 2nd ed. Wiley, 2006. §2.3 (относительная энтропия) — разложение на энтропию и KL.