Введение в языковые модели и Markov Chain (цепь Маркова)
N-граммы
N-граммы – это статистические модели, которые предсказывают следующее слово после N-1 слов на основе вероятности их сочетания. Например, сочетание I want to в английском языке имеет высокую вероятностью, а want I to – низкую. Говоря простым языком, N-грамма – это последовательность n слов. Например, биграммы – это последовательности из двух слов (I want, want to, to, go, go to, to the…), триграммы – последовательности из трех слов (I want to, want to go, to go to…) и так далее.
Такие распределения вероятностей имеют широкое применение в машинном переводе, автоматической проверке орфографии, распознавании речи и умном вводе. Например, при распознавании речи, по сравнению с фразой eyes awe of an, последовательность I saw a van будет иметь большую вероятность. Во всех этих случаях мы подсчитываем вероятность следующего слова или последовательности слов. Такие подсчеты называются языковыми моделями.
Как же рассчитать P(w)? Например, вероятность предложения P(I, found, two, pounds, in, the, library). Для этого нам понадобится цепное правило, которое определяется так:
Таким образом, мы можем оценить совместную вероятность всей цепочки, перемножив условные вероятности. Однако мы не можем рассчитать точную вероятность слова при условии длинной последовательности предшествующих слов, как в этом примере:
Это потому, что возможных последовательностей очень много, а в наших данных просто может не оказаться этих выражений. Поэтому, вместо того, чтобы рассчитывать вероятность слова с учетом всех предшествующих слов, мы можем аппроксимировать вероятность, упростив ее. В этом заключается смысл цепей Маркова, с помощью которых мы можем предсказать вероятность элемента последовательности, не учитывая слишком широкий контекст.
Например, марковская модель первого порядка:
Допустим, у нас есть следующие предложения для обучения моделей:
Используя марковскую цепь первого порядка можно легко посчитать вероятность выражения you found:
Таким образом мы можем рассчитывать биграммы, триграммы, квадрограммы и т.д., причем чем длиннее цепь, тем более детализированной является наша модель, т.е. более длинные предложения включают больше грамматики, чем короткие. В то же время, чем длиннее цепь, тем меньше у нас случаев употребления, а это значит что многие наблюдения будут попадаться всего один раз.
Стоит отметить, что языковые модели – не всегда идеальное решение. Возьмем, к примеру, следующее предложение:
В этом случае маловероятно, что approved относится к month, хоть они и расположены близко, и более вероятно – к request, однако n-граммы эту связь не обнаруживают.
Оценка вероятностей n-грамм
Самый простой и интуитивно понятный способ оценки вероятностей – это метод максимального правдоподобия (Maximum Likelihood Estimate, или MLE).
Вот пример расчета MLE:
Рассчитаем вероятности нескольких биграмм:
Примечательно, что, исходя из нашего маленького корпуса, получается, что после right всегда будет следовать now.
Возьмем больший корпус, состоящий из 9222 предложений. Ниже представлен образец подсчета биграмм, из которого видно, что, например, eat встречается после to 686 раз.
У нас также имеется информация о количестве употреблений каждого из этих слов:
Исходя из этих данных, можно подсчитать вероятности биграмм:
Поскольку это значение крайне мало, мы можем столкнуться с проблемой потери значимости при операциях с плавающей точкой. Поэтому на практике используются логарифмы, при этом логарифм произведения равен сумме логарифмов:
Использование шкалы логарифмов приводит к появлению в наших расчетах отрицательных чисел, но наша основная задача – сделать так, чтобы эти числа были сопоставимы. На данных примерах сразу видно, что первое предложение гораздо более вероятно, чем второе.
Коллекции n-грамм
Самой полной коллекцией n-грамм на английском языке на данный момент является Google N-grams, содержащий частоты для более одного триллиона токенов. Данные собирались из текстов общедоступных веб-страниц. Несмотря на объем, у ресурса есть недостаток – цена в 150 долларов.
Но есть и бесплатная альтернатива, а именно Google Books N-grams – ресурс, созданный на основе наиболее полного корпуса англоязычных книг, собранного Google.