Файл: Вапник В.Н. Теория распознавания образов. Статистические проблемы обучения.pdf

либо соответствовать понятию р, либо не соответствовать ему. Рассмотрим оба этих случая.

С л у ч а й п е р в ы й . Вектор х соответствует по­ нятию р. Тогда правильной реакцией элемента R p на сиг­ нал X должно быть возбуждение, т. е. должно выполнять­ ся неравенство

т

2 М У > о.

1=1

Если веса элемента R p обеспечивают правильную реак­ цию на вектор х, то они не меняются. Если же веса не обес­ печивают правильной реакции элемента R p, т. е. они тако­ вы, что

m

2 м у < о,

і = 1

то веса элемента R p изменяются по правилу

Я? (новое) = Xf (старое) + у1 (і = 1, 2, ..., т).

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

т

2 М У С о.

І = 1

Если веса элемента R p обеспечивают правильную реак­ цию этого элемента на вектор х, то они не меняются. Если же веса элемента R p не обеспечивают правильной реак­ ции, т. е.

т

2 м у > о,

2=1

то веса Xf, ..., Я„ изменяются по правилу

Я? (новое) = Я? (старое) — у1 {і = 1, 2, .... т).

При обучении аналогично меняются веса всех элементов R персептрона.

§ 5. Обобщенная математическая модель

Ф. Розенблатт надеялся, что его персептрон моделиру­ ет существенные черты человеческого восприятия, в осо­ бенности восприятия зрительных образов. Он полагал, что персептрон легко можно будет обучить узнаванию одного и того же изображения независимо от масштаба изображе­ ния, существенных сдвигов его в рецепторном поле и дру­ гих преобразований, при которых человек относит изобра­ жение к одному и тому же понятию. Иными словами, пред­ полагалось, что персептрон будет узнавать предметы инвариантно по отношению к определенным группам пре­ образований.

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

Последовали всевозможные усложнения схемы пер­ септрона. Строились персептроны с большим числом ней­ ронных слоев, допускалась настройка коэффициентов уси­ ления не только на верхнем слое, но и на промежуточных уровнях, предлагалось вводить перекрестные и обратные связи.

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

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

Если предположить, что физиологическая модель чело­ веческого восприятия действительно аналогична персептрону, то следует допустить, что связи преобразующих А- элементов с рецепторами (а вероятнее, нескольких слоев таких элементов) отнюдь не случайны, а построены имен­ но так, чтобы обеспечить новое описание изображения,

которая делит пространство на два полупространства. Счи­ тается, что если вектор х находится по одну сторону от по­ верхности (это значит, что для него выполняется неравен­ ство (1.2)), то он соответст­ вует первому понятию, если же по другую от нее сторону, то второму. Та­ кие гиперповерхности на­ зываются разделяющими

(рис. 2).

Для образования ново­ го понятия надо построить соответствующую разделя­ ющую гиперповерхность. Каждой гиперповерхности

(1.3) пространства X в пространстве У с координатами у1 — (х), ..., ут= фт (X) соответствует гиперплоскость

Введение пространства У позволяет заменять рассмот­ рение разделяющих гиперповерхностей (1.3) разделяющи­ ми гиперплоскостями (1.4). Поэтому пространство векто­ ров Y получило название спрямляющего. В спрямляющем пространстве изучается следующая схема. Каждому объ­ екту ставится в соответствие вектор у = (у1,. .., ут). Этот вектор относится к первому классу, если он лежит по одну сторону от разделяющей гиперплоскости

ТП

2 № = о,

і=1

и ко второму, если по другую.

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

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

имеются в виду случаи, когда такая гиперплоскость в принципе существует.

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

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

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

т

(у, Л) = 2 У%-

і=1

Рассмотрим множество W, состоящее из всех векторов Уі, ..., і/„и — уъ ..., — уь. Тогда система неравенств (1.5) примет вид

(у, Л) >■ 0 для всех у е= W.

Величине р0 может быть дана следующая геометричес­ кая интерпретация. Пусть, как на рис. 3, множество векто­ ров {у} обозначено крестиками, а множество векторов {у} кружками. Утверждение о том, что два множества векто­ ров разделимы гиперплоскостью, проходящей через начало координат, эквивалентно тому, что выпуклая оболочка векторов уъ ..., у аі — Уі, ..., — уь

не содержит нуля или, что то же самое, расстояние от начала коор­ динат до выпуклой оболочки мно­ жества W отлично от нуля *). Ве­ личина ро как раз и равна рассто­ янию от выпуклой оболочки мно­ жества W до начала координат.

Особенность алгоритма персептрона, состоящая в том, что раз­ деляющая гиперплоскость прохо­ дит через начало координат, не является серьезным ограничением при построении произвольной раз­ деляющей гиперплоскости (в том

числе и не проходящей через начало координат). Если для разделения классов необходима гиперплоскость, не проходящая через начало координат, то достаточно рас­

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

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

более к = исправлений коэффициентов (символ [а]

означает целую часть числа а).

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