Диссертация (1090484), страница 3
Текст из файла (страница 3)
В качестве расстояния между словамиможно использовать косинусную близость, которая является скалярным произведением нормализованных векторов. Чем ближе семантические смысли слов,тем больше косинусная близость между векторами слов [27]. Сегодня метод векторного представления слов является одним из важнейших методов обработкитекстов, с помощью которого повышается точность классификации текстов.15Рис.
1.1: Векторное представление слов.Метод векторного представления слов word2vec был предложен в работе [28].word2vec — это набор алгоритмов для вычисления векторных представленийслов. На вход подается набор текстов для обучения, а на выходе набор векторов слов, которые содержатся в текстах. Word2vec собирает статистику посовместному появлению слов в фразах, после чего методами нейронных сетейрешает задачу снижения размерности и выдает на выходе компактные векторные представления слов, в максимальной степени отражающие отношения этихслов в обрабатываемых текстах.
Word2vec реализует две основные архитектуры— Continuous Bag of Words (CBOW) и Skip-gram.16Рис. 1.2: Методы CBOW и SkipGram.Continuous Bag-of-Words (CBOW)JN EG = log Qθ (D = 1|wt , h) + kEw̃∼Pnoise [log Qθ (D = 0|w̃, h)].(1.4)Skip-Gram:JN EG = log Qθ (D = 1|ht , w) + log Qθ (D = 0|hnoise , w).(1.5)В работе [44] был предложен другой метод векторного представления словGloVe. Этот метод учитывает вероятность проявления одного слова в контекстедругого слова в корпусе.Функция потерь для модели GloVe:VXf (Xij )(wiT w̃j + bi + b̃j − log Xij )2 .(1.6)(x/x )α если x ≤ xmaxmaxf (x) =.1в противном случае(1.7)J=i,j=1Где:Близость между двумя словами можно рассчитывать как косинус угла между векторами (скалярное произведение векторов) [45]:17A·Bcos(θ) == qPkAkkBknPn×BqP i.2n2i=1 (Ai )i=1 (Bi )1.2i=1 Ai(1.8)Байесовский метод для классификации текстовБайесовский метод [46] — это класс статистических алгоритмов классификациипо оценке вероятности принадлежности объекта классу.
Для каждого объекта вычисляются функции правдоподобия вероятности принадлежности объектакаждому из классов. Объект принадлежит классу, с максимальной вероятностьпринадлежности [47].Байесовский метод классификации основан на тем, что если известны плотности распределения каждого из классов, то функции вероятности принадлежности объекта каждому из классов можно вычислять аналитическим образом.Этот алгоритм обладает минимальной вероятностью ошибок, он простой и легкореализуется [48].Байесовский метод классификации очень широко используется и дает удивительно хорошие результаты несмотря на его простой принцип, он обладаетпрочную позицию в машинном обучении, в том числе и классификация.
Многиесовременные алгоритмы классификации были разработаны на основе байесовского метода [49].Наивный байесовский классификатор (Naїve Bayes) [50] - это алгоритм классификации, который основан на Байесовском методе с предположением, чтопризнаки объекта являются независимыми.Формула Байеса для условной вероятности:P(A|B) =P(B|A) P(A).P(B)(1.9)Для классификации наивный байесовский классификатор использует модели, в которых объекты представляются в виде векторов значений признаков.18Вероятность принадлежности объекта классу можно записать таким образом:P(c, x1 , x2 , ..., xm ) = P(x1 , x2 , ..., xm , c)(1.10)= P(x1 |x2 , ..., xm , c) P(x2 , ..., xm , c)(1.11)= P(x1 |x2 , ..., xm , c) P(x2 |x3 , ..., xm , c) P(x3 , ..., xm , c)(1.12)= P(x1 |x2 , ..., xm , c) P(x2 |x3 , ..., xm , c)...
P(xm−1 |xm , c) P(xm |c).(1.13)(1.14)Так как признаки объекта независимы, имеем:P(xi |xi+1 , ..., xm , c) = P(xi |c).(1.15)P(c, x1 , x2 , ..., xm ) = P(x1 |c) P(x2 |c)... P(xm |c).(1.16)Получаем:По формуле Байеса для условной вероятности:P(c|x1 , x2 , ..., xm ) ∝ P(c)mYP(xi |c).(1.17)i=1В работе [51] был предложен наивный байесовский подход к классификациитекстов. Каждый текст можно считать как набор слов. Вероятность того, чтослово w относится к классу c выписываем как:Вероятность класса c:P(c) =19nc,N(1.18)где nc - количество текстов класса c, N - суммарное количество текстов вобучаемой выборке.P1 + d∈Dc nwdP P,P(w|c) =k + ẃ d∈Dc nẃd(1.19)где Dc - набор текстов класса c в обучаемой выборке, k - размер словаря.Вероятность того, что данный текст d относится к классу c:P(c|d) = P(c)YP(w|c)nwd ,(1.20)w∈dгде nwd - сколько раз слово w встречается в тексте d, P(d) - константа.Чтобы избежать погрешность вычисления, на практике используются логвероятности:nc,Plog (c) = logN(1.21)P1 + d∈Dc nwdP P,Plog (w|c) = logk + ẃ d∈Dc nẃd(1.22)Plog (c|d) = log P(c)YnwdP(w|c)= Plog (c) +w∈dXnwd Plog (w|c).(1.23)w∈dДля нового текста d класс, к которому он относится определяется как классс наибольшей вероятностью:cd = argmaxć∈C Plog (ć|d).20(1.24)С одной стороны, байесовский классификатор работает очень быстро, егопринцип работы простой и легко реализовать.
С другой стороны, байесовскийклассификатор не учитывает порядок и сематические значения слов в тексте,поэтому он не подходит для задачи классификации текстов по эмоциональнойокраске [52].1.3Метод РоччиоПо методу Роччио [53], каждый объект является точкой во векторном пространстве, каждый класс имеет центроид - усреднение координат всех объектов этогокласса, для нового объекта его класс определяется как класс, центроид которогонаходится ближе всего данного объекта [54].Рис. 1.3: Метод Роччио.Центроид класса c вычисляется как усреднение координат всех текстов векторов этого класса:211 Xµ~ (c) =~v (d),|Dc |(1.25)d∈Dcгде Dc - множество текстов класса c.Класс для нового текста d определяется как ближайший к ~v (d) центроид:cd = argminć∈C distance(~µ(ć), ~v (d)),(1.26)где distance(~x, ~y ) - евклидово расстояние между векторами ~x и ~y .В работе [55] был изучен метод Роччио для классификации текстов, в заключение следует отметить, что метод Роччио лучше работает с классификациейновостей чем байесовский классификатор.1.4Метод «К» ближайших соседей«К» ближайших соседей (англ.
K Nearest Neighbors - KNN) [56] - один из самыхиспользуемых методов классификации. Для классификации объекта рассматриваем его ближайшие соседи в векторном пространстве, объект принадлежиттому классу, которому принадлежат больше всего соседей из этих ближайшихсоседей [57].22Рис. 1.4: Метод KNN.KNN широко используется для классификации текстов. Для начала считаемкоординаты текстов в пространстве [58].
Размер пространства есть количествотерминов в корпусе (объем словаря). Считая TF-IDF для всех текстов в корпусе,получаем представления текста в виде числовых векторов, каждый компонентвектора - важность соответствующего слова для данного текста. Координатытекстов используются для решения различных задач, в том числе классификация. [59]В работе [60] был использован метод KNN для классификации текстов. Эксперименты показали, что классификация текстов с использованием KNN выдаеткачество лучше чем метод Роччио и байесовский классификатор [61]. Недостаток KNN - медленная скорость [62], для классификации нового текста, нужновычислять расстояния между этим текстом со всеми текстами в корпусе, а ихколичество может быть миллионы.
В разделе 3.4 данной работы был предложенвычислительный комплекс алгоритма «К» ближайших соседей с использованием двоичного дерева для повышения скорости работы алгоритма.231.5Метод опорных векторовМетод опорных векторов (англ. Support Vector Machine - SVM) [63] являетсяалгоритмом машинного обучения с учителем, который широко используют длярешения задачи классификации. Основная идея метода заключается в поискегиперплоскости, которые разделяют объектов разных классов с максимальнымзазором в этом пространстве, этот зазор ограничиваются двумя параллельнымигиперплоскости, на которых находятся ближайшие к разделяющей гиперплоскости объекты разделяемых классов [64].
Чем дальше разделяющие гиперплоскости находятся друг от друга, тем меньше средняя ошибка классификацииобъектов. Метод опорных векторов хорошо работает с данными многомерныхпространств [65], многие считают его одним из лучших методов классификации.Рис. 1.5: Метод опорных векторов.Поиск оптимальной разделяющей гиперплоскости [66]:Для начала рассмотрим линейный классификатор для решения задачи клас24сификации. Линейный классификатор - это прямая, которая отделяет объекты(точки) двух классов. Для классификации новой точки, если точка лежит выше прямой, то она принадлежит первому классу, если ниже — второму. Инымисловами, необходимо найти вектор w и b, что для нового объекта x имеем:w.xi + b > 0 ⇒ yi = 1,(1.27)w.xi + b < 0 ⇒ yi = −1.(1.28)Уравнение гиперплоскости, которая разделяет классы в пространстве Rn :w∆xi + b = 0.(1.29)Выбор разделяющей гиперплоскости может быть произвольным, нашей целю является расположение разделяющей гиперплоскости такое, чтобы расстояние между ей и ближайшими к ней объектами обоих классов были максимальным, другими словами надо найти такие w и b, что для некоторого ε > 0 имеем:w.xi + b > +ε ⇒ yi = 1,(1.30)w.xi + b < −ε ⇒ yi = −1.(1.31)Здесь можно умножить w и b на любую константу, неравную нулю, и результат классификации не изменится.
Это свойство позволяет выбрать константутакую, чтобы для ближайших к разделяющей гиперплоскости объектов выполнялись равенство:w.xi + b = yi .(1.32)При оптимальном варианте все пограничные объекты находятся на крае разделяющей полосы, то есть на одинаковом расстоянии к оптимальной разделяю25щей гиперплоскости, а остальные объекты находятся дальше от нее. Умножимпару неравенств на 1ε и выберем ε = 1. Таким образом, для всех объектов xi изобучаемой выборки:w.xi + b ≥ 1, если yi = 1,(1.33)w.xi + b ≤ −1, если yi = −1.(1.34)−1 < w.xi + b < 1 есть уравнение полосы, разделяющую классы. Ширина1разделяющей полосы равна kwk.
Очевидно, что чем больше ширина полосы,тем точнее классифицируются объекты, соответственно, выбор (w, b) с самойширокой полосой является лучшим вариантом.Случай линейной разделимостиЗаписываем уравнение оптимальной разделяющей полосы:y(w.xi + b) ≥ 1.(1.35)1было максимальПереформируем задачу, необходимо найти w и b, чтобы kwkным, следовательно, разделяющая полоса была максимально широкой. Для этого надо минимизировать выражение:kwk2 = w.w.(1.36)при линейных ограничениях y(w.xi + b) ≥ 1. Это задача оптимизации квадратичной функции при линейных ограничениях.Случай отсутствия линейной разделимостиДля обучаемых выборок с ошибками может не существует линейный классификатор. Чтобы допускать ошибки при обучении введем дополнительную переменную ξi > 0, которая является ошибкой на объектах xi ∈ [x1 ..xn ].Переписываем уравнение оптимальной разделяющей полосы:26y(w.xi + b) ≥ 1 − ξi .(1.37)Необходимо решать задачу максимизации разделяющей полосы, или минимизации нормы kwk2 = w.w по w и b при линейных ограничениях y(w.xi + b) ≥1 − ξi .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
