Глава X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ СХОДИМОСТИ ЧАСТОТ К ВЕРОЯТНОСТЯМ ПО КЛАССУ СОБЫТИЙ
§ 1. О близости минимума эмпирического риска к минимуму среднего риска
Перейдем теперь к анализу методов, основанных на минимизации эмпирического риска. Пусть задана выборка

полученная в серии независимых испытаний при неизменном распределении
, и известна функция
. Требуется найти минимум функционала
.
В дальнейшем будем полагать, что минимум
существует и достигается при
.
Рассматриваются методы, где в качестве приближения берется значение
, доставляющее минимум функции
.
Естественно, в качестве меры близости
и
взять разность значений функционала
в этих точках:
.
Как было указано в главе V, близость значений
и
в этом смысле может быть гарантирована, если функция
равномерно по параметру
приближает функцию
. В самом деле, если
,
то
, (10.1)
. (10.2)
Кроме того, поскольку
и
– точки минимума соответственно функций
и
, то
, (10.3)
. (10.4)
Из (10.1)–(10.4) непосредственно вытекает, что
.
Или, иначе,
. (10.5)
Таким образом, если отклонение функций
и
при всех значениях параметра не превосходит
, то значение истинного риска
в точке эмпирического оптимума
не более чем на
отклоняется от минимального. Если же максимальное по
уклонение риска
и его эмпирической оценки велико, то, вообще говоря, замена истинного минимума эмпирическим может привести к большим ошибкам.
В задаче обучения распознаванию образов функция
в функционале
имеет специальный вид. Здесь каждый элемент
есть пара
, где
– описание ситуации, а
– указатель класса, к которому в действительности относится эта ситуация. Обычно число классов невелико, т. е.
может принимать конечное небольшое число значений
. Каждому значению параметра
соответствует решающее правило
, причем функция
принимает те же дискретные значения, что и
.
В качестве критерия
обычно берется вероятность неправильной классификации с помощью правила
. Это значит, что определена функция штрафа

и функционал
задан в виде
.
Функция
есть характеристическая функция множества
.
Соответственно функционал
при каждом значении
есть вероятность события
:
.
Эмпирическая оценка
равна частоте
появлений этого события в обучающей выборке, т. е. частоте ошибок на материале обучения. Пусть теперь параметр
принимает всевозможные допустимые значения
. Соответствующие события
образуют класс событий
. Равномерная близость функций
и
означает равномерную близость частот и вероятностей событий
по классу
.
Применяя формулу (10.5) в данном случае, имеем
. (10.5')
В более общем случае проблема равномерной сходимости функций
и
также может быть сведена к равномерной сходимости частот к вероятностям в определенном классе событий (§ 2 главы XIII).
Перейдем теперь к выводу условий, которым должен удовлетворять класс событий
для того, чтобы выполнялась равномерная по классу сходимость частот появления событий к их вероятностям. Существенно, что при определенных условиях удается получить оценку равномерной близости частот к вероятностям, не зависящую от распределения
, которое обычно неизвестно, и определяемую только внутренней структурой класса
. Эта оценка не содержит произвольных констант и позволяет эффективно оценить близость эмпирического оптимального решающего правила к истинному для заданного класса решающих правил при фиксированной длине обучающей последовательности.