§ 2. Равномерная сходимость частот появления событий к их вероятностям

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

.

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

для каждого решающего правила , определяет частоту неправильной классификации на обучающей последовательности.

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

Предположим для наглядности, что решающие правила  задаются скаляром , который может принимать значения от 0 до 1. Каждому значению  ставится в соответствие решающее правило, для которого существует вероятность ошибки . Таким образом, каждому  может быть поставлено в соответствие число . Рассмотрим функцию  (рис. 10).

Рис. 10

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

Метод минимизации эмпирического риска предлагает по минимуму функции  судить о минимуме функции . Для того чтобы по точке минимума и минимальному значению функции  можно было судить о точке минимума функции  и о ее минимальном значении, достаточно, чтобы кривая  находилась внутри -трубки кривой . Напротив, выброс хотя бы в одной точке (как на рис. 10) может привести к тому, что в качестве минимального значения  будет выбрана точка выброса. В этом случае минимум  никак не характеризует минимум функции . Если же функция  приближает  равномерно по  с точностью , то качество эмпирически оптимального решающего правила отличается от качества истинно оптимального правила не более чем на .

Формально это означает, что нас интересуют не классические условия, когда для любых  и  имеет место

,

а более сильные условия, когда для любого  справедливо

.                  (5.1)

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

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