§ 8. Оценка уклонения эмпирически оптимального решающего правила
В главе X будет получена оценка
скорости равномерной сходимости. Оказывается, что
. (5.9)
Оценка имеет тот же вид, что и
для конечной системы событий, но вместо числа событий 
в правой части неравенства
стоит функция роста. Таким образом, функция роста служит мерой разнообразия
класса событий.
Если емкость класса бесконечна 
, оценка (5.9) тривиальна,
так как правая часть неравенства больше единицы при всех 
.
Если же емкость 
конечна, оценка
приобретает вид
. (5.10)
Правая часть неравенства
стремится к нулю при 
и притом тем быстрее, чем меньше . Можно потребовать,
чтобы вероятность 
не
превышала заданное значение 
.
Это во всяком случае произойдет,
если
.
Это равенство можно разрешить
относительно 
.
Таким образом, справедливо утверждение: с вероятностью, не превышающей 
, максимальное по
классу 
уклонение
частоты выпадения событий от вероятности не превосходит
. (5.11)
Отсюда, в силу сказанного в § 2,
непосредственно следует, что с вероятностью, превышающей , качество эмпирически
оптимального решающего правила отличается от качества истинно оптимального не
более чем на 
,
т. е.
,
где
– длина
обучающей выборки, а – емкость класса решающих правил, из
которого осуществляется выбор. В частности, для линейных решающих правил в
пространстве размерности 
.
Таким образом, при заданной длине
обучающей выборки качество решающего правила, выбранного алгоритмом, тем ближе
к наилучшему в классе, чем меньше емкость класса 
. Но следует помнить, что качество
наилучшего в классе решающего
правила, вообще говоря, напротив, тем выше, чем шире класс .
Разрешая равенство (5.11)
относительно ,
можно оценить для фиксированной точности и надежности достаточную длину обучающей
последовательности (см. главу XIII). Оказывается, что качество эмпирически
оптимального решающего правила с вероятностью, превышающей , отличается от наилучшего в
классе не
более чем на ,
если только длина обучающей выборки достигает
. (5.12)
Следовательно, достаточная длина
выборки пропорциональна емкости класса решающих функций. В частности, для
линейных решающих функций в -мерном спрямляющем пространстве
достаточная длина пропорциональна размерности .
