Глава 1.2 — Статистические и счётные языковые модели

Содержание

  1. Простейший возможный ответ: считать и делить
  2. Марковское допущение: зачем вообще нужны n-граммы
  3. Проблема разреженности
  4. Сглаживание: как дать вероятность тому, чего вы никогда не видели
  5. Сглаживание Кнесера-Нея и почему оно победило
  6. Почему этот подход упёрся в потолок
  7. Взгляд с точки зрения собеседования
  8. Вопросы для самопроверки
  9. Источники

1. Простейший возможный ответ: считать и делить

Глава 1.1 установила, что вся задача языковой модели сводится к оценке \(P(x_i \mid x_1, \ldots, x_{i-1})\) — вероятности следующего токена при известных всех предыдущих. Самый прямой способ оценить условную вероятность по данным — он же и самый старый: подсчитать, как часто это происходило, и разделить на то, как часто выполнялось условие.

$$P(x_i \mid x_1, \ldots, x_{i-1}) \approx \frac{\text{count}(x_1, \ldots, x_{i-1}, x_i)}{\text{count}(x_1, \ldots, x_{i-1})}$$

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

2. Марковское допущение: зачем вообще нужны n-граммы

У формулы выше есть очевидная проблема: по мере роста \(i\) контекст \(x_1, \ldots, x_{i-1}\) становится всё более длинной и специфичной строкой, и вероятность того, что вы когда-либо встречали именно эту строку в конечном корпусе, почти сразу падает до нуля. Таблица, основанная на подсчётах, не может оценить вероятность для контекста, который никогда не наблюдался.

Решение, сделавшее счётное моделирование практически применимым, — это марковское допущение: вместо того чтобы обусловливаться на всей истории, обусловливаться только на последних \(n-1\) токенах.

$$P(x_i \mid x_1, \ldots, x_{i-1}) \approx P(x_i \mid x_{i-n+1}, \ldots, x_{i-1})$$

