Лекции-2016 (1126938), страница 4

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

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

д.• Шаблоны–Предыдущее (следующее) слово имеет тэг X–Два слова перед (после) имеют класс X–Предыдущее слово имеет класс X, а следующее класс Z–...Обработка текстовКакие можно встретить трудности• Разбиение на лексемы–would/MD n’t/RB–children/NNS ‘s/POS• Неизвестные слова–использовать равномерное распределение–использовать априорное распределение–использовать морфологию словОбработка текстовЗаключение• N-граммы - один из наиболее используемыхинструментов при обработке текста• Вероятности оцениваются с помощью методамаксимального правдоподобия• Сглаживание позволяет лучше оцениватьвероятности, чем ММП• Для оценки качества модели могутиспользоваться внутренние и внешние оценки• Задача определения частей речи состоит вназначении метки с частью речи каждому слову• Параметры скрытой марковской модели могутбыть определены из размеченного корпусаОбработка текстовСледующая лекция• Статистические методы поискасловосочетанийОбработка текстовОсновы обработки текстовЛекция 4 Статистические методы поиска словосочетанийОбработка текстовСловосочетания/коллокации• Для данной лекции Словосочетания = Коллокации = Фразеологические обороты -­‐ цепочки слов состоящие из двух или более элементов, имеющее признаки синтаксически и семантически целостной единицы, в котором выбор одного из компонентов осуществляется по смыслу, а выбор второго зависит от выбора первого • Примеры: – Крепкий чай (не “сильный чай”) – Схема Бернулли (сравнить значения со значениями “Схема” и “Бернулли”)Обработка текстовПриложения• Сравнения корпусов текстов –кластеризация документов в информационном поиске –Поиск плагиата • Синтаксический разбор • Компьютерная лексикография • Генерация естественного языка • Машинный перевод • Выделение ключевых слов (терминов)Обработка текстовВыделение словосочетанийОбработка текстовПоиск кандидатов• Основная предпосылка –Если два (или более) слова встречаются вместе часто, то, вероятно, это словосочетание • Инструменты –Частота –Частота и фильтрация по тэгам –Математическое ожидание и дисперсияОбработка текстовЧастота• Подсчет частоты n-­‐грамм • Выбрать наиболее встречающиеся • Результат –Корпус: New York Times • August-­‐November, 1990 –Результат не интересенОбработка текстовЧастота с фильтрацией по тэгам• Подсчет частоты n-­‐грамм • определить части речи • фильтрация кандидатов по шаблонам для частей речи • выбрать наиболее встречающиесяОбработка текстовЧастота с фильтрацией по тэгамОбработка текстовМат.

ожидание и дисперсия• Часто устойчивые пары слов находятся не рядом –Пример • She knocked on his door • They knocked on the door • a man knocked on the metal front door –Важно это понимать, например, при генерации текстовОбработка текстовМат. ожидание и дисперсия• Техника – Рассмотрим все пары слов в некотором окне – Посчитаем расстояние между словами • Меры –Мат. ожидание (возможно отрицательное) • Показывает на сколько часто два слова встречаются вместе –Дисперсия (среднеквадратичное отклонение) • Вариабельность позицииОбработка текстовМат. ожидание и дисперсия• she knocked on his door • they knocked at the door • 100 women knocked on Donaldson’s doord=s =2ni=1Пример: knocked ... doordi1d = (3 + 3 + 5)3nni=1 (dind)21n -­‐ число раз, когда два слова встретились di -­‐ смещение между словами d -­‐ выборочное среднее смещенийs=1((323.67)2 + (31.153.67)2 + (53.673.67)2 )Обработка текстовГистограмма• Пример: strong ...

for –“strong [business] support for”Обработка текстовПример• Большое среднеквадратичное отклонение показывает, что сочетание не очень интересноеОбработка текстовПроверка статистических гипотезОбработка текстовПроверка статистических гипотез• Основная идея: слова словосочетания встречаются вместе значительно чаще чем просто случайно • Инструменты: – t-­‐критерий Стьюдента (t-­‐test) – Критерий согласия Пирсона (Хи-­‐квадрат) – Критерий отношения правдоподобия (Likelihood ra|o test)Обработка текстовНулевая гипотеза• H0-­‐слова встречаются независимо –P(w1,w2)=P(w1)P(w2) • Какова вероятность получить словосочетание w1w2, при условии что гипотеза верна? –p=P(w1w2|H0)Обработка текстовT-­‐критерий Стьюдента• Разработан Уильямом Госсетом для оценки качества пива Гиннесс • Рассмотрим распределение выборочного среднего у всевозможных выборок длины n • По ЦПТ, при больших n:Обработка текстовT-­‐критерий Стьюдента• Если для наших данных наблюдаемое выборочное среднее сильно отклоняется от ожидаемого при нулевой гипотезе, то с вероятностью p гипотеза не верна • α -­‐ ошибка первого рода • p < α -­‐ отвергаем гипотезуαОбработка текстовT-­‐критерий Стьюдента• Т-­‐статистика t=xµs2Nµ -­‐ожидаемое мат.

