Лекции-2016 (1126938), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Luka)Распознавание и генерация рукописного текстаГенерация текстовых описаний изображений и видео...Константин АрхипенкоНейронные сетиНейронные сети прямого распространенияРекуррентные нейронные сетиРекуррентная нейронная сеть ЭлманаЗатухающий градиент и LSTMПриложения рекуррентных нейронных сетейКлючевые слова для гуглежаkeraskeras examplesword2vecgated recurrent unitcolah’s blogdeep learning bookawesome rnntheanotensorflowsebastian ruderwildmlКонстантин Архипенкоattention mechanismbatch normalizationlayer normalizationawesome tensorflowleavesbreathe tensorflowНейронные сетиОбработка текстов Основы обработки текстовЛекция 7 Формальные грамматики и синтаксический анализОбработка текстовПример синтаксическогоразбораОбработка текстовГде может быть полезнознание синтаксиса?• Машинный перевод• Генерация текста–диалоговые системы• Извлечение информации• Понимание на что/кого направленоэмоциональное высказывание• ...Обработка текстовПлан• Грамматика естественного языка• Формальные грамматики–Контекстно-свободные грамматики–Грамматики зависимостей–Категориальные грамматики• Синтаксический разбор• Группировка (Фрагментирование)Обработка текстовГрамматика составляющих• именная группа (группасуществительного, noun phrase, NP)• группа прилагательного (adjectival phrase,ADJP)• наречная группа (adverbial phrase, ADVP)• предложная группа (prepositional phrase,PP)• глагольная группа (verb phrase, VP);Обработка текстовПримерSNPPPNPVPNPЭти школьники скоро будут писать диктант по русскому языку[S[NP Эти школьники] скоро[VP будут писать][NP диктант[PP по [NP русскому языку]]]]Обработка текстовКонтекстно свободные грамматики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 | butSNPNominalVPPP→ 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Обработка текстовПримерSNPVPProVerbIpreferNPDetaNomNomNounNounflightmorningОбработка текстовФормальное определениеN множество нетерминальных символовмножество терминальных символов(непересекающееся с N)множество правил, каждое вида AR где A - нетерминал,- строка символов из множества ( ⇥ N )S символ началаОбработка текстовСогласование• Пример–по русскому языку–русский язык• Проблема: Увеличение количестваправил• Решение: Введение параметров длянетерминальных символов–см.

Jurafsky, Martin глава 15Обработка текстовОткуда взять грамматику?• Написать вручную• Вывод грамматики по банку деревьев–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))))).))Обработка текстовЭквивалентность грамматик• Эквивалентность–сильная (язык + деревья разбора)–слабая (только язык)• Нормальная форма грамматики(Хомского)– A→BC–A→a• Всегда существует преобразование внормальную форму (слабаяэквивалентность)Обработка текстовКонтекстно-свободные грамматики ирегулярные языки• Контекстно-свободные грамматикиявляются обобщением регулярныхграмматик• Центральная вставка AA⇥• Пример:–The luggage arrived.–The luggage that the passengers checked arrived.–The luggage that the passengers that the stormdelayed checked arrived.Обработка текстовСинтаксическая многозначностьSVPVPNPVPНарод Беларуси будет жить плохо, но недолго (А.Г.

Лукашенко)SVPNPVPADVPНарод Беларуси будет жить плохо, но недолго (А.Г. Лукашенко)Обработка текстовДругие типы грамматикОбработка текстовГрамматика зависимостей• Способность предсказывать аргументыпри синтаксическом разборе• Хорошо отражают специфику языков спроизвольным порядком слов• Может быть автоматически получена издерева разбора на составляющиеhidnsubjdobjTheyletterdettheonshelfdettheОбработка текстовКатегориальная грамматика• Категории фраз:–Состоят из функторов и аргуменов–X/Y - функция из Y в X.

Аргумент присоединяетсяк Y справа, чтобы получилось X–X\Y - ... слева ...• ПримерHarryNPФункторeats(S\NP)/NPS\NPSapplesNPАргументОбработка текстовСинтаксический разборОбработка текстовСинтаксический разбор• Рассматриваемые алгоритмы–Метод рекурсивного спуска (top-down parsing)–Восходящий анализ (bottom-up parsing)–Алгоритм Кока-Янгера-Касами (CKY Parsing)• Не рассматриваемые, но частоиспользуемые алгоритмы–Алгоритм Эрли (Earley parser)–Chart parser–http://en.wikipedia.org/wiki/Category:Parsing_algorithmsОбработка текстовПример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 | throughSVPVerbBookNPDetNominalthatNounflightОбработка текстовМетод рекурсивного спускаОбработка текстовВосходящий анализОбработка текстовАлгоритм CKY• Шаг 0.

