Глава X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ СХОДИМОСТИ ЧАСТОТ К ВЕРОЯТНОСТЯМ ПО КЛАССУ СОБЫТИЙ

§ 1. О близости минимума эмпирического риска к минимуму среднего риска

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

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

.

В дальнейшем будем полагать, что минимум  существует и достигается при .

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

.

Естественно, в качестве меры близости  и  взять разность значений функционала  в этих точках:

.

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

,

то

,                     (10.1)

.                     (10.2)

Кроме того, поскольку  и  – точки минимума соответственно функций  и , то

,                   (10.3)

.                     (10.4)

Из (10.1)–(10.4) непосредственно вытекает, что

.

Или, иначе,

.               (10.5)

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

В задаче обучения распознаванию образов функция  в функционале  имеет специальный вид. Здесь каждый элемент  есть пара , где  – описание ситуации, а  – указатель класса, к которому в действительности относится эта ситуация. Обычно число классов невелико, т. е.  может принимать конечное небольшое число значений . Каждому значению параметра  соответствует решающее правило , причем функция  принимает те же дискретные значения, что и .

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

и функционал  задан в виде

.

Функция  есть характеристическая функция множества

.

Соответственно функционал  при каждом значении  есть вероятность события :

.

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

Применяя формулу (10.5) в данном случае, имеем

.                (10.5')

В более общем случае проблема равномерной сходимости функций  и  также может быть сведена к равномерной сходимости частот к вероятностям в определенном классе событий (§ 2 главы XIII).

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