§ 7. Доказательство теоремы Новикова

Докажем теорему Новикова в несколько более общей формулировке.

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

 для всех ,

 для всех

и

.

Тогда при использовании «персептронной» процедуры построения разделяющей гиперплоскости с начальными весами -элемента, равными нулю, число исправлений ошибок не превзойдет числа

.

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

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

Если очередной вектор опознается правильно, т. е.

,

то изменения настройки не происходит, т. е.

.

Если же произошла ошибка, т. е.

,                       (1.6)

производится исправление:

.

Начальный вектор .

Оценим модуль вектора , после  исправлений. Если в момент  произошло исправление, то

.

Учитывая (1.6), а также то обстоятельство, что

,

имеем

.

Таким образом, если к моменту  произошло ровно  исправлений, то

,               (1.7)

поскольку .

Далее, по условию теоремы существует единичный вектор  такой, что для всех

.

Оценим величину . В начальный момент . Если в момент  происходит исправление, то

.

В противном случае . Таким образом, если к моменту  произошло  исправлений, то

.                     (1.8)

В силу неравенства Коши

и, следовательно, справедливо неравенство

.                 (1.9)

Сопоставляя (1.7) и (1.9), убеждаемся, что эти неравенства могут одновременно выполняться только при

.

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

Теорема Новикова была первой теоремой в теории обучения распознаванию образов. В начале 60-х годов она казалась чрезвычайно интересной и была предсказана многими авторами: ведь согласно этой теореме алгоритм, подсмотренный у природы и вначале сформулированный в традиционных для физиологов терминах поощрения и наказания, получил простую геометрическую интерпретацию.

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

.

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