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

Материал из MachineLearning.

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Д. Жумабеков 21:26, 19 июля 2026 (MSD)

Содержание

1 Введение
2 Функционал среднего риска
3 Теорема об оптимальном байесовском классификаторе
- 3.1 Частные случаи
4 Два принципиальных замечания
- 4.1 Подстановка эмпирических оценок не гарантирует оптимальности
- 4.2 Восстановление плотности сложнее задачи классификации
5 Дискриминативный и генеративный подходы
6 Наивный байесовский классификатор
7 Практическое применение: фильтрация спама
8 Практическое применение: медицинская диагностика
9 Байесовское обучение и связь с регуляризацией
10 Ограничения на малых выборках
11 Литература

Введение

Пусть $X$ — множество объектов, $Y = \{1, \dots, M\}$ — конечное множество классов. Предполагается, что пары «объект — класс» $(x, y)$ порождаются некоторым фиксированным, но неизвестным совместным распределением $p(x, y)$ на множестве $X \times Y$ . Задача классификации состоит в построении алгоритма $a: X \to Y$ , приближающего неизвестную зависимость по конечной обучающей выборке $X^\ell = (x_i, y_i)_{i=1}^{\ell}$ , образованной независимыми одинаково распределёнными наблюдениями из $p(x, y)$ .

Совместное распределение раскладывается по формуле Бayeса двумя эквивалентными способами:

$p(x, y) = P(y) \, p(x \mid y) = p(x) \, P(y \mid x)$

Здесь $P(y)$ — априорная вероятность класса $y$ , то есть вероятность появления объекта класса $y$ безотносительно его признакового описания; $p(x \mid y)$ — функция правдоподобия класса $y$ , описывающая плотность распределения признаков внутри этого класса; $p(x)$ — безусловная плотность распределения объектов; $P(y \mid x)$ — апостериорная вероятность класса $y$ при условии, что наблюдается объект $x$ . Из равенства двух представлений следует формула Байеса в её классической форме:

