data.Science(R)

Анализ данных, машинное обучение, и визуализация в R

N-граммная модель прогнозирования слов

wordcloud

Рассмотрим одну из тем, входящих в состав обработки естественного языка (Natural Language Processing, NLP), — тему прогнозирования слов.

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

Эти знания будут полезными во многих областях:

  • Распознавание речи;
  • коррекция правописания;
  • машинный перевод;
  • или, например, чтобы успешно пройти специализацию Data Sciense на Coursera.

Модели, которые присваивают вероятности последовательности слов, называются языковыми моделями (Language models). Под языковыми моделями, как правило, подразумевается вероятностное распределение последовательностей слов, которое пытается предугадать, как часто данная последовательность встречается в предложении. Например, для языковой модели, описывающей разговорный язык, мы можем иметь \(P(ПРИВЕТ)= 0.01\), так как, вероятно, в каждом сотом предложении человек произносит слово “привет”. С другой стороны, \(P(\text{МОЖЕТ ЗДРАВСТВУЙТЕ ДВА})= 0\), так как очень маловероятно, что кто-нибудь произнесёт эту фразу в повседневной жизни.

N-граммная модель

Здесь мы рассмотрим простейшую из таких моделей — n-граммную модель (n-gram). N-грамма — это последовательность из n слов:

  • Биграмма — это последовательность из двух слов (“пожалуйста закрой”);
  • последовательность из трёх слов называется триграмма (“закрой за собой”).
  • не менее четырех и выше элементов обозначаются как n-грамма, где n заменяется на количество последовательных элементов.

Для извлечения и обработки n-грамм из текста или совокупности текстов (Corpus) в R существует множество пакетов: “tm”, “tokenizers”, “ngram” и другие, но можно воспользоваться и базовыми средствами языка:

Расчёт вероятности

Начнем с задачи расчёта \(P(w|h)\), вероятности появления слова \(w\) при заданной предыстории \(h\). Предположим, что мы имеем следующую предысторию: “представителем древней фауны был саблезубый”, и хотим рассчитать вероятность того, что следующим словом в этой последовательности будет слово “тигр”.

Мы будем использовать следующие упрощения:

  • \(P(x_i = ТИГР)\): вероятность случайной величины \(x_i\), принимающей значение “тигр”, мы будем обозначать как \(P(ТИГР)\);
  • последовательность \(N\) слов мы будем обозначать как \(w_1…w_n\) или \(w_1^n\);
  • совместную вероятность каждого слова в последовательности, принимающего конкретное значение, \(P(X = w_1,Y = w_2,Z = w_3,…,W = w_n)\) мы будем обозначать как \(P(w_1,w_2,…,w_n)\).

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

Биграммная модель, например, аппроксимирует (приближает) вероятность слова, при условии наступления всей его предыстории \(P(w_n|w_1^{n-1})\), используя лишь условную вероятность предыдущего слова \(P(w_n|w_{n−1})\). Другими словами, вместо расчёта вероятности \(P(ТИГР|\text{ПРЕДСТАВИТЕЛЕМ ДРЕВНЕЙ ФАУНЫ БЫЛ САБЛЕЗУБЫЙ})\) мы аппроксимируем её к вероятности \(P(ТИГР|САБЛЕЗУБЫЙ)\).

$$P(w_n|w_1^{n-1}) \approx P(w_n|w_{n-1})$$

Допущение, что вероятность слова зависит только от предыдущего слова, было сформулировано русским математиком Андреем Андреевичем Марковым, положившим в работах 1907 года начало теории цепей Маркова (Markov chain).

Мы можем c лёгкостью обобщить нашу модель до n-граммной:

$$P(w_n|w_1^{n-1}) \approx P(w_n|w_{n-N+1}^{n-1})$$

В упрощённой форме, мы можем оценить параметры этой n-граммной модели при помощи метода наибольшего правдоподобия (MLE, maximum likelihood estimation) следующим образом:

$$P(w_n|w_{n-N+1}^{n-1})=\frac{C(w_{n-N+1}^{n-1} w_n)}{C(w_{n-N+1}^{n-1})}$$

Пример с биграммной моделью:

$$P(ТИГР|САБЛЕЗУБЫЙ)=\frac{C(\text{САБЛЕЗУБЫЙ ТИГР})}{C(САБЛЕЗУБЫЙ)}$$

Пример с триграммной моделью:

$$P(ТИГР|\text{БЫЛ САБЛЕЗУБЫЙ})=\frac{C(\text{БЫЛ САБЛЕЗУБЫЙ ТИГР})}{C(\text{БЫЛ САБЛЕЗУБЫЙ})}$$

Данное выражение определяет вероятность n-граммы как отношение наблюдаемой частоты определённой последовательности к наблюдаемой частоте её предыстории. Эта оценка называется относительной частотой (Relative frequency) и всегда находится в промежутке между 1 и 0.

В R такая частота вычисляется при помощи следующего кода:

Оценка эффективности модели

Для оценки языковой модели нам необходима тестовая выборка. Как и для любой другой статистической модели, вероятности n-граммной модели оцениваются на обучающей выборке, после чего качество модели в целом оценивается по её результативности к неизвестным данным из тестовой выборки.

