§ 5. Верхние оценки вероятности ошибок

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

1. Теоремы 6.1 и 6.2 немедленно получаются из оценки скорости равномерной сходимости частот к вероятностям по классу событий. Теорема 6.1 основана на оценке (6.16) скорости равномерной сходимости частот к вероятностям по классу событий Теорема 6.2 — на оценке скорости равномерной сходимости по более узкому классу Обозначим этот класс через

2. В обоих случаях скорость равномерной сходимости определялась произведением двух величин; числа событий в классе и оценки вероятности того, что частота любого фиксированного события в классе уклонится больше чем на х от вероятности этого события. Для событий, рассмотренных в теореме 6.1, эта вероятность не превосходит для событий же, рассмотренных в

теореме 6.2, аналогичная вероятность не превосходит .

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

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

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

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

а не величины

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

4. Оценки скорости равномерной сходимости (6.16) и (6.23) существенно зависят от оценки вероятности уклонения частоты от вероятности для события из

рассматриваемого класса или Для класса наиболее неблагоприятное событие для которого Поэтому возможна лишь оценка Для класса событий наиболее неблагоприятное событие — то, для которого Для оценки вероятности уклонения частоты от вероятности этого события возможна более тонкая оценка (6.22). Таким образом, оценки, полученные для событий и различаются так, как различаются оценки вероятности уклонения события для которого и события для которого Это обстоятельство заставляет внимательнее отнестись к тем требованиям, которые предъявляются к величинам уклонения частот от вероятностей для различных событий в классе. Для наших целей — получения равномерной оценки риска разумно требовать не равномерного уклонения частот от вероятностей для всей событий в классе, а разрешить большее уклонение для тех событий, для которых и меньшее — для событий с вероятностью Например, разумно оценивать равномерную относительную величину уклонения

где для малых справедливо: Найдем оценку вероятности одностороннего относительного уклонения

и построим с ее помощью верхнюю оценку вероятности ошибочной классификации. Для получения оценки вероятности (6.26) воспользуемся следующим фактом (неравенство Бернштейна):

Из справедливости (6.27) следует, что для класса, состоящего из событий, имеет место следующая оценка

скорости равномерной сходимости:

Потребуем, чтобы вероятность равномерного одностороннего относительного уклонения (6.28) не превосходила

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

Пусть условие (6.29) выполнено. Тогда с вероятностью одновременно для всех событий выполняются неравенства

Разрешая неравенства (6.30) относительно получим, что с вероятностью одновременно для всех событий класса справедливо

Подставляя (6.29) в (6.31), получим, что с вероятностью одновременно выполняются неравенств

Таким образом, мы доказали теорему.

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

Замечание. Так как с вероятностью оценка (6.32) справедлива одновременно для всех правил класса, то

она выполняется и для правила минимизирующего эмпирический риск.

Теорема 6.3 позволяет оценить качество правила, минимизирующего эмпирический риск. При этом оценка (6.32) совпадает с оценкой теоремы 6.2, полученной для крайнего случая, когда и близка к оценке теоремы 6.1 для другого крайнего случая, когда Точно такая же структура оценки будет иметь место и для бесконечного класса решающих правил.