Автоматический морфологический анализ Алгоритмические методы (без обучения) Часть 2. - презентация

1 Автоматический морфологический анализ Алгоритмические методы (без обучения) Часть 2

2 План Задачи, этапы (лекция Морфология 1) Задачи, этапы (лекция Морфология 1) Обзор технологий Обзор технологий Организация данных Организация данных Первичный анализ. Базовые формализмы анализа словоформы Первичный анализ. Базовые формализмы анализа словоформы Разрешение омонимии Разрешение омонимии Предсказание незнакомых слов Предсказание незнакомых слов

3 План Задачи, этапы (лекция Морфология 1) Задачи, этапы (лекция Морфология 1) Обзор технологий Обзор технологий Организация данных Организация данных Первичный анализ. Базовые формализмы анализа словоформы Первичный анализ. Базовые формализмы анализа словоформы Разрешение омонимии Разрешение омонимии Предсказание незнакомых слов Предсказание незнакомых слов

4 Задачи морфологического анализа Графематический анализ (токенизация): текстоформы, «не слова» («шаблоны», числа и т.п.), токены из списка (предлоги, союзы и т.п.) Графематический анализ (токенизация): текстоформы, «не слова» («шаблоны», числа и т.п.), токены из списка (предлоги, союзы и т.п.) нормализация словоформ (лемматизация), т.е. сведение различных словоформ к некоторому единому представлению - к исходной форме, или лемме); стемминг - другой вид нормализации, когда разные словоформы приводятся к одной основе, точнее "псевдо основе" (для некоторых задач, включая поиск в интернете, достаточно приведения к одной основе различных дериватов; например, прилагательное фотографический и существительное фотография могут быть приведены к одной основе, так как пользовательскому запросу будут удовлетворять и документы, содержащие словосочетание фотографический портрет, и документы, содержащие словосочетание портретная фотография)

5 частеречная аннотация (pos-tagging), т.е. указание части речи для каждой словоформы в тексте) полный морфологический анализ - приписывание грамматических характеристик словоформе (например, в цепочке словоформ по берегу реки словоформе берегу будут приписаны следующие грамматические характеристики: сущ., неодушевленное, мужского р., единственного числа, дательного падежа) дизамбигуация - разрешение морфологической омонимии (например, ) Основные проблемы, связанные с любым типом морфологического анализа - это морфологическая омонимия (ср. предложение Эти типы стали есть в цехе, где стали может быть формой глагола стать и формой существительного сталь), а также существование новых, редких слов или окказионализмов. Задачи морфологического анализа

6 Основные этапы морфологической разметки в BNC A. Tokenization B. Initial tag assignment C. Tag selection (disambiguation) D. Idiomtagging E. Template Tagger F. Postprocessing: including Ambiguity tagging

7 План Задачи, этапы (лекция Морфология 1) Задачи, этапы (лекция Морфология 1) Обзор технологий Обзор технологий Организация данных Организация данных Первичный анализ. Базовые формализмы анализа словоформы Первичный анализ. Базовые формализмы анализа словоформы Разрешение омонимии Разрешение омонимии Предсказание незнакомых слов Предсказание незнакомых слов

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

9 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

10 Морфологическая разметка: Технологии морфологической разметки Теория vs. практика В гг. все экспериментальные исследования в области машинной морфологии начинались с создания машинного словаря. Не было единого общепринятого формата и структуры такого словаря. Эти обстоятельства имели два последствия: во-первых, все алгоритмы автоматически становились словарно зависимыми, во-вторых, каждый алгоритм разрабатывался под определенный формат словаря. Работы, посвященные морфологии, можно условно разделить на две категории: 1. теоретические, в некоторых представлены описания морфологических законов и формальные модели русской морфологии; 2. прикладные, описание программно-реализованных систем с морфологическим модулем.

11 Теоретический vs. Инженерный подход В теоретических работах строятся многоуровневые формальные модели морфологии, в большинстве своем, предназначенные для синтеза. Такие модели морфологического синтеза подразумевают наличие больших словарей со сложной структурой. Они описывают широкий круг морфологических явлений. Многие компоненты этих моделей избыточны для задач машинного анализа (фонетическая реализация слова, акцентная парадигма, большое число словообразовательных аффиксов). Морфологическая разметка: Технологии морфологического анализа

12 Морфологическая разметка: Технологии морфологической разметки. Вопросы архитектуры.. Данные: контекст vs. информация о внутренней структуре словоформы и о словоизменительных парадигмах словарные методы vs. методы без словаря Словарь: что в словаре? структура словаря? Методы анализа формализм правила vs. статистика Работа с незнакомыми словами: правила предсказания ??? словарь

13 План Задачи, этапы (лекция Морфология 1) Задачи, этапы (лекция Морфология 1) Обзор технологий Обзор технологий Организация данных Организация данных Первичный анализ. Базовые формализмы анализа словоформы Первичный анализ. Базовые формализмы анализа словоформы Разрешение омонимии Разрешение омонимии Предсказание незнакомых слов Предсказание незнакомых слов