Наиболее часто встречающимися методами оценки языковой модели является перплексия (perplexity). Перплексией языковой модели на тестовой выборке является обратная вероятность этой выборки, нормализованная по количеству слов. Для тестовой выборки \(T = w_1w_2…w_N)\) перплексия равна:

$$ PP(T)=P(w_1w_2…w_N)^{-1/N}=\sqrt[N]{\frac{1}{P(w_1w_2…w_N)}} $$ Например, в случае с биграммной моделью, мы рассчитываем: $$ PP(T)=\sqrt[N]{\prod_{i=1}^{N}\frac{1}{P(w_i|w_1…w_{i-1})}} $$

Сглаживание

Что мы будем делать со словами, которые есть в нашем словаре, но появляются в невиданном ранее контексте(например они появляются после слова, после которого до этого не появлялись). MLE присваивает нулевую вероятность всем n-граммам не в корпусе. Чтобы предостеречь нашу модель от присваивания нулевой вероятности таким последовательностям мы должны выражаясь образно “сбрить” немного вероятности от чаще встречающихся событий и присвоить эту вероятность событиям, которых мы никогда не видели.

Дабы продемонстрировать, как важно, чтобы у вероятностей не было нулевых значений, обратимся к важному применению языковых моделей — распознаванию речи. В распознавании речи мы пытаемся найти предложение \(s\) которое бы максимизировало \(P(s|A)=\frac{P(A|s)P(s)}{P(A)}\) для заданного акустического сигнала \(А\). Если \(P(s)=0\), тогда \(P(s|A)\) тоже будет равно нулю и предложение \(s\) не будет рассматриваться как транскрипция независимо от того, насколько акустический сигнал будет однозначным. Таким образом, каждый раз, когда такая фраза будет появляться в процессе распознавания речи, мы будем сталкиваться с ошибкой. Задание всем фразам не нулевой вероятности защитит нас от таких ошибок.

С этой проблемой предлагает справиться сглаживание (Smoothing). Термин сглаживание происходит из того факта, что эта техника делает распределение более равномерным, поднимая нулевые вероятности и опуская высокие. Сглаживание называется также discounting, так как часть вероятности n-грамм с большей вероятностью перераспределяется среди нулевых n-грамм. Образно выражаясь, этот приём как Робин Гуд: крадёт у богатых и раздаёт бедным.

Мы рассмотрим лишь два простейших варианта:

Сглаживание Лапласа

Простейший путь — добавить единицу ко всем биграммам до того, как мы нормализуем их к вероятностям. Все нулевые значения теперь стали 1, единичные значения стали 2, и так далее. Такое сглаживание так же называют add one smoothing. В более общем виде этот метод добавляет единицу к каждому событию и затем нормализует знаменатель.

$$P_{Laplace}(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)+1}{C(w_{n-1})+V}$$

где \(V\) – размер словаря

Такой тип сглаживания даёт довольно бедные результаты, с ним связано несколько проблем:

  • Если сглаживание крадёт у богатых и раздаёт бедным, то в случае Лапласа оно крадёт слишком много.

Улучшенный метод: Additive smoothing или add-k smoothing. Смысл в том, что он просто крадёт меньше:

\(0 < k ≤ 1\)

$$P_{Add-k}(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)+k}{C(w_{n-1})+kV}$$

Интерполяция Йелинека Мерсера

Если мы пытаемся посчитать вероятность \(P(w_n|w_{n-2}w_{n-1})\), но у нас нет примеров триграммы \(w_{n-2}w_{n-1}w_n\) — мы можем взамен оценить её вероятность, используя вероятность биграммы \(P(w_n|w_{n-1})\). Похожим образом, если у нас нет значений, чтобы посчитать \(P(w_n|w_{n-1})\) — мы берём униграмму \(P(w_n)\).

В простейшей интерполяции мы совмещаем n-граммы разного порядка, линейно интерполируя все модели. Таким образом, мы оцениваем вероятность триграммы, комбинируя униграмные биграмные и триграмные вероятности, взвешенные по \(\lambda\), так, чтобы сумма всех \(\lambda\) равнялась единице.

$$
\begin{equation}
\begin{split}
\hat{P}(w_n|w_{n-2}w_{n-1}) = \lambda_1 P(w_n|w_{n-2}w_{n-1}) \\
+ \lambda_2 P(w_n|w_{n-1}) \\
+ \lambda_3 P(w_n)
\end{split}
\end{equation}
$$

Значения \(\lambda_i\) подбираются таким образом, чтобы оптимизировать перплексию на валидационной выборке — дополнительной обучающей выборке, которую используют для задания гиперпараметров, таких как лямбда, выбирая такие её значения, которые максимизируют производительность на валидационной выборке.

Источники:

  • An Empirical Study of Smoothing Techniques for Language Modeling. Stanley F. Chen & Joshua Goodman, Harvard University, 1998
  • Speech and Language Processing. Daniel Jurafsky & James H. Martin, Stanford University, 2014
  • Linguistics 497: Corpus Linguistics. John Fry, Boise State University, 2011