Классификация с обучением. Наивный байесовский классификатор

Самый простой, но вместе с тем один из самых часто используемых при обработке натуральных языков алгоритм классификации — наивный байесовский классификатор (Naive Bayes Classifier, NBC).

В основе NBC лежит теорема Байеса:

где P{cd) — вероятность, что документ d принадлежит классу с, именно её надо рассчитать;

P(dc) — вероятность встретить документ d среди всех документов класса

с;

Р(с) — безусловная вероятность встретить документ класса с в корпусе документов;

P(d) — безусловная вероятность документа d в корпусе документов.

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

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

В естественных языках вероятность появления слова сильно зависит от контекста. Байесовский же классификатор называется «наивным», поскольку представляет документ как набор слов, вероятности которых не зависят друг от друга. Исходя из этого предположения условная вероятность документа аппроксимируется произведением условных вероятностей всех слов (точнее говоря, терминов, отобранных, например, по критерию TF*IDF), входящих в документ:

Подставляя в (4.4), получаем

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

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

Основание логарифма в данном случае не имеет значения.

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

где Д — количество документов, принадлежащих классу с, a D — общее количество документов в обучающей выборке.

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

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

С формулой (4.8) есть одна небольшая проблема. Если на этапе классификации встретится слово, которого не было на этапе обучения, то значения Wic, а следственно и P(Wjc) будут равны нулю. Это приведет к тому, что документ с этим словом нельзя будет классифицировать, так как он будет иметь нулевую вероятность по всем классам. Избавиться от этой проблемы путем анализа большего количества документов не получится. Невозможно составить обучающую выборку, содержащую все возможные слова, включая неологизмы, опечатки, синонимы и т.д. Типичным решением проблемы неизвестных слов является аддитивное сглаживание (сглаживание Лапласа). Идея заключается в том, что к частоте каждого слова прибавляется единица. Добавление единицы к каждой частоте встречаемости термина можно интерпретировать как априорное равномерное распределение (каждый термин встречается в каждом классе по одному разу), которое затем на обучающем множестве уточняется. Логически данный подход смещает оценку вероятностей в сторону менее вероятных исходов. Таким образом, слова, которые отсутствовали на этапе обучения модели, получают пусть маленькую, но все же не нулевую вероятность.

Допустим, на этапе обучения мы видели три имени собственных указанное количество раз: Вася - 3; Петя - 2; Женя - 1. На этапе классификации появляется имя Иннокентий. Тогда оригинальная и смещённая по Лапласу оценка вероятностей будут выглядеть следующим образом (рис. 4.5).

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

Подставив выбранные нами оценки в (4.7), получаем окончательную формулу, по которой происходит байесовская классификация:

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

  • ? относительные частоты классов в корпусе документов. То есть, как часто встречаются документы того или иного класса;
  • ? суммарное количество слов в документах каждого класса;
  • - относительные частоты слов в пределах каждого класса;
  • - размер словаря выборки. Количество уникальных слов в выборке.

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

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

Д — количество документов в обучающей выборке принадлежащих классу с;

О — общее количество документов в обучающей выборке;

IV! — количество уникальных слов во всех документах обучающей выборки;

Ьс — суммарное количество слов в документах класса с в обучающей выборке;

У/-,с — сколько раз /-ое слово встречалось в документах класса с в обучающей выборке;

<2 — множество слов классифицируемого документа (включая повторы).

Допустим, у нас есть три документа, для которых известны их классы: [Спам] вы выиграли миллион долларов',

[Спам] приглашаем играть в лотерею-,

[Не_спам] приглашаем на конференцию в Лондон.

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

Частоты классов

Суммарное кол-во слов

СПАМ

2

6

НЕСПАМ

1

3

выиг

рать

мил

лион

дол

лар

при

глашать

играть

лоте

рея

конфе

ренция

Лон

дон

СПАМ

1

1

1

1

1

1

НЕСПАМ

1

1

1

Теперь классифицируем фразу «Приглашаем на конференцию в Одессу». Рассчитаем значение выражения для класса СПАМ (используем натуральные логарифмы):

Для класса НЕСПАМ:

В данном случае выиграл класс НЕ СПАМ.

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

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

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

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

  • [1] Апостериорный - основанный на опыте, в отличие от априорный - не основанный на опыте,предшествующий ему.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >