N-граммы Докладчик: Федоренко Денис, 327 гр.

Определение Примеры прикладных задач Создание языковой модели n-грамм Подсчет вероятности n-грамм Устранение разреженности обучающего корпуса o Add-one Smoothing o Witten-Bell Discounting o Good-Turing Discounting o Katzs Backoff o Deleted Interpolation Оценка языковой модели n-грамм с помощью энтропии Содержание

N-грамма (англ. N-gram) подпоследовательность из N элементов некоторой последовательности. Рассмотрим последовательности слов. Юниграммы cat, dog, horse,... Биграммы little cat, big dog, strong horse,... Триграммы little cat eats, big dog barks, strong horse runs,... Определение

Примеры прикладных задач Распознавание речи. Некоторые различные по написанию слова произносятся одинаково. Задача выбрать в контексте правильное слово. Генерация текстов заданной тематики. Пример: Яндекс.Рефераты. Поиск семантических ошибок. He is trying to fine out - с точки зрения синтаксиса верно, с точки зрения семантики нет. He is trying to find out – верно. trying to find out встречается в английских текстах гораздо чаще, чем trying to fine out, значит при наличии статистики можно найти и устранить ошибку подобного рода

Создание языковой модели n- грамм Для решения перечисленных прикладных задач, нужно создать языковую модель N- грамм. Для создания модели необходимо: 1. Посчитать вероятности n-грамм в обучающем корпусе. 2. Устранить проблему разреженности корпуса с помощью одного из методов сглаживания. 3. Оценить качество полученной языковой модели n-грамм с помощью энтропии.

Подсчет вероятности N-грамм (1) В обучающем корпусе те или иные n- граммы встречаются с разной частотой. Для каждой n-граммы мы можем посчитать, сколько раз она встретилась в корпусе. На основе полученных данных можно построить вероятностную модель, которая затем может быть использована для оценки вероятности n-грамм в некотором тестовом корпусе.

Подсчет вероятности N-грамм (2) Рассмотрим пример. Пусть корпус состоит из одного предложения: They picnicked by the pool, then lay back on the grass and looked at the stars Выделим n-граммы. Юниграммы: They, picknicked, by, … Биграммы: They picnicked, picknicked by, by the, … Триграммы They picknicked by, picknicked by the, by the pool, …

Подсчет вероятности N-грамм (3) Теперь можно посчитать n-граммы. Все выделенные би- и три- граммы встречаются в корпусе по одному разу. Все юниграммы, за исключением слова the, также встречаются единожды. Слово the встречается трижды. Теперь, когда известно, сколько раз встречается каждая n-грамма, можно построить вероятностную модель n-грамм. В случае юниграмм, вероятность слова u может быть вычислена по формуле: Например, для слова the вероятность будет равна 3/16 (т.к. в корпусе 16 слов, 3 из которых – слово the). Число вхождений слова u в обучающем корпусе They picnicked by the pool, then lay back on the grass and looked at the stars

Подсчет вероятности N-грамм (4) Для n-грамм, где n>1, вероятность считается несколько иначе. Рассмотрим случай биграмм: пусть необходимо вычислить вероятность биграммы the pool. Если рассматривать каждое слово биграммы как некоторое событие, то вероятность совокупности событий может быть вычислена по формуле: Таким образом, вероятность биграммы the pool:, где

Подсчет вероятности N-грамм (5) Теперь рассмотрим подсчет вероятности произвольной n- граммы (или предложения длины n). Расширяя случай биграмм, получаем формулу вероятности для n-грамм: Вычислить вероятность по такой формуле непросто, поэтому вводится упрощение – использовать историю фиксированной длины, т.е. Таким образом, вычисление вероятности предложения сводится к вычислению условной вероятности N-грамм, из которых состоит это предложение:

Подсчет вероятности N-грамм (6) Пример: посчитать вероятность предложения I want to eat British food.

Устранение разреженности корпуса (1) Проблема простой (unsmoothed) языковой модели n- грамм: у некоторых n-грамм вероятность может быть сильно занижена (либо вовсе равна нулю), хотя в действительности (в тестовом корпусе) эти n-граммы могут встречаться довольно часто. Причина: ограниченность обучающего корпуса и его специфика. Решение: за счет понижения вероятности некоторых n-грамм, повысить вероятность тех n-грамм, которые не встречались (либо встречались достаточно редко) в обучающем корпусе.

Устранение разреженности корпуса (2) В докладе рассмотрены следующие методы устранения разреженности: Add-One Smoothing (Laplace Smoothing) Witten-Bell Discounting Good-Turing Discounting Backoff Deleted Interpolation

Устранение разреженности корпуса (3) В алгоритмах устранения разреженности используются следующие понятия: Типы (types) – различные слова (последовательности слов) в тексте. Токены (tokens) – все слова (последовательности слов) в тексте. They picnicked by the pool, then lay back on the grass and looked at the stars – 14 типов, 16 токенов

Add-one smoothing (1) Baseline: прибавить к количеству n-грамм единицу. Тогда в случае биграмм: Ci – кол-во n-грамм типа i, N – число токенов в корпусе, V – число типов в корпусе

Add-one smoothing (2)

Add-one smoothing (3) discounting value – используется для оценки сглаживания Уменьшение в 8 раз! / =

Add-one smoothing (4) Метод провоцирует сильную погрешность в вычислениях (так, на предыдущем слайде было показано, что для слова Chinese кол-во биграмм сократилось в 8 раз). Тесты показали, что unsmoothed-модель часто показывает более точные результаты. Следовательно, метод интересен только с теоретической точки зрения.

Witten-Bell Discounting (1) Основан на простой идее: использовать данные об n- граммах, встречающихся в обучающем корпусе, для оценки вероятности отсутствующих n-грамм. Идея метода взята из алгоритмов сжатия: рассматриваются два типа событий - встретили новый символ (тип) ивстретили символ (токен). Формула вероятности для всех отсутствующих n-грамм (т.е. вероятность встретить в тестовом корпусе n-грамму, которой не было в обучающем корпусе): N – число токенов в обучающем корпусе, T – число типов, которые уже встречались в обучающем корпусе

Witten-Bell Discounting (2) Для случая биграмм справедливы формулы:, где

Witten-Bell Discounting (3) Вычисление Z (размер словаря V равен 1616):

Witten-Bell Discounting (4) =>=>

Witten-Bell Discounting (5) Discounting value (значения в таблицах округлены): / =

Good-Turing Discounting (1) Идея: для n-грамм, которые встретились ноль раз (с раз), оценка пропорциональна кол-ву n-грамм, встретившихся один раз (с + 1 раз). Рассмотрим пример: Пусть было поймано 18 рыб. Всего поймано разных видов – 6, причем у трех видов поймано лишь по одному представителю. Нужно найти вероятность того, что следующая рыба будет принадлежать новому виду. Всего возможных видов – 7 (6 видов уже поймано).

Good-Turing Discounting (2) Возможна ситуация, когда Nc=0, из-за чего становится невозможно воспользоваться формулой c* для n-грамм встречающихся с-1 и с раз. В этом случае Nc считается по формуле: a, b - параметры

Good-Turing Discounting (3)

Katzs Backoff (1) Основная идея: можно оценивать вероятности N- грамм с помощью вероятностей (N-k)-грамм (0

Katzs Backoff (2) Коэффициент α необходим для корректного распределения остаточной вероятности N- грамм в соответствии с распределением вероятности (N-1)-грамм. Если не вводить α, оценка будет ошибочной, т.к. не будет выполняться равенство: Вычисление α приведено в конце доклада.

Deleted Interpolation Оценка вероятности вычисляется как линейная комбинация вероятностей всех (N-k)-грамм (0

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

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

Оценка языковой модели с помощью энтропии (3) Для сравнения различных языковых моделей используется кросс-энтропия: Чем ближе значение кросс-энтропии H(p,m) к реальной энтропии H(p), тем лучше языковая модель: В нашем случае H(p) – энтропия тестового корпуса. m(w) – языковая модель (например, модель N-грамм)

Оценка языковой модели с помощью энтропии (4) Есть другой метод оценки качества языковой модели, основанный на т.н. показателе связности (perplexity). Идея: посчитать вероятность всего тестового корпуса. Более качественная модель покажет большую вероятность. Формула perplexity: Таким образом, чем меньше perplexity, тем лучше модель. Можно трактовать perplexity как среднее кол-во слов, которые могут идти после некоторого слова (т.е. чем больше perplexity, тем выше неоднозначность, и следовательно, тем хуже языковая модель). Связь perplexity и двоичной энтропии:

Оценка языковой модели с помощью энтропии (5) В качестве примера рассмотрим значения perplexity для некоторого корпуса, полученные с помощью обученных моделей юниграмм, биграмм и триграмм: В случае триграмм perplexity наименьшее, т.к. устранению неоднозначности способствует самая большая из всех моделей длина истории (равная 2) при вычислении условных вероятностей триграмм. UnigramBigramTrigram Perplexity

Дополнение: Формулы Katzs Backoff c* - smoothed-значение