14 Контекст: The flights can fly DetNV(mod)V(inf) Что нужно знать? набор тегов (частеречный (N,V…) vs. простой (Nsg) vs. полный – Ncmsnn: Noun Type=common Gender=masculine Number=singular Case=nominative Animate=no) набор словоформ (ручкой – ручка, N; ручке – ручка, N …) возможные порядки тегов (NVN, NVV vs. *DV… из + Gen / * из + CaseGen) частоту порядков …. подробности позже Словарь может состоять из списка всех возможных словоформ Данные Контекст. Пример

15 Такиетипысталтестьвпомеще нии Таки-е:тип-ыстал-тест-ьцех-е N,Sg,n,Nom; N,Sg,Loc; N,Sg,Dat N,pl,Nom N,pl,Acc Adj,Brev,Sg N,Pl,Nom, N,Pl,Acc, N,Sg,Gen … N,sg,f,m,nom; N,sg,f,acc Prep; NN,Sg,n,Nom; N,Sg,Loc; N,Sg,Dat Так-ие Ти-пы Ста-ли Ес-ть Це-хе A,Pl,Nom A,Pl,Acc *V,Pst,PlV,Inf* Данные Внутренний состав словоформы. Пример

16 НЕОПТИМИЗИРОВАННАЯ ФУНКЦИОНАЛЬНАЯ СХЕМА обработки словоформы при машинном переводе исследоватьresearch, explore, investigate, examine, … Inf-ve исследуюresearch, explore, investigate, examine, … Simple Pres. (~3sg), Pres. Cont., Simple Fut., Fut.Cont.,Fut.Perf. исследуешьresearch, explore, investigate, examine, … Simple Pres. (~3sg), Pres. Cont., Simple Fut., Fut.Cont.,Fut.Perf. исследуетresearch, explore, investigate, examine, … Simple Pres. 3sg, Pres. Cont., Simple Fut., Fut.Cont.,Fut.Perf. … исследовалresearch, explore, investigate, examine, … Simple Past, Pres.Perf., Past Cont., Past Perf. исследовалаresearch, explore, investigate, examine, … Simple Past, Pres.Perf., Past Cont., Past Perf. …

17 ОБРАБОТКА СЛОВОФОРМЫ: морфологический анализ исследовать{исследовать} + +Неопр.ф. исследую{исследовать} + + Наст., Буд. вр. + Ед.ч. + 1 л. исследуешь{исследовать} + + Наст., Буд. вр. + Ед.ч. + 2 л. исследует{исследовать} + + Наст., Буд. вр. + Ед.ч. + 3 л. … исследовал{исследовать} + + Прош. вр. + Ед.ч. + М р. исследовала{исследовать} + + Прош. вр. + Ед.ч. + Ж р. … … {исследовать}research, explore, investigate, examine, analyse, test, inquire into… … Неопр.ф.Inf-ve Наст.+Ед.+1S.Pres.(~3sg), Pres. Cont. Наст.+Ед.+2S.Pres.(~3sg), Pres. Cont. Наст.+Ед.+3S.Pres. 3sg, Pres. Cont. Буд.+Ед.+1S. Fut., Fut.Cont.,Fut.Perf. Буд.+Ед.+1S. Fut., Fut.Cont.,Fut.Perf. Буд.+Ед.+1S. Fut., Fut.Cont.,Fut.Perf. Прош.+Ед.S. Past, Pres.Perf., Past Cont., Past Perf.

18 ПОРОЖДЕНИЕ СЛОВОФОРМЫ: морфологический синтез {исследовать} + Неопр.ф.исследовать {исследовать} + Наст. вр. + Ед.ч. + 1 л.исследую {исследовать} + Наст. вр. + Ед.ч. + 2 л.исследуешь {исследовать} + Наст. вр. + Ед.ч. + 3 л.исследует … {исследовать} + Буд. вр. + Ед.ч. + 1 л.исследую, буду исследовать {исследовать} + Буд. вр. + Ед.ч. + 2 л.исследуешь, будешь исследовать {исследовать} + Буд. вр. + Ед.ч. + 3 л.исследует, будет исследовать … {исследовать} + Прош. вр. + Ед.ч. + М р.исследовал {исследовать} + Прош. вр. + Ед.ч. + Ж р.исследовала …

19 ПОРОЖДЕНИЕ СЛОВОФОРМЫ: морфологический синтез {исследовать} + Неопр.ф.исследовать {исследовать} + Наст. вр. + Ед.ч. + 1 л.исследую {исследовать} + Наст. вр. + Ед.ч. + 2 л.исследуешь {исследовать} + Наст. вр. + Ед.ч. + 3 л.исследует … {исследовать} + Буд. вр. + Ед.ч. + 1 л.исследую, буду исследовать {исследовать} + Буд. вр. + Ед.ч. + 2 л.исследуешь, будешь исследовать {исследовать} + Буд. вр. + Ед.ч. + 3 л.исследует, будет исследовать … {исследовать} + Прош. вр. + Ед.ч. + М р.исследовал {исследовать} + Прош. вр. + Ед.ч. + Ж р.исследовала …

20 ПОРОЖДЕНИЕ СЛОВОФОРМЫ: морфологический синтез {исследовать} + Неопр.ф.исследовать {исследовать} + Наст. вр. + Ед.ч. + 1 л.исследую {исследовать} + Наст. вр. + Ед.ч. + 2 л.исследуешь {исследовать} + Наст. вр. + Ед.ч. + 3 л.исследует … {исследовать} + Буд. вр. + Ед.ч. + 1 л.исследую, буду исследовать {исследовать} + Буд. вр. + Ед.ч. + 2 л.исследуешь, будешь исследовать {исследовать} + Буд. вр. + Ед.ч. + 3 л.исследует, будет исследовать … {исследовать} + Прош. вр. + Ед.ч. + М р.исследовал {исследовать} + Прош. вр. + Ед.ч. + Ж р.исследовала …

21 МОРФОЛОГИЧЕСКИЙ АНАЛИЗ и ЛЕММАТИЗАЦИЯ исследовать{исследовать} + +Неопр.ф. исследую{исследовать} + + Наст., Буд. вр. + Ед.ч. + 1 л. исследуешь{исследовать} + + Наст., Буд. вр. + Ед.ч. + 2 л. исследует{исследовать} + + Наст., Буд. вр. + Ед.ч. + 3 л. … исследовал{исследовать} + + Прош. вр. + Ед.ч. + М р. исследовала{исследовать} + + Прош. вр. + Ед.ч. + Ж р. … исследовать{исследовать} исследую{исследовать} исследуешь{исследовать} исследует{исследовать} … исследовал{исследовать} исследовала{исследовать} …

22 МОРФОЛОГИЧЕСКИЙ СИНТЕЗ и ПОРОЖДЕНИЕ ПАРАДИГМЫ {исследовать} + Неопр.ф. исследовать {исследовать} + Наст. вр. + Ед.ч. + 1 л. исследую {исследовать} + Наст. вр. + Ед.ч. + 2 л. исследуешь {исследовать} + Наст. вр. + Ед.ч. + 3 л. исследует … {исследовать} + Буд. вр. + Ед.ч. + 1 л. исследую, буду исследовать {исследовать} + Буд. вр. + Ед.ч. + 2 л. исследуешь, будешь исследовать {исследовать} + Буд. вр. + Ед.ч. + 3 л. исследует, будет исследовать … {исследовать}исследовать исследую исследуешь исследует исследуем исследуете исследуют буду исследовать будешь исследовать будет исследовать … исследовал исследовала …

23 ЕСТЬ ЛИ ДОСТАТОЧНАЯ ПРЕДСКАЗУЕМОСТЬ? дневн(ой) дневник дневн(ой) дневник вечерн(ий)вечерник вечерн(ий)вечерник ночн(ой)ночник ночн(ой)ночник утренн(ий)утренник утренн(ий)утренник

24 ЕСТЬ ЛИ ДОСТАТОЧНАЯ ПРЕДСКАЗУЕМОСТЬ? дневник{дневной} + тетрадь для записей, заполняемая с указанной периодичностью, {дневной} + студент формы обучения, предусматривающей занятия в указанное время суток вечерник{вечерний} + студент формы обучения, предусматривающей занятия в указанное время суток ночник{ночной} + лампа, используемая в указанное время суток утренник{утренний} + представление, происходящее в указанное время суток АНАЛИЗ:

25 ЕСТЬ ЛИ ДОСТАТОЧНАЯ ПРЕДСКАЗУЕМОСТЬ? {дневной} + студент формы обучения, предусматривающей занятия в указанное время суток дневник {вечерний} + студент формы обучения, предусматривающей занятия в указанное время суток вечерник {утренний} + студент формы обучения, предусматривающей занятия в указанное время суток ?? {дневной} + лампа, используемая в указанное время суток ?? {вечерний} + представление, происходящее в указанное время суток ?? СИНТЕЗ:

26 СЛОВОИЗМЕНЕНИЕ И СЛОВООБРАЗОВАНИЕ Внутренний смысл противопоставления: варианты одной лексической единицы или разные лексические единицы варианты одной лексической единицы или разные лексические единицы Подходы в теоретической морфологии: 28 «элементарных различий» словоизменения и словообразования по Ф.Планку 28 «элементарных различий» словоизменения и словообразования по Ф.Планку 15 критериев противопоставления лексического и грамматического у Н.В.Перцова 15 критериев противопоставления лексического и грамматического у Н.В.Перцова вхождение/невхождение в категории противопоставленных единиц и обязательные категории; вхождение/невхождение в категории противопоставленных единиц и обязательные категории; коррелятивность; коррелятивность; композиционность; композиционность; и т.д.

27 СЛОВОИЗМЕНЕНИЕ И СЛОВООБРАЗОВАНИЕ Внутренний смысл противопоставления: варианты одной лексической единицы или разные лексические единицы варианты одной лексической единицы или разные лексические единицы Технические критерии противопоставления: при анализе при анализе композиционность: словоформа без остатка разбивается на формальные показатели (знаки), значение формы без остатка раскладывается на значения этих показателей композиционность: словоформа без остатка разбивается на формальные показатели (знаки), значение формы без остатка раскладывается на значения этих показателей при синтезе при синтезе регулярность (коррелятивность): лексические единицы разбиты на (достаточно большие) классы, и для каждого класса известен набор возможных словоформ, а также правила, по которым их можно строить регулярность (коррелятивность): лексические единицы разбиты на (достаточно большие) классы, и для каждого класса известен набор возможных словоформ, а также правила, по которым их можно строить

28 СЛОВОИЗМЕНЕНИЕ И СЛОВООБРАЗОВАНИЕ Технический критерий позволяет подключить к явлениям словоизменения (для русского языка): образование существительных от прилагательных образование существительных от прилагательных образование существительных (имен действия и имен деятеля) от глаголов образование существительных (имен действия и имен деятеля) от глаголов образование уменьшительных существительных образование уменьшительных существительных Более осторожный термин С.А.Крылова и С.А.Старостина для таких явлений – «номинационное формообразование» (2003)

29 СЛОВОИЗМЕНЕНИЕ И СЛОВООБРАЗОВАНИЕ Общий вывод для компьютерной морфологии: Класс явлений словоизменения может быть расширен, нужно только исчерпывающее и объективное описание указать класс лексем, которые подвергаются такому варьированию (образуют уменьшит./ аугментатив. форму и т.п.) указать класс лексем, которые подвергаются такому варьированию (образуют уменьшит./ аугментатив. форму и т.п.) указать правила варьирования для каждой лексемы из класса достаточно экономным образом указать правила варьирования для каждой лексемы из класса достаточно экономным образом Но следует учитывать фактор практической целесообразности с учетом функции конкретной компьютерной системы фактор практической целесообразности с учетом функции конкретной компьютерной системы

30 ФОРМАЛЬНЫЙ РАЗРЯД В КОМПЬЮТЕРНОЙ МОРФОЛОГИИ учител-ьучител-я учител-ей учител-юучител-ям учител-яучител-ей учител-емучител-ями учител-еучител-ях учитель, соболь, егерь… (типовая парадигма, морфологический тип)

31 ОДНА ПАРАДИГМА ИЛИ БОЛЬШЕ? узелузлы узлаузлов узлуузлам узелузлы узломузлами узлеузлах бубенбубны бубнабубнов бубнубубнам бубенбубны бубномбубнами бубнебубнах хребетхребты хребтахребтов хребтухребтам хребетхребты хребтомхребтами хребтехребтах

32 СТРУКТУРА СЛОВАРНОЙ БАЗЫ ДАННЫХ Идентификатор лексемы Идентификатор парадигмы порогов 302 пород 005 породнени 002 порожда 401

33 СТРУКТУРА СЛОВАРНОЙ БАЗЫ ДАННЫХ Идентификатор лексемы Основа Идентификатор парадигмы пороговыйпорогов 302 породапород 005 породнениепороднени 002 порождатьпорожда 401

34 ПЕРВИЧНЫЕ И ВТОРИЧНЫЕ ФУНКЦИИ (ПРОЦЕДУРЫ) В КОМПЬЮТЕРНОЙ МОРФОЛОГИИ

35 ПРОЦЕДУРА ОПРЕДЕЛЕНИЯ ТИПОВОЙ ПАРАДИГМЫ если слово оканчивается на щийся, то ТП 5; если слово оканчивается на щийся, то ТП 5; если слово оканчивается на ин, ын, то ТП 20; если слово оканчивается на ин, ын, то ТП 20; если слово оканчивается на ов, ёв, ев, то ТП 21; если слово оканчивается на ов, ёв, ев, то ТП 21; если слово оканчивается на цый, то ТП 6; если слово оканчивается на цый, то ТП 6; если слово оканчивается на ый, то ТП 1; если слово оканчивается на ый, то ТП 1; если слово оканчивается на кий, гий, хий, то ТП 3; если слово оканчивается на кий, гий, хий, то ТП 3; если слово оканчивается на щий, то ТП 4; если слово оканчивается на щий, то ТП 4; если слово оканчивается на жий, ший, чий, то ТП 4 или ТП 24; если слово оканчивается на жий, ший, чий, то ТП 4 или ТП 24; если слово оканчивается на ий, то ТП 2 или ТП 24; если слово оканчивается на ий, то ТП 2 или ТП 24; если слово оканчивается на кой, гой, хой, жой, шой, чой, щой, то ТП 8; если слово оканчивается на кой, гой, хой, жой, шой, чой, щой, то ТП 8; если слово оканчивается на ой, то ТП 7. если слово оканчивается на ой, то ТП 7.

36 ТИПИЗАЦИЯ ВНУТРИ ПРЕДСКАЗАНИЯ

37 ВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ КОДОВ ГСРЯ В МОРФОЛОГИЧЕСКИХ МОДУЛЯХ Могут быть слишком дробными (для обработки письменного текста) Могут быть слишком дробными (для обработки письменного текста) дол м 1 е//1 а порт м 1 еимеют одинаковый набор окончаний клён м 1 а Могут быть недостаточно точными (для некоторых процедур компьютерной морфологии) Могут быть недостаточно точными (для некоторых процедур компьютерной морфологии) восстановление начальной формы: бугор м 1*bбугра: (- ра), (+ ор) котёл м 1*bкотла: (- ла), (+ ёл) псалом м 1*bпсалма: (- ма), (+ ом) сон м 1*bсна: (- на), (+ он) хребет м 1*bхребта: (- та), (+ ет)

38 НЕДОСТАТКИ СЛОВАРЯ ЗАЛИЗНЯКА сложная структура словоизменительной характеристики сложная структура словоизменительной характеристики формальная «вседозволенность» (свобода образования форм множественного числа - вреды, зарезы, неонацизмы, кратких форм - бегл, кредитово, соляны, сравнительной степени - тяжелораненее, убитее, изюбревее) формальная «вседозволенность» (свобода образования форм множественного числа - вреды, зарезы, неонацизмы, кратких форм - бегл, кредитово, соляны, сравнительной степени - тяжелораненее, убитее, изюбревее) неполнота словника неполнота словника

39 РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА Леонтьева Н.Н. Автоматическое понимание текстов: системы, модели, ресурсы. М., 2006 (глава 4, (3)) Леонтьева Н.Н. Автоматическое понимание текстов: системы, модели, ресурсы. М., 2006 (глава 4, (3)) Коваль С.А. Лингвистические проблемы компьютерной морфологии. СПб., 2005 Коваль С.А. Лингвистические проблемы компьютерной морфологии. СПб., 2005 Библиография, собранная С. Нагелем (Sebastian Nagel): Библиография, собранная С. Нагелем (Sebastian Nagel): muenchen.de/~wastl/rmorph/rusmorphBib.pd f

40 УПОМЯНУТАЯ ЛИТЕРАТУРА Перцов Н.В. Инварианты в русском словоизменении. М.: Языки русской культуры, 2001 (глава 2) Перцов Н.В. Инварианты в русском словоизменении. М.: Языки русской культуры, 2001 (глава 2) Крылов С.А., Старостин С.А. Актуальные задачи морфологического анализа и синтеза в интегрированной информационной среде STARLING // Тр. Междунар. конф. Диалог 2003 ( 21.ru/Archive/2003/Krylov.htm) Крылов С.А., Старостин С.А. Актуальные задачи морфологического анализа и синтеза в интегрированной информационной среде STARLING // Тр. Междунар. конф. Диалог 2003 ( 21.ru/Archive/2003/Krylov.htm)

41 Данные Внутренняя структура словоформы. Пример Входные данные Результат морфологического анализа: городке городк - е

42 Данные Внутренняя структура словоформы. Пример Морфонологические правила: Обратный пересчет: (1) V -> Ø | __ CV (beglie) (2) C тв -> C мягк | __ Vпередн ряд (Palatalization) Городок | городка |городке (3) C зв -> C гл | __ Сгл (Oglushenie)

43 Данные Внутренняя структура словоформы. Пример

44 Данные Полный список словоформ с их формами Полный список словоформ с их формами Полная декомпозиция: Полная декомпозиция:

45 План Задачи, этапы (лекция Морфология 1) Задачи, этапы (лекция Морфология 1) Обзор технологий Обзор технологий Организация данных Организация данных Первичный анализ. Базовые формализмы анализа словоформы Первичный анализ. Базовые формализмы анализа словоформы Разрешение омонимии Разрешение омонимии Предсказание незнакомых слов Предсказание незнакомых слов

46 Формализмы FST (конечные преобразователи – Finite State Trasducers) FST (конечные преобразователи – Finite State Trasducers) Порождающая грамматика Порождающая грамматика Язык регулярных выражений Язык регулярных выражений

47 Порождающие граммаики упорядоченная четверка, упорядоченная четверка, где V и W - непересекающиеся конечные множества, наз. соответственно основным и вспомогательным алфавитами, или словарями (их элементы наз. соответственно основными, пли терминальными, и вспомогательными, или нетерминальными, символам и), - элемент, наз. начальным символом, и - конечное множество правил, имеющих вид, где - цепочки ( слова).в алфавите и не принадлежит ; Rназ. схемой грамматики. где V и W - непересекающиеся конечные множества, наз. соответственно основным и вспомогательным алфавитами, или словарями (их элементы наз. соответственно основными, пли терминальными, и вспомогательными, или нетерминальными, символам и), - элемент, наз. начальным символом, и - конечное множество правил, имеющих вид, где - цепочки ( слова).в алфавите и не принадлежит ; Rназ. схемой грамматики.

48 ФОРМАЛЬНАЯ (ПОРОЖДАЮЩАЯ) ГРАММАТИКА - пример Четверка (V, W, I, R): V = {а, е, й, к, л, о, у, ы} V = {а, е, й, к, л, о, у, ы} W = {Слово, Основа, Окончание} W = {Слово, Основа, Окончание} I = {Слово} I = {Слово} R – множество правил грамматики R – множество правил грамматики Правила R : 1. Слово Основа Окончание 2. Основа к у к л 3. Окончание а 4. Окончание ы 5. Окончание у 6. Окончание е 7. Окончание о й

49 ВЫВОД В ФОРМАЛЬНОЙ ГРАММАТИКЕ Правила R : 1. Слово Основа Окончание 2. Основа к у к л 3. Окончание а 4. Окончание ы 5. Окончание у 6. Окончание е ВЫВОД: Слово (1) Основа Окончание (2) к у к л Окончание (6) к у к л о й

50 Основные формализмы FST Один из наиболее распространенных Finite State Transducer (Конечные преобразователи) Один из наиболее распространенных Finite State Transducer (Конечные преобразователи) Конечный автомат абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Конечный автомат абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.абстрактный автоматконечноабстрактный автоматконечно

51 Конечный автомат Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров:, где: Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров:, где: Q конечное множество состояний автомата; Q конечное множество состояний автомата; q 0 начальное состояние автомата (); q 0 начальное состояние автомата (); F множество заключительных (или допускающих) состояний, таких что ; F множество заключительных (или допускающих) состояний, таких что ; Σ допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом; Σ допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом; δ заданное отображение множества во множество подмножеств Q: (иногда δ называют функцией переходов автомата). δ заданное отображение множества во множество подмножеств Q: (иногда δ называют функцией переходов автомата).

52 Конечные автоматы Автомат начинает работу в состоянии q 0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается». Автомат начинает работу в состоянии q 0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается». Конечный преобразователь: анализирует цепочку символов на входной ленте и записывает другую цепочку на выходной ленте. Конечный преобразователь: анализирует цепочку символов на входной ленте и записывает другую цепочку на выходной ленте.

53 Недетерминированные конечные автмоматы Существуют переходы, помеченные пустой цепочкой ε Из одного состояния выходит несколько переходов, помеченных одним и тем же символом Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:рованность автоматов достигается двумя способами:

54 КОНЕЧНЫЙ ПРЕОБРАЗОВАТЕЛЬ Правила вида q i a i b i q j читающая головка устройства укол### a1 a1 a2 a2 q i b1 b1 b2b2 направление движения обеих лент Распознавание (порождение) цепочек пар символов Перекодирование (переход от записи на языке верхней ленты к записи на языке нижней ленты и наоборот)

55 КОНЕЧНЫЙ ПРЕОБРАЗОВАТЕЛЬ В ВИДЕ ДИАГРАММЫ К УКЛА:Ø Записать в виде таблицы? Им.:АЕд.: Ø

56 ФРАГМЕНТ АНГЛИЙСКОЙ ГЛАГОЛЬНОЙ СИСТЕМЫ: КОНЕЧНЫЙ ПРЕОБРАЗОВАТЕЛЬ s Ø pr i ng Inf: Ø 3PSg: s i:a i:u n ngPast:Ø gPP: Ø

57 ЛЕКСИКОН В ФОРМАТЕ Xerox Tools Multichar_Symbols +Inf+3pSg +Past+PP LEXICON Root sing+Inf:sing# ; sing+3pSg:sings# ; sing+Past:sang# ; sing+PP:sung# ; spring+Inf:spring# ; spring+3pSg:springs# ; spring+Past:sprang# ; spring+PP:sprung# ;

58 Язык регулярных выражений Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы: Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы:константоператоровмножествастрокоперацийалфавитеконстантоператоровмножествастрокоперацийалфавите (пустое множество). (пустое множество).пустое множествопустое множество (пустая строка) ε обозначает строку, не содержащую ни одного символа. Эквивалентно «». (пустая строка) ε обозначает строку, не содержащую ни одного символа. Эквивалентно «».пустая строкапустая строка (символьный литерал) «a», где a символ алфавита Σ. (символьный литерал) «a», где a символ алфавита Σ.символьный литералсимвольный литерал

59 Язык регулярных выражений и следующие операции: и следующие операции: (сцепление, конкатенация) RS обозначает множество {αβ | α R & β S}. Например, {"boy", "girl"}{"friend", "cott"} = {"boyfriend", "girlfriend", "boycott", "girlcott"}. (сцепление, конкатенация) RS обозначает множество {αβ | α R & β S}. Например, {"boy", "girl"}{"friend", "cott"} = {"boyfriend", "girlfriend", "boycott", "girlcott"}.сцепление, конкатенациясцепление, конкатенация (дизъюнкция, чередование) R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}. [4] (дизъюнкция, чередование) R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}. [4]дизъюнкцияобъединение [4]дизъюнкцияобъединение [4] (замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {"Go", "Russia"}* = {ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}. (замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {"Go", "Russia"}* = {ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}.замыкание Клини, звезда Клининадмножествозамкнутозамыкание Клини, звезда Клининадмножествозамкнуто

60 Язык регулярных выражений Представление символов Представление символов Обычные символы (литералы) и специальные символы (метасимволы) Обычные символы (литералы) и специальные символы (метасимволы)литералыметасимволылитералыметасимволы Большинство символов в регулярном выражении представляют сами себя за исключением специальных символов [ ] \ / ^ $. | ? * + ( ) { }, которые могут быть предварены символом \ (обратная косая черта) («экранированы», «защищены») для представления их самих в качестве символов текста. Большинство символов в регулярном выражении представляют сами себя за исключением специальных символов [ ] \ / ^ $. | ? * + ( ) { }, которые могут быть предварены символом \ (обратная косая черта) («экранированы», «защищены») для представления их самих в качестве символов текста. Городо?[кк]([еауи]/ом/ами/ах)? Городо?[кк]([еауи]/ом/ами/ах)?

61 План Задачи, этапы (лекция Морфология 1) Задачи, этапы (лекция Морфология 1) Обзор технологий Обзор технологий Организация данных Организация данных Первичный анализ. Базовые формализмы анализа словоформы Первичный анализ. Базовые формализмы анализа словоформы Методы, основанные на словарях Методы, основанные на словарях Разрешение омонимии Разрешение омонимии Предсказание незнакомых слов Предсказание незнакомых слов

62 Методы, основанные на словаре. Основные вопросы: Основные вопросы: Как разделять исходную словоформу Как разделять исходную словоформу на сколько частей и какие? на сколько частей и какие? Что хранить в словаре: Что хранить в словаре: словоформу, словоформу, основу + правила преобразования + словоизменительные парадигмы, основу + правила преобразования + словоизменительные парадигмы, квазиосновы + квазиокончания квазиосновы + квазиокончания

63 Морфологическая разметка Методы, основанные на словаре Существует три базовых подхода к проектированию морфологических машинных словарей (лексиконов) для флективных языков. 1)копируется академическая лингвистическая модель описания, где выделяются основные парадигматические классы, соответствующие типу склонения и спряжения, и правила регулярных альтернаций (фонетических чередований), а нерегулярные формы (например, сильные глаголы в немецком и английском языках) задаются перечислением. (на базе модели грамматического словаря А.Зализняка, разрабатывая 8 классов именного склонения и 16 глагольного спряжения, а чередования в основе и глагольной темы выносятся в отдельное множество пост-морфологических правил альтернаций) 2) рассматривается любого вида регулярное и нерегулярное чередование как часть расширенной псевдо-флексии (в таком случае, основа словоформы день – д, а флексия – -ень; для словоформы песок: пес и -ок). В подобной модели описания число парадигматических классов для русского языка возрастает до ) В лексиконе для каждой лексемы приводится полный список словоформ

64 Методы, основанные на словаре. LEXICON Verbs; LEXICON Verbs; вписывать+Verb+Perf:впи(с/ш) V1; вписывать+Verb+Perf:впи(с/ш) V1; LEXICON V1; +Inf+Active:^Hать #; +Imperf+Inf+Passive:^Hаться #; +Ind+NotPast+P1+Sg+Active:^Sьу #; +Ind+NotPast+P2+Sg+Active:^Sьэшь #; +Ind+NotPast+P3+Sg+Active:^Sьэт #; +Ind+NotPast+P1+Pl+Active:^Sьэм #; +Ind+Past+Sg+Masc+Active:^Hал #; +Ind+Past+Sg+Fem+Active:^Hала #; +Ind+Past+Sg+Neut+Active:^Hало #; лексическая форма вписывать+Verb+Perf+Ind+NotPast+P3+Sg+Active соответствует поверхностной форме впи(с/ш) ^Sьэт.

65 Методы, основанные на словаре Морфологическая разметка:. Фрагмент описания парадигмы для лексемы рукоплескать: 1740 %СКАТЬ*ка%СКАВШАЯ*мз%ЩУ*кб%ЩУТ*кж%ЩУЩЕГО* лблглп%…. ………………… РУКОПЛЕ 1740 Рукопле – основа слова в лексиконе; 1740 – уникальный идентификатор парадигматического класса; % маркирует начало псевдо-флексии; * маркирует начало аношкинского кода; ка, кб, лб, лг, etc. – код. В таблице приведена расшифровка аношкинских кодов, использованных в примере:

66 Методы, основанные на словаре Морфологическая разметка:. %СКАТЬ*ка%СКАВШАЯ*мз%ЩУ*кб%ЩУТ *кж%ЩУЩЕГО*лблглп%…. %СКАТЬ*ка%СКАВШАЯ*мз%ЩУ*кб%ЩУТ *кж%ЩУЩЕГО*лблглп%…. Аношкинский код: Аношкинский код:

67 Словари Словарь Mystem В каждой парадигме можно выделить псевдооснову (неизменяемую левую часть), в данном случае мам-, можно выделить StemGrammar (словообразовательные пометы, в данном случае «S,од,жен») и FlexGrammar (словоизменительные пометы). Можно записать данную парадигму в виде тройки, где модель окончаний – это набор пар вида, например: мама =, где F =,..

68 Словари Словарь Mystem В текущей версии словаря используются около 3000 моделей.Некоторые из нихуникальны, например, есть специальная модель для слова, там выделяются окончания, - и т.д. В текущей версии словаря используются около 3000 моделей. Некоторые из них уникальны, например, есть специальная модель для слова Комсомольск-на-амуре, там выделяются окончания -а-на-амуре, -ом-на-амуре и т.д.

69 Морфологическая разметка Методы, основанные на словаре Первый подход к проектированию лексиконов для построения морфологических анализаторов европейских и восточных языков был применен в научно-исследовательском центре Xerox (Гренобль) в середине 90-ых, а позже усовершенствован и доведен до промышленного использования в исследовательских отделах Inxight Software (Санта-Клара, США и Антверпен, Бельгия) в гг. Конечный продукт Inxight LinguistX Platform 3.5 включает в себя морфологии 26 языков: 5 восточных (арабский, корейский, японский, etc.) и 21 европейский (английский, голландский, испанский, русский, etc.).