Отсюда и происходит термин «модель n-грамм» («n-gram model»). Биграммная модель (\(n=2\)) предсказывает следующее слово только по предыдущему слову. Триграммная модель (\(n=3\)) использует два предыдущих слова. Это реальный и значимый компромисс, который стоит явно назвать, потому что тот же самый компромисс снова и снова возникает в каждой архитектуре этой книги под разными именами: чем дальше назад модель может «видеть», тем лучше она в принципе может предсказывать, но тем сложнее становится задача оценки, поскольку количество возможных контекстов растёт экспоненциально с ростом \(n\) (при размере словаря \(|V|\) число различных контекстов длины \(n-1\) равно \(\#\text{contexts} = |V|^{\,n-1}\)). Модели n-грамм решали этот компромисс грубым усечением. RNN позже решили его иначе, перенося состояние фиксированного размера вместо прямого усечения. Трансформеры решили его, обращаясь (attending) напрямую к ограниченному окну. Инженерный вопрос — сколько контекста модель реально может учитывать и каким образом — это сквозная линия всей этой книги, и n-граммы — то, с чего она начинается.

3. Проблема разреженности

Усечение контекста до последних \(n-1\) слов помогает, но не устраняет базовую трудность, а лишь уменьшает её. Даже триграммы при скромном по размеру словаре порождают астрономическое число возможных комбинаций из трёх слов, а естественный язык подчиняется закону Ципфа: небольшое число слов и словосочетаний встречаются крайне часто, а очень длинный хвост слов и словосочетаний по отдельности редок, но в совокупности составляет значительную долю реального текста. Это означает, что независимо от размера обучающего корпуса, во время инференса вы постоянно будете сталкиваться с n-граммами, которые никогда не встречались в обучении или встречались лишь один-два раза — что совершенно недостаточно для надёжной оценки вероятности.

Это и есть проблема разреженности, и это не мелкая деталь реализации; это центральное препятствие, вокруг которого счётное языковое моделирование десятилетиями пыталось найти обходной путь. Если модель присваивает вероятность ровно ноль любой n-грамме, которую она никогда не видела при обучении, то в момент, когда реальное предложение содержит хотя бы одну неувиденную триграмму, вероятность всей последовательности схлопывается до нуля, а перекрёстная энтропия (функция потерь модели, глава 1.1) становится бесконечной. Языковая модель, которую может «сломать» одна-единственная новая комбинация из трёх слов, непригодна для реального мира, так что чем-то пришлось пожертвовать.

4. Сглаживание: как дать вероятность тому, чего вы никогда не видели

Решение — это сглаживание (smoothing): систематическое изъятие небольшой части вероятностной массы у того, что вы наблюдали, и перераспределение её на то, чего вы не наблюдали, так что ничему никогда не присваивается ровно ноль. Простейший вариант, сглаживание Лапласа (add-one smoothing), просто делает вид, что каждая возможная n-грамма была встречена на один раз больше, чем на самом деле. Технически это работает, но грубо — оно распределяет вероятностную массу слишком равномерно по огромному пространству неувиденных n-грамм, большинство из которых по-прежнему лингвистически неправдоподобны, даже если бы они и встретились в обучающих данных.

Более совершенные подходы используют откат (backoff) и интерполяцию — две родственные, но различные стратегии комбинирования оценок разной специфичности, которые стоит точно различать. Интерполяция всегда смешивает оценки триграммы, биграммы и униграммы во взвешенную смесь, независимо от того, была ли сама триграмма вообще когда-либо реально замечена. Откат, формализованный Кацем как откат Каца (Katz backoff), придерживается более строгого взгляда: использовать конкретную оценку триграммы всякий раз, когда триграмма реально встречалась (слегка дисконтированную, чтобы зарезервировать часть вероятностной массы), и откатываться к оценке биграммы только тогда, когда триграмма вообще не наблюдалась, откатываясь ещё дальше к униграмме, если не наблюдалась и биграмма. Дисконтирование внутри отката Каца — само по себе именованная техника сглаживания, которую стоит знать: сглаживание Гуда-Тьюринга (Good-Turing discounting) оценивает, сколько вероятностной массы зарезервировать для ненаблюдавшихся событий, глядя на то, сколько различных событий наблюдалось ровно один раз, ровно два раза и так далее, — то, с какой скоростью появляются совершенно новые события по мере накопления данных, само оказывается информативным о том, какая доля массы истинного распределения всё ещё приходится на ненаблюдавшееся. Формально событие, встретившееся \(r\) раз, получает переоценённую частоту

$$r^{*} = (r+1)\,\frac{N_{r+1}}{N_r}$$

где \(N_r\) — число n-грамм, встретившихся ровно \(r\) раз. Идея, объединяющая все эти подходы, — доверять самому специфичному контексту, для которого у вас достаточно данных, чтобы ему доверять, а иначе плавно деградировать к менее специфичным, но более надёжно оцениваемым контекстам, — возникла задолго до n-грамм и постоянно встречается в статистике, но именно в языковом моделировании на n-граммах она была проработана наиболее тщательно.

5. Сглаживание Кнесера-Нея и почему оно победило

Среди множества методов сглаживания, разработанных в 1990-х годах, сглаживание Кнесера-Нея (Kneser-Ney smoothing) (и его последующее уточнение — модифицированное сглаживание Кнесера-Нея, формализованное Ченом и Гудманом) стало фактическим стандартом, и стоит понять почему, поскольку в основе лежит по-настоящему изящное статистическое наблюдение, а не просто инженерный трюк.

Простые схемы отката используют для отката к статистикам более низкого порядка сырую частоту: если нужна оценка униграммы для слова, используется то, как часто это слово встречается в целом. Инсайт Кнесера-Нея состоит в том, что сырая частота униграммы — неверная вещь для отката. Рассмотрим слово «Francisco» («Франциско»). Оно может быть очень частотным в корпусе — но почти исключительно потому, что следует за словом «San» («Сан»). Его сырая частота завышает его полезность как общего запасного предсказания, потому что фактически оно встречается не во многих разных контекстах, а в одном конкретном контексте, но очень часто. Вместо этого сглаживание Кнесера-Нея оценивает распределение более низкого порядка на основе вероятности продолжения (continuation probability): не того, как часто встречается слово, а того, после скольких различных контекстов оно встречается:

$$P_{\text{cont}}(w) = \frac{|\{v : c(v, w) > 0\}|}{\sum_{w'} |\{v : c(v, w') > 0\}|}$$

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

Именно это различие — между сырой частотой и разнообразием контекста — позволило сглаживанию Кнесера-Нея настолько стабильно превосходить другие методы сглаживания, что оно оставалось сильнейшим стандартным методом сглаживания для n-грамм примерно два десятилетия, вплоть до эпохи, когда нейросетевые методы начали конкурировать со счётными моделями на тех же самых бенчмарках.

6. Почему этот подход упёрся в потолок

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

Во-первых, марковское усечение — это реальная потеря информации, а не просто удобство реализации. Дальние зависимости — местоимение, отсылающее к существительному, введённому десятью словами ранее, глагол, правильное время которого зависит от подлежащего далеко слева, тема, заданная абзацем ранее и которая должна влиять на следующее слово, — невидимы для модели, способной видеть только последние \(n-1\) токенов. Увеличение \(n\) на самом деле не решает эту проблему, потому что разреженность катастрофически усугубляется с ростом \(n\); на практике модели n-грамм редко выходили за пределы \(n=5\) даже при огромных корпусах и агрессивном сглаживании.

Во-вторых, и это более фундаментально, счётные модели рассматривают каждую отдельную строку слов как совершенно самостоятельную сущность. Нет механизма, посредством которого изучение чего-либо о фразе «кот сидел на коврике» дало бы модели хоть какое-то знание о фразе «пёс сидел на подстилке», хотя эти предложения почти взаимозаменяемы по смыслу и грамматической структуре. Слова, с точки зрения таблицы, — это просто отдельные символы, подлежащие подсчёту: у модели нет никакого понятия о том, что «кот» и «пёс» в каком-либо смысле похожи и что между ними должна переноситься статистическая сила. Именно этот разрыв и была призвана закрыть нейросетевая языковая модель — заменив символьные идентичности слов на выученные векторные представления, размещающие похожие слова рядом друг с другом в непрерывном пространстве, — тема главы 1.3 и самый большой концептуальный скачок между этой главой и следующей.

7. Взгляд с точки зрения собеседования

Интервьюеры редко просят построить модель n-грамм с нуля, но эта глава постоянно всплывает как способ проверить, понимаете ли вы, почему нейросетевые подходы были необходимы, а не просто знаете, что они существуют:

  • «Почему нельзя просто масштабировать модели n-грамм вместо использования нейросетей?» — сильный ответ явно называет оба режима отказа: потолок разреженности/марковского усечения по длине контекста и отсутствие какого-либо обобщения между похожими, но различными словами или фразами.
  • «В чём суть инсайта Кнесера-Нея, одним предложением?» — ожидаемый ответ говорит о вероятности продолжения (разнообразии контекстов, после которых встречается слово), а не о сырой частоте, и умение чётко это сформулировать сигнализирует о реальном понимании, а не заученном факте.
  • «Как бы вы обработали слово, которое ваша модель никогда не видела на этапе инференса?» — на самом деле это вопрос о том, понимаете ли вы сглаживание и, шире, обработку слов вне словаря (out-of-vocabulary) — проблему, которая почти в неизменном виде вновь возникнет в главе о токенизации.

8. Вопросы для самопроверки

  1. Запишите оценку максимального правдоподобия для вероятности триграммы через подсчёты по корпусу и объясните, почему эта оценка становится ненадёжной по мере роста длины контекста.
  2. Какую конкретную проблему решает марковское допущение и чем приходится за это платить?
  3. Объясните своими словами проблему разреженности и почему присвоение вероятности ноль неувиденной n-грамме недопустимо для работающей языковой модели.
  4. В чём разница между откатом (backoff) и интерполяцией как стратегиями сглаживания?
  5. Объясните, почему использование «вероятности продолжения» в сглаживании Кнесера-Нея — лучшая запасная оценка, чем сырая частота униграммы. Используйте пример со словом «Francisco» или свой собственный.
  6. Назовите две структурные причины, по которым модели n-грамм упёрлись в потолок, который не могло исправить одно лишь сглаживание, и объясните, как каждая из них конкретно мотивирует переход к нейросетевым языковым моделям в следующей главе.

9. Источники

  • Kneser, R., & Ney, H. (1995). Improved backing-off for M-gram language modeling. ICASSP 1995, vol. 1, pp. 181–184. RWTH Aachen PDF
  • Chen, S. F., & Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4), 359–394.

