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

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

Пусть $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$.

Определение:

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

Теорема (об оптимальности байесовского классификатора):

Если известны априорные вероятности $P_y$ и функции правдоподобия $p_y(x)$, то минимум среднего риска $R(a)$ достигается алгоритмом [math] a(x) = \displaystyle\arg\min_{s \in Y}\sum_{y \in Y}\lambda_{ys}P_yp_y(x) [/math]

Доказательство:

[math]\triangleright[/math]

Для произвольного $t \in Y$ запишем функционал среднего риска: [math] 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). [/math] Применив формулу полной вероятности, $P(A_t \mid y) = 1 −\displaystyle\sum_{ s \in Y \setminus \{t\} }P(A_s \mid y)$, получим: [math] 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) = [/math] [math] = 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. [/math] Введём для сокращения записи обозначение $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$ совпадает с областью неположительности подынтегрального выражения. [math] A_s=\{x \in X \mid g_s(x) \leq g_t(x), \forall t \in Y, t \leq s\}. [/math] С другой стороны, $A_s=\{x \in X \mid a(x) = s\}$. Значит, $a(x) = s$ тогда и только тогда, когда $s= \displaystyle\arg\min_{t \in Y}g_t(x)$.

[math]\triangleleft[/math]

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

Допустим, что объекты $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)$ являются независимыми случайными величинами. Следовательно, функции правдоподобия классов представимы в виде:

[math] p_y(x) = \displaystyle\prod^n_{i=1}p_{yi}(\xi_i) [/math]

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

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

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

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

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

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

• Википедия — Наивный байесовский классификатор
• К.В.Воронцов Математические методы обучения по прецедентам