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