Байесовская классификация

2019-04-01T14:12:12Z

92.100.91.51:

== Вероятностная постановка задачи классификации ==

Пусть $X$ множество объектов, $Y$ конечное множество имён классов,
множество $X \times Y$ является вероятностным пространством с плотностью распределения $p(x,y)=P(y)p(x|y)$.
Вероятности появления объектов каждого из классов $P_y=P(y)$ называются ''априорными вероятностями классов''.
Плотности распределения $p_y(x)=p(x|y)$ называются ''функциями правдоподобия классов''.

'''Вероятностная постановка задачи классификации разделяется на две независимые подзадачи:'''
* Имеется простая выборка $X^l=(x_i, y_i)^l_{i=1}$ из неизвестного распределения $p(x,y)=P_yp_y(x)$. Требуется построить ''эмпирические оценки'' априорных вероятностей $P'_y$ и функций правдоподобия $p'_y(x)$ для каждого из классов $y \in Y$.
* По известным плотностям распределения $p_y(x)$ и априорным вероятностям $P_y$ всех классов $y \in Y$ построить алгоритм $a(x)$, минимизирующий вероятность ошибочной классификации.

Априорные вероятности классов $P_y$ можно оценить согласно закону больших чисел,
тогда частота появления объектов каждого из классов равна $P'_y=\frac{l_y}{l}$ где $l_y=|X^l_y|, y \in Y$
сходится по вероятности к $P_y$ при $l_y \to \infty$. Чем больше длина выборки, тем точнее выборочная оценка $P'_y$.

== Оптимальный байесовский классификатор ==

Рассмотрим произвольный алгоритм $a:X \to Y$.
Он разбивает множество $X$ на не пересекающиеся области $A_y=\{x \in X | a(x) = y\}, y \in Y$.
Вероятность того,что появится объект класса $y$ и алгоритм $a$ отнесёт его к классу $s$, равна $P_yP(A_s|y)$.
Каждой паре $(y,s) \in Y \times Y$ поставим в соответствие величину потери $\lambda_{ys}$
при отнесении объекта класса $y$ к классу $s$.

{{Определение
|definition =
'''Функционал среднего риска''' {{---}} ожидаемая величина потери при классификации объектов алгоритмом $a$:
<tex>
R(a) = \displaystyle\sum_{y \in Y}\sum_{s \in Y}\lambda_{ys}P_yP(A_s|y)
</tex>
}}

{{Теорема
|about=
об оптимальности байесовского классификатора
|statement=
Если известны априорные вероятности $P_y$ и функции правдоподобия $p_y(x)$,
то минимум среднего риска $R(a)$ достигается алгоритмом
<tex>
a(x) = \displaystyle\arg\min_{s \in Y}\sum_{y \in Y}\lambda_{ys}P_yp_y(x)
</tex>
|proof=

Для произвольного $t \in Y$ запишем функционал среднего риска:

<tex>
R(a)=\displaystyle\sum_{y \in Y}\sum_{s \in Y}\lambda_{ys}P_yP(A_s|y) =
\sum_{y \in Y}\lambda_{yt}P_yP(A_t|y) + \sum_{s \in Y\setminus\{t\} }\sum_{y \in Y}\lambda_{ys}P_yP(A_s|y).
</tex>

Применив формулу полной вероятности, $P(A_t \mid y) = 1 −\displaystyle\sum_{ s \in Y \setminus \{t\} }P(A_s \mid y)$, получим:

<tex>
R(a) = \displaystyle\sum_{y \in Y}\lambda_{yt}P_y + \sum_{ s \in Y \setminus \{t\} } \sum_{y \in Y}
(\lambda_{ys} - \lambda_{yt})P_yP(A_s|y) =
</tex>

<tex>
= const(a) + \displaystyle\sum_{ s \in Y \setminus \{t\} }
\int_{A_s}\sum_{y \in Y} (\lambda_{ys}−\lambda_{yt})P_yp_y(x)dx.
</tex>

Введём для сокращения записи обозначение
$g_s(x) = \displaystyle\sum_{y \in Y}\lambda_{ys}P_yp_y(x)$, тогда
$R(a) = const(a) + \displaystyle\sum_{ s \in Y \setminus \{t\} }\int_{A_s}(g_s(x)−g_t(x))dx$.

Минимум интегрла достигается, когда $A_s$ совпадает с областью неположительности подынтегрального выражения.
<tex>
A_s=\{x \in X \mid g_s(x) \leq g_t(x), \forall t \in Y, t \leq s\}.
</tex>

С другой стороны, $A_s=\{x \in X \mid a(x) = s\}$. Значит, $a(x) = s$ тогда и только тогда, когда
$s= \displaystyle\arg\min_{t \in Y}g_t(x)$.
}}

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

Допустим, что объекты $x \in X$ описываются $n$ числовыми признаками $f_j:X→R,j= 1,...,n$.
Обозначим через $x = (\xi_1,...,\xi_n)$ произвольный элемент пространства объектов $X=R^n$, где $\xi_j=f_j(x)$.

Предположим, что признаки $f_1(x),...,f_n(x)$ являются независимыми случайными величинами.
Следовательно, функции правдоподобия классов представимы в виде:

<tex>
p_y(x) = \displaystyle\prod^n_{i=1}p_{yi}(\xi_i)
</tex>

где $p_{yj}(\xi_j)$ плотность распределения значений $j$-го признака для класса $y$.
Алгоритмы классификации исходящие их этого предположения, называются ''наивными байесовскими''

Подставим эмпирические оценки одномерных плотностей в байесовский классификатор. Получим алгоритм:

<tex>
a(x) = \displaystyle\arg\max_{y \in Y}(\ln\lambda_yP'_y + \sum^n_{j=1}\ln p'_{yj}(\xi_j)).
</tex>

Основные его преимущества {{---}} простота реализации и низкие вычислительные затраты при обучении и классификации.
В тех редких случаях, когда признаки почти независимы, наивный байесовский классификатор близок к оптимальному.

Основной его недостаток {{---}} низкое качество классификации.

== Источники информации ==

* [https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%B1%D0%B0%D0%B9%D0%B5%D1%81%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80 Википедия {{---}} Наивный байесовский классификатор]
* [http://www.machinelearning.ru/wiki/images/6/6d/Voron-ML-1.pdf К.В.Воронцов Математические методы обучения по прецедентам]

Викиконспекты - Вклад участника [ru]

Байесовская классификация