Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

Это во всяком случае произойдет, если

Это равенство можно разрешить относительно е. Таким образом, справедливо утверждение: с вероятностью, не превышающей 1 — р, максимальное по классу S укло­ нение частоты выпадения событий от вероятности не пре­ восходит

Отсюда, в силу сказанного в § 2, непосредственно сле­ дует, что с вероятностью, превышающей 1 — р, качество эмпирически оптимального решающего правила отлича­ ется от качества истинно оптимального не более чем на Л — 2е, т. е.

где I — длина обучающей выборки, а г — емкость класса решающих правил, из которого осуществляется выбор. В частности, для линейных решающих правил в простран­ стве размерности т

Таким образом, при заданной длине обучающей вы­ борки качество решающего правила, выбранного алго­ ритмом, тем ближе к наилучшему в классе, чем меньше емкость класса £2. Но следует помнить, что качество наи­ лучшего в классе Q решающего правила, вообще говоря, напротив, тем выше, чем шире класс Q.

Разрешая равенство (5.11) относительно I, можно оценить для фиксированной точности и надежности до­ статочную длину обучающей последовательности (см. главу XIII). Оказывается, что качество эмпирически оптимального решающего правила с вероятностью,

превышающей 1—ц, отличается от наилучшего в классе Q не более чем на е, если только длина обучающей выборки достигает

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

§9. Метод минимизации эмпирического риска

вдетерминистской постановке задачи обучения

распознаванию образов

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

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

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

вы борку Хх, . . ., Ж(.

!-й Искать такое решающее правило будем'методом мини­ мизации эмпирического риска. Так как среди функций {F (х, а,})} есть та, которая идеально решает задачу, то заведомо ясно, что на любой выборке хх, . . ., xt зна­ чение минимума эмпирического риска будет равно нулю.

Однако этот минимум может достигаться на многих функциях. Поэтому возникает необходимость оценить ве-

§ 9. МИНИМИЗАЦИЯ РИСКА В ДЕТЕРМИНИСТСКОЙ ЗАДАЧЕ Ю5

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

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

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

{sup I V* — Р і І-Ѳ (ѵj) > е}.

г

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

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

РІ < (1 - б)'.

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

Р {sup [ ѵ4 — Рі I -Ѳ (Vj) > e} < N (1 — e)'.

І

Для того чтобы вероятность Р {sup [ ѵг— Р і |-Ѳ(ѵг) Д> е} i

не превосходила величину Г|, достаточно выполнения

9 10. ЗАМЕЧАНИЕ ОБ ОЦЕНКЕ СКОРОСТИ СХОДИМОСТИ Ю7

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

Р {sup I Р (а) — V(а) I • Ѳ(ѵ(а)) )> е}

а

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

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

§10. Замечание об оценке скорости равномерной сходимости частот появления событий

ких вероятностям

Почему же оценки, полученные для детерминистского и стохастического вариантов постановки задачи, так сильно различаются

Объяснение этому частично дано в предыдущем пара­ графе, где формулы (5.3), (5.10) и (5.13), (5.18) определяют скорости равномерной сходимости частот появления событий к их вероятностям по различным классам событий S.

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