Преобразовать грамматику кнормальной форме• Алгоритм (динамическое программирование)Обработка текстовРаспознаваниеBooktheSP, VP,Nominal,Verb,Noun[0,1]flightthroughS, VP, X2[0,2][0,3]DetNP[1,2][1,3]S1, VP1,S2, VP2,S3[0,4][0,5]NP[1,4]Nominal,Noun[2,3]Houston[1,5]Nominal[2,4][2,5]PrepPP[3,4][3,5]NP,ProperNoun[0,1]Обработка текстовЗапоминание путейОбработка текстовСинтаксический разборBookS → NP VPS → X1 VPX1 → Aux NPS → VPS → X2 PPNP → PronounNP → Proper-NounNP → Det NominalNominal → NounNominal → Nominal NounNominal → Nominal PPVP → VerbVP → Verb NPVP → X2 PPX2 → Verb NPVP → Verb PPVP → VP PPPP → Preposition NPtheS, VP, Verb,Nominal,Noun[0,1]flightthroughS1, VP1,S2, VP2,S3S, VP, X2[0,2][0,3]DetNP[1,2][1,3][0,4][0,5]NP[1,4]Nominal,Noun[2,3]Houston[1,5]Nominal[2,4][2,5]PrepPP[3,4][3,5]NP,ProperNoun[0,1]Обработка текстовГруппировка• Partial parsing, Shallow parsing• Chunking, фрагментирование–[NP The morning flight][PP from][NP Denver][VP hasarrived]–[NP The morning flight] from [NP Denver] has arrivedОбработка текстовГруппировка на основе правилS → PP* NP PP* VP PP*PP → IN NPNP → (Det) Noun* NounNP → Proper-NounVP → VBVP → Aux VB(Конечный преобразователь)Обработка текстовГруппировка на основемашинного обучения• Классы BIO (begin, inside, outside)• Тренировочное множество - TreebankB_NPI_NP?ClassifierDTNNNNINNNPThemorningflightfromDenverhasarrivedПризнаки: The, DT, B_NP, morning, NN, I_NP, flight, NN, from, IN, Denver, NNPОбработка текстовЗаключение• Изучены–некоторые особенности грамматикестественного языка–наиболее используемые типы формальныхграмматик–некоторые алгоритмы синтаксического разбора–подходы к группировкеОбработка текстовСледующая лекция• Статистические методы синтаксическогоанализаОбработка текстовОсновы обработки текстовЛекция 8 Статистические методы синтаксического анализа1Обработка текстовМотивация• СКС-грамматики позволяют определитьлучшее дерево разбора (т.е.

устранитьмногозначность)• Более точное моделирование языка, посравнению с n-граммами–––––распознавание речимашинный переводизвлечение информации...выделение ключевых словОбработка текстов• Стохастические контекстно-свободныеграмматики (СКС)–разрешение синтаксической многозначности–моделирование языка• Вероятностная версия алгоритма CKY• Обучение СКС• Проблемы СКС–разделение и слияние нетерминалов–СКС с поддержкой лексики• алгоритм Коллинза• Разбор в грамматику зависимости• Методы оценкиОбработка текстовСтохастические контекстно-свободныеграмматикиN множество нетерминальных символовмножество терминальных символов(непересекающееся с N)множество правил, каждое вида A[p]гдеA - нетерминал,R- строка символов из множества ( ⇥ N )p - вероятность правила P ( |A) , P (A ) = 1S символ началаОбработка текстовПримерГрамматикаВероятностьS → NP VPS → Aux NP VPS → VPNP → PronounNP → Proper-NounNP → Det NominalNominal → NounNominal → Nominal NounNominal → Nominal PPVP → VerbVP → Verb NPVP → VP PPPP → Prep NP0.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Обработка текстовРазрешение многозначности• Вероятность разбораnP (T, S) =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 )TОбработка текстовРазрешение многозначностиSSVPVerbBookVPNPDetVerbNPNominalBookthattheNPNominalNoundinnerDetNominalNominaltheNounNoundinnerflightNounflightP(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 -7Обработка текстовМоделирование языкаP (S) =P (T, S) =TP (T )T• Вариант 1:–Этап 1: с помощью n-граммной моделиполучить m лучших предложений–Этап 2: выбрать наиболее вероятноепредложение на основе грамматики• Вариант 2:–Модифицировать парсер для предсказанияследующего слова (Xu et.

al 2002)Обработка текстовВероятностная версияалгоритма CKY• Добавляем в каждую ячейку вероятностьнетерминального символа• Ячейка [i,j] должна содержать наиболеевероятный вывод, покрывающий c i+1 по jслова и содержать их вероятность.• При трансформации грамматики кнормальной форме необходимосохранить вероятности правилОбработка текстовПреобразование грамматикиОригинальная грамматикаS → NP VPS → Aux NP VP0.80.1S → VP0.1NP → Pronoun0.2NP → Proper-Noun0.2NP → Det NominalNominal → Noun0.60.3Nominal → Nominal Noun 0.2Nominal → Nominal PP0.5VP → Verb0.2VP → Verb NPVP → VP PPPP → Prep NP0.50.31.0Грамматика в нормальной форме ХомскогоS → NP VPS → X1 VPX1 → Aux NPS → book | include | prefer0.01 0.004 0.006S → Verb NPS → VP PPNP → I | he | she | me0.1 0.02 0.02 0.06NP → Houston | NWA0.16.04NP → Det NominalNominal → book | flight | meal | money0.03 0.15 0.06 0.06Nominal → Nominal NounNominal → Nominal PPVP → book | include | prefer0.10.040.06VP → Verb NPVP → VP PPPP → Prep NP0.80.11.00.050.030.60.20.50.50.31.0Обработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightNoneDet:.6NP:.6*.6*.15=.054Nominal:.15Noun:.5through HoustonОбработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightNoneVP:.5*.5*.054=.0135Det:.6NP:.6*.6*.15=.054Nominal:.15Noun:.5through HoustonОбработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054=.0135NP:.6*.6*.15=.054Nominal:.15Noun:.5through HoustonОбработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightthrough HoustonS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054 None=.0135NP:.6*.6*.15=.054NoneNominal:.15Noun:.5NonePrep:.2Обработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightthrough HoustonS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054 None=.0135NP:.6*.6*.15=.054NoneNominal:.15Noun:.5NonePrep:.2PP:1.0*.2*.16=.032NP:.16PropNoun:.8Обработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightthrough HoustonS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054 None=.0135NP:.6*.6*.15=.054Nominal:.15Noun:.5NoneNonePrep:.2Nominal:.5*.15*.032=.0024PP:1.0*.2*.16=.032NP:.16PropNoun:.8Обработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightthrough HoustonS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054 None=.0135NP:.6*.6*.15=.054Nominal:.15Noun:.5NoneNP:.6*.6*.0024=.000864NoneNominal:.5*.15*.032=.0024Prep:.2PP:1.0*.2*.16=.032NP:.16PropNoun:.8Обработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightthrough HoustonS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054 None=.0135S:.05*.5*.000864=.0000216NP:.6*.6*.15=.054NoneNP:.6*.6*.0024=.000864NoneNominal:.5*.15*.032=.0024Nominal:.15Noun:.5Prep:.2PP:1.0*.2*.16=.032NP:.16PropNoun:.8Обработка текстовВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightthrough HoustonS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054 None=.0135NP:.6*.6*.15=.054Nominal:.15Noun:.5S:.03*.0135*.032=.00001296S:.0000216NoneNP:.6*.6*.0024=.000864NoneNominal:.5*.15*.032=.0024Prep:.2PP:1.0*.2*.16=.032NP:.16PropNoun:.8Обработка текстовВероятностная версияалгоритма CKYВыбираем наиболее вероятное дерево разбораBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightthrough HoustonS:.05*.5*.054=.00135NoneDet:.6S:.0000216VP:.5*.5*.054 None=.0135NP:.6*.6*.15=.054Nominal:.15Noun:.5NoneNP:.6*.6*.0024=.000864NoneNominal:.5*.15*.032=.0024Prep:.2PP:1.0*.2*.16=.032NP:.16PropNoun:.8Обработка текстовОбучение СКС• Вычисление вероятности на основе банкадеревьевP(⇥| ) =Count(Count(Count(⇥)⇥)=⇥)Count( )• Вывод без тренировочного множества (EM)–На основе множества предложений построитьмножество наиболее вероятных синтаксическихразборов–Обновить значения вероятностей на основеполученных данных–(Manning and Schutze 1999)Обработка текстовПроблемы СКС• Предположение о независимости правил,не позволяет хорошо моделироватьструктурные зависимости в дереверазбора• СКС не могут моделироватьсинтаксические факты о конкретныхсловахОбработка текстовПримерS → NP VPS → VPNP → Det A NNP → NP PPNP → PropNA→εA → Adj APP → Prep NPVP → V NPVP → VP PP0.90.10.50.30.20.60.41.00.70.3John likes the dog in the pen.SNPPCFGParserVPJohnVlikesNPthe dog in the penEnglishS → NP VPS → VPNP → Det A NNP → NP PPNP → PropNA→εA → Adj APP → Prep NPVP → V NPVP → VP PPEnglish0.90.10.50.30.20.60.41.00.70.3John likes the dog in the pen.SNPPCFGParserJohnVPVlikesNPPPthe dog in the penОбработка текстовПримерS → NP VPS → VPNP → Det A NNP → NP PPNP → PropNA→εA → Adj APP → Prep NPVP → V NPVP → VP PP0.90.10.50.30.20.60.41.00.70.3John put the dog in the pen.SNPPCFGParserVPJohnVNPput the dog in the penEnglishS → NP VPS → VPNP → Det A NNP → NP PPNP → PropNA→εA → Adj APP → Prep NPVP → V NPVP → VP PPEnglish0.90.10.50.30.20.60.41.00.70.3John put the dog in the pen.SNPPCFGParserJohnVPVNPPPput the dog in the penОбработка текстовРешение проблемызависимостей• Для добавления контекстуальнойинформации нетерминалы можноразделить на несколько, используяродительские узлы в дереве разбора(parent annotation)SNP^SNNP ^NPJohnVP^S → VBZ^VP NP^VPVP ^SVBZ ^VPlikesNP^VPDT^NPNominal ^NPPP^Nominalthe Nominal^NominalNNIN^PP^NominaldoginNP^PPDT^NPNominal ^NPtheNN ^NominalpenОбработка текстовРазделение и слияние• Разделение нетерминальных символовсильно увеличивает грамматику• Лучше разделять нетерминалы, толькоесли это приведет к улучшению точности• Также можно объединять некоторыенетерминальные символы, чтобы достичьболшей точности• Метод: эвристический поиск наилучшейкомбинации разделений и слиянийкоторая будет максимизироватьправдоподобие банка деревьевОбработка текстовСКС с поддержкой лексики• Расширение правил– VP → VP PP–VP (put) → VP (put) PP (in)– VP (put,VDB) → VP (put, VDB) PP (in,IN)Slikes-VBZNPJohn-NNPNNPJohnVPlikes-VBZVBZlikesNPdog-NNDTNominal dog-NNPPin-INthe Nominaldog-NNNNINdoginNPpen-NNDTtheNominalpen-NNNNpenОбработка текстовОценка вероятности• Точная оценка невозможна, так как несуществует достаточного количествадеревьев• Необходимо сделать еще предположения(о независимости), которые помогутоценить эти вероятности• Алгоритмы (Collins, 1999), (Charniak, 1997)Обработка текстовАлгоритм Коллинза• Использует простую производящуюмодель• LHS → LnLn−1…L1H R1…Rm−1Rm• H-вершина группы• L - символы слева• R - символы справа• По краям символы STOP• Вероятности левых и правых символовзависят только от вершины группы инетерминала в левой части правилаОбработка текстовПримерVPput-VBD → VBDput-VBD NPdog-NN PPin-INVPput-VBD → STOP VBDput-VBD NPdog-NN PPin-IN STOPL1R1R2R3HVPput-VBDSTOPVBDput-VBDNPdog-NN PPin-IN STOPP(VPput-VBD → VBDput-VBD NPdog-NN PPin-IN) == PH(VBDput-VBD| VPput-VBD) ** PL(STOP | VBDput-VBD, VPput-VBD) ** PR(NPdog-NN | VBDput-VBD, VPput-VBD) ** PR(PPin-IN | VBDput-VBD, VPput-VBD) ** PR(STOP | VBDput-VBD, VPput-VBD)Обработка текстовОценка вероятностей• Вероятности можно оценить на основебанка деревьевPR(PPin-IN | VPput-VBD) =Count(PPin-IN справа от вершины в правиле для VPput-VBD)Count(символы справа от вершины в правиле для VPput-VBD)• Сглаживание можно осуществлять черезоткат или линейную интерполяциюsmPR(PPin-IN | VPput-VBD) = λ1 PR(PPin-IN | VPput-VBD)+ (1− λ1) (λ2 PR(PPin-IN | VPVBD) +(1− λ2) PR(PPin-IN | VP))Обработка текстовРазбор в грамматикузависимостей• Dependency parser–Malt parser (2006)–Stanford Neural Network Dependency Parser (2014)• Итеративный алгоритм разборапредложения w1 , w2 , .

Характеристики

Список файлов лекций