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

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

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

wN )=!1101"−N10–что если 0 встречается в 10 раз чаще?18 октября 2011 г.Задача определения частей речи• Задача: назначить каждомуслову класс:–существительное,–глагол,–прилагательное,–местоимение–предлог–...• Открытые и закрытыеклассы18 октября 2011 г.Части речиADJ adjective (new, good, high, special, big, local)ADV adverb (really, already, still, early, now)CNJ conjunction (and, or, but, if, while, although)DET determiner (the, a, some, most, every, no)EX existential (there, there's)FW foreign word (dolce, ersatz, esprit, quo, maitre)MOD modal verb (will, can, would, may, must, should)N noun (year, home, costs, time, education)NP proper noun (Alison, Africa, April, Washington)NUM number (twenty-four, fourth, 1991, 14:24)PRO pronoun (he, their, her, its, my, I, us)P preposition (on, of, at, with, by, into, under)TO the word to toUH interjection (ah, bang, ha, whee, hmpf, oops)V verb (is, has, get, do, make, see, run)VD past tense (said, took, told, made, asked)VG present (participle making, going, playing, working)VN past participle (given, taken, begun, sung)WH wh determiner (who, which, when, what, where, how)http://www.comp.leeds.ac.uk/ccalas/tagsets/brown.html18 октября 2011 г.S — существительное (яблоня, лошадь, корпус)A — прилагательное (коричневый, таинственный)NUM — числительное (четыре, десять, много)A-NUM — числительное-прилагательное (один,седьмой, восьмидесятый)V — глагол (пользоваться, обрабатывать)ADV — наречие (сгоряча, очень)PRAEDIC — предикатив (жаль, хорошо, пора)PARENTH — вводное слово (кстати, по-моему)S-PRO — местоимение-существительное (она, что)A-PRO — местоимение-прилагательное (который)ADV-PRO — местоименное наречие (где, вот)PRAEDIC-PRO — местоимение-предикатив(некого, нечего)PR — предлог (под, напротив)CONJ — союз (и, чтобы)PART — частица (бы, же, пусть)INTJ — междометие (увы, батюшки)Примерimport nltktext = nltk.word_tokenize("They refuse to permit us toobtain the refuse permit")print nltk.pos_tag(text)[('They', 'PRP'), ('refuse', 'VBP'), ('to', 'TO'), ('permit', 'VB'), ('us', 'PRP'),('to', 'TO'), ('obtain', 'VB'), ('the', 'DT'), ('refuse', 'NN'), ('permit', 'NN')]18 октября 2011 г.Тренировочные и проверочные корпуса• Английский язык:–Brown–http://www.archive.org/details/BrownCorpus–NLTK corpora• Русский язык–НКРЯ–http://www.ruscorpora.ru/corpora-usage.html18 октября 2011 г.Примерimport nltkfrom nltk.corpus import brownbrown_tagged_sents = brown.tagged_sents(categories='news')default_tagger = nltk.DefaultTagger('NN')print default_tagger.evaluate(brown_tagged_sents)# 0.13089484257218 октября 2011 г.Алгоритмы• Основанные на правилах (rule-based)• Основанные на скрытых марковскихмоделях• Основанные на трансформации (Brilltagger)18 октября 2011 г.Алгоритмы, основанные на правилахimport nltkfrom nltk.corpus import brownpatterns = [(r'.*ing$', 'VBG'),(r'.*ed$', 'VBD'),(r'.*es$', 'VBZ'),(r'.*ould$', 'MD'),(r'.*\'s$', 'NN$'),(r'.*s$', 'NNS'),(r'^-?[0-9]+(.[0-9]+)?$', 'CD'),(r'.*', 'NN')]########gerundssimple past3rd singular presentmodalspossessive nounsplural nounscardinal numbersnouns (default)regexp_tagger = nltk.RegexpTagger(patterns)brown_tagged_sents = brown.tagged_sents(categories='news')print regexp_tagger.evaluate(brown_tagged_sents)# 0.20326391789518 октября 2011 г.HMM-based POS tagger• Из окна сильно дулоnt̂1=nnarg max P (t1 |w1 )tn1• Правило БайесаP (y|x)P (x)P (x|y) =P (y)• В нашем случаеn nnP(w|t)P(t1 11)nt̂1 = arg maxn)nP(wt1118 октября 2011 г.Оценка параметровn nnP(w|t)P(t1 11)nt̂1 = arg maxn)nP(wt11t̂n1 = arg max P (w1n |tn1 )P (tn1 )tn1• Предположение 1n nP (w1 |t1 )=n!i=1P (wi |ti )• Предположение 2nP (t1 )=n!i=118 октября 2011 г.P (ti |ti−1 )АвтоматPRSADVV!"#$%&'!()%#*+(#PRSADVS!"#$%&'!()%#*+(#• Необходимо выбрать наиболее вероятнуюпоследовательность тэгов–Алгоритм декодирования18 октября 2011 г.Примерimport nltkfrom nltk.corpus import brownbrown_tagged_sents = brown.tagged_sents(categories='news')unigram_tagger = nltk.UnigramTagger(brown_tagged_sents)print unigram_tagger.evaluate(brown_tagged_sents)# 0.93490065039718 октября 2011 г.Разделяем тренировочный ипроверочный корпусаimport nltkfrom nltk.corpus import brownbrown_tagged_sents = brown.tagged_sents(categories='news')# separate train and test corporasize = int(len(brown_tagged_sents) * 0.9)train_sents = brown_tagged_sents[:size]test_sents = brown_tagged_sents[size:]unigram_tagger = nltk.UnigramTagger(train_sents)print unigram_tagger.evaluate(test_sents)# 0.81102362204718 октября 2011 г.Используем биграммыbigram_tagger = nltk.BigramTagger(train_sents)print bigram_tagger.evaluate(test_sents)# 0.102162862554t0 = nltk.DefaultTagger('NN')t1 = nltk.UnigramTagger(train_sents, backoff=t0)t2 = nltk.BigramTagger(train_sents, backoff=t1)print t2.evaluate(test_sents)# 0.84471244891918 октября 2011 г.Алгоритмы,основанные на трансформации• Алгоритм–Выбрать правило, даующее наилучший результат–Выбрать правило, исправляющее наибольшееколичество ошибок–и т.

