lecture7-2016 (1126937)

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

Текст из файла

Обработка текстов Основы обработки текстовЛекция 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 - ...

слева ...• ПримерФункторHarryNPeatsapples(S\NP)/NPS\NPSNPАргументОбработка текстовСинтаксический разборОбработка текстовСинтаксический разбор• Рассматриваемые алгоритмы–Метод рекурсивного спуска (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Обработка текстовЗаключение• Изучены–некоторые особенности грамматикестественного языка–наиболее используемые типы формальныхграмматик–некоторые алгоритмы синтаксического разбора–подходы к группировкеОбработка текстовСледующая лекция• Статистические методы синтаксическогоанализа.

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

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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