1. Некоторые замечания о методах nlp, ir и Data Mining




Скачать 173.28 Kb.
Дата02.08.2016
Размер173.28 Kb.

-1. Некоторые замечания о методах NLP, IR и Data Mining


Алгоритмы самообучения (методы распознавания образов):

  • Модель языка (скрытые марковские модели)

  • Энтропийные модели

  • Кластеризация

  • Классификация

  • Машинные методы обучения для построения классификатора (метод максимальной энтропии, наивная байесовская классификация, скрытые марковские модели и т.п.)

Методы разрешения семантической неоднозначности

Статистические методы построения таксономии

  1. Предварительная постановка задачи


Проблема 1: омонимия и многозначность при автоматической обработке текста

Проблема 2.: группировка лексики, автоматическое создание нужных лексикографических ресурсов, например, тезаурусов.

Семантическая неоднозначность (технический термин - семантическая многозначность):

Bank vs. bank (см. предыдущую лекцию)

Он нашел возможность vs. Он нашел квартиру

Язык: естественный язык vs. Говяжий язык

Используется в:

(а) семантическая разметка корпусов

(б) прикладные задачи информационного поиска: простой поиск по запросу пользователя, автоматическая классификация текстов

(в) автоматические системы перевода

(г) вопросно-ответные системы

(д) извлечение знаний из текстов (омонимия именованных сущностей NER) и т.п.

WSD — word sense disambiguation

2001 г. - мировое первенство систем автоматического разрешения неоднозначности значений слов Senseval-2[1], в котором участвовали 94 системы, созданные в 35 различных научных организациях. Соревнование проводилось на текстах на 12 языках (английский, баскский, голландский, датский, испанский, итальянский, китайский, корейский, чешский, шведский, эстонский, японский). Значения слов брались из соответствующих вариантов словаря WordNet, что позволяло сравнивать результаты, полученные различными системами, несмотря на то, что версии этого словаря для всех языков, кроме английского, оставляют желать лучшего.


  • Существуют два основных подхода:

    • основанный на статистике

    • основанный на знаниях.

На данном этапе преобладающим является подход, основанный на статистике, т.е. использующий исключительно статистические методы работы с корпусом текстов, без привлечения дополнительных источников информации о языке (Manning and Shutze, 1999; Jurafsky and Martin, 2000). К широко применяемым методам относятся, например, байесовские классификаторы, метод разделяющего вектора (support vector machine) и другие чисто статистические методы.

  • На какие вопросы надо ответить, чтобы решить задачу

  • На что опираться, чтобы различить разные смыслы лексемы в тексте

    1. Лингвистические основания

Значения: словари, тезаурусы, WordNet

Источники:

(а) значение в словаре

(б) тезаурусный класс

(в) синонимический ряд в словаре синонимов

(г) synset в WordNet

(д) Wikipedia


  • класс контекстных слов ((а) – (г) источники для выделения класса контекстных слов)

  • задача для каждого из "значений" определить "класс эквивалентности"

    1. Вопрос о признаковой базе

    2. Алгоритмы самообучения

Задача: найти множество признаков контекста, которые бы максимально точно определяли данное значение слова (значение X в контексте С (с1 …. ст) было бы максимально вероятно)

Можно приписать в лексикографическом источнике

Можно извлечь в процессе самообучения:

(а) из размеченного корпуса (supervised learning)

(б) из неразмеченного корпуса (unsupervised)


  • Классификатор

  • Кластеризация для контекстов

  • Выбор признаков (все, что только можно)

    • Контекстные слова

    • Контестные POS тэги

    • Место контекстного слова

Задачи обучения:

  • Дано: "мешок" признаков

  • Выход: максимально "близкая" к действительности модель (такие параметры модели, которые бы давали максимальную вероятность того, что данная модель порождает то, что мы наблюдаем) – веса параметров, правила классификации и т.п.

Примеры признакового множества:

Supervised: размеченный корпус, автоматически извлекаются признаки (POS, коллокации), по размеченному корпусу строится классификатор (см. ниже)


  1. Методы, основанные на знаниях (knowledge-based methods)

    1. Методы контекстного пересечения


Ср. Стадартные методы выделения коллокаций

См. предыдущую лекцию

t-сатистика, взаимная информация, loglikelihood

Списки контекстных лексем, максимально "дифференцирующих" смыслы




    1. Система Леска


М.Леском (Lesk 1988). В качестве корпуса он использовал толкования из словаря для получения исходных данных для своей системы. Предположим, что мы хотим определить значение слова ash 'пепел; ясень' в следующем предложении (см. Диссертация Б.Кобрицова):


    1. Расширение толкований по методу Уилкса


