§ 7. Свойства функции роста

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

В главе X будет показано, что функция роста обладает одним замечательным свойством, которое дает возможность ее легко оценивать: она либо тождественно равна , либо мажорируется степенной функцией , где  – минимальное число, при котором нарушается равенство .

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

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

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

Нетрудно убедиться, что, если емкость класса конечна, всегда имеет место равномерная сходимость частот к вероятностям. В самом деле, при этом

и достаточное условие выполнено.

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

.

Тот факт, что емкость класса линейных правил конечна (равна ), доказывает обобщенную теорему Гливенко. Отметим, что для гиперплоскостей, проходящих через начало координат, более точная оценка функции роста фактически была выведена в предыдущем параграфе.