Особенности применения наивного байесовского классификатора

Сокращенный и переработанный перевод статьи Harry Zhang. 

Наивный байесовский классификатор один из наиболее эффективных алгоритмов машинного обучения и data mining. Его неплохие результаты в задачах классификации удивительны, поскольку предположение об условной независимости, на котором он основан, редко встречается в реальных условиях. Отсюда возникает вопрос: какова истинная причина успехов алгоритма в задачах классификации?

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

Введение

Как известно, в задаче классификации обучающий пример E представляется в виде кортежа значений атрибутов (x₁, x₂, ··· , x_n), где x_i является значением атрибута X_i. Пусть C представляет классифицируемую переменную, а c - конкретное значение C. Далее будем предполагать, что имеется только 2 класса: + (положительный класс) и - (отрицательный класс).

Классификатор - это функция, которая присваивает метку класса некоторому кортежу атрибутов. С точки зрения теории вероятностей, в соответствии с правилом Байеса, вероятность принадлежности примера E = (x₁, x₂, ··· , x_n) классу c определяется формулой:

Пример E классифицируется в положительный класс тогда и только тогда, когда

при этом функция f_b(E) называется байесовским классификатором.

Используя предположение о независимости атрибутов при данном значении c, получаем

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

 Функция f_nb(E) называется наивным байесовским классификатором. На рисунке ниже приведена схема наивного байесовского классификатора. Узел каждого атрибута не имеет родителей за исключением узла класса.

Такой граф является простейшей байесовской сетью, в которой все атрибуты независимы для данного значения переменной класса. Это называется условной независимостью. Очевидно, что такая независимость редко встречается в реальной жизни. Наиболее подходящий способ обойти это ограничение - расширить структуру графа для представления связей между узлами атрибутов. Назовем дополненным наивным байесовским классификатором (augmented naive Bayes - ANB) расширенный наивный классификатор Байеса, в котором существуют связи между узлами-атрибутами. На рисунке ниже представлен пример ANB    

 

Совместное распределение вероятностей для этого графа может быть описано формулой:

где pa(x_i) обозначает значения родительских узлов X_i(здесь и далее pa(x_i) не включает узел C - прим. перев.). Таким образом, ANB является специальной формой байесовской сети, в которой нет выделенного узла, представляющего классифицируемую переменную.

Объяснение эффективности наивного байесовского классификатора

Определение 1. Два классификатора f₁ и f₂ называются равными для данного примера E, если  f₁(E) ≥ 0, тогда и только тогда, когда f₂(E) ≥ 0. Обозначим это как f₁(E)  = f₂(E). Если для каждого примера из набора выполняется f₁(E) = f₂(E), будем называть f₁ и f₂ равными и обозначать это как f₁ = f₂.

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

Рассмотрим некоторый ANB граф G с двумя классами {+, -}, как было указано выше зависимости между узлами графа представлены дугами. Для каждого узла влияние ее родителей определяется соответствующей условной вероятностью. Назовем локальной зависимостью узла зависимость между им и его родителями. Как можно измерить локальную зависимость узла для каждого класса? Естественно, отношением условных вероятностей узла с учетом и без учета значений родительских узлов. Это отношение покажет насколько сильно родители влияют на  узел в каждом классе.

Определение 2. Для узла X в ANB графе G дериват локальной зависимости X в классах + и - определяется как:

dd⁺_G(x|pa(x)) отражает силу локальной зависимости узла X в классе +. Аналогично для dd^-_G(x|pa(x)).

Подведем промежуточный итог:

1. Когда узел X не имеет родителей, дериваты обоих классов равны 1.
2. Когда дериват dd⁺_G(x|pa(x)) ≥ 1, локальная зависимость X в классе + поддерживает решение в пользу класса +. В противном случае - в пользу класса -. Аналогично когда дериват класса - больше 1, локальная зависимость X поддерживает решение в пользу класса -, в противном случае - в пользу класса +.

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

Определение 3.  Для узла X ANB графа G отношением дериватов локальной зависимости называется следующая величина: 

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

1. Если X не имеет родительских узлов ddr_G(x)=1
2. Если dd⁺_G(x|pa(x)) = dd^-_G(x|pa(x)), то ddr_G(x)=1. Это означает, что локальные зависимости X распределены в обоих классах равномерно. Таким образом, зависимости не влияют на классификацию, насколько бы сильными они ни были.
3. Если  ddr_G(x) > 1, то поддержка оказываемая локальной зависимостью в классе + сильнее, чем в классе -. Значение меньше 1 означает противоположное. 

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

Теорема 1. Для данного ANB графа G и соответствующего ему наивного байесовского графа G_nb (полученного из G путем отбрасывания дуг между узлами атрибутов) и соответствующих им классификаторов f_b и f_nb для данного примера E = (x₁, x₂, ··· , x_n) выполняется следующее соотношение:

где П ⁿ  _i=1 ddr_G(x_i) называется коэффициентом распределения зависимости и обозначается как DF_G(E).

Из теоремы следует, что именно коэффициент распределения зависимости определяет разницу между ANB и соответствующим NB-классификатором. Далее, видно, что коэффициент является произведением отношений дериватов локальных зависимостей всех атрибутных узлов. Поэтому он отражает общее распределение зависимости. Например, когда DF_G(E)=1, G будет классифицировать E как и G_nb. На самом деле, не обязательно даже требовать выполнения DF_G(E)=1, чтобы получить равенство классификаторов. См. теорему ниже.

Теорема 2. Для данного примера E = (x₁, x₂, ··· , x_n), ANB граф G равен (определение равенства см. в начале статьи) соответствующему графу G_nb тогда и только тогда, когда  f_b(E) ≥ 1, DF_G(E) ≤ f_b(E) или f_b(E) < 1, DF_G(E) > f_b(E).

Итак, мы получаем следующие результаты:
1. Когда DF_G(E)=1, зависимости  в ANB графе G не имеют влияния на решение классификации. Всего существует три причины для DF_G(E)=1:

• отсутствие зависимости между атрибутами
• равенство ddr_G(x)=1 для всех атрибутов, что означает равномерное распределение локальных зависимостей в обоих классах
• влияние, которое распространяют некоторые локальные зависимости поддерживая класс + для примера E,  нивелируется влиянием других локальных зависимостей, поддерживающих класс -.

2. Равенство f_b(E) = f_nb(E) не требует, чтобы  DF_G(E)=1. Точное условие дается в Теореме 2.
3. Зависимости в ANB графе меняет решение классификации по сравнению с наивным классификатором, только в случае нарушения условий Теоремы 2.

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