Й.Уилкса (Wilks et all. 1990): метод "расширения" словарных толкований.

Для каждого слова W берется его словарное толкование (которое является некоторым предложением на метаязыке словаря), затем из него вычеркиваются все семантически нерелевантные слова (предлоги, союзы и т.п.) – в результате получается множество метаслов {w1,..,wn}. После этого такое множество метаслов сравнивается с толкованиями других слов: если слово wi из толкования рассматриваемого слова W присутствует в нескольких других толкованиях вместе с метасловом vj, то (основываясь на допущении выше, о семантическом родстве вместе встречающихся слов) алгоритм устанавливает дополнительную связь между словом W и vj. Таким образом, помимо семантической связи между W и wi, которая устанавливается из-за того, что wi присутствует в толковании рассматриваемого слова W, устанавливается еще и связь между W и vj, именно так и происходит "расширение" толкования. Итак, к исходному набору метаслов {w1,..wn} из толкования рассматриваемой лексемы добавляется новое слово vj. По окончании работы для рассматриваемого слова WN образуется семантическая сеть, связи в которой отражают некоторую степень семантического родства. В отличие от описанного выше метода Леска такой подход позволяет использовать не только данные толкований слов, но и другую информацию из словаря, что позволяет значительно увеличить исходный набор свидетельств, на основе которых осуществляется выбор правильного значения.

Для своей системы в качестве эталона Уилкс выбрал словарь Longmans Dictionary of Contemporary English (Longman 1988) (LDOCE), которой использовал для расширения толкований рассматриваемых слов. Этот словарь предназначен для людей, для которых английский является вторым языком, поэтому в его толкованиях применяется упрощенный словарь из порядка 2000 слов. Уилкс обнаружил, что при использовании толкований из этого словаря значительно возрастает число встречающихся вместе слов. А это, в свою очередь, существенно расширяет возможности расширения толкований. Преимущество этого словаря еще и в том, что в нем содержится гораздо меньше синонимов, что в противном случае создало бы серьезные проблемы при подсчете вместе встречающихся слов.

ТОЧНОСТЬ ТАКИХ СИСТЕМ – 50% - 70%

1.4.





  1. Классификационные методы





    1. Пример. Байесовская классификация. Математические основания

Наи́вный ба́йесовский классифика́тор — простой вероятностный классификатор, основанный на применении Теоремы Байеса со строгими (наивными) предположениями о независимости.

Абстрактно, вероятностная модель для классификатора — это условная модель



над зависимой переменной класса C с малым количеством результатов или классов, зависимая от нескольких переменных F1Fn. Проблема заключается в том, что когда количество свойств n очень велико или когда свойство может принимать большое количество значений, тогда строить такую модель на вероятностных таблицах становится невозможно. Поэтому мы переформулируем модель, чтобы сделать ее легко поддающейся обработке.

Используя теорему Байеса, запишем

На практике мы заинтересованы лишь в числителе этой дроби, так как знаменатель не зависит от C и значения свойств Fi даны, так что знаменатель — константа.

Числитель эквивалентен совместной вероятности модели

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











и т. д. Теперь начинаем использовать «наивные» предположения условной независимости: предположим, что каждое свойство Fi условно независимо от любого другого свойства Fj при . Это означает



таким образом, совместная модель может быть выражена как





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



где Z — это масштабный множитель, зависящий только от , то есть константа, если значения переменных известны.


Оценка параметров


Все параметры модели могут быть аппроксимированы относительными частотами из набора данных обучения. Это оценки максимального правдоподобия вероятностей. Не дискретные свойства должны быть сначала дискретизированы.

Если данный класс и значений свойства никогда не встречаются вместе в наборе обучения, тогда оценка, основанная на вероятностях, будет равна нулю. Это проблема, так как при перемножении нулевая оценка приведет к потере информации о других вероятностях. Поэтому предпочтительно проводить небольшие поправки во все оценки вероятностей так, чтобы никакая вероятность не была строго равна нулю.


Построение классификатора по вероятностной модели


Наивный байесовский классификатор объединяет модель с правилом решения. Одно общее правило должно выбрать наиболее вероятную гипотезу; оно известно как апостериорное правило принятия решения (MAP). Соответствующий классификатор — это функция classify, определённая следующим образом:


Пример: классификация документов


Рассморим пример применения наивной байесовской классификации к задаче классификации документов. Рассмотрим задачу классификации документов по их содержимому, например в спам и не-спам E-Mail. Будем считать, что документы выбраны из нескольких классов документов, которые могут быть представлены множеством слов с (независимой) вероятностью, что i-ое слово данного документа встречается в документе класса C:

