Распознаванию образов: § 14. Приложение к главе VI

§ 14. Приложение к главе VI

Оценим снизу величину минимакса потерь в задачах обучения распознаванию образов.

Пусть задан класс решающих правил , . Рассмотрим некоторый круг задач обучения , совокупность алгоритмов, выбирающих по обучающей последовательности решающее правило вида . Величина минимакса потерь определена так:

где – качество алгоритма при решении задачи , – качество решающего правила для задачи .

Примем что алгоритм оптимален в смысле минимакса потерь, т. е.

Пусть теперь известно, что задачи из могут появиться с вероятностью и алгоритм оптимален в смысле средней величины потерь при решении этих задач, т. е.

Нетрудно убедиться, что

. (П.1)

В самом деле,

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

(П.2)

(равенство достигается, если ).

Таким образом, из (П.1), (П.2) получаем

(П.3)

и для оценки снизу минимакса потерь достаточно рассмотреть некоторую совокупность задач с заданными вероятностями появления, построить оптимальный по Байесу алгоритм и найти в этом случае среднюю величину потерь .

Случай 1. Оценим величину для задач обучения в детерминистской постановке, когда допустимы только такие задачи, что в классе есть безошибочное решающее правило ( для любой задачи ).

Пусть характеризует емкость класса ; тогда (см. главы V, X) существует точек таких, что правила из разбивают их всеми возможными способами. Поставим каждому разбиению точек в соответствие задачу (всего задач) следующим образом.

Полагаем, что вероятностная мера сосредоточена в точках , причем точка имеет вероятность , а остальные равновероятны и имеют вероятности .

Точка принадлежит первому классу, если разбиением она отнесена к первому классу, и принадлежит второму классу, если разбиением она отнесена ко второму классу. Иными словами,

если отнесена разбиением к первому классу;

если отнесена разбиением ко второму классу. Этими соотношениями задача задана полностью. Очевидно, что для каждой задачи в классе есть безошибочное решающее правило.

Предположим далее, что задачи появляются с равной вероятностью

Можно убедиться, что оптимальный по Байесу алгоритм для этой совокупности задач таков.

Пусть дана обучающая последовательность длины ; с вероятностью 1 в ней встречаются только точки из набора . Точки из набора , встретившиеся в обучающей последовательности, следует относить к тому классу, к которому они отнесены в материале обучения. Классификация остальных точек безразлична. При этом средние потери равны

. (П.4)

Здесь – средние потери при классификации точки при условии, что она не встретится в обучении; – вероятность того, что она не встретится в обучении; аналогично – средние потери при классификации точки при условии, что она не встретится в обучении, a – вероятность осуществления этого условия.

Найдем значение , при котором выражение

достигает максимума. Это произойдет, если

Подставляя в (П. 4) и учитывая (П.3), получаем

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

Пусть , как и ранее, совокупность точек, разбиваемых правилами из всеми возможными способами. Поставим в соответствие каждому разбиению задачу следующим образом.

1. Вероятность сосредоточена в точках , причем все точки равновероятны: .

2. Условная вероятность в точках задана так:

Оптимальным решающим правилом в классе для задачи , очевидно, является такое правило , которое классифицирует точки в соответствии с разбиением . При этом качество

Оптимальная по Байесу стратегия обучения в случае оказывается следующей:

а) Допустим, что точка встречалась в материале обучения, причем раз была отнесена к первому классу и раз ко второму. Тогда точку следует отнести к первому классу, если , и ко второму, если . При классификация безразлична (выбирается на удачу).

б) Если точка не встречалась в обучающей последовательности, ее классификация безразлична (выбирается на удачу).

Потери при решении каждой задачи по этому алгоритму равны между собой и задаются выражением

где – потери, если точка , относимая разбиением к первому классу, будет отнесена после обучения ко второму , или соответственно, наоборот, точка, относимая ко второму, будет отнесена в результате обучения к первому классу ; – потери в случае, когда ; – вероятность того, что при или при ; – вероятность того, что . Точные значения и задаются формулами: