§ 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) следует, что

.