§ 9. Метод минимизации эмпирического риска в детерминистской постановке задачи обучения распознаванию образов

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

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

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

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

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

Введем функцию

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

.

Так как число функций, на которых достигается нуль величины эмпирического риска, не превосходит  – числа всех элементов в классе, то справедливо неравенство

,                 (5.13)

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

.

Подставляя оценку  в (5.13), получим

.

Для того чтобы вероятность  не превосходила величину , достаточно выполнения условия

.                       (5.14)

Разрешая относительно  это равенство, получим

.                      (5.15)

Так как для малых  справедливо , то формула (5.15) может быть представлена в виде

.                      (5.16)

В отличие от оценки (5.6) здесь знаменатель равен , а не . Разрешая (5.14) относительно , аналогично получим

.                      (5.17)

Таким образом, справедлива следующая теорема.

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

.

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

,                      (5.18)

где  – функция роста класса решающих правил . В (5.18) величина  играет роль «числа элементов» в классе.

Если объем класса ограничен:

,

т. е. выполнены достаточные условия равномерной сходимости, то можно потребовать, чтобы вероятность

не превосходила заданное значение .

Это заведомо произойдет, если величины , , ,  будут связаны соотношением

.

Разрешая это равенство относительно , можно получить (см. главу ХШ)

                    (5.19)

(в отличие от (5.12) здесь знаменатель не , а ). Разрешим еще это же равенство относительно . Заменяя  по формуле Стирлинга, получаем

.                   (5.19')

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