Усредненные оценки с одной зависимостью

Усредненные оценки с одной зависимостью ( AODE вероятностной ) — это метод обучения классификации . Он был разработан для решения проблемы независимости атрибутов популярного наивного байесовского классификатора . Часто он разрабатывает значительно более точные классификаторы, чем наивный Байес, ценой небольшого увеличения объема вычислений. ^[1]

Классификатор АОДЕ

AODE пытается оценить вероятность каждого класса y с учетом заданного набора признаков x ₁ , ... x _n , P( y | x ₁ , ... x _n ). Для этого используется формула

{\hat {P}}(y\mid x_{1},\ldots x_{n})={\frac {\sum _{i:1\leq i\leq n\wedge F(x_{i})\geq m}{\hat {P}}(y,x_{i})\prod _{j=1}^{n}{\hat {P}}(x_{j}\mid y,x_{i})}{\sum _{y^{\prime }\in Y}\sum _{i:1\leq i\leq n\wedge F(x_{i})\geq m}{\hat {P}}(y^{\prime },x_{i})\prod _{j=1}^{n}{\hat {P}}(x_{j}\mid y^{\prime },x_{i})}}

где ${\hat {P}}(\cdot )$ обозначает оценку $P(\cdot )$ , $F(\cdot )$ — это частота, с которой аргумент появляется в выборочных данных, а m — заданная пользователем минимальная частота, с которой термин должен появляться, чтобы его можно было использовать во внешнем суммировании. В недавней практике m обычно устанавливается равным 1.

Вывод классификатора AODE

Мы стремимся оценить P( y | x ₁ , ... x _n ). По определению условной вероятности

P(y\mid x_{1},\ldots x_{n})={\frac {P(y,x_{1},\ldots x_{n})}{P(x_{1},\ldots x_{n})}}.

Для любого $1\leq i\leq n$ ,

P(y,x_{1},\ldots x_{n})=P(y,x_{i})P(x_{1},\ldots x_{n}\mid y,x_{i}).

В предположении, что x ₁ , ... x _n независимы при данных y и x _i , отсюда следует, что

P(y,x_{1},\ldots x_{n})=P(y,x_{i})\prod _{j=1}^{n}P(x_{j}\mid y,x_{i}).

Эта формула определяет специальную форму оценки одной зависимости (ODE), варианта наивного байесовского классификатора , который делает вышеуказанное предположение независимости более слабым (и, следовательно, потенциально менее вредным), чем наивное предположение независимости Байеса. Как следствие, каждое ОДУ должно создавать менее смещенную оценку, чем наивный Байес. Однако поскольку каждая оценка базовой вероятности обусловлена двумя переменными, а не одной, они формируются на основе меньшего количества данных (обучающих примеров, удовлетворяющих обеим переменным) и, следовательно, вероятно, будут иметь большую дисперсию. AODE уменьшает эту дисперсию, усредняя оценки всех таких ОДУ.

Особенности классификатора AODE

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

AODE имеет вычислительную сложность $O(ln^{2})$ во время тренировки и $O(kn^{2})$ во время классификации, где n — количество признаков, l — количество обучающих примеров, а k — количество классов. Это делает невозможным его применение к многомерным данным. Однако в рамках этого ограничения он линеен по отношению к количеству обучающих примеров и, следовательно, может эффективно обрабатывать большое количество обучающих примеров.