§ 7. Свойства функции роста
Функция роста класса решающих правил имеет простой смысл: она равна максимальному числу способов разделения
точек на два класса с помощью решающих правил
.
В главе X будет показано, что функция роста обладает одним замечательным свойством, которое дает возможность ее легко оценивать: она либо тождественно равна
, либо мажорируется степенной функцией
, где
– минимальное число, при котором нарушается равенство
.
В первом случае для любого
найдется комбинация точек
такая, что ее можно разбить всеми возможными способами на два класса с помощью решающих правил
.
Во втором случае это не всегда возможно. Существует максимальное число точек
, которое еще разбивается всеми возможными способами с помощью правил
, но уже никакие
точек этим свойством не обладают. Оказывается, что при этом функция роста мажорируется степенной функцией с показателем роста
.
Число
, таким образом, может служить мерой разнообразия решающих правил в классе
. Мы будем называть его емкостью класса
(при
считаем емкость бесконечной).
Нетрудно убедиться, что, если емкость класса конечна, всегда имеет место равномерная сходимость частот к вероятностям. В самом деле, при этом
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_39.files/image010.gif)
и достаточное условие выполнено.
Найдем функцию роста для класса линейных решающих функций. Для этого достаточно определить максимальное число точек в пространстве размерности
, которые с помощью гиперплоскости можно разбить всеми возможными способами на два класса. Известно, что это число равно
. Поэтому
.
Тот факт, что емкость класса линейных правил конечна (равна
), доказывает обобщенную теорему Гливенко. Отметим, что для гиперплоскостей, проходящих через начало координат, более точная оценка функции роста фактически была выведена в предыдущем параграфе.