Морфологическая разметка (3). Автоматический морфологический анализ Введение Введение Примеры Примеры Проблемы и задачи Проблемы и задачи Основные этапы. - презентация

1 Морфологическая разметка (3)

2 Автоматический морфологический анализ Введение Введение Примеры Примеры Проблемы и задачи Проблемы и задачи Основные этапы Основные этапы Основные методы Основные методы Алгоритмические методы Алгоритмические методы Технологии с самообучением Технологии с самообучением

3 Омонимия Пример: Омонимия Пример: грамматическая внутриглагольная омонимия Выявленные типы омоформ Отношен ие «сло­ варные // текс­товые омонимы» (к-во слов) Из них омогра фы (к-во слов) К-во упот - ребл. 1-е значение (к-во употр. / сло в), его статус 2-е значение. (к-во употр / слов), его статус 1) 1 л. мн. буд. вр. // причаст. кратк. стр. наст. мужск. р. (Мы любим // Он любим) 206/ / 200 ведущее 11 / 9 возможное 2) 2 л. мн. изъявит. / / 2 л. мн. пов. (Если вы ходите… // Не хо­ди­те туда) 159/ / 73 возможное 255 / 108 возможное 3) 3 л. мн. буд. вр. // прич. с трад. кратк. мужск. р. (Они тронут // он тронут) 9/ / 5 возможное 9 / 5 возможное 4) 2 л. ед. пов. // 2 л. ед. нас т. (Давай ешь! Ты еще ешь?) 1/ абсолютное 5) Инфинитив // 2 л. ед. по в. (перестал расти // Скорей расти! ) 6/ ведущее 3 возможное

4 Омонимия Из данной таблицы видно, что рассматриваемый тип омонимии представлен 5-ю случаями, наиболее важны­ми и частотными из которых являются первые два (см. табл.). Можно говорить о том, что они носят регулярный характер. Количественно эта зона омонимии представлена 381 словоформами – словарными омонимами. Однако в зву­ чащей речи она сужается до 269 единиц (см. число омографов). Текстовыми омонимами при этом являются толь­ко 28 словоформ, для которых в корпусе действительно зафиксировано наличие разных значений. Таким образом, текстовая омонимия в этой зоне во много раз уже, чем словарная, потенциальная, что существенно облегчает возможность автоматического разрешения омонимии.

5 Омонимия С точки зрения семантической центральным для этой зоны является совпадение форм повелительного наклонения с другими формами (см. 2, 4, 5). Однако большой процент омографов (100 словоформ из 166) показывает, что в звучащей речи зона омонимии повелительного на­клонения намного меньше и что грамматическая роль ударения в выражении значения повелительного наклонения в русском языке действительно очень велика.

6 Омонимия Порядок тэгаЧастотаДоля в процентах Однозначный ,34 Двузначный ,12 Трехзначный ,13 Четырехзначный658 3,33 Пятизначный756 3,82 Шестизначный232 1,17 Остальные613 3,1 Всего Потенциальная омонимия

7 Омонимия Порядок тэгаЧастотаДоля в процентах Однозначный ,38 Двузначный ,31 Трехзначный ,65 Четырехзначный603 0,45 Пятизначный162 0,12 Шестизначный75 0,06 Остальные51 0,04 Всего Реальная омонимия Как мы видим, доля абсолютно однозначных тэгов в языке по данным анализируемых текстов составляет 54,34%, т.е. если бы мы просто приписывали тэги только словам, имеющим один вариант разбора, 45,66% слов в тексте остались бы неразмеченными.

8 Технологии морфологического анализа с самообучением

9 1994 г.: Массачусетский технологический институт, Э.Брилл Обучение начинается с присвоения каждому слову в обучающей выборке наиболее частотного для данной словоформы (только одного!) тега. Сравнение с правильной разметкой. Формулируются правила, которые дают наилучший результат. Действие правила – изменение приписанного тега. Несколько итераций, пока будет достигнут запланированный эффект (полное отсутствие улучшений, запланированная степень близости к правильной разметке, запланированное максимальное число правил) Правила двух видов: лексические и контекстные. Алгоритмы, основанные на правилах Алгоритм Э.Брилла с управляемым обучением

10 Для вывода правил: Для вывода правил: для части тренингового корпуса производится первоначальная разметка (наиболее вероятная без контекста) для части тренингового корпуса производится первоначальная разметка (наиболее вероятная без контекста) сравнивается правильная разметка с той, которая получилась сравнивается правильная разметка с той, которая получилась для каждой ошибки устанавливается, какой набор пэтчей приводит к максимальному сокращению ошибки. для каждой ошибки устанавливается, какой набор пэтчей приводит к максимальному сокращению ошибки. Пример типов пэтчей: Пример типов пэтчей: поменяй А на В, если предыдущее слово имеет тэг С поменяй А на В, если предыдущее слово имеет тэг С Пример пэтча: Пример пэтча: TO IN NEXT-TAG AT TO IN NEXT-TAG AT VBN VBD PREV-WORD-IS-CAP YES VBN VBD PREV-WORD-IS-CAP YES Алгоритмы, основанные на правилах Алгоритм Э.Брилла с управляемым обучением

11 Rule-based taggers Для вывода правил: Для вывода правил: для части тренингового корпуса производится первоначальная разметка (наиболее вероятная без контекста) для части тренингового корпуса производится первоначальная разметка (наиболее вероятная без контекста) сравнивается правильная разметка с той, которая получилась сравнивается правильная разметка с той, которая получилась для каждой ошибки устанавливается, какой набор пэтчей приводит к максимальному сокращению ошибки. для каждой ошибки устанавливается, какой набор пэтчей приводит к максимальному сокращению ошибки. Пример типов пэтчей: Пример типов пэтчей: поменяй А на В, если предыдущее слово имеет тэг С поменяй А на В, если предыдущее слово имеет тэг С Пример пэтча: Пример пэтча: TO IN NEXT-TAG AT TO IN NEXT-TAG AT VBN VBD PREV-WORD-IS-CAP YES VBN VBD PREV-WORD-IS-CAP YES

12 Контекстные правила Примеры условий: предыдущая/следующая словоформа (на расстоянии одна, две или три словоформы) маркирована тегом Z предыдущая/следующая пара словоформ маркирована тегами Y Z предыдущая/следующая словоформа (на расстоянии 1 или 2 словоформы) есть w текущая словоформа есть w, предыдущая/следующая словоформа есть w текущая словоформа есть w, предыдущая/следующая словоформа маркирована тегом Z Примеры контекстных правил (что меняем – на что меняем – условие): NN VB PREVTAG TO[усл.: предыд. тег] VB VBP PREVTAG PRP[усл.: предыд. тег] VBD VBN PREV1OR2TAG VBD[усл.: предыд. или предпред. тег] VBN VBD PREVTAG PRP[усл.: предыд. тег] NN VB PREV1OR2TAG MD[усл.: предыд. тег] VB VBP PREVTAG NNS[усл.: предыд. тег] Алгоритмы, основанные на правилах Алгоритм Э.Брилла с управляемым обучением

13 1996 г. Используются корпус текстов, не содержащий предварительной разметки, и словарь. Происходит предварительная разметка текста в соответствии со словарем, с указанием всех вариантов. Thecanwillrust DTMD NN VB MD NN VB NN VB Возможные маркировки предложения "The can will rust" («Консервная банка заржавеет») Алгоритмы, основанные на правилах Алгоритм Э.Брилла с неуправляемым обучением

14 Анализируя корпус текстов при помощи словаря, мы можем обнаружить, что из всех слов, которые встречаются после слова "the" (и для которых в словаре указан только один возможный тэг), чаще всего встречаются слова с тэгом NN. Исходя из этого, мы можем сформулировать следующее правило: Заменять тег MD_NN_VB (т.е. сохраняющий три варианта разметки) на NN после слова "the" Таким образом: Первичная маркировка дает неоднозначно маркированный текст Затем выводятся правила вида: Заменить тег χ на тег Y в контексте C, где χ является последовательностью из двух или более тегов, а Y – один тег, такой что Y χ. Алгоритмы, основанные на правилах Алгоритм Э.Брилла с неуправляемым обучением

15 Шаблоны выводимых правил: Заменить тэг χ на тэг Y, если... предшествующая словоформа маркирована тэгом Z предшествующая словоформа есть W последующая словоформа маркирована тэгом Z последующая словоформа есть W Алгоритмы, основанные на правилах Алгоритм Э.Брилла с неуправляемым обучением

16 Стохастические парсеры Leech et al, Jelinek, Deroualt and Merialdo, Church, DeRose, Kupiec, Ayuso et al, etc. Leech et al, Jelinek, Deroualt and Merialdo, Church, DeRose, Kupiec, Ayuso et al, etc % на слово 95-99% на слово Если игнорировать контекст и приписывать максимально вероятные тэги – 90% Если игнорировать контекст и приписывать максимально вероятные тэги – 90% лексическая вероятность (вероятность тэга Х при условии, что мы имеем дело с лексемой У) лексическая вероятность (вероятность тэга Х при условии, что мы имеем дело с лексемой У) контекстная вероятность контекстная вероятность

17 Стохастические парсеры Детерминистические парсеры не учитывают лексических особенностей, например, частота saw как существительного 4 раза на весь Брауновский корпус, а как глагола – 337 раз (в 100 раз) ср. русский для, уж, и

18 Омонимия При статистической оценке тегов в 6 млн. корпусе со снятой омонимией - в словаре содержится 88,38% однозначных тэгов, что говорит о том, что уровень реальной омонимии значительно ниже потенциального и еще раз подтверждает тот тезис, что несмотря на наличие у словоформы нескольких потенциальных разборов, один из них является наиболее частотным. Поэтому если при подсчете потенциальной омонимии учитываются даже самые редкие варианты, то при подсчете реальной омонимии они могут зачастую не браться в расчет, поскольку не появились в тренировочном корпусе в силу своей низкочастотности. По этой же причине уменьшается доля многозначных тэгов (для двухзначных – в 2,6 раза, для трехзначных – в 6 раз и далее по возрастанию) в реальной омонимии по сравнению с потенциальной.

19 Стохастические парсеры Детерминистические парсеры не учитывают лексических особенностей, например, частота saw как существительного 4 раза на весь Брауновский корпус, а как глагола – 337 раз (в 100 раз) Детерминистические парсеры не учитывают лексических особенностей, например, частота saw как существительного 4 раза на весь Брауновский корпус, а как глагола – 337 раз (в 100 раз) I see a bird I see a bird I pronoun/noun seeverb/noun (The Holy See) aarticle/noun birdnoun/verb I/noun see/noun a/noun bird/V ср. sity school committee meeting

20 I see a bird I pronoun/noun seeverb/noun (The Holy See) aarticle/noun birdnoun/verb I/noun see/noun a/noun bird/V ср. sity school committee meeting Морфологическая разметка. Технологии Проблемы детерминистических парсеров

21 Стохастические парсеры Марковская модель Большинство вероятностно-статистических алгоритмов [Linda Van Guilder, 1995] использует два источника информации: 1. Словарь словоформ языка, в котором каждой словоформе соответствует множество возможных тэгов (морфологических разборов) 2. Информацию о встречаемости всех возможных последовательностей тэгов (например, информацию о частоте триграм - всех возможных последовательностях из трех грамматических тэгов

22 Морфологическая разметка. Технологии Марковская модель Условная вероятность: P(e | e') = P(e & e') / P(e') P(сущ | прил) = P(сущ & прил) / P(прил)

23 Морфологическая разметка. Технологии Марковская модель Марковская модель включает некоторый набор состояний, путей перехода между этими состояниями и вероятностей этих путей. Целью является получение максимально вероятного пути, который, если модель корректна, соответствует правильно приписанным аннотациям.

24 СКРЫТЫЕ МАРКОВСКИЕ МОДЕЛИ КАК МЕТОД СНЯТИЯ ОМОНИМИИ (1) Предположения о марковском характере зависимости (модель первого порядка): - встречаемость каждого тега в определенном месте цепочки зависит только от предыдущего тега; - то, какое слово находится в том или ином месте цепочки, полностью определяется тегом (а не, допустим, соседними словами). Таким образом, порождение правильно построенной цепочки тегов уподобляется действию конечного автомата, где дуги помечены тегами с приписанными им вероятностями, а слова – это наблюдаемые реализации тегов. Состояния определяются парой «текущий тег + предыдущий тег»

25 СКРЫТЫЕ МАРКОВСКИЕ МОДЕЛИ КАК МЕТОД СНЯТИЯ ОМОНИМИИ (2)

26 Морфологическая разметка. Технологии Марковская модель Для английского языка в такой модели выделяются примерно 50 состояний.

27 Условная вероятность: Условная вероятность: PROB(e | e') = PROB(e & e') / PROB(e') PROB(e | e') = PROB(e & e') / PROB(e') PROB(noun | det) = PROB(det & noun) / PROB(det) PROB(noun | det) = PROB(det & noun) / PROB(det) PROB(Cat i = noun | Cat i-1 = det) Count(det at position i-1 and noun at i) / Count(det at position i-1) PROB(Cat i = noun | Cat i-1 = det) Count(det at position i-1 and noun at i) / Count(det at position i-1) PROB(Cat i = noun | Cat i-1 = det) Count(det at position i-1 and noun at i) / (Count(det at position i-1) * Count(noun at position i)) PROB(Cat i = noun | Cat i-1 = det) Count(det at position i-1 and noun at i) / (Count(det at position i-1) * Count(noun at position i)) Морфологическая разметка. Марковская модель

28 Морфологическая разметка. Технологии Марковская модель 1. Словарь словоформ языка, в котором каждой словоформе соответствует множество лексико-грамматических классов, которые могут иметься у данной словоформы: Например, для словоформы кругом в словаре указано, что она может быть наречием, существительным и предлогом Кругом - Н раз в корпусе Кругом – ПРЕДЛ - 2 раза в корпусе Кругом - С - 2 раза в корпусе

29 (1) частота встречаемости относительно других лексико- грамматических классов данной словоформы. Частота обычно подсчитывается на корпусе текстов, в котором предварительно вручную каждому слову приведен в соответствие лексико-грамматический класс. Таким образом, словоформа well в словаре будет представлена следующим образом: wellnoun4 occurences in corpus welladverb1567occurences in corpus welladjective6 occurences in corpus wellinterjection1occurences in corpus

30 Морфологическая разметка. Технологии Марковская модель 2. Информация о встречаемости всех возможных последовательностей лексико-грамматических классов (например, информацию о частоте триграм - всех возможных последовательностях из трех грамматических тэгов 2. Информация о встречаемости всех возможных последовательностей лексико-грамматических классов (например, информацию о частоте триграм - всех возможных последовательностях из трех грамматических тэгов неопр.артикль + сущ.ед.ч occurences in corpus неопр.артикль + сущ.мн.ч 7494 occurences in corpusопр. артикль + сущ.ед.ч occurences in corpus неопр.артикль + сущ.мн.ч 47 occurences in corpus неопр.артикль + глагол 3 л., ед.ч 0 occurences in corpus

31 Если известна наблюдаемая реализация цепочки тегов (т.е. предложение как цепочка слов), то предстоит найти наиболее вероятную цепочку тегов, лежащую в ее основе, т.е. максимизировать вероятность того, что данной цепочке слов приписывается именно такая цепочка тегов : По теореме Байеса: то есть вводятся в рассмотрение вероятности соответствия именно такой цепочки слов заданной цепочке тегов и вероятность существования именно такой цепочки тегов. Морфологическая разметка Марковская модель

32 Морфологическая разметка. Технологии Марковская модель лексическая вероятность (вероятность тэга Х при условии, что мы имеем дело с лексемой У) контекстная вероятность (вероятность тэга Х при условии, что ему предшествовал / за ним следовал тэг У)

33 Морфологическая разметка Марковская модель

34 Для каждого входного предложения Trigram определяет наиболее вероятные теги каждого слова по следующим формулам: T = argmax T P(W|T)P(T), P(T) = П i=3..n p smooth (t i | t i-2, t i-1 ) P(W|T) = П i=3..n p smooth_lex (w i | t i, t i-1 ).

35 Морфологическая разметка Марковская модель Пример работы Trigram: По ПРЕДЛ=дт двору С=мр=но=ед=дт прогуливается Г=нс=нп=дст=нст=3л=ед друг С=мр=од=ед=им и СОЮЗ одноклассник С=мр=од=ед=им моего МС- П=мр=ед=рд Димки С=мр=од=имя=ед=рд,

36 TheAT manNNVB stillNNVBRB sawNNVBD herPPOPP$ Морфологическая разметка. Марковская модель

37 NNPPOPP$RBVBVBD. AT NN PPO PP$ RB VB VBD Морфологическая разметка. Марковская модель

38 Iseeabird A1PPSSVBATNN10 -4 A2PPSSVBINNN10 -9 A3PPSSUHATNN0 A4PPSSUHINNN0 A5NPVBATNN A6NPVBINNN A7NPUHATNN0 A8NPUHINNN0 Морфологическая разметка. Марковская модель

39 Результаты тестирование парсеров Сравнение парсеров на частеречном наборе тэгов Название модуля Частичн. снятие омонимии Средн. уровень оставш. неоднозначн. ТочностьЛекс. точность SynanДа %99.26% Нет %99.26% TrigramДа %99.76% Да %99.63% Нет %99.17% AccopostНет %-

40 Для обучения парсера необходим тренировочный (эталонный) корпус Чем больше такой корпус, тем лучше Чем больше необходимо учитывать грамматических характеристик, тем меньше вероятность встретить конкретную последовательность грамматических характеристик (конкретный тэг) в корпусе, тем больше должен быть тренировочный корпус Морфологическая разметка Марковская модель

41 Морфологическая разметка. Марковская модель Множество тэгов (тэг – полное грамматическое описание словоформы) состояний для флективных языков более 1000 Проблема разреженных данных

42 Part of Speech Taggers Freely downloadable TreeTagger A decision tree based tagger from the University of Stuttgart (Helmut Scmid). It's language independent, but comes complete with parameter files for English, German, French (and Old French), and Italian. (Solaris and Linux versions.) Usable online here. Used at VISL.hereVISL Maximum Entropy part of speech tagger By Adwait Ratnaparkhi. JAVA version downloadable. A sentence boundary detector is also included. Now works with JDK1.3+. Class files, not source. ACOPOST (formerly ICOPOST) ACOPOST Open source C taggers originally written by by Ingo Schröder. Implements maximum entropy, HMM trigram, and transformation- based learning. C source available under GNU public license. fnTBL A fast and flexible implementation of Transformation-Based Learning in C++. Includes a POS tagger, but also NP chunking and general chunking models. mu-TBL

43 Краткий обзор основных методов разметки

44 SUPERVISEDUNSUPERVISED selection of tagset/tagged corpus induction of tagset using untagged training data creation of dictionaries using tagged corpus induction of dictionary using training data calculation of disambiguation tools. may include: induction of disambiguation tools. may include: word frequencies affix frequencies tag sequence probabilities "formulaic" expressions tagging of test data using dictionary information tagging of test data using induced dictionaries disambiguation using statistical, hybrid or rule based approaches calculation of tagger accuracy