70 План Задачи, этапы (лекция Морфология 1) Задачи, этапы (лекция Морфология 1) Обзор технологий Обзор технологий Организация данных Организация данных Первичный анализ. Базовые формализмы анализа словоформы Первичный анализ. Базовые формализмы анализа словоформы Разрешение омонимии Разрешение омонимии Предсказание незнакомых слов Предсказание незнакомых слов

71 1) 1) предсказание префиксального образования 2) 2) предсказание по концовке, взятой из известных словоформ Морфологическая разметка Методы «борьбы» с незнакомыми словами: предсказания в АОТ

72 1) 1) предсказание префиксального образования 2) 2) предсказание по концовке, взятой из известных словоформ Морфологическая разметка Методы «борьбы» с незнакомыми словами

73 Предсказания незнакомых слов Один из первых алгоритмов морфологического предсказания для русского языка был предложен в работах Г.Г.Белоногова. Главным в этом алгоритме предсказания был принцип «корреляции между грамматическими признаками слов и буквенным составом их концов». o o Белоногов Г. Г. Об использовании метода аналогии при обработке текстовой информации // Проблемы кибернетики,., 1974, вып. 28. o o Белоногов Г. Г., Зеленков Ю. Г. Алгоритм морфологического анализа русских слов // Вопросы информационной теории и практики. 53. Автоматическая словарная служба. Автоматическое индексирование документов. М., С

74 Предсказания незнакомых слов В 80-е и 90-e годы на факультете ВМК МГУ активно разрабатывалась система TULIPS-2, которая включала морфологический компонент, эта система использовала для предсказания словарь основ и словарь флексий, учитывались чередования. o o Мальковский М.Г., Волкова И.А. Анализатор системы TULIPS-2. Морфологический уровень // Вестн. Моск. Ун-та, сер. 15, 1981, N 1, с

75 Предсказания незнакомых слов Развитие корпусной лингвистики подстегнуло рост интереса к системам, которые в качестве решающего фактора используют частотность тех или иных морфологических схем в текстовом корпусе. Например, в работе Wicentowski исследуется система, которая построена на трех простых факторах: 1. Расстояние Левенштейна, модифицированное под поиск морфологических вариантов. 2. Контекстная близость по соседним словам в корпусе. 3. Близость по частоте форм в одинаковых моделях словоизменения. Показывается, что система дает точность лемматизации порядка 80% на 30 различных языках. o o Richard Wicentowski. Modeling and Learning Multilingual Inflectional Morphology in a Minimally Supervised Framework, 2002.

76 Предсказания незнакомых слов В работе Ляшевской и др. был предложен метод взвешивания морфологического предсказания, основанный на следующем утверждении. Если некоторое слово открытого (словоизменительного) класса встретилось в тексте в форме, то скорее всего оно встретится в тексте в форме, отличной от первой Если некоторое слово открытого (словоизменительного) класса встретилось в тексте в форме X, то скорее всего оно встретится в тексте в форме Y, отличной от первой. Из этого можно сделать предположение, что парадигмы новых слов тем лучше, чем больше разных форм этой парадигмы найдено в корпусе. В этой работе строились парадигмы для слов из НКРЯ o o Ляшевская О.Н., Д.В. Сичинава, Б.П. Кобрицов. Автоматизация построения словаря на материале массива не словарных словоформ // Браславский П. И. (отв. ред.), Интернет-математика – 2007: сб. работ участников конкурса науч. проектов по информ. поиску. Екатеринбург: Изд-во Урал. ун-та. С нального корпуса русского языка (НКРЯ).

77 Морфологическая разметка Методы «борьбы» с незнакомыми словами: предсказания в АОТ попытка найти существующую словоформу языка, которая максимально совпадала бы справа со входным словом. Если левая часть (потенциальный префикс) не длиннее M символов (пяти), а правая часть (совпавшая с известной словоформой) не короче N символов (четырех), то слово разбирается по образцу известной словоформы. [евро]технологию, [супер]коньками

78 ПРЕДСКАЗАНИЕ В АОТ: ПРЕДСКАЗАНИЕ ПО КОНЦОВКЕ ИЗ ИЗВЕСТНОЙ СЛОВОФОРМЫ создается конечный автомат, построенный на строках вида: ReverseSuffix(X)|Annot(X), где ReverseSuffix(Х) – инвертированная концовка известной словоформы длины K (пять букв), Annot(X) – аннотация словоформы X (анкод), например: меина|ед где аннотация «ед» интерпретируется как «ср. род, ед. ч., тв. пад.» Такая строка заносится в исходный лексикон, если она встречается: не менее L раз (трех) и чаще конкурентов (строк с таким же ReverseSuffix(X), но другим Annot(X) ) в пределах одной части речи ВСЕГДА предусматривается разбор именем существительным, хотя бы неизменяемым.

79 ПРЕДСКАЗАНИЕ В АОТ: ОЦЕНКА КАЧЕСТВА В новостных текстах наугад выбраны 150 неповторяющихся предсказанных слов. Исключались слова, у которых все буквы в верхнем регистре (аббревиатуры). Все слова оказались либо существительными, либо прилагательными. Для 131 слова в результатах предсказания был хотя бы один правильный результат (одновременно лемма, часть речи, род, число и падеж). Т.е. точность предсказания – 87%. Результат вполне сравним с известными результатами для английского языка - 85 % или для французского – 88%.