Классификация текстов и анализ тональности

Классификация текстов (документов) (Document classification) — задача компьютерной лингвистики, заключающаяся в отнесении документа к одной из нескольких категорий на основании содержания документа.

Анализ тональности текста (Sentiment analysis) — задача компьютерной лингвистики, заключающаяся в определении эмоциональной окраски (тональности) текста и, в частности, в выявлении эмоциональной оценки авторов по отношению к объектам, описываемым в тексте.

Задачи классификации текстов

Классификация текстов применяется, в том числе, для:

• Разделения веб страниц и сайтов по тематическим каталогам;
• Борьбы со спамом;
• Определение языка текста;
• Показа более релевантной рекламы;

Задачи анализа тональности текста

Основной задачей анализа тональности текста является определение его эмоциональной окраски. Это необходимо, в том числе, для:

• Анализа отзывов о товарах и услугах;
• Определение языка вражды;

В общем случае, задача анализа тональности текста эквивалентна задаче классификации текста, где категориями текстов могут быть тональные оценки. Примеры тональных оценок:

• позитивная;
• негативная;
• нейтральная;

Под «нейтральной» подразумевается, что текст не содержит эмоциональной окраски.

Классификация текстов методами машинного обучения

Постановка задачи

Имеется множество категорий (классов, меток) [math]\mathfrak{C}=\{c_1,...,c_{\left|\mathfrak{C}\right|}\}[/math].

Имеется множество документов [math]\mathfrak{D}= \{ d_1, ... , d_{ \left| \mathfrak{D} \right| } \}[/math].

Неизвестная целевая функция [math]\Phi\colon \mathfrak{C} \times \mathfrak{D} \rightarrow \{ 0, 1 \}[/math].

Необходимо построить классификатор [math] \Phi^\prime [/math], максимально близкий к [math]\Phi[/math].

Имеется некоторая начальная коллекция размеченных документов [math]\mathfrak{R} \subset \mathfrak{C} \times \mathfrak{D}[/math], для которых известны значения [math]\Phi[/math]. Обычно её делят на «обучающую» и «проверочную» части. Первая используется для обучения классификатора, вторая — для независимой проверки качества его работы.

Классификатор может выдавать точный ответ [math]\Phi^\prime\colon \mathfrak{C} \times \mathfrak{D} \rightarrow \{ 0, 1 \}[/math] или степень подобия [math]\Phi^\prime\colon \mathfrak{C} \times \mathfrak{D} \rightarrow [ 0, 1 ][/math].

Этапы подготовки

Этапы подготовки не отличается от обработки текста, описанной выше в анализе тональности.

Алгоритмы классификации

Наивная байесовская модель

Пусть [math]P(c_i|d)[/math] — вероятность того, что документ, представленный вектором [math]d = (t_1, ..., t_n)[/math], соответствует категории [math]c_i[/math] для [math]i = 1, ..., |C|[/math]. Задача классификатора заключается в том, чтобы подобрать такие значения [math]c_i[/math] и [math]d[/math], при которых значение вероятности [math]P(c_i|d)[/math] будет максимальным:

[math]c_m = \underset{c \in C}{\operatorname{argmax}} \, P(c|d)[/math]

Для вычисления значений [math]P(c_i|d)[/math] пользуются теоремой Байеса:

[math]P(c_i|d) = \frac{P(d|c_i)P(c_i)}{P(d)}[/math]

где [math]P(c_i)[/math] – априорная вероятность того, что документ отнесен к категории [math]c_i[/math]; [math]P(d | c_i)[/math] – вероятность найти документ, представленный вектором [math]d = (t_1, ..., t_n)[/math], в категории [math]c_i[/math]; [math]P(d)[/math] – вероятность того, что произвольно взятый документ можно представить в виде вектора признаков [math]d = (t_1, ..., t_n)[/math].

По сути [math]P(c_i)[/math] является отношением количества документов из обучающей выборки [math]L[/math], отнесенных в категорию c_i , к количеству всех документов из [math]L[/math].

[math]P(d)[/math] не зависит от категории [math]c_i[/math], а значения [math]t_1, ..., t_n[/math] заданы заранее, поэтому знаменатель — это константа, не влияющая на выбор наибольшего из значений [math]P(c_i|d)[/math].

Вычисление [math]P(d | c_i)[/math] затруднительно из-за большого количества признаков [math]t_1, ..., t_n[/math] , поэтому делают «наивное» предположение о том, что любые две координаты, рассматриваемые как случайные величины, статистически не зависят друг от друга. Тогда можно воспользоваться формулой

