Наивный байесовский классификатор

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

Заметка разбита на две части: теоретическая, в которой описаны аспекты классификации, и практическая часть построения классификатора. Если вы хотите быстро создать прототип классификатора, то обратитесь к практической части заметки, там на приводится пример классификатора. Также на github доступны исходники примера. Если же вам интересны теоретические принципы работы классификации, то обратитесь к теоретической части заметки.

Теория

Осторожно, в этой части заметки много формул.

В основе NBC (Naïve Bayes Classifier) лежит, как вы уже могли догадаться, теорема Байеса.

$$ P(c|d) = \frac{ P(d|c)P(c) }{ P(d) } $$

где,

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

Цель классификации состоит в том чтобы понять к какому классу принадлежит документ, поэтому нам нужна не сама вероятность, а наиболее вероятный класс. Байесовский классификатор использует оценку апостериорного максимума (Maximum a posteriori estimation) для определения наиболее вероятного класса. Грубо говоря, это класс с максимальной вероятностью.

$$ c_{map}=\operatorname*{arg\,max}_{c \in C} \frac{ P(d|c)P(c) }{ P(d) }$$

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

$$ c_{map}=\operatorname*{arg\,max}_{c \in C} \left[ P(d|c)P(c) \right] $$

Формула №1

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

Предположение условной независимости

Если я вам скажу “темно как у негра в …”, вы сразу поймете о каком месте чем идет речь, даже если я не закончу фразу. Так происходит потому что в натуральном языке вероятность появления слова сильно зависит от контекста. Байесовский же классификатор представляет документ как набор слов вероятности которых условно не зависят друг от друга. Этот подход иногда еще называется bag of words model. Исходя из этого предположения условная вероятность документа аппроксимируется произведением условных вероятностей всех слов входящих в документ.

$$ P(d|c) \approx P(w_1|c)P(w_2|c)…P(w_n|c) = \prod_{i=1}^n P(w_i|c) $$

Этот подход также называется Unigram Language Model. Языковые модели играют очень важную роль в задачах обработки натуральных языков, но выходят за пределы этой заметки.

Подставив полученное выражение в формулу №1 мы получим:

$$ c_{map}=\operatorname*{arg\,max}_{c \in C} \left[ P(c) \prod_{i=1}^n P(w_i|c) \right] $$

Проблема арифметического переполнения

При достаточно большой длине документа придется перемножать большое количество очень маленьких чисел. Для того чтобы при этом избежать арифметического переполнения снизу зачастую пользуются свойством логарифма произведения $\log ab = \log a+\log b$. Так как логарифм функция монотонная, ее применение к обоим частям выражения изменит только его численное значение, но не параметры при которых достигается максимум. При этом, логарифм от числа близкого к нулю будет числом отрицательным, но в абсолютном значении существенно большим чем исходное число, что делает логарифмические значения вероятностей более удобными для анализа. Поэтому, мы переписываем нашу формулу с использованием логарифма.

$$ c_{map}=\operatorname*{arg\,max}_{c \in C} \left[ \log P(c)+\sum_{i=1}^n \log P(w_i|c) \right] $$

Формула №2

Основание логарифма в данном случае не имеет значения. Вы можете использовать как натуральный, так и любой другой логарифм.

Оценка параметров Байесовской модели

Оценка вероятностей $ P(c) $ и $ P(w_i|c) $ осуществляется на обучающей выборке. Вероятность класса мы можем оценить как:

$$ P(c)=\frac{D_c}{D} $$

где, $D_c$ – количество документов принадлежащих классу $c$, а $D$ – общее количество документов в обучающей выборке.

Оценка вероятности слова в классе может делаться несколькими путями. Здесь я приведу multinomial bayes model.

$$ P(w_i|c)=\frac{W_{ic}}{ \sum_{i’\in V} W_{i’c} } $$

Формула №3

Другими словами, числитель описывает сколько раз слово встречается в документах класса (включая повторы), а знаменатель – это суммарное количество слов во всех документах этого класса.

Проблема неизвестных слов

С формулой №3 есть одна небольшая проблема. Если на этапе классификации вам встретится слово которого вы не видели на этапе обучения, то значения $W_{ic}$, а следственно и $P(w_i|c)$ будут равны нулю. Это приведет к тому что документ с этим словом нельзя будет классифицировать, так как он будет иметь нулевую вероятность по всем классам. Избавиться от этой проблемы путем анализа большего количества документов не получится. Вы никогда не сможете составить обучающую выборку содержащую все возможные слова включая неологизмы, опечатки, синонимы и т.д. Типичным решением проблемы неизвестных слов является аддитивное сглаживание (сглаживание Лапласа). Идея заключается в том что мы притворяемся как будто видели каждое слово на один раз больше, то есть прибавляем единицу к частоте каждого слова.

$$ P(w_i|c)=\frac{W_{ic}+1}{ \sum_{i’\in V} \left( W_{i’c} + 1 \right) } = \frac{W_{ic}+1}{ |V| + \sum_{i’\in V} W_{i’c} } $$

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

Имя Частота
Вася 3
Петя 2
Женя 1

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

Смещёная и несмещённая оценка вероятности

Из графика видно что смещённая оценка никогда не бывает нулевой, что защищает нас от проблемы неизвестных слов.

Собираем все вместе

Подставив выбранные нами оценки в формулу №2 мы получаем окончательную формулу по которой происходит байесовская классификация.

$$ c_{map}=\operatorname*{arg\,max}_{c \in C} \left[ \log\frac{D_c}{D} + \sum_{i=1}^n\log{\frac{W_{ic}+1}{ |V|+\sum_{i’\in V} W_{i’c}}} \right] $$

Формула №4

Реализация классификатора

Для реализации Байесовского классификатора нам необходима обучающая выборка в которой проставлены соответствия между текстовыми документами и их классами. Затем нам необходимо собрать следующую статистику из выборки, которая будет использоваться на этапе классификации:

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

$$ \log\frac{D_c}{D} + \sum_{i \in Q}\log{\frac{W_{ic}+1}{ |V|+L_{c} }} $$

Упрощенная запись формулы №4

в этой формуле:

Информация необходимая для осознания смысла этого выражения приведена выше в разделе Теория.

Пример

Допустим, у нас есть три документа для которых известны их классы (HAM означает – не спам):

Модель классификатора будет выглядеть следующим образом:

  spam ham
частоты классов 2 1
суммарное количество слов 6 3
  spam ham
предоставляю 1 0
услуги 1 0
бухгалтера 1 0
спешите 1 0
купить 1 1
виагру 1 0
надо 0 1
молоко 0 1

Теперь классифицируем фразу “надо купить сигареты”. Рассчитаем значение выражения для класса SPAM:

$$ \log\frac{2}{3} + \log\frac{1}{8+6} + \log\frac{2}{8+6} + \log\frac{1}{8+6} \approx -7.629 $$

Теперь сделаем то же самое для класса HAM:

$$ \log\frac{1}{3} + \log\frac{2}{8+3} + \log\frac{2}{8+3} + \log\frac{1}{8+3} \approx -6.906 $$

В данном случае класс HAM выиграл и сообщение не будет помечено как спам.

Формирование вероятностного пространства

В простейшем случае вы выбираете класс который получил максимальную оценку. Но если вы например хотите помечать сообщение как спам только если соответствующая вероятность больше 80%, то сравнение логарифмических оценок вам ничего не даст. Оценки которые выдает алгоритм не удовлетворяют двум формальным свойствам которым должны удовлетворять все вероятностные оценки:

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

Здесь — это логарфмическая оценка алгоритма для класса , а возведение (основание натурального логарфима) в степерь оценки используется для того чтобы избавиться от логарифма (). Таким образом, если вы в рассчетах использовали не натуральный логарифм, а десятичный, вам необходимо использовать не , а 10.

Для вышеприведенного примера вероятность что сообщение спам равно:

то есть сообщение является спамом с вероятностью 32.7%.

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

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

В заключении

Show me the code

На github доступен пример описанного классификатора реализованный на Scala. Имплементация занимает 50 с лишним строк кода, разобраться с ним у вас не составит труда, просто посмотрите тест ClassifierSpec. Для запуска тестов необходим Maven.

$ mvn test

Вопросы оставшиеся за бортом

Сушествует целый ряд вопросов который остался без рассмотрения на текущий момент:

Учитывая объем данного поста, эти вопросы я смело оставляю для будущих заметок.