Лекция 9. Теорема Новикова

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

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

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

, .

(9.1)

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

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

.

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

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

Рис. 9.1.

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

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

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

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

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

для всех ,

для всех

и

,

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

.

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

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

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

,

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

.

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

,

(9.2)

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

.

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

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

.

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

.

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

,

(9.3)

поскольку .

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

.

Оценим величину (,). В начальный момент (,)=0. Если в момент времениi+1 происходит исправление, то

.

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

.

(9.4)

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

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

.

(9.5)

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

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