§ 14. Приложение к главе VI
Оценим снизу величину минимакса потерь в задачах обучения распознаванию образов.
Пусть задан класс решающих правил
,
. Рассмотрим некоторый круг задач обучения
, совокупность
алгоритмов, выбирающих по обучающей последовательности решающее правило вида
. Величина минимакса потерь
определена так:
,
,
где
– качество алгоритма
при решении задачи
,
– качество решающего правила
для задачи
.
Примем что алгоритм
оптимален в смысле минимакса потерь, т. е.
.
Пусть теперь известно, что задачи
из
могут появиться с вероятностью
и алгоритм
оптимален в смысле средней величины потерь при решении этих задач, т. е.
.
Нетрудно убедиться, что
. (П.1)
В самом деле,
.
Пусть, наконец,
– оптимальный по Байесу алгоритм для задач
, появляющихся с вероятностями
, и
– средние потери для этого алгоритма (алгоритм
не обязательно принадлежит
). Тогда
(П.2)
(равенство достигается, если
).
Таким образом, из (П.1), (П.2) получаем
(П.3)
и для оценки снизу минимакса потерь достаточно рассмотреть некоторую совокупность задач с заданными вероятностями появления, построить оптимальный по Байесу алгоритм и найти в этом случае среднюю величину потерь
.
Случай 1. Оценим величину
для задач обучения в детерминистской постановке, когда допустимы только такие задачи, что в классе
есть безошибочное решающее правило (
для любой задачи
).
Пусть
характеризует емкость класса
; тогда (см. главы V, X) существует
точек
таких, что правила из
разбивают их всеми возможными способами. Поставим каждому разбиению
точек
в соответствие задачу
(всего
задач) следующим образом.
Полагаем, что вероятностная мера
сосредоточена в точках
, причем точка
имеет вероятность
, а остальные равновероятны и имеют вероятности
.
Точка
принадлежит первому классу, если разбиением
она отнесена к первому классу, и принадлежит второму классу, если разбиением
она отнесена ко второму классу. Иными словами,
,
если
отнесена разбиением
к первому классу;
,
если
отнесена разбиением
ко второму классу. Этими соотношениями задача
задана полностью. Очевидно, что для каждой задачи
в классе
есть безошибочное решающее правило.
Предположим далее, что задачи
появляются с равной вероятностью
.
Можно убедиться, что оптимальный по Байесу алгоритм для этой совокупности задач таков.
Пусть дана обучающая последовательность длины
; с вероятностью 1 в ней встречаются только точки из набора
. Точки из набора
, встретившиеся в обучающей последовательности, следует относить к тому классу, к которому они отнесены в материале обучения. Классификация остальных точек безразлична. При этом средние потери равны

. (П.4)
Здесь
– средние потери при классификации точки
при условии, что она не встретится в обучении;
– вероятность того, что она не встретится в обучении; аналогично
– средние потери при классификации точки
при условии, что она не встретится в обучении, a
– вероятность осуществления этого условия.
Найдем значение
, при котором выражение

достигает максимума. Это произойдет, если
.
Подставляя
в (П. 4) и учитывая (П.3), получаем

.
Случай 2. Пусть теперь задачи
произвольны, а алгоритмы
выбирают по-прежнему из класса
емкости
(задача в вероятностной постановке). Оценим величину минимакса потерь
.
Пусть
, как и ранее, совокупность точек, разбиваемых правилами из
всеми возможными способами. Поставим в соответствие каждому разбиению
задачу
следующим образом.
1. Вероятность
сосредоточена в точках
, причем все точки равновероятны:
.
2. Условная вероятность
в точках
задана так:

.
Оптимальным решающим правилом в классе
для задачи
, очевидно, является такое правило
, которое классифицирует точки
в соответствии с разбиением
. При этом качество
.
Оптимальная по Байесу стратегия обучения
в случае оказывается следующей:
а) Допустим, что точка
встречалась в материале обучения, причем
раз была отнесена к первому классу и
раз ко второму. Тогда точку
следует отнести к первому классу, если
, и ко второму, если
. При
классификация безразлична (выбирается на удачу).
б) Если точка
не встречалась в обучающей последовательности, ее классификация безразлична (выбирается на удачу).
Потери при решении каждой задачи
по этому алгоритму равны между собой и задаются выражением
,
где
– потери, если точка
, относимая разбиением
к первому классу, будет отнесена после обучения ко второму
, или соответственно, наоборот, точка, относимая
ко второму, будет отнесена в результате обучения к первому классу
;
– потери в случае, когда
;
– вероятность того, что
при
или
при
;
– вероятность того, что
. Точные значения
и
задаются формулами:
, (П.5)
. (П.6)
При
положим
. Тогда
. (П.7)
При
положим
. В этом случае учтем только первые члены суммы (П.5) и (П.6) (в первой сумме
, во второй
):
. (П.8)
При
положим

и аппроксимируем распределение величины
нормальным законом (для определенности считаем, что
). Эта величина имеет математическое опадание и дисперсию
,
.
Таким образом, нормальное распределение имеет вид
,
откуда
.
При 
.
Таким образом,
. (П.9)
Итак из (П.7), (П.8), (П.9) следует, что
.