Лекции-2016 (1126938), страница 3
Текст из файла (страница 3)
Русскийморфологический анализ и синтез с генерациеймоделей словоизменения для не описанных всловаре слов.• Используется словарь словоформ А.А. Зализняка• Находит нормальную форму даже для не словарныхслов• Алгоритм реализован в системе mystemОбработка текстовЛемматизация• Вариант русского лемматайзерареализован в ISPRAS API• lemmatizationAnnotate(text)Так говорила в июле 1805 года известная Анна Павловна Шерер, фрейлина иприближенная императрицы Марии Феодоровны, встречая важного и чиновного князяВасилия, первого приехавшего на ее вечер.
Анна Павловна кашляла несколько дней,у нее был грипп, как она говорила (грипп был тогда новое слово, употреблявшеесятолько редкими). В записочках, разосланных утром с красным лакеем, было написанобез различия во всех: так говорить в июль 1805 год известный анна павловна шерер фрейлин иприближенный императрица мария феодоровна встречать важный и чиновнойкнязь василий первый приехавший на она вечер анна павловна кашлялнесколько день у она быть грипп как она говорить грипп быть тогда новый словоупотребляться только редкий в записочка разосылать утро с красный лакейбыть писать без различие в весьОбработка текстовОпределение границ предложений• Поиск терминов необходимо производитьвнутри предложений• Как автоматически определять границыпредложений?• Обычно определяются по точке• Точка - имеет много значений• граница предложения• сокращение: “Dr.”, “U.S.A.”• Разделитель в числах 3.14•…Обработка текстовОпределение границ предложений• Необходимы алгоритмы разрешениямногозначности точки• Задача сводится к классификации точки на двакласса: конец предложения или нет• Например, можно написать список правил• перед точкой и после нее стоят цифры• слово перед точкой есть в словаресокращений• Правил может быть много и хочется выводить ихкомбинировать автоматически• Используется машинное обучениеОбработка текстовЗакон ЦипфаЗакон Ципфа — эмпирическая закономерность распределения частоты словестественного языка: если все слова языка (или просто достаточно длинноготекста) упорядочить по убыванию частоты их использования, то частота n-го словав таком списке окажется приблизительно обратно пропорциональной егопорядковому номеру n.
(Википедия)Обработка текстовЗакон Ципфа• Распределение частоты слов в первом томе“Война и мир” (логарифмическая шкала)from urllib import urlopen from bs4 import BeautifulSoup as bs from nltk import WordPunctTokenizer from collections import Counter import matplotlib.pyplot as plt f = urlopen("http://az.lib.ru/t/tolstoj_lew_nikolaewich/text_0040.shtml") data = f.read().decode("cp1251") f.close() text = bs(data).get_text() tokens = WordPunctTokenizer().tokenize(data) cnt = Counter(tokens).most_common() # draw plot X = range(len(cnt)) Y = [y[1] for y in cnt] plt.loglog(X, Y) plt.show()Обработка текстовСтоп-слова• Во многих задачахиспользование наиболеечастотных слов создает шум• Например, при полнотекстовомпоиске, система может вернутьпочти все документы, если взапросе были предлоги• Поэтому часто наиболеечастотные слова фильтруют и неиспользуют при анализебытьвотвыдаещеикакмыненетоониотссказатьтолькоуэтотбольшойввсеговоритьдляжеизкоторыйнанегониходиноноотосвойтатотчтоябывесьвсейгоддознатькмочьнашнееноонаоныйпосебятакойтыэтоhttp://www.artlebedev.ru/everything/yandex/site/saved/stopword.htmlОбработка текстовРезюме• Изучены регулярные выражения–регулярные выражения - мощный инструмент дляобработки текстов–любое регулярное выражение может быть реализовано спомощью КА (кроме памяти)–автомат неявно определяет формальный язык–для любого НКА существует ДКА• Рассмотрены базовые задачи обработки текстов–Токенизация и сегментация–Стемминг и лемматизация–Определение границ предложений–Фильтрация стоп-слов• Для представления результатов работы алгоритмовудобно использовать аннотацииОбработка текстовЗадания для тренировки• Написать аналог ELIZA• Реализовать конечный автомат дляраспознавания всех русских числительных• Спроектировать КА для дат: March 12, the22nd of November, Christmas• Расширить предыдущий автоматотносительными датами: yesterday,tomorrow, a week from tomorrow, the daybefore yesterday, three weeks fromSaturday, next Monday, ...Обработка текстовСледующая лекция• Языковые модели• Задача определения частей речи словОбработка текстовОсновы обработки текстовЛекция 3 Языковые модели и задача определения частей речи1Обработка текстовN-граммы• Формализация процессапредсказания с помощьюмоделей N-граммОсенью часто идет ...• N-грамма–последовательность из Nслов–модель предсказания...
на одном из этапов для ...... одном на из для этапов ...Обработка текстовПриложения• Определение языка• Распознавание речи• Распознавание письменного текста• Машинный перевод• Определение частей речи• Выделение терминов• Генерация текстов• Поиск семантических ошибок–Hi is trying to fine outОбработка текстовПример генератора:Яндекс рефератыТема: «Естественный позитивизм: сомнение илиощущение мира?»Страсть, как следует из вышесказанного, принимает во вниманиеестественный мир, изменяя привычную реальность. Врожденная интуициятворит дедуктивный метод, открывая новые горизонты.
Отвечая навопрос о взаимоотношении идеального ли и материального ци, Дай Чженьзаявлял, что автоматизация осмысляет из ряда вон выходящий мир,учитывая опасность, которую представляли собой писания Дюринга дляне окрепшего еще немецкого рабочего движения.Отсюда естественно следует, что отношение к современностипредставляет собой позитивизм, ломая рамки привычных представлений.Обработка текстовТренировочный и проверочныйкорпуса• Корпус - собрание текстов, объединенныхобщим признаком• Тренировать и тестировать модель надона различных данных• Перекрестная проверка (cross-validation)• Validation datasetОбработка текстовДоступные корпуса• Текстовые–Project Guttenberg–Reuters corpora–lib.ru–Web• Размеченные–Brown corpus–Linguistic Data Consortium–NLTK corpora–Национальный корпус русского языкаОбработка текстовПримеры N-грамм• Юниграммы–кошка, собака, лошадь–а, и, о• Биграммы–пушистая кошка, большая собака–ал, ин, оп• Триграммы–пушистая кошка мурчит, большая собака лает–али, инт, опаОбработка текстовПодсчет вероятности N-грамм• В обучающем корпусе те или иные nграммы встречаются с разной частотой.• Для каждой n-граммы мы можемпосчитать, сколько раз она встретилась вкорпусе.• На основе полученных данных можнопостроить вероятностную модель, котораязатем может быть использована дляоценки вероятности n-грамм в некоторомтестовом корпусе.Обработка текстовОценка вероятностиP("Дубровский принужден был выйти в отставку")=?nP (w1 )==n 12P (w1 )P (w2 |w1 )P (w3 |w1 ) .
. . P (wn |w1 )nk 1P (wk |w1 )k=1• Предположение Марковаn 1P (wn |w1 )• ТогдаnP (w1 )P (wn |wn1)n=k=1P (wk |wk1)А. А. Марков=Обработка текстовОценка вероятности• Метод максимального правдоподобияp(wn |wnp(wn |wn1)=C(wn 1 wn )w C(wn 1 w)C(wn 1 wn )1) =C(wn 1 )Обработка текстовПример• Пусть корпус состоит из трех предложений–<s> I am Sam </s>–<s> Sam I am </s>–<s> I do not like green eggs and ham </s>21P (I| < s >) = = .67 P (< /s > |Sam) = = .53221P (am|I) = = .67P (do|I) = = .333311P (Sam|am) = = .5 P (Sam| < s >) = = .3332Обработка текстовГенератор текстаimport nltkf=open("../data/pushkin.txt")train=nltk.PunktWordTokenizer().tokenize(f.read())f.close()for i in range(3):model = nltk.NgramModel(i+1,train)print (i+1, " “.join(model.generate(10)))# 1 случай .
.# 2 Несколько лет тому назад в неделю страдал от коихбывал# 3 Несколько лет тому назад в одном сословии ,воспитанные одинаковоОбработка текстовСглаживание• Разреженность языка• Ограниченность корпуса–занижена вероятность–вероятность равна нулю• Сглаживание - повышение вероятностинекоторых n-грамм, за счет понижениявероятности другихОбработка текстовМетоды сглаживания• Сглаживание Лапласа (add-one)• Откат (backoff)• Интерполяция• Сглаживание Кнесера-Нея (Kneser-Ney)• Сглаживание Виттена-Белла (Witten-Bell)• Сглаживание Гуда-Тьюринга (Good-Turing)Обработка текстовСглаживание Лапласа• Добавим 1 к встречаемости каждой nграммы• Пусть в словаре V слов, тогда⇥PLaplace(wn |wn 1 )C(wn 1 wn ) + 1=C(wn 1 ) + VОбработка текстовСглаживание Лапласа(практическое применение)• Метод провоцирует сильную погрешностьв вычислениях• Тесты показали, что unsmoothed-модельчасто показывает более точныерезультаты• Следовательно, метод интересен только стеоретической точки зренияОбработка текстовОткат (backoff)• Основная идея: можно оценивать вероятностиN-грамм с помощью вероятностей (N-k)-грамм(0<k<N).• Особенность: метод можно сочетать с другимиалгоритмами сглаживания (Witten-Bell, GoodTuring и т.
д.)• Оценка вероятности в случае триграмм:Обработка текстовКоэффициент α• Коэффициент α необходим длякорректного распределения остаточнойвероятности N-грамм в соответствии сраспределением вероятности (N-1)-грамм.•• Если не вводить α, то P (wn ) > 1Обработка текстовИнтерполяция• Смешение вероятностей n-грамм разнойдлиныP̂ (wn |wn2 wn 1 )• при этом= 1 P (wn |wn+ 2 P (wn |wn+ 3 P (wn )ii=12 wn 1 )1)Обработка текстовИнтерполяция• Значения также могут зависеть отконтекста• Например, если известно, что оценки дляконкретных биграмм достаточно точны, томожно использовать их с большим весомдля оценки вероятности триграммP̂ (wn |wn2 wn1) =++• Для оценкиdatasetn(w1nn2 (wnn3 (wn12 )P (wn |wn 2 wn 1 )12 )P (wn |wn 1 )12 )P (wn )можно использовать validationОбработка текстовМетоды оценки качества моделей• Как понять, что одна модель лучшедругой?• Внешняя оценка (in vivo)–как изменение параметра модели влияет накачество решения задачи• Внутренняя оценка (in vitro)–коэффициент неопределенности (perplexity)Обработка текстовКоэффициент неопределенности(перплексия)• Основан на теории информации• Лучше та модель, которая лучшепредсказывает детали тестовойколлекции (меньше перплексия)1P P (w) = P (w1 w2 .
. . 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Обработка текстовTheATBEZbearisonthemove-‐12.58-1.79-‐2.08-1.79IN-1.79NN-1.79VB-1.79(.)-1.79-‐2.15weight=argmaxj (log(P(T he|AT ))tag2TAGS(log(P (T he|AT ))argmaxtag2T AGS+log(P (AT |tag))++log(P (AT |tagi ))++log(P (AT+weightj 1|tag)))-‐6.12-‐2.62-‐2.42-1.79+(-0.29)+(-0.00) = -2.0839Обработка текстовTheAT-1.79bear-‐12.58-2.08-‐2.08isontheweightj =argmax (log(P (T he|AT ))-1.79tag2T AGSIN-1.79+log(P (AT |tagi ))++weightj 1NN-1.79VB-1.79(.)-1.79BEZ-‐2.15move-‐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.79-13.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.79-13.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Обработка текстовАлгоритмы,основанные на трансформации• Алгоритм–Выбрать правило, дающее наилучший результат–Выбрать правило, исправляющее наибольшееколичество ошибок–и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
