§ 7. Свойства функции ростаФункция роста класса решающих правил имеет простой смысл: она равна максимальному числу способов разделения точек на два класса с помощью решающих правил . В главе X будет показано, что функция роста обладает одним замечательным свойством, которое дает возможность ее легко оценивать: она либо тождественно равна , либо мажорируется степенной функцией , где – минимальное число, при котором нарушается равенство . В первом случае для любого найдется комбинация точек такая, что ее можно разбить всеми возможными способами на два класса с помощью решающих правил . Во втором случае это не всегда возможно. Существует максимальное число точек , которое еще разбивается всеми возможными способами с помощью правил , но уже никакие точек этим свойством не обладают. Оказывается, что при этом функция роста мажорируется степенной функцией с показателем роста . Число , таким образом, может служить мерой разнообразия решающих правил в классе . Мы будем называть его емкостью класса (при считаем емкость бесконечной). Нетрудно убедиться, что, если емкость класса конечна, всегда имеет место равномерная сходимость частот к вероятностям. В самом деле, при этом и достаточное условие выполнено. Найдем функцию роста для класса линейных решающих функций. Для этого достаточно определить максимальное число точек в пространстве размерности , которые с помощью гиперплоскости можно разбить всеми возможными способами на два класса. Известно, что это число равно . Поэтому . Тот факт, что емкость класса линейных правил конечна (равна ), доказывает обобщенную теорему Гливенко. Отметим, что для гиперплоскостей, проходящих через начало координат, более точная оценка функции роста фактически была выведена в предыдущем параграфе.
|