Презентации лекций (1126940), страница 5
Текст из файла (страница 5)
al. 1996)Обработка текстовМарковская модельмаксимальной энтропии• Позволяет смоделировать сложные признаки(например для определения части речи)T̂ = arg max P (T |W ) = arg maxtTiP (tagi |wordi , tagi1)• Сравнить с марковской модельюT̂ = arg max P (T |W ) = arg maxtTiP (wordi |tagi )P (tagi , tagi#Скрытые марковскиемоделиСкрытые марковскиемодели максимальнойэнтропии1)Обработка текстовПризнаки в MEMM#NNPSecretariatVBZisVBNexpectedTOVBNtorace⇥⇤1P (q|q , o) =expwi fi (o, q)Z(o, q )iVBNtomorrowОбработка текстовДекодирование и обучение• Декодирование - алгоритм Витерби, гдена каждом шаге вычисляетсяvt (j) =Nmaxi=1 vt 1 (i)P (sj |si , ot ), 1jN, 1 < t• Обучение аналогично логистическойрегрессииTОбработка текстовКластеризацияобучение без учителяОбработка текстовМотивация• Данные можноразбить нанесколько групп попринципу схожести• Поиск схожих документов• Поиск схожих слов и терминов• Реферирование документов• Для задач обучения с учителем–Кластер, как признак для обучения–Кластер, как набор данных для обученияОбработка текстовВход для алгоритмов• Пусть каждый документ {x1 , x2 , .
. . , xk }представлен вектором xi = (xi1 , xi2 , . . . , xin )в пространстве X Rn• Задается расстояние между векторами–Евклидово–Чебышева–Хэмминга–Минковского–...Обработка текстовВзвешивание слов• Частота слова в документе (tf)• tf-idfОбработка текстовПлан• Иерархическая кластеризация• k-means• Affinity propogation• MeanShift• Спектральная кластеризация• WARD• DBSCANОбработка текстовИерархическая кластеризация• Строится дендрограмма - деревообозначающее вложеннуюпоследовательность кластеровОбработка текстовТипы иерархической кластеризации• Агломеративная–каждая точка - кластер–объединяем два наиболее близких кластера водин–останавливаемся, когда все данныеобъединены в один кластер• Дивизимная–все данные - один кластер–разделяем наименее плотный кластер на два–останавливаемся, когда достиглиминимального допустимого размераОбработка текстовРасстояние между кластерами• Между двумя ближайшими точками–Можно получить кластеры произвольнойформы–“Эффект цепи”• Между двумя самыми дальними точками–Чувствителен к выбросам• Среднее расстояниеОбработка текстовK-средних• Алгоритм k-means разбивает данные на kкластеров–Каждый кластер имеет центр - центроид–Параметр k - задается вручную• Алгоритм1.Выбираются k точек в качестве начальныхцентроидов2.Сопоставить каждой точке ближайший центроид3.Пересчитать центроиды4.Если алгоритм не сошелся перейти на шаг 2Обработка текстовКритерий останова• Нет перехода точек в другой кластер• Нет (незначительно) изменениецентроидов• Мало убывает погрешность (sum ofsquared error)kSSE =dist(x, mj )2j=1 x CjОбработка текстовK-средних.
ПримерОбработка текстовK-средних. ПримерОбработка текстовK-средних. ПримерОбработка текстовK-средних. ПримерОбработка текстовK-средних. ПримерОбработка текстовПроблемы• Алгоритм чувствителен к начальномувыбору центроидов–запуск с различной начальной инициализациейи выбор варианта с наиболее плотнымикластерами• Чувствителен к выбросам–можно фильтровать выбросы• Не подходит для нахождения кластеров,не являющихся элипсоидами–преобразование пространстваОбработка текстовКакой алгоритм выбрать*http://scikit-learn.org/stable/modules/clustering.htmlОбработка текстовЧто делать*http://scikit-learn.org/stable/tutorial/machine_learning_map/index.htmlОбработка текстовСледующая лекция• Статистические методы поискасловосочетанийОбработка текстовОсновы обработки текстовЛекция 5 Статистические методы поиска словосочетанийОбработка текстовСловосочетания/коллокации• Для данной лекции Словосочетания = Коллокации = Фразеологические обороты -‐ цепочки слов состоящие из двух или более элементов, имеющее признаки синтаксически и семантически целостной единицы, в котором выбор одного из компонентов осуществляется по смыслу, а выбор второго зависит от выбора первого • Примеры: – Крепкий чай (не “сильный чай”) – Схема Бернулли (сравнить значения со значениями “Схема” и “Бернулли”)Обработка текстовПриложения• Сравнения корпусов текстов –кластеризация документов в информационном поиске –Поиск плагиата • Синтаксический разбор • Компьютерная лексикография • Генерация естественного языка • Машинный перевод • Выделение ключевых слов (терминов)Обработка текстовВыделение словосочетанийОбработка текстовПоиск кандидатов• Основная предпосылка –Если два (или более) слова встречаются вместе часто, то, вероятно, это словосочетание • Инструменты –Частота –Частота и фильтрация по тэгам –Математическое ожидание и дисперсияОбработка текстовЧастота• Подсчет частоты n-‐грам • Выбрать наиболее встречающиеся • Результат –Корпус: New York Times • August-‐November, 1990 –Результат не интересенОбработка текстовЧастота с фильтрацией по тэгам• Подсчет частоты n-‐грам • определить части речи • фильтрация кандидатов по шаблонам для частей речи • выбрать наиболее встречающиесяОбработка текстовЧастота с фильтрацией по тэгамОбработка текстовМат.
ожидание и дисперсия• Часто устойчивые пары слов находятся не рядом –Пример • She knoked on his door • They knoked on the door • a man knocked on the metal front door –Важно это понимать, например при генерации текстовОбработка текстовМат. ожидание и дисперсия• Техника –Рассмотрим все пары слов в некотором окне –Посчитаем расстояние между словами • Меры –Мат. ожидание (возможно отрицательное) • Показывает на сколько часто два слова встречаются вместе –Дисперсия (среднеквадратичное отклонение) • Вариабельность позицииОбработка текстовМат. ожидание и дисперсияShe knocked on his door Пары в окне длиной 3: She knocked She on She his knocked on knocked his knocked door on his on door his 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=i,jOij EijEij• Результат – Смотрим число в таблице для распределения χ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Обработка текстовЗаключение• Поиск словосочетаний может улучшить качество многих приложений • Для поиска словосочетаний могут использоваться простые статистические модели в комбинации эвристиками • Для проверки “значимости” словосочетаний применяются методы проверки статистических гипотезОбработка текстовСледующая лекция• Синтаксический анализОбработка текстов Основы обработки текстовЛекция 6 Формальные грамматики и синтаксический анализОбработка текстовПример синтаксическогоразбораОбработка текстовГде может быть полезнознание синтаксиса?• Машинный перевод• Генерация текста–диалоговые системы• Извлечение информации• Понимание на что/кого направленоэмоциональное высказывание• ...Обработка текстовПлан• Грамматика естественного языка• Формальные грамматики–Контекстно-свободные грамматики–Грамматики зависимостей–Категориальные грамматики• Синтаксический разбор• Группировка (Фрагментирование)Обработка текстовГрамматика составляющих• именная группа (группасуществительного, noun phrase, NP)• группа прилагательного (adjectival phrase,ADJP)• наречная группа (adverbial phrase, ADVP)• предложная группа (prepositional phrase,PP)• глагольная группа (verb phrase, VP);Обработка текстовПримерSNPPPNPVPNPЭти школьники скоро будут писать диктант по русскому языку[S[NP Эти школьники] скоро[VP будут писать][NP диктант[PP по [NP русскому языку]]]]Обработка текстовКонтекстно свободные грамматикиNoun→ flights | breeze | trip | morningVerb→ is | prefer | like | need | want| flyAdjective→ cheapest | non-stop | first | latest | other | directPronoun→ me | I | you | itProper-Noun → Alaska | Los Angeles | ChicagoDeterminer → the | a | an | this | these | thatPreposition → from | to | on | nearConjunction → and | or | butSNPNominalVPPP→ NP VP→ Pronoun| Proper-Noun| Det Nominal→ Nominal Noun| Noun→ Verb| Verb NP| Verb NP PP| Verb PP→ Preposition NPI + want a morning flightILos Angelesa + flightmorning + flightflightsdowant + a flightleave + Boston + in the morningleaving + on Thursdayfrom + Los AngelesОбработка текстовПримерSNPVPProVerbIpreferNPDetaNomNomNounNounflightmorningОбработка текстовФормальное определениеN множество нетерминальных символовмножество терминальных символов(непересекающееся с N)множество правил, каждое вида AR где A - нетерминал,- строка символов из множества ( ⇥ N )S символ началаОбработка текстовСогласование• Пример–по русскому языку–русский язык• Проблема: Увеличение количестваправил• Решение: Введение параметров длянетерминальных символов–см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
