Глава X. ДОСТАТОЧНЫЕ УСЛОВИЯ РАВНОМЕРНОЙ СХОДИМОСТИ ЧАСТОТ К ВЕРОЯТНОСТЯМ ПО КЛАССУ СОБЫТИЙ§ 1. О близости минимума эмпирического риска к минимуму среднего рискаПерейдем теперь к анализу методов, основанных на минимизации эмпирического риска. Пусть задана выборка полученная в серии независимых испытаний при неизменном распределении , и известна функция . Требуется найти минимум функционала . В дальнейшем будем полагать, что минимум существует и достигается при . Рассматриваются методы, где в качестве приближения берется значение , доставляющее минимум функции . Естественно, в качестве меры близости и взять разность значений функционала в этих точках: . Как было указано в главе V, близость значений и в этом смысле может быть гарантирована, если функция равномерно по параметру приближает функцию . В самом деле, если , то , (10.1) . (10.2) Кроме того, поскольку и – точки минимума соответственно функций и , то , (10.3) . (10.4) Из (10.1)–(10.4) непосредственно вытекает, что . Или, иначе, . (10.5) Таким образом, если отклонение функций и при всех значениях параметра не превосходит , то значение истинного риска в точке эмпирического оптимума не более чем на отклоняется от минимального. Если же максимальное по уклонение риска и его эмпирической оценки велико, то, вообще говоря, замена истинного минимума эмпирическим может привести к большим ошибкам. В задаче обучения распознаванию образов функция в функционале имеет специальный вид. Здесь каждый элемент есть пара , где – описание ситуации, а – указатель класса, к которому в действительности относится эта ситуация. Обычно число классов невелико, т. е. может принимать конечное небольшое число значений . Каждому значению параметра соответствует решающее правило , причем функция принимает те же дискретные значения, что и . В качестве критерия обычно берется вероятность неправильной классификации с помощью правила . Это значит, что определена функция штрафа и функционал задан в виде . Функция есть характеристическая функция множества . Соответственно функционал при каждом значении есть вероятность события : . Эмпирическая оценка равна частоте появлений этого события в обучающей выборке, т. е. частоте ошибок на материале обучения. Пусть теперь параметр принимает всевозможные допустимые значения . Соответствующие события образуют класс событий . Равномерная близость функций и означает равномерную близость частот и вероятностей событий по классу . Применяя формулу (10.5) в данном случае, имеем . (10.5') В более общем случае проблема равномерной сходимости функций и также может быть сведена к равномерной сходимости частот к вероятностям в определенном классе событий (§ 2 главы XIII). Перейдем теперь к выводу условий, которым должен удовлетворять класс событий для того, чтобы выполнялась равномерная по классу сходимость частот появления событий к их вероятностям. Существенно, что при определенных условиях удается получить оценку равномерной близости частот к вероятностям, не зависящую от распределения , которое обычно неизвестно, и определяемую только внутренней структурой класса . Эта оценка не содержит произвольных констант и позволяет эффективно оценить близость эмпирического оптимального решающего правила к истинному для заданного класса решающих правил при фиксированной длине обучающей последовательности.
|