lecture5-2016 (1126936)

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

Текст из файла

Обработка текстовВведение в обработкутекстовЛекция 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.

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Обработка текстовГруппировка при классификациипоследовательностей• Классы + метки• IO (inside, outside)• BIO (begin, inside, outside) - стандарт• BMEWO (begin, middle, end, whole, outside)B_NPBI_NPI?ClassifierDTNNNNINNNPThemorningflightfromDenverhasarrivedОбработка текстовКластеризацияобучение без учителяОбработка текстовМотивация• Данные можноразбить нанесколько групп попринципу схожести• Поиск схожих документов• Поиск схожих слов и терминов• Реферирование документов• Для задач обучения с учителем–Кластер, как признак для обучения–Кластер, как набор данных для обученияОбработка текстовВход для алгоритмов• Пусть каждый документ {x1 , x2 , .

. . , xk }представлен вектором xi = (xi1 , xi2 , . . . , xin )в пространстве X Rn• Задается расстояние между векторами–Евклидово–Чебышева–Хэмминга–Минковского–...Обработка текстовВекторное представлениедокумента• Модель мешка слов (bag of words)• Вес слова–Частота слова в документе (tf)–TF-IDF–Вложение слов (Word Embedding): word2vec,GloVe и т. д.Обработка текстовПлан• Иерархическая кластеризация• 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Обработка текстовСледующая лекция• Методы классификации текстов на основеискусственных нейронных сетей.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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