lecture7-2015 (1126926)

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

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

Обработка текстовОсновы обработки текстовЛекция 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• Сложность понимания людьми–чем проще конструкция, тем легче пониманиесмысла текстаОбработка текстовЗаключение• Статистические модели, такие как СКСпозволяют разрешать многозначность• СКС может можно выучить на основебанка деревьев• Учет лексики и разделениенетерминальных символов позволяетразрешить дополнительныенеоднозначности• Точность современных алгоритмовсинтаксического разбора высока, но недостигает уровня экспертного разбораОбработка текстовСледующая лекция• Лексическая семантика и разрешениелексической многозначности.

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

Тип файла PDF

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

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

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