§ 7. Доказательство теоремы Новикова
Докажем теорему Новикова в
несколько более общей формулировке.
Теорема 1.1. Пусть дана произвольная
бесконечная ограниченная по модулю последовательность векторов 
, принадлежащих множествам 
и 
. Пусть существует
гиперплоскость, проходящая через начало координат и разделяющая множества и , m. е. существует единичный вектор 
такой, что
для всех 
,
для всех
и
.
Тогда при использовании
«персептронной» процедуры построения разделяющей гиперплоскости с начальными
весами 
-элемента,
равными нулю, число исправлений ошибок не превзойдет числа
.
Эта теорема утверждает, что если
существует гиперплоскость, разделяющая множества и , то персептрон после конечного числа
исправлений ошибок построит разделяющую гиперплоскость (которая безошибочно
будет делить весь бесконечный оставшийся хвост последовательности).
Доказательство. Рассмотрим новую
последовательность 
,
которая отличается от исходной только тем, что векторы 
принадлежащие , заменены на 
. Тогда работа
персептрона может быть описана так. Обозначим через 
вектор, координатами которого
являются веса -элемента
после просмотра 
членов
последовательности.
Если очередной вектор опознается
правильно, т. е.
,
то
изменения настройки не происходит, т. е.
.
Если
же произошла ошибка, т. е.
, (1.6)
производится
исправление:
.
Начальный
вектор 
.
Оценим модуль вектора , после 
исправлений. Если в
момент 
произошло
исправление, то
.
Учитывая
(1.6), а также то обстоятельство, что
,
имеем
.
Таким
образом, если к моменту 
произошло ровно исправлений, то
, (1.7)
поскольку
.
Далее, по условию теоремы
существует единичный вектор такой, что для всех
.
Оценим
величину 
. В
начальный момент 
.
Если в момент происходит
исправление, то
.
В
противном случае 
.
Таким образом, если к моменту произошло исправлений, то
. (1.8)
В
силу неравенства Коши
и,
следовательно, справедливо неравенство
. (1.9)
Сопоставляя
(1.7) и (1.9), убеждаемся, что эти неравенства могут одновременно выполняться только
при
.
Следовательно,
число исправлений не превосходит 
, после чего все остальные члены
последовательности будут опознаваться правильно. Теорема доказана.
Теорема Новикова была первой
теоремой в теории обучения распознаванию образов. В начале 60-х годов она
казалась чрезвычайно интересной и была предсказана многими авторами: ведь
согласно этой теореме алгоритм, подсмотренный у природы и вначале
сформулированный в традиционных для физиологов терминах поощрения и наказания,
получил простую геометрическую интерпретацию.
Интересной казалась и оценка,
полученная в этой теореме: если спрямляющее пространство персептрона бинарное,
то величина 
не
превосходит величины размерности пространства 
. В этом случае справедлива оценка
.
Интересно
в этой оценке то, что число коррекций растет с ростом размерности пространства
не быстрее чем линейно. Такой медленный рост числа коррекций позволял
надеяться, что удастся построить алгоритмы, эффективно решающие задачи
достаточно большой размерности.
