Теоремы Розенблатта об элементарных перцептронах

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

Теорема 2.1. Пусть дано множество черно-белых изобра-жений на некоторой сетчатке , тогда для любой классификации C(W) множества W черно-белых изображений на два подмножества W¹, W² существует не пустой класс элементарных перцептронов с сетчаткой S, способных выполнить эту классификацию.

Доказательство. Для доказательства достаточно показать существование хотя бы одного элементарного перцептрона, способного выполнить произвольную классификацию C(W). Рассмотрим перцептрон, каждому изображению на сетчатке S которого соответствует один А-элемент – нейрон A_k, функционирование которого определяется выражением:

(2.24)

где – выходной сигнал нейрона А_k; – сигнал на входе нейрона А_k,

; (2.25)

- выходной сигнал j-го S-элемента,

(2.26)

w_jk – вес связи между j-м S-элементом и k-м А-нейроном; – порог срабаты-вания k-го А-элемента; .

Для каждого изображения W_k зададим веса w_j_k соотноше-нием:

(2.27)

При предъявлении любого изображения перцептрону, удов-летворяющему соотношениям (2.24) – (2.27), только на входе одного k-го А-ней-рона, будет сигнал, равный в соответствии с соотношением (2.25) числу m, и только на выходе этого нейрона в соответствии с выражением (2.24) будет единичный выходной сигнал. Теперь для правильного выполнения разделение исходного множества W на два подмножества W¹, W² с помощью элементарного перцептрона необходимо только всем весам связей между R- и A-нейронами, которые соответствуют A-элементам, возбуждаемым изображениями подмножества W¹, придать положительные значения, а всем весам связей А-ней-ронов, которые возбуждаются изображениями подмножества W², - отрицательные значения, а затем задать выходной сигнал R-нейрона выражением вида:

где – входной сигнал R-элемента.

В этом случае все изображения подмножества W¹ будут кодироваться положительным единичным выходным сигналом нейронной сети, а подмно-жества W² – отрицательным, т.е. будет правильно выполняться классификация C(W) исходного множества W изображений.

Хотя построенная таким образом нейронная сеть не имеет существенного практического значения, однако ее наличие показывает, что элементарный перцептрон является универсальным устройством классификации любого множества изображений на два класса. В том случае, когда число изображений множества W превышает число А-нейронов, элементарный перцептрон теряет свою универсальную способность классифицировать изображения.

Теорема 2.2. Если число n изображений в множестве W больше числа А-элементов элементарного перцептрона, то существует некоторая класси-фикация С(W) множества W черно-белых изображений на два подмножества W¹, W², которая не может быть выполнена перцептроном.

Теорема 2.3. Для любого элементарного перцептрона с конечным числом А-нейронов вероятность выполнения классификации С(W), которая выбирается из равномерного распределения по всем возможным классификациям множества изображений на два класса, стремится к нулю при n, стремящемся к бесконечности.

Теорема 2.1 доказывает существование элементарного перцептрона, способного выполнять любую заданную классификацию С(W) изображений некоторого множества W на два класса, однако она не указывает алгоритмов достижения этой способности в процессе обучения нейронной сети. Розенблаттом была доказана важная для теории элементарных перцептронов теорема о наличии таких алгоритмов для α-перцептронов.

Рассмотрим некоторую классификацию С(W) множества W изображений на два подмножества W¹, W², которая может осуществляться перцептроном с R-элементом, выходной сигнал которого удовлетворяет условиям:

(2.28)

Положим также, что:

(2.29)

Определение 2.9. Метод коррекции ошибок без квантования – этот метод системы подкрепления с коррекцией ошибок, когда при ошибочной реакции R-элемента с порогом q на некоторое изображение к весу каждой из связей, соединяющих активные А-нейроны с R-элементом, прибавляется величина , где коэффициент выбирается из условия, что после коррекции весов связей выполняется соотношение (2.28), т.е. перцептрон правильно классифицирует предъявленное изображение. В методе коррекции ошибок с квантованием применяется это же правило коррекции весов связей, но величина в общем случае гораздо меньше и правильный сигнал на выходе R-нейрона, как правило, достигается не за одну итерацию.

Теорема 2.4. Пусть дан элементарный α-перцептрон, множество черно-белых изображений , некоторая классификация С(W) этих изображений на два подмножества, которая может быть выполнена α-перцеп-троном. Изображения подаются на вход перцептрона в произвольной последовательности, в которой каждое из них появляется неоднократно, через конечное число предъявлений других изображений. Тогда процесс обучения перцептрона методом коррекции ошибок ( с квантованием или без квантования подкрепления) независимо от начальных значений весов связей между R- и А-элементами всегда приводит за конечное число итераций к множеству весов связей, с помощью которых α-перцептрон может выполнить заданную классификацию изображений.

Теорема 2.4 доказывает наличие сходящегося детерминированного метода обучения с коррекцией ошибок для элементарного перцептрона с квантованием или без квантования подкрепления. Следующая теорема доказывает, что обучение элементарного перцептрона может быть выполнено и при менее жестких требованиях к виду коррекции – методом коррекции ошибок со случайным законом подкрепления, когда при появлении ошибки сигнал подкрепления формируется как в α-системе, но знак подкрепления с вероятностью 0,5 может быть положительным или отрицательным.