[math]P(d|c_i) = \prod_{k=1}^{n} P(t_k|c)[/math]

Далее все вероятности подсчитываются по методу максимального правдоподобия.

[math]c = argmax_{c \in C} P(c)\prod_{k=1}^{n} P(t_k|c)[/math]

Преимущества метода:

• высокая скорость работы;
• простая реализация алгоритма;
• легкая интерпретируемость результатов работы алгоритма.

Недостатками являются частое низкое качество классификации и неспособность учитывать зависимость результата классификации от сочетания признаков.

Многомерная модель

В многомерной(multivariate) модели документ – это вектор бинарных атрибутов, показывающих, встретилось ли в документе то или иное слово. Когда мы подсчитываем правдоподобие е документа, мы перемножаем вероятности того, что встретилось каждое слово из документа и вероятности того, что не встретилось каждое (словарное) слово, которое не встретилось. Получается модель многомерных испытаний Бернулли. Наивное предположение в том, что события «встретилось ли слово» предполагаются независимыми.

Математически: пусть [math]V = \{w_t\}_{t=1}^{|V|}[/math] – словарь. Тогда документ [math]d_i[/math] – это вектор длины [math]|V|[/math], состоящий из битов [math]B_{it}[/math]. [math]B_{it} = 1[/math] тогда и только тогда, когда слово [math]w_{t}[/math] встречается в документе [math]d_{i}[/math].

Правдоподобие принадлежности [math]d_{i}[/math] классу [math]c_{j}[/math]:

[math]P(d_i|c_j) = \prod_{t=1}^{|V|}(B_{it} \times P(w_t|c_j) + (1 - B_{it}) \times (1 - P(w_t|c_j)))[/math]

Для обучения такого классификатора нужно обучить [math]P(w_t|c_j)[/math].

Пусть дан набор документов [math]D = \{d_{i}\}[/math], которые уже распределены по классам [math]c_{j}[/math] (возможно, даже вероятностно распределены), дан словарь [math]V = \{w_t\}[/math], и мы знаем биты [math]B_{it}[/math] (знаем документы).

Тогда можно подсчитать оптимальные оценки вероятностей того, что то или иное слово встречается в том или ином классе (при помощи лапласовой оценки):

[math]P(w_i|c_j) = \frac{1 + \sum_{i=1}^{|D|} B_{it} \times P(c_j|d_i)}{2 + \sum_{i=1}^{|D|} P(c_j|d_i)}[/math]

Априорные вероятности классов можно подсчитать как [math]P(c_j) = \frac{1}{|D|}\sum_{i=1}^{|D|}P(c_j|d_i)[/math]. Классификация происходит как обычно - максимизацией правдоподобия: [math]c = argmax_{j}P(c_j)P(d_i|c_j) = argmax_{j}(\log{\sum_{i=1}^{|D|}P(c_j|d_i)} + \sum_{t=1}^{|V|}\log{(B_{it} \times P(w_t|c_j) + (1 - B_{it}) \times (1 - P(w_t|c_j)))})[/math].

Мультиномиальная модель

В мультиномиальной(multinomial) модели документ – это последовательность событий. Каждое событие – это случайный выбор одного слова из того самого «bag of words». Когда мы подсчитываем правдоподобие документа, мы перемножаем вероятности того, что мы достали из мешка те самые слова, которые встретились в документе. Наивное предположение в том, что мы достаём из мешка разные слова независимо друг от друга. Получается мультиномиальная генеративная модель, которая учитывает количество повторений каждого слова, но не учитывает, каких слов нет в документе.

Математически: пусть [math]V = \{w_t\}_{t=1}^{|V|}[/math] – словарь. Тогда документ [math]d_i[/math] – это вектор длины [math]|V|[/math], состоящий из слов, каждое из которых «вынуто» из словаря с вероятностью [math]P(w_t|c_j)[/math].

Правдоподобие принадлежности [math]d_{i}[/math] классу [math]c_{j}[/math]:

[math]P(d_i|c_j) = P(|d_i|) \times |d_i|! \times \prod_{t=1}^{|V|}\frac{P(w_t|c_j)^{N_{it}}}{N_{it}!}[/math], где 𝑁𝑖𝑡 – количество вхождений [math]w_t\lt \math\gt в \lt math\gt d_i)[/math].

Для обучения такого классификатора тоже нужно обучить вероятности [math]P(w_t|c_j)[/math].

Пусть дан набор документов [math]D = \{d_{i}\}[/math], которые уже распределены по классам [math]c_{j}[/math] (возможно, даже вероятностно распределены), дан словарь [math]V = \{w_t\}[/math], и мы знаем вхождения [math]N_{it}[/math].

