§ 5. Оценка числа различных линейных разделений векторов

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

Рис. 11.

Заметим, что в соответствие каждому вектору  пространства  может быть поставлена гиперплоскость

,

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

.

Таким образом,  векторам  в пространстве  ставится в соответствие  гиперплоскостей (рис. 11). Наше утверждение состоит в том, что число различных разделений векторов равно числу компонент, на которые эти  гиперплоскостей разбивают -мерное пространство .

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

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

Очевидно, что в одномерном случае справедливо

.

Одна гиперплоскость делит пространство размерности  на две части, т. е. справедливо

.

Пусть известно, что  гиперплоскость  делит -мерное пространство не более чем на  компонент. Добавим новую гиперплоскость . Если эта гиперплоскость проходит через одну из «старых» компонент, то она дробит ее надвое. В противном случае старая компонента сохраняется. Таким образом, при проведении гиперплоскости , число компонент увеличится на столько, сколько компонент окажется разделено надвое. В свою очередь каждая такая компонента  оставляет на  след . Число таких следов в точности равно числу компонент, на которое гиперплоскости  дробят новую гиперплоскость . Поскольку размерность  равна , число следов не превосходит .

Таким образом, мы получим следующее рекуррентное уравнение:

,

,

.                (5.7)

Решением уравнения (5.7) является выражение

Нам, однако, удобнее будет пользоваться не этой формулой, а ее оценкой сверху (см. главу X)

,

или даже более грубой оценкой

.

Число различных бинарных векторов не превосходит  и, следовательно, справедлива еще более грубая оценка числа различных разделяющих гиперплоскостей:

.

Эта-то оценка используется для получения оценки длины обучающей последовательности.

Подставляя оценку  в (5.6), получаем

,

т. е. длина обучающей последовательности должна быть пропорциональна .

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