Презентации лекций (1126940), страница 4
Текст из файла (страница 4)
. . wN ) N=• Для биграмм⌅⇤⇤⇥P P (w) = NN1P (w1 w2 ...wN )n1P(w|wiii=11)Обработка текстовЗадача определения частей речи• Задача: назначить каждомуслову класс:–существительное,–глагол,–прилагательное,–местоимение–предлог–...• Открытые классы: существительные,глаголы, ...• Закрытые классы: местоимения, предлоги...Обработка текстовЧасти речи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)S — существительное (яблоня, лошадь, корпус)A — прилагательное (коричневый, таинственный)NUM — числительное (четыре, десять, много)A-NUM — числительное-прилагательное (один,седьмой, восьмидесятый)V — глагол (пользоваться, обрабатывать)ADV — наречие (сгоряча, очень)PRAEDIC — предикатив (жаль, хорошо, пора)PARENTH — вводное слово (кстати, по-моему)S-PRO — местоимение-существительное (она, что)A-PRO — местоимение-прилагательное (который)ADV-PRO — местоименное наречие (где, вот)PRAEDIC-PRO — местоимение-предикатив(некого, нечего)PR — предлог (под, напротив)CONJ — союз (и, чтобы)PART — частица (бы, же, пусть)INTJ — междометие (увы, батюшки)http://www.comp.leeds.ac.uk/ccalas/tagsets/brown.htmlhttp://www.ruscorpora.ru/corporamorph.htmlОбработка текстовПример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')]Обработка текстовТренировочные и проверочные корпуса• Английский язык:–Brown–http://www.archive.org/details/BrownCorpus–NLTK corpora• Русский язык–НКРЯ–http://www.ruscorpora.ru/corpora-usage.htmlОбработка текстовПример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.130894842572Обработка текстовАлгоритмы• Основанные на правилах (rule-based)• Основанные на скрытых марковскихмоделях• Основанные на трансформации (Brilltagger)Обработка текстовАлгоритмы, основанные на правилах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.203263917895Обработка текстов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(wt11Обработка текстовОценка параметровn nnP(w|t)P(t1 11)nt̂1 = arg maxn)nP(wt11t̂n1 = arg max P (w1n |tn1 )P (tn1 )tn1• Предположение 1nn nP (w1 |t1 )=i=1P (wi |ti )• Предположение 2nnP (t1 )=i=1P (ti |ti1)Обработка текстовАвтоматPRSADVVизокнасильнодулоPRSADVSизокнасильнодуло• Необходимо выбрать наиболее вероятнуюпоследовательность тэгов–Алгоритм Витерби для декодированияОбработка текстовАлгоритм Витерби• Алгоритм динамического программирования• Находит наиболее вероятнуюпоследовательность скрытых состояний(тэгов) за линейное (от длины входа) время• Идея: Для подсчета наиболее вероятнойпоследовательности длины k+1 нужнознать:–вероятность перехода между тэгами–вероятность слова при условии тэга–наиболее вероятные последовательности тэговдля последовательностей длины kОбработка текстовАлгоритм ВитербиОбработка текстовПримерThe bear is on the move+ добавим сглаживание Лапласа35Обработка текстовПримерСчитаем вероятностиATATBEZINNNVBPERIODbearismoveonpresidentprogressthe.BEZIN2.05478e-05 2.05478e-05 2.05478e-05NNVBPERIOD0.9993842.05478e-05 0.0004109560.7488620.0003793630.1619880.07132020.0003793630.01479510.696871.60854e-050.02132930.2785190.000176940.002991890.01317740.04591110.5240230.1452720.00758810.2639550.4334450.003069020.3396620.1054170.009278420.10870.5329740.005052520.30960.08841910.06348896.64805e-05ATBEZINNNVBPERIOD1.44877e-059.92753e-050.001999270.001872660.2340432.04847e-051.44877e-050.9993050.0001817520.001872660.005319152.04847e-051.44877e-059.92753e-050.0001817520.06928840.7127662.04847e-051.44877e-059.92753e-050.996910.001872660.005319152.04847e-051.44877e-059.92753e-050.0001817520.7172280.005319152.04847e-051.44877e-059.92753e-050.0001817520.204120.02659572.04847e-050.9998999.92753e-050.0001817520.001872660.005319152.04847e-051.44877e-059.92753e-050.0001817520.001872660.005319150.99985736Обработка текстовПримерЧтобы не работать произведением вероятностей будем суммировать логарифмы вероятностейATBEZINNNVBPERIODbearismoveonpresidentprogressthe.ATBEZINNNVBPERIOD-10.7928-10.7928-10.7928-10.7928-7.79702-0.289201-7.87702-1.82023-0.000616624-2.64058-7.877020.0147951-0.361157-11.0376-3.84767-1.27827-8.6397-5.81185-4.32925-3.08105-1.92915-4.88117-1.33198-0.83599-5.7864-1.07981-2.24983-4.68006-2.21916-0.629282-5.28787-1.17247-2.42567-2.75689-9.6186ATBEZINNNVBPERIOD-11.1422-9.21761-6.21497-6.2804-1.45225-10.7958-11.1422-0.000695169-8.61287-6.2804-5.23644-10.7958-11.1422-9.21761-8.61287-2.66948-0.338602-10.7958-11.1422-9.21761-0.00309457-6.2804-5.23644-10.7958-11.1422-9.21761-8.61287-0.332361-5.23644-10.7958-11.1422-9.21761-8.61287-1.58905-3627-10.7958-0.000101419-9.21761-8.61287-6.2804-5.23644-10.7958-11.1422-9.21761-8.61287-6.2804-5.23644-0.000143403-0.6462237Обработка текстовTheAT-1.79BEZ-1.79IN-1.79NN-1.79VB-1.79(.)-1.79bearisonthemove38Обработка текстовTheATBEZINbearisonthemove-‐12.58-1.79argmax (log(P (T he|AT ))-‐2.08-1.79-1.79NN-1.79VB-1.79(.)-1.79-‐2.15tag2T AGS+log(P (AT |tag))++log(P (AT |tag)))-‐6.12-‐2.62-‐2.42-1.79+(-0.29)+(-0.00) = -2.0839Обработка текстовTheATBEZIN-1.79bear-‐12.58-2.08-‐2.08-1.79-1.79NN-1.79VB-1.79(.)-1.79-‐2.15isonthemoveargmax (log(P (T he|AT ))tag2T AGS+log(P (AT |tag))++log(P (AT |tag)))-‐6.12-‐2.62-‐2.42-1.79+(-0.29)+(-0.00) = -2.0840Обработка текстовTheAT-1.79-2.08BEZ-1.79-14.09IN-1.79-11.05NN-1.79-8.07VB-1.79-9.78(.)-1.7913.91bearisonthemove41Обработка текстовThebearisonthemove-21.76 -23.83 -22.87 -13.62 -35.56AT-1.79-2.08BEZ-1.79-14.09 -20.37 -11.44 -28.53 -32.66 -33.12IN-1.79-11.05 -14.93 -17.62 -13.26 -25.72 -30.08NN-1.79-8.07 -8.36 -16.57 -20.36 -20.82 -16.29VB-1.79-9.78 -14.32 -18.47 -24.55 -27.14 -24.75(.)-1.7913.91 -20.20 -20.48 -26.45 -29.87 -32.2242Обработка текстовThebearisonthemove-21.76 -23.83 -22.87 -13.62 -35.56AT-1.79-2.08BEZ-1.79-14.09 -20.37 -11.44 -28.53 -32.66 -33.12IN-1.79-11.05 -14.93 -17.62 -13.26 -25.72 -30.08NN-1.79-8.07 -8.36 -16.57 -20.36 -20.82 -16.29VB-1.79-9.78 -14.32 -18.47 -24.55 -27.14 -24.75(.)-1.7913.91 -20.20 -20.48 -26.45 -29.87 -32.22the/AT bear/NN is/BEZ on/IN the/AT move/NNВероятность: 8.34932985587e-0843Обработка текстовПример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.934900650397Обработка текстовРазделяем тренировочный ипроверочный корпуса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.811023622047Обработка текстовИспользуем биграммыbigram_tagger = nltk.BigramTagger(train_sents)print bigram_tagger.evaluate(test_sents)# 0.102162862554Добавим сглаживание (backoff):t0 = nltk.DefaultTagger('NN')t1 = nltk.UnigramTagger(train_sents, backoff=t0)t2 = nltk.BigramTagger(train_sents, backoff=t1)print t2.evaluate(test_sents)# 0.844712448919Обработка текстовАлгоритмы,основанные на трансформации• Алгоритм–Выбрать правило, дающее наилучший результат–Выбрать правило, исправляющее наибольшееколичество ошибок–и т.
д.• Шаблоны–Предыдущее (следующее) слово имеет тэг X–Два слова перед (после) имеют класс X–Предыдущее слово имеет класс X, а следующее класс Z–...Обработка текстовКакие можно встретить трудности• Разбиение на лексемы–would/MD n’t/RB–children/NNS ‘s/POS• Неизвестные слова–использовать равномерное распределение–использовать априорное распределение–использовать морфологию словОбработка текстовЗаключение• N-граммы - один из наиболее используемыхинструментов при обработке текста• Вероятности оцениваются с помощью методамаксимального правдоподобия• Сглаживание позволяет лучше оцениватьвероятности, чем ММП• Для оценки качества модели могутиспользоваться внутренние и внешние оценки• Задача определения частей речи состоит вназначении метки с частью речи каждому слову• Параметры скрытой марковской модели могутбыть определены из размеченного корпусаОбработка текстовСледующая лекция• Статистические методы поискасловосочетанийОбработка текстовВведение в обработкутекстовЛекция 4Методы классификации и кластеризацииОбработка текстовМодели классификации• Производящие (наивная байесовскаямодель, скрытые марковские модели)– предполагают независимость наблюдаемыхпеременных• Разделяющие (логистическая регрессия,модель максимальной энтропии,марковские модели максимальнойэнтропии)Обработка текстовПлан• Наивный байесовский классификатор• Линейная регрессия• Логистическая регрессия• Модель максимальной энтропии• Марковская модель максимальнойэнтропииОбработка текстовЗадача классификации• Есть множество классов и множествообъектов, которые могут относиться кодному или более классам.• Задача состоит в отнесении объектов снеизвестным классом к одному или болееклассов• Факторы, на основе которых делаетсяпредсказание класса, называютсяпризнаками (feature)• Пример, классификация людей по расамна основе цвета кожи и формы глаз.Обработка текстовНаивный байесовскийклассификатор• Выбор наиболее вероятного значенияŝ = arg max P (s|f )s S• По правилу БайесаP (s)P (f |s)ŝ = arg max= arg max P (s)P (f |s)P (f )s Ss S• Наивное предположение об условнойнезависимости признаковnŝ = arg max P (s)s Sj=1P (fi |s)Обработка текстовОбучение наивногобайесовского классификатора• Метод максимального правдоподобия• Другими словам, просто считаем• Алгоритм прост в реализации, но– Исчезновение значащих цифр àиспользовать сумму логарифмов вместопроизведения– Нулевые вероятность à сглаживание илипредположение о распределении P (fj |s)Обработка текстовПримерfrom sklearn.nayve_bayes import *corpus = [['list of texts'],['classes']]# initialize classifierclassifier = MultinominalNB()# use unigrams and bigrams as featuresvectorizer = CountVectorizer(ngram_range=(1,2))y = corpus[1]X = vectorizer.fit_transform(corpus[0])classifier.fit(X,y) # train classifier#transform new texts into feature vectorsunseen_texts = ["list of unseen texts"]feature_vectors = vectorizer.transform(unseen_texts)answers = classifier.predict(feature_vectors)Обработка текстовМодель максимальной энтропии• Полиномиальная логистическаярегрессия• Модель классификации вида1p(c|x) = exp(Zwi fi )iОбработка текстовЛинейная регрессияКол-во неопределенныхприлагательныхПрибыль сверхзапрашиваемой430$10002$15002$60001$140000$18000price = w0 + w1 N um AdjectivesОбработка текстовЛинейная регрессияy = -4900x+16550Обработка текстовЛинейная регрессияprice = w0 + w1 N um Adjectives + w2 M ortgage Rate + w3 N um U nsold Houses• В терминах признаковNprice = w0 +wifii=1• введем дополнительный признак f0 = 0Ny=wii=0fiилиy =w·fОбработка текстовВычисление коэффициентов• Минимизировать квадратичнуюпогрешностьMj(ypredcost(W ) =j2yobs )j=0• Вычисляется по формулеW = (X X)T1T⇥X yОбработка текстовЛогистическая регрессия• Перейдем к задаче классификации• Определить вероятность, с которойнаблюдение относится к классу• Попробуем определить вероятность черезлинейную модельNP (y = true|x) =i=0wi ⇥ fi = w · fОбработка текстовЛогистическая регрессия• Попробуем определить отношениевероятности принадлежать классу квероятности не принадлежать классуP (y = true|x)=w·f1 P (y = true|x)Обработка текстовЛогистическая регрессия• Проблема с несоответствием областизначений решается вводом натуральногологарифмаlnP (y = true|x)1 P (y = true|x)⇥=w·f• Логит-преобразованиеlogit(P (x)) = lnP (x)1 P (x)⇥• Определим вероятность ...Обработка текстовЛогистическая регрессияw·feP (y = true|x) =1 + ew·f1P (y = f alse|x) =1 + ew·f• Или1P (y = true|x) =1+ew·fw·feP (y = f alse|x) =1+e• Логистическая функция11+exw·fОбработка текстовЛогистическая регрессияP (y = true|x) > P (y = f alse|x)P (y = true|x)>11 P (y = true|x)w·fe>1w·f >0Nwi fi > 0i=0разделяющая гиперплоскостьОбработка текстовПолиномиальнаялогистическая регрeссия• Классификация на множество классов1p(c|x) = exp(Zp(c|x) = ⇤cwi fi )iexpC⇤Nexpi=0wci fi⇤Ni=0⇥wc i fi⇥Обработка текстовПризнаки• Принято использовать бинарные признаки• Индикаторная функция зависящая откласса и наблюдения• Примерf1 (c, x) =1 if suffix(wordi ) = ”ing” & c=VBG0f2 (c, x) =1 if wordi = ”race” & c=NN0Обработка текстовПример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 eОбработка текстовОбучение модели• Найти параметры, которые максимизируютлогарифмическое правдоподобие натренировочном набореNŵ = arg maxwilogP (y i |xi )j=1wj22 j2• Используются методы выпуклойоптимизации• Такой способ позволяет из всех моделей,удовлетворяющих ограничениям тестовойвыборки, выбрать модель с максимальнойэнтропией (Berger et.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
