Байесовский подход минимальной цены (Bayes decision rule)

Основные понятия

Пусть $X^l = \{ x_1, \dots, x_l \}$: выборка, $X$: множество всех возможных объектов, $Y$: множество ответов (метки классов) на $X$. В байесовском подходе предполагается, что выборка берётся независимо из некоторого распределения: $p(x, y)$.

$p(x,y) = p(y)p(x|y)$

$p(y)$ называется априорной вероятностью, $p(x|y)$ называется функцией правдоподобия.

$p(y|x) = \frac{p(x|y)p(y)}{p(x)}$

Байесовское правило минимальной цены (Bayes minimum cost decision rule)

Пусть $\lambda_{yf}$ цена предсказания класса $f$ объекту с истинным классом $y$. Матрица $\{\lambda_{ij}\}_{ij},~i,j \in 1, \dots ,C$ называется матрицей штрафов. Тогда ожидаемая цена предсказания класса $f$ объекту $x$равна

$L(f) = \sum_{y=1}^{C}p(y|x)\lambda_{yf}$

Тогда оптимальным классификатором будет классификатор:

$a(x) = argmin_fL(f)$

Пусть дан классификатор $a: X \rightarrow Y$

$A_s = \{x \in X | a(x) = s \}$

Вероятность признать объект класса y объектом класса s:

$P(A_s, y) = \int\limits_{A_s}p(x, y) \, dx$

Тогда логичным выглядит введение мат.ожидания потери (штрафа) для классификатора $a(x)$ (функционал среднего риска):

$R(a) = \sum_{y=1}^C \sum_{s=1}^C \lambda_{ys} P(A_s, y)$

Выбор такого классификатора $a(x)$ называется байесовским правилом минимальной цены (то есть это означает, что для каждого объекта должен быть предсказан тот класс, который даст меньший суммарный штраф, вычисленный по правилу: штраф за предсказание класса $f$ равен произведению вектора-строки апостериорных вероятностей классов на $f$-ый столбец матрицы штрафов.).

Первый частный случай

Упростим задачу. Пускай $\lambda_{yf} = \lambda_{y}[y \neq f]$; то есть мы штрафуем только за неправильные ответы и размер штрафа зависит только от истинного класса. Тогда ожидаемая цена будет выглядеть:

$L(f) = \sum_{y \neq f}^C p(y|x) \lambda_y = \sum_{y=1}^C p(y|x) \lambda_{y} - p(f|x) \lambda_f$

Первое слагаемое не зависит от $f$, поэтому:

$a(x) = argmin_fL(f) = argmax_f p(f|x) \lambda_f$

Второй частный случай (байесовское правило максимальной апостериорной вероятности классов (Bayes minimum error decision rule))

Теперь, если сделать штраф одинаковым для всех $y$, то получится решающее правило, называемое байесовским правилом максимальной апостериорной вероятности классов (Bayes minimum error decision rule):

$a(x) = argmax_f p(f|x)$.

Покажем, что данный классификатор минимизирует функционал среднего риска. Рассмотрим произвольный классификатор $b(x)$. Тогда:

$R(b) = \sum_{y=1}^C \sum_{s=1}^C \lambda_{ys} P(B_s, y) = \sum_{y=1}^C \sum_{s=1}^C [y \neq s] P(B_s, y) = \sum_{y=1}^C \sum_{s=1}^C \int\limits_{B_s} [y \neq s]p(x, y) \, dx =$

$= \int\limits_X \sum_{y \neq b(x)} p(x, y) \, dx = 1 - \int\limits_X p(x, b(x)) \, dx \geq 1 - \int\limits_X max_fp(x, f) \, dx = \{ a(x) =$$= argmax_f p(f|x) = argmax_f p(f|x)\cdot p(x) =$

$= argmax_f p(x, f)\} = 1 - \int\limits_X p(x, a(x)) \, dx = \int\limits_X \sum_{y \neq a(x)} p(x, y) = R(a)$

Что и требовалось доказать.