Вероятностная обработка лингвистической информации

1. Вероятностная обработка лингвистической информации

Совокупность текстов (corpora) – большая коллекция текстов,
подобная миллиардам страниц, из которых состоит World Wide Web
Задача программного обеспечения состоит в упрощении поиска нужной
информации. Предусматривается использование статистики
Применяются Вероятностные языковые модели, обучение которых
может проводиться с использованием существующих данных
Задачи, решаемые при помощи Вероятностных языковых моделей –
информационный поиск, извлечение информации, машинный перевод.
Вероятностные модели имеют ряд преимуществ. Обучение этих
моделей сводится лишь к подсчету количества вариантов. Эти модели
являются более надежными (способны принять любую строку, хотя и с
низкой вероятностью).
Такие модели могут использоваться для устранения неоднозначности,
поскольку для выбора наиболее подходящей интерпретации могут
применяться вероятностные законы.

2. Вероятностная языковая модель

позволяет определить распределение
вероятностей множества строк
Примеры таких моделей:
Однословные модели (модели однословных
сочетаний).
Двух- и трехсловные языковые модели
(применяются для распознавания речи).

3. Однословная вероятностная модель

В однословной модели каждому слову в словаре присваивается вероятность
Р(W). В этой модели предполагается, что слова выбираются независимо,
поэтому вероятность строки представляет собой произведение вероятностей
входящих в нее слов
Пi P(wi).
Рассмотрим последовательность из 20 слов, которая сформирована
случайным образом из слов книги с помощью однословной модели.
Logical are as are confusion a may right tries agent goal the was diesel more object
then information-gathering search is
В двухсловной модели каждому слову присваивается вероятность
Р(wi I wi-1).
Последовательность из слов, которая сформирована случайным образом
из слов книги с помощью двухсловной модели:
planning purely diagnostic expert systems are very similar computational approach
would be represented compactly using tic tac toe a predicate
В трехсловной модели каждому слову присваивается вероятность
Р(wi I wi-2 wi-1).
Последовательность из слов, которая сформирована случайным образом
из слов книги с помощью трехсловной модели:
planning and scheduling are integrated the success of naïve bayes model is just a
possible prior source by that time

4.

Модель трехсловных сочетаний превосходит модель двухсловных,
последняя превосходит модель однословных сочетаний как с точки
зрения качества приближенного представления текста, так и с точки
зрения успешной аппроксимации изложения темы в книге.
Использование модели n-словных сочетаний в задаче сегментации –
поиска границ между словами в тексте без пробелов. Решением этой
задачи обычно приходится заниматься при обработке текстов на
японском и китайском языках, в которых отсутствуют пробелы между
словами…
itiseasytoreadwordswithoutspaces
(1)
В данном предложении (1) можно восстановить пробелы с помощью
модели однословных сочетаний.
Для решения задачи сегментации используется алгоритм Витерби:
входные данные – распределение вероятностей однословных
сочетаний Р(word) и некоторая строка;
2
для каждой позиции i=1…n в данной строке алгоритм сохраняет в
переменной best(i) значение вероятности наиболее вероятностной
строки, которая охватывает участок от начала до позиции i
3
в переменной words(i) сохраняется слово, оканчивающееся в
позиции I, которое получило наибольшую вероятность р
наиболее приемлемая последовательность слов принимает
вид: it is easy to read words without spaces с вероятностью 10-25

5.

Сравнивая отдельные части этого предложения, можно
обнаружить, что слово easy имеет вероятность однословного
сочетания 2,6*10-4, а альтернативный вариант его прочтения e
as y имеет более низкую вероятность 9,8*10-12, несмотря на
то, что e и y часто встречаются как переменные в
уравнениях.
Аналогично – другая часть предложения:
P(without)=0,0004
P(with)=0,005
P(out)=0,0008
P(with out)=0,005*0,0008=0,000004
Слово without имеет в 100 раз большую вероятность, чем
сочетание слов with out

6. Информационный поиск

- это задача поиска документов, отвечающих потребностям пользователя
в информации.
Для систем информационного поиска (системы ИП) применяются
следующие характеристики:
1)
Определение коллекции документов. В каждой системе должно быть
принято определенное решение о том, что рассматривается в ней как
документ – отдельный абзац, страница или многостраничный текст.
2)
Способ формулировки запроса на языке запросов. Язык запросов
может предусматривать лишь список слов – AI book, или может позволять
задавать сочетание слов, которые должны быть расположены близко друг
от друга «AI book», он может содержать логические операторы, как в
запросе AI AND book, а также включать операторы, отличные от
логических, как в запросе AI NEAR book или AI book SITE: www.aaai.org
3)
Результирующий выбор. Это подмножество документов, которые
система ИП определяет как релевантные данному запросу. Под словом
релевантный подразумевается вероятно полезный для того лица, которое
сформулировало запрос.

7.

4)
Способ представления результирующего набора.
Может быть простым, как ранжированный список названий
документов. Может быть сложным, как вращающаяся цветная
карта результирующего набора, спроектированная на
трехмерное пространство.
Самые ранние системы ИП действовали на основе булевой модели
ключевых слов. Каждое слово в коллекции документов рассматривается как
булева характеристика, которая является истинной применительно к
данному документу, если соответствующее слово встречается в документе,
и ложной в противном случае. В таком случае язык запросов представляет
собой язык булевых функций, заданных на характеристиках. Документ
считается релевантным, только если соответствующее выражение
принимает истинное значение. Например, запрос информация AND поиск
принимает истинное значение, если в документе присутствуют оба слова.
Недостатки – булевы выражения непривычны для пользователей, не
являющимися программистами или логиками. Задача формулировки
подходящего запроса может оказаться достаточно сложной. Например, запрос
информация AND поиск AND модели AND оптимизация
может выдать пустой результирующий набор.
информация OR поиск OR модели OR оптимизация
возвращает слишком большой объем результатов

8.

• В этом случае необходимо вычислить значение
вероятности того, что найденные документы будут
релевантными по отношению к запросу.
Р(R=true I D, Q),
где D – документ, Q – запрос, R – булева случайная
переменная, обозначающая релевантность. После
получения этого значения можно применить принцип
ранжирования вероятностей, который указывает, что
если результирующий набор должен быть
представлен в виде упорядоченного списка, это
следует сделать в порядке уменьшения вероятности
релевантности.

9. Языковое моделирование

• В ЯМ предусматривается получение оценки
языковой модели для каждого документа, а затем
вычисление для каждого запроса вероятности этого
запроса с учетом языковой модели документа.
• Коэффициент Р(R=true I D) / Р(R=true I D) измеряет
независимую от запроса вероятность того, что
документ является релевантным.
• Таким образом этот коэффициент представляет
собой меру качества документа, некоторые
документы с большой вероятностью будут
релевантными к любому запросу, поскольку эти
документы имеют изначально высокое качество.
Применительно к статьям для академических
журналов качество можно оценивать на основании
количества упоминаний об этих статьях в других
источниках.

10. Модель мультимножества слов

• Один из широко распространенных подходов состоит в том, что
документы представляются с помощью модели однословных
сочетаний. В проблематике информационного поиска она
известна также под названием модели мультимножества
слов, поскольку в ней учитывается только частота появления
каждого слова в документе, а не их порядок.
• При использовании такой модели следующие примеры
документов рассматриваются как идентичные «man bites dog» и
«dog bites man». Очевидно, что эти документы имеют
различный смысл, но верно и то, что они являются
релевантными по отношению к запросам о собаках и укусах.
• Чтобы рассчитать вероятность запроса при наличии
релевантного документа, достаточно перемножить вероятности
слов в запросе, руководствуясь моделью однословных
сочетаний данного документа. В этом состоит наивная
байесовская модель данного запроса. Используя Qj для
обозначения j–го слова в запросе, получим
Р(Q I D, r) = П Р(Q j I D, r)

11. Cравнительный анализ систем информационного поиска

• Применяются два критерия оценки: полнота выборки и точность.
Пусть некоторая СИП выдала результирующий набор,
относящийся к одному запросу, применительно к которому
известно, какие из 100 документов являются релевантными, а
какие – нет. Результат приведен в таблице:
В результирующем
выборе
Не в результирующем
выборе
Релевантный
30
20
Нерелевантный
10
40
Показатель точности измеряет долю документов в результирующем
наборе, которые действительно являются релевантными. В данном
примере точность составляет 30/(30+10)=0,75. Относительное количество
ложных положительных оценок равно 1-0,75=0,25. Показатель полноты
выборки измеряет долю всех релевантных документов в коллекции,
которые находятся в результирующем наборе. Полнота выборки в
данном примере 30/(30+20)=0,60.

12. Cравнительный анализ систем информационного поиска