$P(y \mid x) = \frac{P(y) \, p(x \mid y)}{p(x)} = \frac{P(y) \, p(x \mid y)}{\sum_{y' \in Y} P(y') \, p(x \mid y')}$

Апостериорное распределение $P(y \mid x)$ аккумулирует всю информацию, необходимую для принятия решения об отнесении объекта $x$ к одному из классов, и является центральным объектом байесовской теории классификации.

Функционал среднего риска

Качество классификатора $a(x)$ определяется не только частотой ошибок, но и их «ценой»: в прикладных задачах ошибки разного рода, как правило, неравнозначны. Пусть $\lambda_{y}(a, x)$ — величина потерь (штраф) при использовании ответа $a$ для объекта истинного класса $y$ . В простейшем и наиболее употребительном случае, когда потери зависят только от пары (истинный класс, предсказанный класс), вводят матрицу потерь $\lambda_{y s}$ , $y, s \in Y$ , где $\lambda_{y s}$ — цена ответа $s$ при истинном классе $y$ , причём обычно $\lambda_{y y} = 0$ .

Средним риском алгоритма $a$ называется его ожидаемая величина потерь по совместному распределению $p(x, y)$ :

$R(a) = \mathsf{E}_{(x,y) \sim p(x,y)} \, \lambda_{y, a(x)} = \sum_{y \in Y} \int_{X} \lambda_{y, a(x)} \, p(x, y) \, dx$

Задача обучения классификатора формулируется как задача минимизации среднего риска:

$R(a) \to \min_{a}$

Ключевая особенность этой постановки в том, что минимум берётся по всем измеримым отображениям $a: X \to Y$ , а не по параметрическому семейству — то есть речь идёт о теоретически наилучшем возможном классификаторе, а не о наилучшем алгоритме внутри заданного класса моделей (см. Метод максимального правдоподобия для сопоставления с параметрическим оцениванием).

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

Теорема (оптимальный байесовский классификатор, OBC). Средний риск $R(a)$ минимизируется алгоритмом

$a^{*}(x) = \arg\min_{s \in Y} \sum_{y \in Y} \lambda_{y s} \, P(y \mid x)$

Доказательство (идея). Средний риск можно переписать, вынося интегрирование по $y$ внутрь и группируя по значениям $x$ :

$R(a) = \int_X p(x) \left( \sum_{y \in Y} \lambda_{y, a(x)} \, P(y \mid x) \right) dx$

Поскольку $p(x) \geq 0$ , интеграл минимизируется, если для почти каждого $x$ минимизируется подынтегральное выражение — внутренняя сумма по $y$ . Так как выбор ответа $a(x)$ для разных $x$ никак не связан (каждому $x$ отвечает своё, независимое от других значение $a(x)$ ), достаточно для каждого фиксированного $x$ отдельно выбрать $s \in Y$ , минимизирующий $\sum_{y} \lambda_{ys} P(y \mid x)$ , что и даёт формулу OBC. ∎

Важно подчеркнуть смысл результата: оптимальный алгоритм относит объект $x$ не к классу с максимальной апостериорной вероятностью автоматически, а к классу с минимальным ожидаемым штрафом, который вычисляется как взвешенная — с весами $P(y \mid x)$ — сумма потерь по всем возможным истинным классам.

Частные случаи

Случай симметричных 0-1 потерь. Если $\lambda_{ys} = 1$ при $y \neq s$ и $\lambda_{yy} = 0$ (ошибка любого рода штрафуется одинаково), то

$\sum_{y} \lambda_{ys} P(y \mid x) = \sum_{y \neq s} P(y \mid x) = 1 - P(s \mid x)$

и минимизация суммы потерь эквивалентна максимизации $P(s \mid x)$ . OBC сводится к правилу максимума апостериорной вероятности (maximum a posteriori, MAP):

$a^{*}(x) = \arg\max_{y \in Y} P(y \mid x) = \arg\max_{y \in Y} P(y) \, p(x \mid y)$

Случай равных априорных вероятностей. Если дополнительно классы равновероятны, $P(y) = \mathrm{const}$ , то множитель $P(y)$ не влияет на положение максимума, и правило вырождается в классификацию по максимуму правдоподобия:

$a^{*}(x) = \arg\max_{y \in Y} p(x \mid y)$

что напрямую связывает OBC с методом максимального правдоподобия. Для двухклассовой задачи ( $Y = \{1, -1\}$ ) правило MAP эквивалентно сравнению отношения правдоподобий с порогом, определяемым отношением априорных вероятностей — это составляет основу так называемых линейных и квадратичных дискриминантных классификаторов, восстанавливающих $p(x \mid y)$ в предположении о гауссовской природе классов.

Два принципиальных замечания

Подстановка эмпирических оценок не гарантирует оптимальности

Теорема об OBC устанавливает оптимальность классификатора при условии, что величины $P(y)$ и $p(x \mid y)$ известны точно. На практике эти величины неизвестны и заменяются оценками $\widehat{P}(y)$ , $\widehat{p}(x \mid y)$ , восстановленными по конечной выборке $X^{\ell}$ , после чего строится «подстановочный» алгоритм $\widehat{a}(x) = \arg\min_s \sum_y \lambda_{ys} \widehat{P}(y) \widehat{p}(x \mid y)$ . Существенно, что оптимальность OBC доказана только для точных значений $P(y \mid x)$ ; замена их состоятельными, но не точными, оценками не переносит гарантию минимальности риска на $\widehat{a}(x)$ при конечном $\ell$ . Риск подстановочного алгоритма $R(\widehat{a})$ в общем случае строго больше $R(a^{*})$ , и разность $R(\widehat{a}) - R(a^{*})$ зависит от точности восстановления плотностей, то есть от объёма выборки, размерности признакового пространства и адекватности выбранной параметрической модели плотности. Асимптотическая состоятельность оценок $\widehat{p}(x \mid y) \to p(x \mid y)$ при $\ell \to \infty$ обеспечивает лишь предельную, но не гарантированную на конечной выборке оптимальность.

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

Второе замечание носит принципиальный характер и восходит к общей методологии статистического обучения^[1]: для получения классификатора $a^{*}(x)$ достаточно знать лишь разбиение пространства $X$ на области предпочтения того или иного класса, то есть, по существу, знак разности $\sum_y \lambda_{ys} P(y \mid x) - \sum_y \lambda_{ys'} P(y \mid x)$ для пар классов $s, s'$ . Восстановление же полной плотности $p(x \mid y)$ — существенно более информативная и более трудная задача: она требует точной аппроксимации функции во всех точках пространства $X$ , тогда как для классификации важна лишь взаимная упорядоченность классов в каждой точке. Иными словами, генеративный путь решает задачу, которая заведомо труднее непосредственно стоящей задачи классификации, что и объясняет, почему прямое оценивание разделяющей функции (дискриминативный подход) часто оказывается практически эффективнее восстановления плотностей при ограниченном объёме данных.

Дискриминативный и генеративный подходы

Все методы построения классификатора, приближающего OBC, можно разбить на два принципиально различных подхода к моделированию $p(x, y)$ .

Генеративный подход состоит в раздельном оценивании $P(y)$ и $p(x \mid y)$ по каждому классу, после чего решение принимается по формуле OBC с подставленными оценками. Типичные представители: наивный байесовский классификатор, линейный и квадратичный дискриминантный анализ, смеси распределений, скрытые марковские модели. Название связано с тем, что модель $p(x \mid y)$ может быть использована для генерации новых объектов данного класса.

Дискриминативный подход состоит в непосредственном оценивании апостериорной вероятности $P(y \mid x)$ или разделяющей функции без промежуточного восстановления плотностей $p(x \mid y)$ . Типичные представители: Логистическая регрессия, метод опорных векторов, метрические методы классификации.

Сопоставление дискриминативного и генеративного подходов
Критерий	Генеративный подход	Дискриминативный подход
Что оценивается	$P(y)$ и $p(x \mid y)$ для каждого класса	$P(y \mid x)$ или разделяющая граница напрямую
Требования к данным	выше: нужна точная модель плотности во всей области $X$	ниже: достаточно точности вблизи разделяющей границы
Устойчивость при малой выборке	ниже при неверной модели плотности, но эффективнее при верной	выше при отсутствии знаний о форме $p(x \mid y)$
Интерпретируемость	выше: явная вероятностная модель по классам	ниже: параметры разделяющей функции не имеют прямого вероятностного смысла
Использование новых классов	допускает добавление класса без переобучения по остальным	требует переобучения всей разделяющей модели
Асимптотика при $\ell \to \infty$ и верной модели	сходится к OBC	сходится к OBC

Выбор между подходами определяется соотношением объёма выборки, размерности признакового пространства и наличия априорных знаний о форме распределения $p(x \mid y)$ ^[1].

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

Основное препятствие генеративного подхода — восстановление многомерной плотности $p(x \mid y)$ при $x = (x^1, \dots, x^n)$ : без дополнительных предположений это требует экспоненциально растущего с ростом $n$ объёма выборки (проклятие размерности). Наивный байесовский классификатор преодолевает эту трудность за счёт упрощающего предположения о взаимной независимости признаков внутри каждого класса:

$p(x \mid y) = p(x^1, \dots, x^n \mid y) = \prod_{j=1}^{n} p(x^j \mid y)$

При таком предположении задача сводится к оцениванию $n$ одномерных условных плотностей $p(x^j \mid y)$ вместо одной $n$ -мерной, что радикально снижает требования к объёму выборки. Подставляя разложение в правило MAP, получаем классификатор:

$a(x) = \arg\max_{y \in Y} \left( \ln P(y) + \sum_{j=1}^{n} \ln p(x^j \mid y) \right)$

где переход к логарифмам используется для численной устойчивости при перемножении большого числа сомножителей.

Предположение о независимости признаков в подавляющем большинстве прикладных задач нарушается — признаки, как правило, коррелированы. Тем не менее классификатор демонстрирует высокую устойчивость к нарушению этого предположения: для правильности классификации существен не точный численный расчёт $P(y \mid x)$ , а лишь корректное упорядочение классов по этой величине, и систематическое искажение оценок часто затрагивает все классы согласованно, не меняя итогового упорядочения^[1]. Практическое следствие для размерности задачи: наивный байесовский классификатор остаётся работоспособным при $n$ , сопоставимом или превышающем длину выборки $\ell$ , тогда как методы, восстанавливающие полную совместную плотность, в таком режиме, как правило, неприменимы.

Практическое применение: фильтрация спама

Классическая иллюстрация наивного байесовского классификатора — задача фильтрации спама. Пусть $Y = \{\text{spam}, \text{ham}\}$ , а признаковое описание письма образовано индикаторами присутствия $n$ ключевых слов из заранее фиксированного словаря: $x^j \in \{0, 1\}$ , $x^j = 1$ , если слово $j$ встречается в письме.

Пусть по обучающей выборке из $\ell$ писем получены оценки: $\widehat{P}(\text{spam}) = 0{,}30$ , $\widehat{P}(\text{ham}) = 0{,}70$ , и условные частоты появления трёх ключевых слов — $x^1$ = «выигрыш», $x^2$ = «бесплатно», $x^3$ = «отчёт» — раздельно по классам:

$\widehat{p}(x^1=1 \mid \text{spam}) = 0{,}60$ , $\widehat{p}(x^1=1 \mid \text{ham}) = 0{,}02$
$\widehat{p}(x^2=1 \mid \text{spam}) = 0{,}70$ , $\widehat{p}(x^2=1 \mid \text{ham}) = 0{,}05$
$\widehat{p}(x^3=1 \mid \text{spam}) = 0{,}05$ , $\widehat{p}(x^3=1 \mid \text{ham}) = 0{,}40$

Пусть новое письмо содержит слова «выигрыш» и «бесплатно», но не содержит слова «отчёт»: $x = (x^1, x^2, x^3) = (1, 1, 0)$ . По формуле наивного Байеса:

$\widehat{p}(x \mid \text{spam}) \cdot \widehat{P}(\text{spam}) = 0{,}60 \cdot 0{,}70 \cdot 0{,}95 \cdot 0{,}30 \approx 0{,}1197$

$\widehat{p}(x \mid \text{ham}) \cdot \widehat{P}(\text{ham}) = 0{,}02 \cdot 0{,}05 \cdot 0{,}60 \cdot 0{,}70 \approx 0{,}00042$

После нормировки апостериорная вероятность спама составляет $P(\text{spam} \mid x) \approx 0{,}9965$ , и письмо классифицируется как спам. Данный пример иллюстрирует и типичную практическую проблему: если некоторое слово ни разу не встретилось в обучающих письмах одного из классов, соответствующая частота обращается в ноль и «обнуляет» всё произведение независимо от прочих признаков. Для устранения этого эффекта применяется сглаживание Лапласа (аддитивное сглаживание):

$\widehat{p}(x^j = 1 \mid y) = \frac{c_{jy} + \alpha}{\ell_y + 2\alpha}$

где $c_{jy}$ — число писем класса $y$ , содержащих слово $j$ , $\ell_y$ — общее число писем класса $y$ , $\alpha > 0$ — параметр сглаживания.

Практическое применение: медицинская диагностика

Рассмотрим задачу принятия решения об операции по двум признакам: возраст пациента $x^1$ (лет) и субъективно оцениваемая переносимость инфаркта $x^2$ (балл по шкале тяжести состояния). Пусть $Y = \{1, 0\}$ , где $y=1$ — «операция показана», $y=0$ — «операция не показана», и по накопленной статистике оценены априорные вероятности $\widehat{P}(y=1) = 0{,}25$ , $\widehat{P}(y=0) = 0{,}75$ , а условные плотности признаков в каждом классе приближены нормальным законом с параметрами:

класс $y=1$ : $x^1 \sim \mathcal{N}(58,\ 9^2)$ , $x^2 \sim \mathcal{N}(7{,}2,\ 1{,}1^2)$
класс $y=0$ : $x^1 \sim \mathcal{N}(49,\ 11^2)$ , $x^2 \sim \mathcal{N}(3{,}8,\ 1{,}4^2)$

Принципиальная особенность задачи — асимметрия потерь. Отказ от операции пациенту, которому она была необходима (ошибка $y=1 \to a=0$ ), как правило, значительно опаснее необоснованного назначения операции (ошибка $y=0 \to a=1$ ), сопряжённого с операционными рисками, но не с гарантированным летальным исходом. Пусть матрица потерь задана как

$\lambda_{1,0} = 10, \quad \lambda_{0,1} = 2, \quad \lambda_{1,1} = \lambda_{0,0} = 0$

Тогда правило OBC (общий случай, не сводящийся к MAP из-за неравенства потерь) принимает вид: назначить операцию ( $a=1$ ), если

$\lambda_{0,1} \, P(0 \mid x) < \lambda_{1,0} \, P(1 \mid x)$

то есть

$\frac{P(1 \mid x)}{P(0 \mid x)} > \frac{\lambda_{0,1}}{\lambda_{1,0}} = \frac{2}{10} = 0{,}2$

Порог отношения правдоподобий смещён с «естественного» значения $1$ (соответствующего правилу MAP при равных потерях) до $0{,}2$ — операция назначается уже при сравнительно небольшом перевесе апостериорной вероятности в пользу $y=1$ , что отражает более высокую цену пропуска показанной операции. Для пациента 55 лет с оценкой переносимости $6{,}5$ подстановка в нормальные плотности даёт отношение правдоподобий, заметно превышающее порог $0{,}2$ , что и приводит алгоритм к решению $a(x) = 1$ , тогда как правило простого MAP при тех же данных могло бы дать противоположный ответ.

Байесовское обучение и связь с регуляризацией

До сих пор рассматривалось восстановление плотностей $p(x \mid y)$ в рамках параметрического семейства с фиксированным, но неизвестным вектором параметров $\theta$ , оцениваемым методом максимального правдоподобия:

$\widehat{\theta} = \arg\max_{\theta} \sum_{i=1}^{\ell} \ln p(x_i \mid \theta, y_i)$

Байесовский подход к обучению рассматривает сам параметр $\theta$ как случайную величину с априорным распределением $p(\theta)$ , отражающим предварительные предположения о его правдоподобных значениях до наблюдения выборки. По формуле Байеса апостериорное распределение параметров имеет вид

$p(\theta \mid X^{\ell}) \propto p(X^{\ell} \mid \theta) \, p(\theta) = p(\theta) \prod_{i=1}^{\ell} p(x_i \mid \theta, y_i)$

Точечная оценка, максимизирующая апостериорную плотность параметра, называется MAP-оценкой:

$\widehat{\theta}_{\mathrm{MAP}} = \arg\max_{\theta} \left( \ln p(\theta) + \sum_{i=1}^{\ell} \ln p(x_i \mid \theta, y_i) \right)$

Сопоставление с методом максимального правдоподобия показывает, что MAP-оценка отличается от $\widehat{\theta}_{\mathrm{ML}}$ ровно на слагаемое $\ln p(\theta)$ — логарифм априорной плотности параметра. Это устанавливает точное соответствие между регуляризацией и байесовским априорным распределением: любой регуляризатор $\Omega(\theta)$ , добавляемый к функционалу правдоподобия со знаком минус, эквивалентен выбору априорного распределения $p(\theta) \propto \exp(-\Omega(\theta))$ . В частности:

нормальное априорное распределение $p(\theta) \propto \exp\left(-\frac{\|\theta\|^2}{2\tau^2}\right)$ эквивалентно $L_2$ -регуляризации (гребневая регрессия, weight decay);
распределение Лапласа $p(\theta) \propto \exp(-\gamma \|\theta\|_1)$ эквивалентно $L_1$ -регуляризации, порождающей разреженные решения.

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

Ограничения на малых выборках

Байесовские оценки $\widehat{P}(y)$ и $\widehat{p}(x \mid y)$ , лежащие в основе OBC, строятся по эмпирическим частотам и распределениям в подвыборках, соответствующих отдельным классам. При малом объёме выборки $\ell$ и значительном числе признаков $n$ точность таких оценок резко падает по следующим причинам.

Число объектов, приходящихся на каждый класс, $\ell_y \ll \ell$ при большом числе классов или при существенном дисбалансе классов, из-за чего оценка $\widehat{p}(x \mid y)$ строится по недостаточной статистике.
При отсутствии предположения о независимости признаков объём данных, необходимый для надёжного восстановления $n$ -мерной плотности, растёт экспоненциально с $n$ (проклятие размерности), что делает генеративные модели общего вида практически неприменимыми уже при умеренных $n$ .
Даже при использовании наивного предположения о независимости оценки одномерных плотностей $\widehat{p}(x^j \mid y)$ становятся неустойчивыми при малом $\ell_y$ , а редко встречающиеся значения признаков (в частности, для дискретных признаков) приводят к обнулению оценок и требуют сглаживания.
Как следствие первого замечания раздела «Два принципиальных замечания», разность $R(\widehat{a}) - R(a^{*})$ между риском подстановочного классификатора и риском OBC растёт с уменьшением $\ell$ и ростом $n$ , и на малых выборках может оказаться сопоставимой с самим риском, обесценивая теоретическую оптимальность OBC на практике.

В таких режимах смещение выбора в пользу дискриминативных методов, методов с сильной регуляризацией (см. предыдущий раздел) или байесовского усреднения по параметрам вместо точечных MAP-оценок, как правило, даёт более устойчивый результат, чем прямое построение подстановочного байесовского классификатора.

Литература

Источник — «http://recognition.su/wiki/index.php?title=%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%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»

Категории: Байесовские методы | Энциклопедия анализа данных | Классификация | Теория вероятностей и математическая статистика