Тогда можно подсчитать апостериорные оценки вероятностей того, что то или иное слово встречается в том или ином классе (не забываем сглаживание – правило Лапласа):

[math]P(w_t|c_j) = \frac{1 + \sum_{i=1}^{|D|} N_{it} \times P(c_j|d_i)}{|V| + \sum_{s=1}^{|V|}\sum_{i=1}^{|D|} N_{is}P(c_j|d_i)}[/math].

Априорные вероятности классов можно подсчитать как [math]P(c_j) = \frac{1}{|D|}\sum_{i=1}^{|D|}P(c_j|d_i)[/math]. Тогда классификация будет происходить как [math]c = argmax_{j}P(c_j)P(d_i|c_j) = argmax_{j}(\log{\sum_{i=1}^{|D|}P(c_j|d_i)} + \sum_{t=1}^{|V|}N_{it}\log{P(w_t|c_j)})[/math].

Метод опорных векторов (SVM)

Будем представлять каждый документ, как вектор, задаваемый своим содержимым в общем векторном пространстве. После этого будем строить разделяющую гиперплоскость для каждого известного класса.

Преимущества метода:

• один из наиболее качественных методов;
• возможность работы с небольшим набором данных для обучения;
• сводимость к задаче выпуклой оптимизации, имеющей единственное решение.

Недостатки метода: сложная интерпретируемость параметров алгоритма и неустойчивость по отношению к выбросам в исходных данных.

pLSA (Hoffmann, 1999)

Каждое слово [math]d[/math] порождается некой темой [math]t \in T[/math]. Lокумент порождается некоторым распределением на темах [math]p(t|d)[/math]. Cлово порождается именно темой, а не документом - [math]p(w|d, t) = p(w|d)[/math]. Итого получается следующая функция правдоподобия: [math]p(w|d) = \sum_{t \in T}p(w|t)p(t|d)[/math].

Можно оценить [math]p(w|d) = \frac{n_{wd}}{n_{d}}[/math], а требуется найти [math]\phi_{wt} = p(w|t), \theta_{td} = p(t|d)[/math]. Правдоподобие выглядит следующим образом [math]p(D) = \prod_{d \in D}\prod_{w \in d}p(d, w)^{n_dw} = \prod_{d \in D}\prod_{w \in d}(\sum_{t \in T}p(w|t)p(t|d))^{n_dw}[/math].

Максимизировать такое правдоподобие следует ЕМ-алгоритмом. На Е-шаге ищемм, сколько слов [math]w[/math] в документе [math]d[/math] из темы [math]t[/math]:

[math]n_{dwt} = n_{dw}p(t|d, w)=n_{dw}\frac{\phi_{wt}\theta_{td}}{\sum_{s \in T}\phi_{ws}\theta_{sd}}[/math]

На М шаге пересчитываем параметры модели: [math]n_{wt} = \sum_d n_{dwt}[/math], [math]n_{td} = \sum_{w \in d} n_{dwt}[/math], [math]n_{t} = \sum_w n_{wt}[/math], [math]\theta_{td} = \frac{n_{td}}{n_d}[/math], [math]\phi_{wt} = \frac{n_{wt}}{n_t}[/math].

Параметров очень много, что явно введет к оверфиттингу, только если корпус не будет на порядки больше числа тем. Однако это решается регуляризацией(Есть целая наука о разных регуляризаторах для pLSA (К.В. Воронцов)).

В общем виде так: добавим регуляризаторы [math]R_{i}[/math] в логарифм правдоподобия: [math]\sum_{d \in D}\sum_{w \in d}n_{dw}\log{(\sum_{t \in T}\phi_{wt}\theta_{td})} + \sum_i \tau R_i(\Phi, \Theta)[/math]

Тогда ЕМ-алгоритме на М-шаге появятся частные производные [math]R[/math]:

[math]n_{wt} = \sum_{d \in D}n_{dwt} + \phi\frac{\partial R}{\partial \phi_{wt}}[/math], [math]n_{td} = \sum_{w \in d}n_{dwt} + \theta\frac{\partial R}{\partial \theta_{td}}[/math].

Также известное расширение pLSA это LDA.

Оценка качества классификации

Для оценки качества классификации, как и для оценки качества работы многих других алгоритмов машинного обучения вычисляется точность и полнота.

Применение семантических тезаурусов для анализа тональности текстов

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

Основной проблемой методов, основанных на словарях является трудоёмкость построения словаря: отдельного для каждого нового языка и каждой новой тематики.

Известные тезаурусы:

• WordNet-Affect;
• SentiWordNet;
• SenticNet