Слайды со всех лекций (1126919), страница 4
Текст из файла (страница 4)
al. 1996)22 октября 2011 г.Марковская модельмаксимальной энтропии• Позволяет смоделировать сложные признаки(например для определения части речи)T̂ = arg max P (T |W ) = arg maxtT!iP (tagi |wordi , tagi−1 )• Сравнить с марковской модельюT̂ = arg max P (T |W ) = arg maxtT!iP (wordi |tagi )P (tagi , tagi−1 )#!"#$%$& '(#")*+",&')-&.,22 октября 2011 г.!"#$%$& '(#")*+",&')-&., '("+,'(./0)120%#)3,,Признаки в MEMMNNP#SecretariatVBZisVBNexpected1P (q|q , o) =expZ(o, q ! )!22 октября 2011 г.!"iTOVBNtorace#wi fi (o, q)VBNtomorrowДекодирование и обучение• Декодирование - алгоритм Витерби, гдена каждом шаге вычисляетсяvt (j) =Nmaxi=1 vt−1 (i)P (sj |si , ot ), 1≤ j ≤ N, 1 < t ≤ T• Обучение аналогично логистическойрегрессии• Аналогично с марковскими моделямиможно оценить параметры полуавтоматически (версия EM-алгоритма)22 октября 2011 г.Заключение• Скрытые марковские модели предоставляютспособ по последовательности наблюдений получитьпоследовательность скрытых классов, описывающихнаблюдения• Для декодирования обычно используется алгоритмВитерби• Модель максимальной энтропии позволяеткомбинировать различные признаки для улучшенияклассификации• Марковская модель максимальной энтропии расширение предыдущей модели дляпоследовательной классификации.
Длядекодирования используется алгоритм Витерби22 октября 2011 г.Упражнения• Реализовать алгоритм Витерби дляскрытой марковской модели первогопорядка• Обобщить реализацию для более высокихпорядков• Реализовать алгоритм Баума-Велша• Реализовать модель MEMM• Обучить модели и протестировать назадаче определения частей речи длярусского языка22 октября 2011 г.Следующая лекция• Контекстно-свободные граматики• Синтаксический анализ текстов22 октября 2011 г.Введение в обработкутекстовЛекция 5Формальные грамматики и синтаксический анализ28 октября 2011 г.Пример синтаксическогоразбора28 октября 2011 г.Где может быть полезнознание синтаксиса?• Машинный перевод• Генерация текста–диалоговые системы• Извлечение информации• ...28 октября 2011 г.План• Грамматика естественного языка–Составляющие–Модель управления• Формальные грамматики–Контекстно-свободные грамматики–Грамматики зависимостей–Категориальные грамматики• Синтаксический разбор• Фрагментирование28 октября 2011 г.Составляющие!"# $%&'()#%# *%&+& ,-.-" /#*0"( .#%"0)" /& +-**%&1- 234%-28 октября 2011 г.Грамматика составляющих• именная группа (группасуществительного, noun phrase, NP)• группа прилагательного (adjectival phrase,ADJP)• наречная группа (adverbial phrase, ADVP)• предложная группа (prepositional phrase,PP)• глагольная группа (verb phrase, VP);28 октября 2011 г.ПримерSNPPPNPVPNP!"# $%&'()#%# *%&+& ,-.-" /#*0"( .#%"0)" /& +-**%&1- 234%[S[NP Эти школьники] скоро[VP будут писать][NP диктант[PP по [NP русскому языку]]]]28 октября 2011 г.Контекстно свободные грамматикиNoun→ flights | breeze | trip | morningVerb→ is | prefer | like | need | want| flyAdjective→ cheapest | non-stop | first | latest | other | directPronoun→ me | I | you | itProper-Noun → Alaska | Los Angeles | ChicagoDeterminer → the | a | an | this | these | thatPreposition → from | to | on | nearConjunction → and | or | butSNPNominalVPPP28 октября 2011 г.→ NP VP→ Pronoun| Proper-Noun| Det Nominal→ Nominal Noun| Noun→ Verb| Verb NP| Verb NP PP| Verb PP→ Preposition NPI + want a morning flightILos Angelesa + flightmorning + flightflightsdowant + a flightleave + Boston + in the morningleaving + on Thursdayfrom + Los AngelesПримерSNPVPProVerbIpreferNPDetaNomNomNounNounflightmorning28 октября 2011 г.Формальное определениеN множество нетерминальных символовмножество терминальных символовΣ(непересекающееся с N)множество правил, каждое вида A → βR где A - нетерминал,β - строка символов из множества (Σ ∪ N )∗S символ начала28 октября 2011 г.Согласование• Пример–по русскому языку–русский язык• Увеличение количества правил• Введение параметров длянетерминальных символов28 октября 2011 г.Банк деревьев• Treebank–Penn Treebank Project• Вывод граматики по банку деревьев( (S (NP-SBJ (NP Pierre Vinken),(ADJP (NP 61 years)old),)(VP will(VP join(NP the board)(PP-CLR as(NP a nonexecutive director))(NP-TMP Nov.
29))).))( (S (NP-SBJ Mr. Vinken)(VP is(NP-PRD (NP chairman)(PP of(NP (NP Elsevier N.V.),(NP the Dutch publishing group))))).))28 октября 2011 г.Эквивалентность грамматик• Эквивалентность–сильная–слабая• Нормальная форма грамматики(Хомского)– A→BC–A→a• Преобразование в нормальную форму28 октября 2011 г.Контекстно-свободные грамматики ирегулярные языки• Контекстно-свободные грамматикиявляются обобщением регулярныхграмматик• Центральная вставка A → αAβ• Пример:–The luggage arrived.–The luggage that the passengers checked arrived.–The luggage that the passengers that the stormdelayed checked arrived.28 октября 2011 г.Грамматика зависимостей• Способность предсказывать арументыпри синтаксическом разборе• Хорошо отражают специфику языков спроизвольным порядком слов• Может быть автоматически получена издерева фразhidnsubjdobjTheyletterdettheonshelfdetthe28 октября 2011 г.Модель управления• Глаголы: транзитивные и нетранзитивные– I found a flight– *I disappeared a flight• Рамка валентности (subcategorizationframe)28 октября 2011 г.Категориальная грамматика• Комбинаторные правила–X/Y, Y\X• примерHarryNPeatsapples(S\NP)/NPS\NPS28 октября 2011 г.NPСинтаксический разбор• Рассматриваемые алгоритмы–Метод рекурсивного спуска (top-down parsing)–Восходящий анализ (bottom-up parsing)–Алгоритм Кока-Янгера-Касами (CKY Parsing)• Не рассматриваемые, но частоиспользуемые алгоритмы–Алгоритм Эрли (Earley parser)–Chart parser–http://en.wikipedia.org/wiki/Category:Parsing_algorithms28 октября 2011 г.ПримерS → NP VPS → Aux NP VPS → VPNP → PronounNP → Proper-NounNP → Det NominalNominal → NounNominal → Nominal NounNominal → Nominal PPVP → VerbVP → Verb NPVP → Verb NP PPVP → Verb PPVP → VP PPPP Preposition NPDet → that | this | aNoun → book | flight | meal | moneyVerb → book | include | preferPronoun → I | she | meProper-Noun → Houston | TWAAux → doesPreposition → from | to | on | near | throughSVPVerbBookNPDetNominalthatNounflight28 октября 2011 г.Метод рекурсивного спуска28 октября 2011 г.Восходящий анализ28 октября 2011 г.Синтаксическая многозначностьSVPVPNPVP!"#$% &'("#)*+ ,)%'- .+-/ 0($1$, 2$ 2'%$(3$ (4.5.
6)7"8'27$)SVPNPVPADVP!"#$% &'("#)*+ ,)%'- .+-/ 0($1$, 2$ 2'%$(3$ (4.5. 6)7"8'27$)28 октября 2011 г.Алгоритм CKY• Шаг 0. Преобразовать грамматику кнормальной форме• Алгоритм (динамическое прогаммирование)28 октября 2011 г.Распознавание28 октября 2011 г.Запоминание путей28 октября 2011 г.Синтаксический разбор28 октября 2011 г.Фрагментирование• Partial parsing, Shallow parsing• Chunking–[NP The morning flight][PP from][NP Denver][VP hasarrived]–[NP The morning flight] from [NP Denver] has arrived28 октября 2011 г.Фрагментирование на основеправилS → PP* NP PP* VP PP*PP → IN NPNP → (Det) Noun* NounNP → Proper-NounVP → VBVP → Aux VB28 октября 2011 г.(Конечный преобразователь)Фрагментирование на основемашинного обучения• Классы BIO• Тренировочное множество - TreebankB_NPI_NP?ClassifierDTNNNNINNNPThemorningflightfromDenverhasarrivedПризнаки: The, DT, B_NP, morning, NN, I_NP, flight, NN, from, IN, Denver, NNP28 октября 2011 г.Заключение• Изучены–некоторые особенности грамматикестественного языка–наиболее используемые типы формальныхграмматик–некоторые алгоритмы синтаксического разбора–подходы к фрагментированию28 октября 2011 г.Следующая лекция• 11 Ноября• Статистические методы синтаксическогоанализа28 октября 2011 г.Введение в обработкутекстовЛекция 6Статистические методы синтаксического анализа11 ноября 2011 г.Мотивация• КС-грамматики не позволяют определитьлучшее дерево разбора (т.е.
устранитьмногозначность)• Более точное моделирование языка, посравнению с n-граммами– распознавание речи– машинный перевод– улучшение текстов11 ноября 2011 г.План• Стохастические контекстно-свободныеграмматики (СКС)–разрешение синтаксической многозначности–моделирование языка• Вероятностная версия алгоритма CKY• Обучение СКС• Проблемы СКС–разделение и слияние нетерминалов–СКС с поддержкой лексики• алгоритм Коллинза• Методы оценки11 ноября 2011 г.Стохастические контекстно-свободныеграмматикиN множество нетерминальных символовмножество терминальных символовΣ(непересекающееся с N)множество правил, каждое вида A → β[p]где A - нетерминал,Rβ - строка символов из множества (Σ ∪ N )∗!p - вероятность правила P (β|A) , P (A → β) = 1βS символ начала11 ноября 2011 г.ПримерГрамматикаВероятностьS → NP VPS → Aux NP VPS → VPNP → PronounNP → Proper-NounNP → Det NominalNominal → NounNominal → Nominal NounNominal → Nominal PPVP → VerbVP → Verb NPVP → VP PPPP → Prep NP11 ноября 2011 г.0.80.10.10.20.20.60.30.20.50.20.50.31.0+ 1.0+ 1.0+ 1.0+ 1.0ЛексиконDet → the | a | that | this0.6 0.2 0.1 0.1Noun → book | flight | meal | money0.1 0.50.2 0.2Verb → book | include | prefer0.50.20.3Pronoun → I | he | she | me0.5 0.1 0.1 0.3Proper-Noun → Houston | NWA0.80.2Aux → does1.0Prep → from | to | on | near | through0.25 0.25 0.1 0.2 0.2Разрешение многозначности• Вероятноть разбораP (T, S) =n!i=1P (RHSi |LHSi )• Вероятность P (T, S) = P (T )P (S|T ) = P (T )• Выбор наиболее вероятного дереваразбора T̂ (S) = arg max P (T |S)TP (T, S)T̂ (S) = arg maxP (S)TT̂ (S) = arg max P (T, S)TT̂ (S) = arg max P (T )T11 ноября 2011 г.Разрешение многозначностиSSVPVerbBookVPNPDetVerbNPNominalBookthatNPNominalNoundinnerDetNominalNominaltheNounNoundinnerflightNounflightP(T-left) = .05*.20*.20*.20*75*.30*.60*.10*.40=2.2*10 -6P(T-right) = .05*.10*.20*.15*.75*.75*.30*.60*.10*.40=6.1*10 -711 ноября 2011 г.Моделирование языкаP (S) =!P (T, S) =T• Вариант 1:!P (T )T–Этап 1: с помощью n-граммной моделиполучить m лучших предложений–Этап 2: выбрать наиболее веротноепредложение на основе грамматики• Вариант 2:–Модифицировать парсер для предсказанияследующего слова (достаточно направлениеXu et.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