д.• Шаблоны–Предыдущее (следующее) слово имеет тэг X–Два слова перед (после) имеют класс X–Предыдущее слово имеет класс X, а следующее класс Z–...18 октября 2011 г.Какие можно встретить трудности• Разбиение на лекемы• Неизвестные слова18 октября 2011 г.Заключение• N-граммы - один из наиболее используемыхинструментов при обработке текста• Вероятности оцениваются с помощью методамаксимального правдоподобия• Сглаживание позволяет лучше оцениватьвероятности, чем ММП• Для оценки качества модели могутиспользоваться внутренние и внешние оценки• Задача определения частей речи состоит вназначении метки с частью речи каждому слову• Параметры скрытой марковской модели могутбыть определены из размеченного корпуса18 октября 2011 г.Следующая лекция• Скрытые марковские модели• Модели максимальной энтропии18 октября 2011 г.Введение в обработкутекстовЛекция 4Марковские модели22 октября 2011 г.Андрей Андреевич Марков• Старший 14.06.1856 20.07.1922• Статистика, МоделиМаркова• Младший 22.09.1903 11.10.1979• Нормальные алгоритмы22 октября 2011 г.Предположения о процессах• (Стационарные процессы) Изменения всостоянии мира вызваны процессом,подчиняющимся законам, которые сами неменяются во времени• (Марковское предположение) Текущеесостояние зависит лишь от конечного числапредыдущих состояний• Марковский процесс первого порядка:P (qi |q1 .

. . qi−1 ) = P (qi |qi−1 )22 октября 2011 г.Цепь маркова• Специальный случай взвешенногоконечного автомата• Входная последоваьельность уникальноопределяет состояния автомата• Q=q q ..q• A=a a ...a• q ,q1 201 020FNsnow...annn12a02a24Startend04a01is1a31a13white3a14a0322 октября 2011 г.Скрытая модель• Q=q q ..q - множество состояний• A=a a ...a ...a - матрица переходов• O=о о ...o - последовательность1 2N01 02n11 2Tnnнаблюдений• B = b (o ) - вероятности наблюдений• q ,qi022 октября 2011 г.FtПримерStart0HotCold12P (1|Hot).2 P (2|Hot)  =  .3 P (3|Hot).422 октября 2011 г.P (1|Cold).5 P (2|Cold)  =  .4 P (3|Cold).1Решаемые задачи• Вычисление вероятности: фильтрация,предсказание• Наиболее правдоподобное объяснение• Вычисление паостериорныхвероятностей: Обучение, сглаживание22 октября 2011 г.Вероятностьпоследовательности•Имея HMM λ = (A, B) ипоследовательность наблюдений O,определить вероятность P (O|λ)• Вычислить вероятность 1 3 122 октября 2011 г.ВероятностьпоследовательностиP (O|Q) =T!i=1HotHotCold313P (oi |qi )P (3, 1, 3|Hot, Hot, Cold) = P (3|Hot) × P (1|hot) × P (3|Cold)22 октября 2011 г.ВероятностьпоследовательностиHot.7Hot.3Cold.4.2.1313P (O, Q) = P (O|Q) × P (Q) ==T!i=1P (oi |qi ) ×T!i=1P (qi |qi−1 )P (3, 1, 3, Hot, Hot, Cold) = P (Hot|Start) × P (Hot|Hot) × P (Cold|Hot)××P (3|Hot) × P (1|Hot) × P (3|Cold)22 октября 2011 г.ВероятностьпоследовательностиP (O) =!QP (O, Q) =!P (O|Q)P (Q)QP (3, 1, 3) = P (3, 1, 3, Cold, Cold, Cold) + P (3, 1, 3, Cold, Cold, Hot) + .