ожидание x -­‐выборочное среднее s2 -­‐выборочная дисперсия N -­‐размер выборки• Распределение Стьюдента (стремится к нормальному при больших N)Обработка текстовT-­‐критерий. Пример• Предположим,что средний рост мужчин в популяции равен 158 см 2x = 169, s = 2600• Для выборки из 200 мужчин 169 158= 3.05• Тогда t =2600200• Для α=0.005: • 3.05>2.576 • отвергаем гипотезуОбработка текстовT-­‐критерий для словосочетаний• Пусть нулевая гипотеза верна • Рассмотрим процесс случайной генерации биграмм, если встретили биграмму w1w2 (с вероятностью p) генерируем 1, в противном случае 0 (схема Бернулли) биномиальное распределение • мат.

ожидание = p • дисперсия = p(1-­‐p) p при малых pt=xµs2Nµ =H0=P(w1)P(w2) x -­‐отношение w1w2 к общему кол-­‐ву биграмм s2 -­‐отношение w1w2 к общему кол-­‐ву биграмм N -­‐общее количество биграммОбработка текстов Пример• new companies (встретилась 8 раз) 15828P (new) =143076684675P (companies) =14307668H0 : P (new companies) = P (new)P (companies) =8x=⇥ 5.59114307668t=xµs2N⇤1015828143076684675⇥ 3.6151430766810775.591 ⇥ 1073.615 ⇥ 105.591⇥10 714307668• не можем отвергнуть гипотезу7⇤ 0.999932Обработка текстовДля корпусаОбработка текстовХи-­‐квадрат• Сравнить наблюдаемые частоты в корпусе с ожидаемыми частотами при верной гипотезе о независимости • Если различие большое -­‐ отвергаем гипотезу • (Выборка должна быть большая)Обработка текстов2χ- общая формула• Меры: –Eij = ожидаемое кол-­‐во коллокаций –Oij = наблюдаемое кол-­‐во коллокаций 2=X (Oiji,jEij )2Eij• Результат – Смотрим число в таблице для распределения χ2• если число в таблице меньше, то отвергаем гипотезуОбработка текстов2χ- для биграммОбработка текстовКритерий отношения правдоподобия• На сколько более правдоподобна одна гипотеза, чем другая • H1: P (w2 |w1 ) = p = P (w2 |¬w1 )• H2: P (w2 |w1 ) = p1 = p2 = P (w2 |¬w1 )(p1 >> p2 )Обработка текстовКритерий отношения правдоподобияH1H2c2p=Nc2p=Nc12p=cc2 1c12p=N c1H1H2P (w2 |w1 )P (w2 |¬w1 )• Так же как в t-­‐критерии предполагаем схему Бернулли и биномиальное распределениеb(k; n, x) = Cnk xk (1 x)n kc12 из с1 биграм-­‐это w1w2c2-­‐c12 из N-­‐с1 биграм-­‐это не w1w2b(c12 ; c1 , p)b(c2c12 ; Nb(c12 ; c1 , p1 )c1 , p)b(c2L(H1 ) = b(c12 ; c1 , p)b(c2 c12 ; N c1 , p)L(H2 ) = b(c12 ; c1 , p1 )b(c2 c12 ; N c1 , p2 )c12 ; Nc1 , p2 )Обработка текстовОтношение правдободобиягдеОбработка текстовРезультат для корпуса• 2log имеет распределение χ2Обработка текстовЗаключение• Поиск словосочетаний может улучшить качество многих приложений • Для поиска словосочетаний могут использоваться простые статистические модели в комбинации эвристиками • Для проверки “значимости” словосочетаний применяются методы проверки статистических гипотезОбработка текстовСледующая лекция• Методы классификации и кластеризации текстовОбработка текстовВведение в обработкутекстовЛекция 5Методы классификации и кластеризацииОбработка текстовПлан• Наивный байесовский классификатор• Линейная регрессия• Логистическая регрессия• Модель максимальной энтропии• Марковская модель максимальнойэнтропииОбработка текстовЗадача классификации• Есть множество классов и множествообъектов, которые могут относиться кодному или более классам.• Задача состоит в отнесении объектов снеизвестным классом к одному или болееклассов• Факторы, на основе которых делаетсяпредсказание класса, называютсяпризнаками (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)Обработка текстовОбучение наивногобайесовского классификатора• Метод максимального правдоподобия• Другими словам, просто считаемcount(s)count(fj , s)P (s) = PP (fj |s) =count(s)s2S count(si )• Алгоритм прост в реализации, но– Исчезновение значащих цифр àиспользовать сумму логарифмов вместопроизведения– Нулевые вероятность à сглаживание илипредположение о распределении 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 = 1Ny=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.

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

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