§ 4. Емкость множества произвольных функций

В главе VI мы ввели понятие «емкость» для множества характеристических функций. Емкость определялась максимальным числом точек которые всеми возможными способами могли быть разделены на два класса с помощью заданного множества характеристических функций.

Распространим теперь понятие «емкость» на множества функций произвольной природы. Для этого введем параметрическое множество характеристических функций

(по параметрам ; S — действительное число).

Определение. Назовем емкостью множества емкость множества характеристических функций .

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

Емкость множества линейных по параметрам функций

равна

При таком определении емкости функция роста системы событий

при оценивается величиной

Итак, пусть емкость множества функций равна и по-прежнему функция потерь ограничена величиной В этих условиях справедлива

Теорема 7.3. При с вероятностью одновременно для всего класса функций выполняются неравенства

Доказательство. Выразим функционалы через интегралы Лебега:

Здесь означает вероятность события частоту этого события, вычисленную на обучающей последовательности.

Обозначим через событие

Тогда

И следовательно,

Далее следует

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

Приравняв правую часть неравенства величине и разрешив это равенство относительно х, получим

Таким образом, из (7.13) и (7.14) следует, что при с вероятностью одновременно для всех функций множества выполняются неравенства

Теорема доказана.