§ 9. Оценка уклонения эмпирически оптимального решающего правила
В приложении к главе получена оценка скорости равномерной сходимости частот к вероятностям по классу событий 
Показано, что имеет место неравенство
Оценка (6.41) имеет тот же вид, что и раньше, - она образуется произведением емкостной характеристики системы событий 
и оценкой вероятности того, что уклонение частоты от вероятности превзойдет 
Если емкость класса решающих правил бесконечна 
, то оценка (6.41) травиальна, так как при всех к правая часть неравенства больше единицы. Оценка (6.41) становится содержательной, когда емкость класса
решающих правил конечна:
В этом случае она принимает вид
С ростом 
правая часть неравенства (6.42) стремится к нулю и притом тем быстрее, чем меньше емкость класса 
Потребуем, чтобы вероятность
не превышала 
. Это во всяком случае произойдет, если выполняется равенство
Равенство (6.43) можно разрешить относительно к (используя формулу Стирлинга):
И тогда из (6.42) — (6.44) следует справедливость следующей теоремы.
Теорема 6.7. Пусть 
— класс решающих правил ограниченной емкости 
и пусть 
— частота ошибок, вычисленная по обучающей последовательности для правила 
Тогда с вероятностью 
можно утверждать, что при 
одновременно для всех правил 
вероятность ошибочной классификации заключена в пределах
Замечание. Из теоремы 6.7 следует, что для правила 
минимизирующего эмпирический риск, с
вероятностью 
справедлива оценка сверху
В приложении к главе показано, что наряду с (6.41) справедлива и оценка
которая для класса решающих правил ограниченной емкости является нетривиальной:
Потребуем, чтобы правая часть неравенства равнялась 
Это произойдет, если
С другой стороны, неравенство (6.45) можно переписать в виде утверждения: с вероятностью 
одновременно для всех а справедливо неравенство
Из (6.46) и (6.47) следует справедливость следующей теоремы.
Теорема 6.8. Пусть 
класс решающих правил ограниченной емкости 
и пусть для каждого правила 
частота ошибок, вычисленная на обучающей последовательности, равна 
Тогда с вероятностью 
можно утверждать, что при 
одновременно для всех
правил класса имеет место оценка
Замечание. Из теоремы 6.8 следует, что для правила 
минимизирующего эмпирический риск, справедлива оценка
