Слайды со всех лекций (1126919), страница 5

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

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

al 2002)11 ноября 2011 г.Вероятностная версияалгоритма CKY• Добавляем в каждую ячейку вероятностьнетерминального символа• Ячейка [i,j] должна содержать наиболеевероятный вывод, покрывающий c i+1 по jслова и содержать их вероятность.• При трансформации граматики кнормальной форме необходимосохранить вероятности правил11 ноября 2011 г.Преобразование грамматикиОригинальная грамматика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 NP11 ноября 2011 г.0.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:.511 ноября 2011 г.through HoustonВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightNoneVP:.5*.5*.054=.0135Det:.6NP:.6*.6*.15=.054Nominal:.15Noun:.511 ноября 2011 г.through HoustonВероятностная версияалгоритма CKYBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflightS:.05*.5*.054=.00135NoneDet:.6VP:.5*.5*.054=.0135NP:.6*.6*.15=.054Nominal:.15Noun:.511 ноября 2011 г.through 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:.211 ноября 2011 г.Вероятностная версияалгоритма 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:.811 ноября 2011 г.Вероятностная версияалгоритма 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:.811 ноября 2011 г.Вероятностная версияалгоритма 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:.811 ноября 2011 г.Вероятностная версияалгоритма 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:.811 ноября 2011 г.Вероятностная версияалгоритма 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:.811 ноября 2011 г.Вероятностная версияалгоритма 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:.811 ноября 2011 г.Обучение СКС• Вычисление вероятности на основе банкадеревьевCount(α → β)Count(α → β)P (α → β|α) = !=Count(α)γ Count(α → β)• Вывод без тренировочного множества (EM)–На основе множества предложений построитьмножество наиболее вероятных синтаксическихразборов–Обновить значения вероятностей на осонвеполученных данных–(Manning and Schutze 1999)11 ноября 2011 г.Проблемы СКС• Предположение о независимости правил,не позволяет хорошо моделироватьструктурные зависимости в дереверазбора• СКС не могут моделироватьсинтаксические факты о конкретныхсловахS → NP VPS → VPNP → Det A NNP → NP PPNP → PropNA→εA → Adj APP → Prep NPVP → V NPVP → VP PPEnglish11 ноября 2011 г.0.90.10.50.30.20.60.41.00.70.3John put the dog in the pen.SNPPCFGParserJohnVPVputNPPPthe dog in the penПроблемы СКС• Предположение о независимости правил,не позволяет хорошо моделироватьструктурные зависимости в дереверазбора• СКС не могут моделироватьсинтаксические факты о конкретныхсловахS → NP VPS → VPNP → Det A NNP → NP PPNP → PropNA→εA → Adj APP → Prep NPVP → V NPVP → VP PPEnglish11 ноября 2011 г.0.90.10.50.30.20.60.41.00.70.3John put the dog in the pen.PCFGParserXSNPJohnVPVputNPthe dog in the penПроблема зависимостей• Для добавления контекстуальнойинформации нетерминалы можноразделить на несколько, используяродительские узлы в дереве разбора(parent annotation)SNP^SNNP ^NPJohnVP^S → VBD^VP NP^VPVP ^SVBD ^VPlikedNP^VPDT^NPNominal ^NPPP^Nominalthe Nominal^NominalNNIN^PP^NominaldoginNP^PPDT^NPNominal ^NPtheNN ^Nominalpen11 ноября 2011 г.Разделение и слияние• Разделение нетерминальных символовсильно увеличивает грамматику• Лучше разделять нетерминалы, толькоесли это приведет к улучшению точности• Также можно объединять некоторыенетерминальные символы, чтобы достичьболшей точности• Метод: эвристический поиск наилучшейкомбинации разделений и слиянийкоторая будет максимизироватьправдоподобие банка деревьев11 ноября 2011 г.СКС с поддержкой лексики• Расширение правил– VP → VP PP–VP (put) → VP (put) PP (in)– VP (put,VDB) → VP (put, VDB) PP (in,IN)Sliked-VBDNPJohn-NNPNNPJohnVP liked-VBDVBDlikedNPdog-NNDTNominal dog-NNPPin-INthe Nominaldog-NNNNINdoginNPpen-NNDTtheNominalpen-NNNNpen11 ноября 2011 г.Оценка вероятности• Точная оценка невозможна, так как несуществует достаточного количествадеревьев• Необходимо сделать еще предположения(о независимости), которые помогутоценить эти вероятности• Алгоритмы (Collins, 1999), (Charniak, 1997)11 ноября 2011 г.Алгоритм Коллинза• Использует простую производящуюмодель• LHS → LnLn−1…L1H R1…Rm−1Rm• H-вершина группы• L - сиволы слева• R - символы справа• По краям символы STOP• Вероятности левых и правых символовзависят только от вершины группы инетерминала слева11 ноября 2011 г.Пример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)11 ноября 2011 г.Оценка вероятностей• Вероятности можно оценить на основебанка деревьев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))11 ноября 2011 г.Оценка качества алгоритма• Метрика PARSEVAL: пусть P - дереворазбора, созданное алгоритмом, Т дерево разбора, созданное экспертами–Точность = (# правильных компонент в P) / (# компонент в T)–Полнота = (# правильных компонент в P) / (# компонент в P)–F-мера = 2PR / (P + R)• Современные алгоритмы показываютточность и полноту более 90%11 ноября 2011 г.Оценка качества алгоритмаT - дерево, размеченноевручнуюP - вычисленное деревоSSVPVerbbookVPNPDetVPNominalthe NominalNounVerbPPbookPrepNPflight through Proper-NounNPDettheNominalNounflightPrepТочность = 10/12= 83.3%Полнота = 10/12= 83.3%F1 = 83.3%11 ноября 2011 г.NPthrough Proper-NounHouston# компонент: 12PP# компонент: 12# правильных компонент: 10HoustonДелают ли люди синтаксическийразбор?• Психолингвистика• Алгоритмы синтаксического разбора могутбыть использованы для предсказаниявремени, которое потребуется человеку дляпрочтения каждого слова в предложении• Чем выше вероятность слова, тем скоростьчтения больше• Для моделирования этого эффекта требуетсяинкрементальный алгоритм11 ноября 2011 г.Предложения, вводящие взаблуждение• Garden path sentence–Complex houses married students–The horse raced past the barn fell–The students forgot the solution was• Инкрементальные парсеры могут найти иобъяснить сложность таких предложений11 ноября 2011 г.Сложность языка• Является ли естественный языкреулярным?• Является ли естественный языкконтекстно-свободным?• Сложность понимания людьми.11 ноября 2011 г.Заключение• Статистические модели, такие как СКСпозволяют разрешать многозначность• СКС может можно выучить на основебанка деревьев• Учет лексики и разделениенетерминальных символов позволяетразрешить дополнительныенеоднозначности• Точность современных алгоритмовсинтаксического разбора высока, но недостигает уровня экспертного разбора11 ноября 2011 г.Следующая лекция• Лексическая семантика и разрешениелексической многозначности11 ноября 2011 г.Введение в обработкутекстовЛекция 7Лексическая семантика21 ноября 2011 г.Возможные взгляды насемантику• Лексическая семантика–значение индивидуальных слов• Композиционная семантика–как значения комбинируются и определяютновые значения для словосочетаний• Дискурс или прагматика–как значения комбинируются между собой идругими знаниями, чтобы задать значениетекста или дискурс21 ноября 2011 г.План• Основные понятия– слова и отношения между ними– словари и тезаурусы• Вычислительная семантика– Разрешение лексической многозначности– Семантическая близость слов– Некоторые современные направления21 ноября 2011 г.Основные понятия• Значение слова и многозначность• Омонимия VS многозначность–ключ–платформа• Метонимия–Я провел вечер (читая Шекспира)/(за бутылкой)• Зевгма–За окном шел снег и рота красноармейцев• Типы омонимов–омофоны (луг-лук, плод-плот)–омографы (м’ука - мук’а, гв’оздик-гвозд’ик)21 ноября 2011 г.Отношения между словами• Синонимия– Машина / автомобиль• Антонимия– большой / маленький, вверх / вниз, ложь / истина• Обобщение и детализация (hyponym andhypernym/superordinate)– машина - транспорнтое средство– яблоко - фрукт• Меронимы (партонимы) и холонимы– колесо - машина21 ноября 2011 г.Многозначность на практике• Text-to-Speech–омографы• Информационный поиск• Извлечение информации• Машинный перевод0,9000Frequency• Закон Ципфа (Zipf law)0,6750NounVerbAdjAdv0,4500SemCor0,225001234567Sense number21 ноября 2011 г.8910WordNet• База лексических отношений––––содержит иерархиисочетает в себе тезаурус и словарьдоступен on-lineразрабатываются версии для языков кромеанглийского (в т.ч.

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

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