• В некоторых системах может происходить потеря точности из-за
увеличения полноты выборки. Другая крайность состоит в том,
что система может возвращать единственный документ и
показывать низкую полноту выборки, но достигать высокой
вероятности получения 100% точности.
Один из способов достижения компромисса между точностью и
полнотой выборки состоит в использовании кривой ROC (receiver
operating characteristic) «рабочая характеристика приемника» - график,
где по оси у откладывается количество ложных отрицательных оценок, по
оси х - относительное количество ложно положительных оценок.
Площадь под этой кривой представляет собой суммарную оценку
эффективности системы информационного поиска.
• Для пользователей сети важно найти ответ «немедленно». В
этом случае используется в качестве критерия средний
обратный ранг первого релевантного результата (оценка 1,
если первый документ релевантный, оценка 1/3, если третий
документ релевантный. Еще одним критерием можно
рассматривать время ожидания ответа.

13. Машинный перевод

• Машинным переводом называется автоматический
перевод текста с одного естественного языка
(исходного) на другой (целевой). Задачи:
Грубый перевод (определить смысл отрывка текста).
Перевод источников с ограниченной тематикой (система перевода
сообщений о погоде с английского на французский)
Перевод с предварительным редактированием (для перевода одного
текста на много языков, например, тиражирование инструкций).
Литературный перевод. Выходит за рамки машинного перевода!!!
• Есть системы машинного перевода, основанные на методе
передачи. В них используется база данных, состоящая из
правил перевода или примеров, а перевод осуществляется
непосредственно путем согласования текста с этими правилами
из БД.

14. Статистический машинный перевод

• В последнее десятилетие наметилась тенденция к
использованию систем машинного перевода,
основанных на статистическом анализе.
Проблему перевода английского предложения Е во французское F можно
представить в виде правила Байеса:
max P(F I E)= max P(E I F) P(F)
Это правило указывает, что следует рассмотреть все возможные
французские предложения и выбрать из них то, которое
максимизирует произведение P(E I F) P(F)
P(F) представляет собой языковую модель для французского языка. Он
указывает, насколько велика вероятность появления данного конкретного
предложения во французском тексте. Вероятность P(E I F) представляет
собой модель перевода, она указывает, насколько велика вероятность
того, что некоторое английское предложение будет использоваться в
качестве перевода, если дано определенное французское предложение.
В качестве языковой модели P(F) может использоваться любая модель,
позволяющая присвоить предложению определенное значение
вероятности.

15. ВЫВОДЫ:

• Вероятностные ЯМ, основанные на n-элементных сочетаниях,
позволяют получить значительный объем информации о языке.
В системах ИП используется очень простая ЯМ, основанная на
обработке мультимножеств слов, но даже эта модель позволяет достичь
высоких показателей полноты и точности на очень больших
совокупностях текстов.
В современных системах машинного перевода используются
статистические методы, основанные на учете частот слов.
При формировании статистической языковой системы лучше всего
опереться на модель, позволяющую эффективно использовать
имеющиеся данные, даже, если эта модель кажется чрезмерно
упрощенной.

16. Вопросы к экзамену:

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
Определение модели, моделирования. Цели моделирования
4 классификации моделей. Виды информационных моделей
Этапы моделирования
Геометрическое моделирование. Конструирование на плоскости, трехмерное
конструирование
Словесное моделирование. Пример словесной модели
Структурное моделирование. Примеры
Логические модели. Примеры. Среда реализации
Математические модели. Классификация (аналитические и имитационные,
детерминированные и стохастические). Примеры
Математические модели в планировании и управлении. Анализ данных.
Имитационное математическое моделирование. Пример
Вероятностное моделирование. Вероятностная модель и мат. Статистика
Методика статистического моделирования. Этапы
Метод Монте-Карло. Определение площади фигуры
Генерация случайных чисел. Датчик RND. Метод деления отрезка пополам. Линейный
конгруэнтный метод.
Проверка на равномерное распределение последовательности псевдослучайных чисел
критерием хи2 Пирсона.
Формула перевода случайных чисел из интервала (0,1) в интервал (а, в).
Моделирование вычисления статистической вероятности (на примере бросания монеты)
Статистическая функция СЛЧИСЛО. Пример использования
Основные способы формирования последовательности нормально распределенных
случайных величин
Перевод равномерно распределенных случайных чисел в нормальное распределение с
заданным средним и стандартным отклонением (центральная предельная теорема
закона больших чисел)

17.

21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
Перевод равномерно распределенных случайных чисел в нормальное распределение с
заданным средним и стандартным отклонением. Метод полярных координат (с
использованием функции ln(x))
Aлгоритм вычисления последовательности нормально распределенных случайных чисел
X с требуемым математическим ожиданием AM и среднеквадратичным отклонением S
Проверка последовательности нормально распределенных случайных чисел на
нормальное распределение
Вероятностные модели в лингвистике: автоматическое реферирование и аннотирование.
Выделение ключевых слов
Тематическое моделирование. Постановка задачи тематического моделирования
Тематическое моделирование. Гипотеза условной независимости. Алгоритм
Тематическое моделирование. Вероятностный латентный семантический анализ.
Алгоритм
Определение тематического дерева. Гипотеза о существовании тематического дерева
Вероятностная интерпретация отношения «тема-подтема»
Вероятностные языковые модели. Задачи сегментации. Алгоритм Витерби
Вероятностные языковые модели. n–словные вероятностные модели
Информационный поиск. Вероятность релевантности
Вероятностные языковые модели (мера качества документа)
Модель мультимножества слов. Наивная байесовская модель запроса
Cравнительный анализ систем информационного поиска. Точность и полнота выборки.
Кривая ROC
Машинный перевод. Задачи
Статистический машинный перевод. Правило Байеса