. .•Перебор всевозможных состояний неэффективен• Существует алгоритм со сложностью• Динамическое программирование22 октября 2011 г.O(N T )2Прямой алгоритм•••22 октября 2011 г.α1 (j) = a0j bj (o1 )at (j) =N!i−1at−1 (i)aij bJ (ot ); 1 ≤ j ≤ N, 1 < t ≤ TP (O|λ) = aT (qF ) =N!i=1aT (i)aiFАлгоритм Витерби• Наиболее правдоподобное объяснение• Суть аналогична!прямому алгоритмуmaxНадозаменитьна•• Добавлять обратные ссылкиNi=122 октября 2011 г.Ni=1Обучение• Задача 1: имея размеченный корпусоценить параметры модели• Задача 2: Имея поседовательностьнаблюдений и множество возможныхсостояний модели, оценить параметрымодели• Прямой-обратный алгоритм (АлгоритиБаума-Велша) - для самостоятельногоизучения22 октября 2011 г.Пример22 октября 2011 г.Перерыв 5 минут22 октября 2011 г.Модели классификации• Производящие (наивная байесовскаямодель, скрытые марковские модели)– предполагают независимость наблюдаемыхпеременных• Разделяющие (логистическая регрессия,модель максимальной энтропии,марковские модели максимальнойэнтропии)22 октября 2011 г.План• Линейная регрессия• Логистическая регрессия• Модель максимальной энтропии• Марковская модель максимальнойэнтропии22 октября 2011 г.Модель максимальной этропии• Полиномиальная логистическаярегрессия• Модель классификации вида!1wi fi )p(c|x) = exp(Zi22 октября 2011 г.Линейная регрессияКол-во неопределенныхприлагательныхПрибыль сверхзапрашиваемой430$10002$15002$60001$140000$18000price = w0 + w1 ∗ N um Adjectives22 октября 2011 г.Линейная регрессияy = -4900x+1655022 октября 2011 г.Линейная регрессияprice = w0 + w1 ∗ N um Adjectives + w2 ∗ M ortgage Rate + w3 ∗ N um U nsold Houses• Факторы, на основе которых делаетсяпредсказание, называются признаками(feature)price = w0 +N!i=1wi × fi• введем дополнительный признак f0 = 0y=N!i=022 октября 2011 г.wi × fiилиy =w·fВычисление коэффициентов• Минимизировать квадратичнуюпогрешностьcost(W ) =M!j(ypredj=0−j2yobs )• Вычисляется по формулеW = (X X)T22 октября 2011 г.−1→T−X yЛогистическая регрессия• Перейдем к задаче классификации• Определить вероятность, с которойнаблюдение отностися к классу• Попробуем определить вероятность черезлинейную модельP (y = true|x) =N!i=022 октября 2011 г.wi × fi = w · fЛогистическая регрессия• Попробуем определить отношениевероятности принадлежать классу квероятности не принадлежать классуP (y = true|x)=w·f1 − P (y = true|x)22 октября 2011 г.Логистическая регрессия• Проблема с несоответствием областизначений решается вводом натуральногологарифмаln!P (y = true|x)1 − P (y = true|x)"=w·f• Логит-преобразованиеlogit(P (x)) = ln!P (x)1 − P (x)"• Определим вероятность ...22 октября 2011 г.Логистическая регрессияw·feP (y = true|x) =1 + ew·f1P (y = f alse|x) =1 + ew·f• Или1P (y = true|x) =1 + e−w·feP (y = f alse|x) =1 + e−w·f• Логистическая функция11 + e−x22 октября 2011 г.−w·fЛогистическая регрессияP (y = true|x) > P (y = f alse|x)P (y = true|x)>11 − P (y = true|x)w·fe>1w·f >0N!i=022 октября 2011 г.wi fi > 0разделяющая гиперплоскостьПолиномиальнаялогистическая регрeссия• Классификация на множество классов!1wi fi )p(c|x) = exp(Zi!"#Nexpi=0 wci fi!"#p(c|x) = "N!i=0 wc i fic! ∈C exp22 октября 2011 г.Признаки• Принято использовать бинарные признаки• Индикаторная функция зависящая откласса и наблюдения• Пример.f1 (c, x) =!1 if suffix(wordi ) = ”ing” & c=VBG0f2 (c, x) =!1 if wordi = ”race” & c=NN022 октября 2011 г.ПримерVB fwNN fwf1010.8f2 f3100.800f410.010f5 f6100.101-1.3e0.8 e−1.3p(N N |x) = 0.8 −1.3=0.2e e+ e0.8 e0.01 e0.10.8 0.01 0.1ee ep(V B|x) = 0.8 −1.3= 0.80.80.010.1e e+e e e22 октября 2011 г.Обучение модели• Найти параметры, которые максимизируетлогарифмическое правдоподобие натренировочном набореŵ = arg maxw!iN2!wji ilogP (y |x ) −22σjj=1• Используются методы выпуклойоптимизации• Такой способ позволяет из всех моделей,удовлетворяющих ограничениям тестовойвыборки, выбрать модель с максимальнойэнтропией (Berger et.

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

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