Презентации лекций (1126940), страница 6

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

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

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Обработка текстовЗаключение• Изучены–некоторые особенности грамматикестественного языка–наиболее используемые типы формальныхграмматик–некоторые алгоритмы синтаксического разбора–подходы к группировкеОбработка текстовСледующая лекция• Статистические методы синтаксическогоанализаОбработка текстовОсновы обработки текстовЛекция 7 Статистические методы синтаксического анализа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-NNPNNPJohnVP likes-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))Обработка текстовОценка качества алгоритма• Метрика PARSEVAL: пусть P - дереворазбора, созданное алгоритмом, Т дерево разбора, созданное экспертами–Точность = (# правильных компонент в P) / (# компонент в T)–Полнота = (# правильных компонент в P) / (# компонент в P)–F-мера = 2PR / (P + R)• Современные алгоритмы показываютточность и полноту более 90%Обработка текстовОценка качества алгоритмаT - дерево, размеченноевручнуюP - вычисленное деревоSSVPVerbbookVPNPDetVPNominalthe NominalNounVerbPPbookPrepNPflight through Proper-NounNPDettheNominalNounflightPrepТочность = 10/12= 83.3%Полнота = 10/12= 83.3%F1 = 83.3%NPthrough Proper-NounHouston# компонент: 12PP# компонент: 12# правильных компонент: 10HoustonОбработка текстовДелают ли люди синтаксическийразбор?• Психолингвистика• Алгоритмы синтаксического разбора могутбыть использованы для предсказаниявремени, которое потребуется человеку дляпрочтения каждого слова в предложении• Чем выше вероятность слова, тем скоростьчтения больше• Для моделирования этого эффекта требуетсяинкрементальный алгоритмОбработка текстовПредложения с временнойнеоднозначностью• Garden path sentence–Complex houses married students–The horse raced past the barn fell• Инкрементальные парсеры могут найти иобъяснить сложность таких предложенийОбработка текстовСложность языка• Является ли естественный языкрегулярным?–контр-пример был на прошлой лекции• Является ли естественный языкконтекстно-свободным?–Диалект немецкого языка в Швейцариисодержит контекстно-зависимые конструкциивида anbmcndm• Сложность понимания людьми–чем проще конструкция, тем легче пониманиесмысла текстаОбработка текстовЗаключение• Статистические модели, такие как СКСпозволяют разрешать многозначность• СКС может можно выучить на основебанка деревьев• Учет лексики и разделениенетерминальных символов позволяетразрешить дополнительныенеоднозначности• Точность современных алгоритмовсинтаксического разбора высока, но недостигает уровня экспертного разбораОбработка текстовСледующая лекция• Лексическая семантика и разрешениелексической многозначностиОбработка текстовОсновы обработкитекстовЛекция 8Лексическая семантикаОбработка текстовВозможные взгляды насемантику• Лексическая семантика–значение индивидуальных слов• Композиционная семантика–как значения комбинируются и определяютновые значения для словосочетаний• Дискурс или прагматика–как значения комбинируются между собой идругими знаниями, чтобы задать значениетекста или дискурсОбработка текстовПлан• Основные понятия– слова и отношения между ними– словари и тезаурусы• Вычислительная семантика– Разрешение лексической многозначности– Семантическая близость слов– Некоторые современные направленияОбработка текстовОсновные понятия• Значение слова и многозначность• Омонимия VS многозначность–ключ–платформа• Метонимия– Я три тарелки съел• Зевгма–За окном шел снег и рота красноармейцев• Типы омонимов–омофоны (луг-лук, плод-плот)–омографы (м’ука - мук’а, гв’оздик-гвозд’ик)Обработка текстовОтношения между словами• Синонимия– Машина / автомобиль• Антонимия– большой / маленький, вверх / вниз, ложь / истина• Обобщение и детализация (hyponym andhypernym/superordinate)– машина - транспорнтое средство– яблоко - фрукт• Меронимы (партонимы) и холонимы– колесо - машинаОбработка текстовМногозначность на практике• Text-to-Speech–омографы• Закон Ципфа (Zipf law)Frequency• Информационный поиск• Извлечение информации• Машинный перевод• Эмоциональная окраска0,90000,6750NounVerbAdjAdv0,4500SemCor0,22500,00001234567Sense number8910Обработка текстовWordNet• База лексических отношений––––содержит иерархиисочетает в себе тезаурус и словарьдоступен on-lineразрабатываются версии для языков кромеанглийского (в т.ч.

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

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