Monday, 30 November 2015

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

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

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

Введение

Как известно, в задаче классификации обучающий пример E представляется в виде кортежа значений атрибутов (x1, x2, ··· , xn), где xi является значением атрибута Xi. Пусть C представляет классифицируемую переменную, а c - конкретное значение C. Далее будем предполагать, что имеется только 2 класса: + (положительный класс) и - (отрицательный класс).
Классификатор - это функция, которая присваивает метку класса некоторому кортежу атрибутов. С точки зрения теории вероятностей, в соответствии с правилом Байеса, вероятность принадлежности примера E = (x1, x2, ··· , xn) классу c определяется формулой:
Пример E классифицируется в положительный класс тогда и только тогда, когда
при этом функция fb(E) называется байесовским классификатором.
Используя предположение о независимости атрибутов при данном значении c, получаем
 и итоговая формула для классификатора будет выглядеть так:

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



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

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

Определение 1. Два классификатора f1 и f2 называются равными для данного примера E, если  f1(E) ≥ 0, тогда и только тогда, когда f2(E) ≥ 0. Обозначим это как f1(E)  = f2(E). Если для каждого примера из набора выполняется f1(E) = f2(E), будем называть f1 и f2 равными и обозначать это как f1 = f2.
Попытаемся показать при каких условиях наивный байесовский классификатор будет равен соответствующему ему 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 не имеет родительских узлов ddrG(x)=1
  2. Если dd+G(x|pa(x)) = dd-G(x|pa(x)), то ddrG(x)=1. Это означает, что локальные зависимости X распределены в обоих классах равномерно. Таким образом, зависимости не влияют на классификацию, насколько бы сильными они ни были.
  3. Если  ddrG(x) > 1, то поддержка оказываемая локальной зависимостью в классе + сильнее, чем в классе -. Значение меньше 1 означает противоположное. 
Теперь рассмотрим условия, при которых ANB классификатор работает в точности как соответствующий наивный байесовский классификатор. Связь между ними устанавливает следующая теорема.
Теорема 1. Для данного ANB графа G и соответствующего ему наивного байесовского графа Gnb (полученного из G путем отбрасывания дуг между узлами атрибутов) и соответствующих им классификаторов fb и fnb для данного примера E = (x1, x2, ··· , xn) выполняется следующее соотношение:


где П n  i=1 ddrG(xi) называется коэффициентом распределения зависимости и обозначается как DFG(E).
Из теоремы следует, что именно коэффициент распределения зависимости определяет разницу между ANB и соответствующим NB-классификатором. Далее, видно, что коэффициент является произведением отношений дериватов локальных зависимостей всех атрибутных узлов. Поэтому он отражает общее распределение зависимости. Например, когда DFG(E)=1, G будет классифицировать E как и Gnb. На самом деле, не обязательно даже требовать выполнения DFG(E)=1, чтобы получить равенство классификаторов. См. теорему ниже.
Теорема 2. Для данного примера E = (x1, x2, ··· , xn), ANB граф G равен (определение равенства см. в начале статьи) соответствующему графу Gnb тогда и только тогда, когда  fb(E) ≥ 1, DFG(E) ≤ fb(E) или fb(E) < 1, DFG(E) > fb(E).

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

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

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

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


No comments:

Post a Comment