Тест для самопроверки

Проверьте понимание главы с помощью короткого теста — вопросы по теории и небольшие расчёты.

Что делает марковское предположение, используемое в моделях n-грамм?

Объяснение: Вместо обусловливания на всей истории x_1...x_{i-1}, марковское предположение обусловливает только на последних n−1 токенах — отсюда и название «модель n-грамм».

В чём заключается «проблема разреженности» в языковом моделировании на n-граммах?

Объяснение: Естественный язык подчиняется закону Ципфа, поэтому независимо от размера корпуса при инференсе постоянно будут встречаться n-граммы, никогда не виденные при обучении — присвоение им нулевой вероятности отправило бы перекрёстную энтропию в бесконечность.

В чём состоит ключевой инсайт сглаживания Кнесера-Нея по сравнению с простым откатом?

Объяснение: Пример со словом «Francisco»: оно частотно только потому, что следует за «San» — сырая частота завышает его ценность как общего запасного варианта. Кнесер-Ней вместо этого поощряет слова, встречающиеся после многих разных контекстов.

В чём состоит более глубокое структурное ограничение счётных моделей n-грамм, которое не может исправить никакое сглаживание?

Объяснение: Счётные таблицы никак не отражают, что «кот» и «собака» похожи — знание об одном предложении никак не переносится на почти синонимичное. Именно этот разрыв призваны закрыть нейросетевые представления слов (глава 1.3).

В обучающем корпусе последовательность «кот сидел на» встречается 8 раз, а префикс «кот сидел» встречается 40 раз. Используя оценку максимального правдоподобия, чему равна $P(\text{на} \mid \text{кот сидел})$?

Объяснение: Оценка MLE = count(«кот сидел на») / count(«кот сидел») = 8 / 40 = 0.2.

Модель n-грамм с $n = 5$ (5-грамма) обусловливает своё предсказание на скольких предыдущих токенах?

Объяснение: Модель n-грамм обусловливает предсказание на последних n−1 токенах, поэтому при n=5 это 5−1 = 4 предыдущих токена.

При сглаживании Лапласа (add-one) слово $w$ встречается 3 раза в обучающем корпусе из 100 токенов всего, а размер словаря — 1000. Чему равна сглаженная оценка вероятности $P_{\text{Лапласа}}(w) = \dfrac{\text{count}(w) + 1}{\text{всего} + V}$? (Округлите до 4 знаков после запятой.)

Объяснение: (3 + 1) / (100 + 1000) = 4 / 1100 ≈ 0.0036.

Биграмма «в течение» встречается в корпусе 450 раз, а слово «в» встречается всего 9000 раз. Чему равна оценка максимального правдоподобия $P(\text{течение} \mid \text{в})$?

Объяснение: 450 / 9000 = 0.05.

Что использует сглаживание Гуда-Тьюринга, чтобы оценить, сколько вероятностной массы зарезервировать для ещё ненаблюдавшихся событий?

Объяснение: Гуд-Тьюринг смотрит на то, сколько различных событий наблюдалось ровно один раз, ровно два раза и так далее — то, с какой скоростью появляются совершенно новые события по мере накопления данных, оказывается информативным о том, какая доля массы истинного распределения всё ещё приходится на ненаблюдавшееся.

Используя переоценку Гуда-Тьюринга $r^{*} = (r+1) \frac{N_{r+1}}{N_r}$, n-грамма наблюдалась $r = 2$ раза. Есть $N_2 = 50$ n-грамм, встретившихся ровно два раза, и $N_3 = 20$ n-грамм, встретившихся ровно три раза. Чему равна переоценённая частота $r^{*}$?

Объяснение: $r^{*} = (2+1) \times (20/50) = 3 \times 0.4 = 1.2$ — Гуд-Тьюринг дисконтирует сырую частоту 2 до эффективной частоты 1.2.