(Для этой задачи предположим, что вероятность встречи слова в документе независима от длины документа и все документы имеют одинаковую длину.)

Тогда вероятность для данного документа D и класса C

Вопрос, на который мы хотим ответить: «какова вероятность того, что данный документ D принадлежит классу C?» Другими словами, чему равна ?

По определению, (см. Аксиома вероятности)



Байесовская теорема манипулирует этим в терминах подобия.



Предположим, что мы имеем только два класса: S и ¬S (напр. спам и не-спам).



и

Используя байесовский результат выше, мы можем написать:



Разделив один на другой, будем иметь:



Можно переписать как:



Итак, вероятность p(S | D) / p(¬S | D) может быть выражена в терминах последовательности степени правдопобия.

Действительная вероятность p(S | D) может быть просто посчитана из ln(p(S | D) / p(¬S | D)) основываясь на наблюдении, что p(S | D) + p(¬S | D) = 1.

Взяв логарифм всех этих степеней, имеем:



(Этот метод «степеней логарифмического правдопобия» — часто встречающийся метод в статистике.)

Наконец, документ может быть классифицирован следующим образом. Это спам, если , иначе это не спам.


    1. WSD

(см. презентацию http://yury.name/internet/#seminar Семинар Юрия Лифшица, авторы: Александр Котов, Николай Красильников)



    1. Математические основы

Кластеризация – это автоматическое разбиение элементов некоторого множества (объекты, данные, вектора характеристик) на группы (кластеры) по принципу схожести.

  • Цель кластеризации – построить оптимальное разбиение объектов на группы:

      • разбить N объектов на k кластеров;

      • просто разбить N объектов на кластеры.




    1. Пример 1. Иерархическая кластеризация с использованием корреляционной матрицы

Апресян Ю.Д.. Семантическая классификация глаголов в зависимости от модели управления







Gen

Acc

Ins

"о"+Prep-l

Acc, от+Gen

Acc, для+Gen

Acc, из+Gen

Acc, в+Prep-l

1

беседовать

0

0

0,82

0,18

0

0

0

0

2

бояться

0,29

0

0

0

0

0

0

0

3

ждать

0,24

0,33

0

0

0,02

0

0

0

4

изменить

0

0,86

0

0

0

0

0

0,14

5

испугаться

0,1

0

0

0

0

0

0

0

6

наладить

0

0,8

0

0

0

0

0

0,1

7

ожидать

0,27

0,48

0

0

0,03

0

0

0

8

построить

0

0,88

0

0

0

0,07

0

0

9

производить

0

0,88

0

0

0

0,04

0

0

10

разговаривать

0

0

0,54

0,08

0

0

0

0

11

создавать

0

0.9

0

0

0

0

0,03

0

Сила управления: условная вероятность того, что в тексте появится данная форма или совокупность данных форм, при условии, что появился данный глагол

Расстояние между глаголами:











беседо-

вать


боять-

ся


ждать

изме-

нить


испу-

гаться


нала-

дить


ожи-

дать


постро-

ить


произ-

водить


разго

варивать


созда-

вать


1

беседо-

вать


0

1,29

1,62

2

1,1

1,9

1,78

1,95

1,92

0,38

1,93

2

бояться




0

0,43

1,29

0,19

0,19

0,53

1,24

1,21

0,91

1,22

3

Ждать







0

0,9

0,52

0,8

0,16

0,85

0,82

1,24

0,83

4

изменить










0

1,1

0,1

0,82

0,23

0,2

1,62

0,21

5

испугаться













0

1

0,68

1,05

1,02

0,72

1,03

6

наладить
















0

0,72

0,25

0,22

1,52

0,23

7

ожидать



















0

0,77

0,74

1,4

0,75

8

построить






















0

0,03

1,57

0,12

9

произ-

водить


























0

1,54

0,09

10

разгова-

ривать





























0

1,55

11

созда-

вать
































0

  1. Выбираем два наиболее удаленных друг от друга элемента - задаем 2 разных класса

Условие: выбранные элементы не должны относиться к одному классу

  1. Добавляем по одному элементу - добавляем тот глагол, который находится на минимальном расстоянии от какого-то уже выделенного элемента одного из формирующихся классов

  2. Проверяем, не нарушено ли условие (1)

  3. Нарушитель задает новый класс

  4. Если образование нового класса не вызывает нарушения первого условия ни для одного из уже выделенных элементов - то 2, если нарушение имеет место - нарушители извлекаются из уже построенных классов и возвращаются в число нерасклассифицированных элементов. Это продолжается, пока нарушение не будет ликвидирован.



База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница