§ 6. Теорема Новикова

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

В 1960 году американский ученый А. Новиков показал, что если последовательность, составленную из всех элементов множеств  и , предъявить персептрону достаточное число раз, то он, в конце концов, разделит ее (конечно, если разделение с помощью гиперплоскости в принципе возможно). Это утверждение оказалось чрезвычайно важным для развития теории обучающихся программ. Использованные для его доказательства понятия оказались полезными и при установлении более тонких свойств алгоритмов обучения. Рассмотрим их подробнее.

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

, ,

, .     (1.5)

Здесь использовано обозначение

.

Рассмотрим множество , состоящее из всех векторов  и . Тогда система неравенств (1.5) примет вид

 для всех .

Если обозначить

,

а

,

то условие разделимости векторов  и  может быть формально выражено так: .

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

Рис. 3.

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

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

Тогда, как показал Новиков, после многократного предъявления обучающей последовательности, составленной из элементов множеств  и , будет проведено не более  исправлений коэффициентов (символ  означает целую часть числа ).