§ 8. Оценка уклонения эмпирически оптимального решающего правила

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

.                  (5.9)

Оценка имеет тот же вид, что и для конечной системы событий, но вместо числа событий  в правой части неравенства стоит функция роста. Таким образом, функция роста служит мерой разнообразия класса событий.

Если емкость класса бесконечна , оценка (5.9) тривиальна, так как правая часть неравенства больше единицы при всех .

Если же емкость  конечна, оценка приобретает вид

.                  (5.10)

Правая часть неравенства стремится к нулю при  и притом тем быстрее, чем меньше . Можно потребовать, чтобы вероятность  не превышала заданное значение .

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

.

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

.                (5.11)

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

,

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

.

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

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

.                   (5.12)

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