Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемmodis.ispras.ru
1 N-граммы Докладчик: Федоренко Денис, 327 гр.
2 Определение Примеры прикладных задач Создание языковой модели n-грамм Подсчет вероятности n-грамм Устранение разреженности обучающего корпуса o Add-one Smoothing o Witten-Bell Discounting o Good-Turing Discounting o Katzs Backoff o Deleted Interpolation Оценка языковой модели n-грамм с помощью энтропии Содержание
3 N-грамма (англ. N-gram) подпоследовательность из N элементов некоторой последовательности. Рассмотрим последовательности слов. Юниграммы cat, dog, horse,... Биграммы little cat, big dog, strong horse,... Триграммы little cat eats, big dog barks, strong horse runs,... Определение
4 Примеры прикладных задач Распознавание речи. Некоторые различные по написанию слова произносятся одинаково. Задача выбрать в контексте правильное слово. Генерация текстов заданной тематики. Пример: Яндекс.Рефераты. Поиск семантических ошибок. He is trying to fine out - с точки зрения синтаксиса верно, с точки зрения семантики нет. He is trying to find out – верно. trying to find out встречается в английских текстах гораздо чаще, чем trying to fine out, значит при наличии статистики можно найти и устранить ошибку подобного рода
5 Создание языковой модели n- грамм Для решения перечисленных прикладных задач, нужно создать языковую модель N- грамм. Для создания модели необходимо: 1. Посчитать вероятности n-грамм в обучающем корпусе. 2. Устранить проблему разреженности корпуса с помощью одного из методов сглаживания. 3. Оценить качество полученной языковой модели n-грамм с помощью энтропии.
6 Подсчет вероятности N-грамм (1) В обучающем корпусе те или иные n- граммы встречаются с разной частотой. Для каждой n-граммы мы можем посчитать, сколько раз она встретилась в корпусе. На основе полученных данных можно построить вероятностную модель, которая затем может быть использована для оценки вероятности n-грамм в некотором тестовом корпусе.
7 Подсчет вероятности 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, …
8 Подсчет вероятности 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
9 Подсчет вероятности N-грамм (4) Для n-грамм, где n>1, вероятность считается несколько иначе. Рассмотрим случай биграмм: пусть необходимо вычислить вероятность биграммы the pool. Если рассматривать каждое слово биграммы как некоторое событие, то вероятность совокупности событий может быть вычислена по формуле: Таким образом, вероятность биграммы the pool:, где
10 Подсчет вероятности N-грамм (5) Теперь рассмотрим подсчет вероятности произвольной n- граммы (или предложения длины n). Расширяя случай биграмм, получаем формулу вероятности для n-грамм: Вычислить вероятность по такой формуле непросто, поэтому вводится упрощение – использовать историю фиксированной длины, т.е. Таким образом, вычисление вероятности предложения сводится к вычислению условной вероятности N-грамм, из которых состоит это предложение:
11 Подсчет вероятности N-грамм (6) Пример: посчитать вероятность предложения I want to eat British food.
12 Устранение разреженности корпуса (1) Проблема простой (unsmoothed) языковой модели n- грамм: у некоторых n-грамм вероятность может быть сильно занижена (либо вовсе равна нулю), хотя в действительности (в тестовом корпусе) эти n-граммы могут встречаться довольно часто. Причина: ограниченность обучающего корпуса и его специфика. Решение: за счет понижения вероятности некоторых n-грамм, повысить вероятность тех n-грамм, которые не встречались (либо встречались достаточно редко) в обучающем корпусе.
13 Устранение разреженности корпуса (2) В докладе рассмотрены следующие методы устранения разреженности: Add-One Smoothing (Laplace Smoothing) Witten-Bell Discounting Good-Turing Discounting Backoff Deleted Interpolation
14 Устранение разреженности корпуса (3) В алгоритмах устранения разреженности используются следующие понятия: Типы (types) – различные слова (последовательности слов) в тексте. Токены (tokens) – все слова (последовательности слов) в тексте. They picnicked by the pool, then lay back on the grass and looked at the stars – 14 типов, 16 токенов
15 Add-one smoothing (1) Baseline: прибавить к количеству n-грамм единицу. Тогда в случае биграмм: Ci – кол-во n-грамм типа i, N – число токенов в корпусе, V – число типов в корпусе
16 Add-one smoothing (2)
17 Add-one smoothing (3) discounting value – используется для оценки сглаживания Уменьшение в 8 раз! / =
18 Add-one smoothing (4) Метод провоцирует сильную погрешность в вычислениях (так, на предыдущем слайде было показано, что для слова Chinese кол-во биграмм сократилось в 8 раз). Тесты показали, что unsmoothed-модель часто показывает более точные результаты. Следовательно, метод интересен только с теоретической точки зрения.
19 Witten-Bell Discounting (1) Основан на простой идее: использовать данные об n- граммах, встречающихся в обучающем корпусе, для оценки вероятности отсутствующих n-грамм. Идея метода взята из алгоритмов сжатия: рассматриваются два типа событий - встретили новый символ (тип) ивстретили символ (токен). Формула вероятности для всех отсутствующих n-грамм (т.е. вероятность встретить в тестовом корпусе n-грамму, которой не было в обучающем корпусе): N – число токенов в обучающем корпусе, T – число типов, которые уже встречались в обучающем корпусе
20 Witten-Bell Discounting (2) Для случая биграмм справедливы формулы:, где
21 Witten-Bell Discounting (3) Вычисление Z (размер словаря V равен 1616):
22 Witten-Bell Discounting (4) =>=>
23 Witten-Bell Discounting (5) Discounting value (значения в таблицах округлены): / =
24 Good-Turing Discounting (1) Идея: для n-грамм, которые встретились ноль раз (с раз), оценка пропорциональна кол-ву n-грамм, встретившихся один раз (с + 1 раз). Рассмотрим пример: Пусть было поймано 18 рыб. Всего поймано разных видов – 6, причем у трех видов поймано лишь по одному представителю. Нужно найти вероятность того, что следующая рыба будет принадлежать новому виду. Всего возможных видов – 7 (6 видов уже поймано).
25 Good-Turing Discounting (2) Возможна ситуация, когда Nc=0, из-за чего становится невозможно воспользоваться формулой c* для n-грамм встречающихся с-1 и с раз. В этом случае Nc считается по формуле: a, b - параметры
26 Good-Turing Discounting (3)
27 Katzs Backoff (1) Основная идея: можно оценивать вероятности N- грамм с помощью вероятностей (N-k)-грамм (0
28 Katzs Backoff (2) Коэффициент α необходим для корректного распределения остаточной вероятности N- грамм в соответствии с распределением вероятности (N-1)-грамм. Если не вводить α, оценка будет ошибочной, т.к. не будет выполняться равенство: Вычисление α приведено в конце доклада.
29 Deleted Interpolation Оценка вероятности вычисляется как линейная комбинация вероятностей всех (N-k)-грамм (0
30 Оценка языковой модели с помощью энтропии (1) Энтропия – мера неопределенности. При помощи энтропии можно определить наиболее подходящую языковую модель N-грамм для данной прикладной задачи. Формула двоичной энтропии: Пример: посчитать энтропию испытания, заключающегося в бросании монеты. Ответ: 1 бит, при условии, что результаты опыта равновероятны (любая сторона выпадает с вероятностью 1/2).
31 Оценка языковой модели с помощью энтропии (2) Энтропия цепочек слов длины n в языке L: При подсчете энтропии всего языка L, число n (длина цепочки) стремится к бесконечности, т.е. По теореме Шеннона-Макмиллана-Бреймана, можно упростить формулу:
32 Оценка языковой модели с помощью энтропии (3) Для сравнения различных языковых моделей используется кросс-энтропия: Чем ближе значение кросс-энтропии H(p,m) к реальной энтропии H(p), тем лучше языковая модель: В нашем случае H(p) – энтропия тестового корпуса. m(w) – языковая модель (например, модель N-грамм)
33 Оценка языковой модели с помощью энтропии (4) Есть другой метод оценки качества языковой модели, основанный на т.н. показателе связности (perplexity). Идея: посчитать вероятность всего тестового корпуса. Более качественная модель покажет большую вероятность. Формула perplexity: Таким образом, чем меньше perplexity, тем лучше модель. Можно трактовать perplexity как среднее кол-во слов, которые могут идти после некоторого слова (т.е. чем больше perplexity, тем выше неоднозначность, и следовательно, тем хуже языковая модель). Связь perplexity и двоичной энтропии:
34 Оценка языковой модели с помощью энтропии (5) В качестве примера рассмотрим значения perplexity для некоторого корпуса, полученные с помощью обученных моделей юниграмм, биграмм и триграмм: В случае триграмм perplexity наименьшее, т.к. устранению неоднозначности способствует самая большая из всех моделей длина истории (равная 2) при вычислении условных вероятностей триграмм. UnigramBigramTrigram Perplexity
35 Дополнение: Формулы Katzs Backoff c* - smoothed-значение
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.