Теорема 2.5. Пусть дан элементарный α-перцептрон с конечным числом значений весов связей между R- и А-нейронами, множество черно-белых изображений , некоторая классификация C(W) этих изображений на два подмножества, которая может быть выполнена α-перцептроном при некотором наборе весов связей между R- и А-нейронами, изображения подаются на вход перцептрона в произвольной последо-вательности, в которой каждое из них появляется неоднократно через конечное число предъявлений других изображений. Тогда процесс обучения перцептрона, величина сигналов подкрепления которого формируется как и в α-системе с квантованием подкрепления, а знак подкрепления выбирается с вероятностью 0,5 положительным или отрицательным, может быть выполнен за конечное время с вероятностью, равной единице, независимо от начальных значений весов связей между R‑ и А‑нейронами.

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

Менее универсальной системой подкрепления, чем α-система и системы со случайным формированием подкрепления, является γ-система. Это доказыва-ет следующая теорема Розенблатта.

Теорема 2.6. Пусть дан элементарный γ-перцептрон, подмножество черно-белых изображений и некоторая классификация C(W) этих изображений на два класса W¹, W². Тогда для выполнения классификации C(W) может существовать набор весов связей, недостижимый для γ-системы подкреплений.

Доказательство. Пусть функционирование А-нейронов определяется выражением:

где – соответственно выходной и входной сигналы k-го A-нейрона; – порог срабатывания А-нейронов.

Пусть также каждый А-нейрон возбуждается только одним изображением из множества W, а классификация C(W) осуществляется с помощью R-элемента, функционирование которого описывается соотношением:

где – соответственно выходной и входной сигналы R-нейрона. Выберем классификацию C(W), которая относит все изображения к классу или к классу . Очевидно, что в первом случае решение существует только тогда, когда веса всех связей между R- и А-элементами положительны (или отрицательны, если все изображения относятся к классу ). Если для первого случая начальные веса всех связей между R- и А-нейронами отрицательны, а для второго – положительны, то в силу свойства консервативности γ-системы подкрепления относительно суммы всех весов связей между R- и А-нейронами, она не сможет выполнить правильную настройку весов связей перцептрона для рассматриваемой классификации C(W).

ЗАДАЧА

Формировать два образа и выполнить обучение элементарного перцептрона с бинарными S- и A-нейронами и биполярным R-нейроном (рис. 2.3) их распознавание.

При этом потребуем, чтобы при предъявлении первого образа на выходе R-элемента был сигнал “–1”, при появлении второго – сигнал “+1”.

Задать в таблицах 2.1 и 2.2 веса связей ( ), ( ) соответственно между бинарными S- и A-нейронами и между A-нейронами и биполярным нейроном R с помощью генератора случайных чисел, генерирующего их из конечного множества {0,1; 0,2; …; 0,9}.

Таблица 2.1. Веса связей перцептрона между S- и A-элементами

	S₁	S₂	S₃	S₄	S₅	S₆	S₇	S₈	S₉
A₁
A₂
A₃
A₄
A₅
A₆

Таблица 2.2. Веса связей перцептрона между R- и A-элементами

	A₁	A₂	A₃	A₄	A₅	A₆
R

Подать на вход перцептрона 1 образ.. Единичные сигналы с выходов возбужденных бинарных S-нейронов через связи, весовые коэффициенты которых заданы табл. 2.1, поступают на входы А-нейронов. Суммарный входной сигнал на входе i-го А-элемента определяется соотно-шением:

, (2.8)

где – сигнал на входе i-го А-нейрона; – сигнал на выходе j-го S-ней-рона; w_ji – вес связи между j-м S-нейроном и i-м А-элементом.

Аналогично вычислить сигналы на входах остальных А-элементов. Результаты этих вычислений свести в табл. 2.3.

Таблица 2.3. Величины сигналов на входах A-элементов

Изображе-ние	Сигналы на входах A-элементов
U_вх._A₁	U_вх._A₂	U_вх._A₃	U_вх._A₄₁	U_вх._A₅	U_вх._A6
1 образ
2 образ

Для упрощения расчетов пороги всех А-нейронов принять одинаковыми

Для обеспечения работоспособности нейронной сети порог необходимо выбрать между min и max и таким образом, чтобы при предъявлении разных изображений возбуждались различные множества M₁, M₂ А-элементов, причем желательно, чтобы эти множества не пересекались, т.е.

. (2.9)

Выходной сигнал А-элементов рассчитать по соотношению

Использовать для настройки перцептрона α-систему подкрепления при величине сигнала подкрепления η равном 0,1 и при предъявлении последовательности образов в моменты времени t₁, t₂, t₃, … . Процесс адаптации весов связей между R- и A-нейронами занести в табл. 2.4.

Таблица 2.4. Адаптация весов связей перцептрона с помощью -системы