Двухслойный векторный персептрон

В. М. КРЫЖАНОВСКИЙ, И. С. ЖЕЛАВСКАЯ

Научно-исследовательский институт системных исследований РАН, Москва

Vladimir. *****@***com, *****@***ru

ДВУХСЛОЙНЫЙ ВЕКТОРНЫЙ ПЕРСЕПТРОН

Предложена новая модель – двухслойный векторный персептрон. По сравнению с однослойным персептроном незначительное (на 5%) увеличение вычислительной сложности и требований к оперативной памяти с лихвой компенсируются понижением вероятности ошибки (до 4 порядков и более).

Ключевые слова: векторные нейронные сети, модель Поттса

Введение

Первой и наиболее известной векторной нейронной сетью (НС) является модель Поттса [1-2]. Эта модель по-прежнему исследуется учеными из таких различных областей как физика, медицина, сегментация изображений и нейронные сети. Позже была предложена модель параметрической нейронной сети [3], всесторонне исследованная небольшим коллективом Института оптико-нейронных технологий РАН (ныне ЦОНТ НИИСИ РАН). Похожая модель (CMM) независимо разработана и продолжает исследоваться в Йоркском университете [4]. В кандидатской диссертации [5] представлена модель векторной нейронной сети с мерой близости между состояниями нейронов. Эта модель обобщила все перечисленные модели. Исследователями рассматривались как полносвязные, так и персептронные архитектуры. Были изучены различные правила обучения векторных сетей [6]. Полученные результаты говорят о высокой эффективности векторных сетей.

Для практических приложений, требующих реализации ассоциативной памяти, более всего подходят персептроны. (В нашем случае речь идет о векторных персептронах.) Однако они имеют следующий существенный недостаток – достаточно даже одному выходному нейрону переключиться в неправильное состояние, чтобы входной вектор был идентифицирован неверно. Чтобы с этим бороться, приходится повышать надежность каждого нейрона путем повышения избыточности НС, либо уменьшая загрузку сети. Иначе можно сказать, что векторный персептрон состоит из «надежных» нейронов, которым нельзя ошибаться, а это, в общем, противоречит всей идеологии нейронных сетей.

Альтернативный подход заключается в применении «слабых» нейронов (weak-neurons). При равных затратах к оперативной памяти совокупность «слабых» нейронов оказываются эффективнее небольшого числа «надежных» нейронов. Трюк заключается в том, чтобы оснастить векторный персептрон дополнительным слоем из одного нейрона, количество состояний которого равно количеству запомненных образов. Его задача заключается в накоплении информации от предыдущего слоя и непосредственной идентификации входного образа. К предложенной идее близка идея, изложенная в работах [7-8].

Статья, в целом, состоит из трех разделов: формального описания модели; качественного описания, в котором авторами была сделана попытка на простом примере показать суть предлагаемого нововведения; и раздела содержащего экспериментальные результаты. В силу ограниченного объема статьи авторами представлены только наиболее интересные экспериментальные результаты.

Постановка задачи

Рассмотрим некоторый q-нарный вектор X (компоненты могут принимать одно из q дискретных значений), который получен в результате искажения одного из эталонных векторов, q ≥ 2. Необходимо построить систему, позволяющую найти эталонный вектор Xm, имеющий минимальное расстояние по Хеммингу к входному вектору X. Для простоты изложения рассмотрим частный случай, при котором в качестве эталонных векторов выступают бинарные векторы (т. е. q = 2), а искажение выполняется простой инверсией компонент.

Формальное описание модели

Рис. 1. Схема двухслойного векторного персептрона в общем случае

Описание модели. Рассмотрим двухслойную архитектуру (рис. 1.). Входной слой состоит из N скалярных нейронов, каждый из которых может принимать два состояния, , . Первый (внутренний) слой состоит из n векторных нейронов, имеющих 2q фиктивных состояний каждый, описываемых орт-векторами q-мерного пространства:

,

где – единичный вектор, содержащий 1 на k-позиции. Фиктивность состояний заключается в том, что на этапе обучения нейроны второго слоя имеют 2q дискретных состояний, а в процессе работы нейроны рассматриваются как простые сумматоры. Это сделано с целью упрощения описания модели. Второй (выходной) слой состоит из одного векторного нейрона, который может принимать M состояний, описываемый орт-вектором M-мерного пространства .

Состояние персептрона можно описать тремя векторами:

1) входной слой описывается N-мерным бинарным вектором , где ;

2) первый (внутренний) слой n-мерным 2q-нарным вектором , где , – q-мерный единичный вектор, содержащий 1 на k-ой позиции;

3) второй (выходной) слой – M-нарным вектором , где – M-мерный единичный вектор, содержащий 1 на r-ой позиции.

Каждому эталонному образу Xm поставим в однозначное соответствие вектор Ym, в свою очередь каждому вектору Ym поставим в однозначное соответствие вектор om. Каждая компонента вектора Ym генерируется так, чтобы с одной стороны вектор Ym в целом был уникальным, а с другой стороны возможные состояния были распределены между эталонами строго поровну, т. е. . Если последнее требование не исполняется, то вероятность ошибки возрастает на несколько порядков. Таким образом, мы строим нейронную сеть, запоминающую ассоциацию:

(1)

Обучение. Синаптические связи векторного персептрона вычисляются по обобщенному правилу Хебба:

и (2)

где – q-мерный вектор, описывающий связь, идущую от i-ого нейрона входного слоя к j-ому нейрону второго слоя; – матрица размерности , описывающая связь, идущую от j-ого нейрона второго слоя к единственному выходному нейрону; , .

Идентификация. Пусть на вход сети поступил некоторый вектор . Вычислим отклик сети . Для этого сначала вычислим локальные поля на нейронах второго слоя:

(3)

Нейроны второго слоя на этапе распознавания выступают в роли простых сумматоров, поэтому далее сформированный сигнал без изменений распространяется к выходному нейрону. Поэтому локальное поле на выходном нейроне имеет вид:

(4)

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

Качественное описание модели

Общая идея. Каждому векторному нейрону соответствует свое уникальное разбиение всего множества эталонных образов на q подмножеств. Например, на рис. 2 представлены два разбиения всего множества эталонов на q = 4 частей, M = 12.

Рис. 2. Пример разбиения двумя различными способами множества объектов

Для каждого разбиения мы можем вычислить q «вероятностей» (компоненты вектора локальных полей ) того, что входной образ принадлежит каждому из этих q подмножеств. Каждый векторный нейрон – это своего рода решатель, выбирающий подмножество, имеющее максимальную «вероятность» (на рис. 3 это подмножества №1 в первом разбиении и №1 во втором). Пересечение подмножеств выбранных всеми решателями определяет выход однослойного персептрона. При оценке этих «вероятностей» могут совершаться ошибки, связанные со статистической природой проводимых вычислений. Следовательно, решение, основанное только на выборе подмножеств по максимальной вероятности, может быть ошибочным. Достаточно неправильно определить «подмножество-победитель» хотя бы в одном разбиении, чтобы конечное решение было ошибочным (рис. 3).

Рис. 3. Результатом пересечения подмножеств-победителей из первого

и второго разбиений является пустое подмножество

Базовой идеей предлагаемой модели является учет этого недостатка. Предлагается не принимать промежуточных решений, основываясь только на «вероятностях» отдельного разбиения (отсекая тем самым возможные решения), а выполнить накопление такой информации по всем разбиениям. Полученные «вероятности» для каждого подмножества из всех разбиений будем трактовать как статистические показатели того, что любой паттерн из некоторого подмножества данного разбиения тождественен входному образу . После оценки «вероятностей» для всех разбиений каждому паттерну можно поставить в соответствие набор этих статистических показателей – по одному из каждого разбиения:

(5)

(Стоит отметить еще раз, что под «вероятностью» здесь подразумевается некая статистическая величина, а именно компонента локального поля . Ее значение тем больше, чем вероятнее входной паттерн является одним из образов, принадлежащих подмножеству соответствующего этому локальному полю.)

Пример. Поясним основную идею на простом примере. На рис. 2 представлено разбиение множества из 12 объектов (паттернов), обозначенных латинскими буквами, на 4 подмножества двумя различными способами (n = 2). Пусть на вход был подан искаженный объект B. На рисунке рядом с каждым подмножеством указана вычисленная «вероятность» того, что входной паттерн является одним из паттернов данного подмножества.

При идентификации по схеме однослойного персептрона, в первом разбиении «подмножеством-победителем» является первое подмножество (табл. 1.), которое действительно содержит входной паттерн, а во втором – также подмножество №1, однако входного паттерна оно не содержит.

Таблица 1. Значения вероятностей принадлежности входного паттерна

к подмножеству для первого и второго разбиения

Разбиение № 1		Разбиение № 2
№ подмножества	Вероятность принадлежности входного паттерна к подмножеству		№ подмножества	Вероятность принадлежности входного паттерна к подмножеству
1	0.70		1	0.38
2	0.10		2	0.37
3	0.15		3	0.20
4	0.05		4	0.05

Результатом пересечения этих подмножеств будет пустое множество (см. рис. 3), т. е. сеть не может идентифицировать входной паттерн. Таким образом, ошибка на одном нейроне влечет ошибку всей системы. В то же время, видно, что во втором разбиении вероятность принадлежности входного паттерна к подмножеству №1 отличается от соответствующей вероятности для подмножества № 2 всего на 0%) (табл. 1). Т. е. почти с равной вероятностью входной паттерн может принадлежать как первому, так и второму подмножествам.

В предложенной модели этот факт учитывается, и решение принимается уже на основании значений вероятностей из обоих разбиений для каждого паттерна (табл. 2). В качестве ответа выбирается образ, которому соответствует максимальное суммарное значение «вероятности». В результате получаем, что сеть правильно идентифицировала и какой паттерн был подан на вход системы.

Таблица 2. Значения вероятностей того, что данный образ является входным

образом, полученные по обоим разбиениям и их суммарная вероятность

Объект / образ	Вероятность по разбиению № 1	Вероятность по разбиению № 2	Сумма
A	0.15	0.37	0.52
B	0.70	0.37	1.07
C	0.10	0.37	0.47
D	0.10	0.38	0.48
E	0.15	0.38	0.53
F	0.05	0.38	0.43

Характеристики алгоритма

	Однослойный	Двухслойный	2с/1с*
Вычислительная сложность идентификации, операций	2Nnq	2Nnq+(n+1)M	1,025
Требования к оперативной памяти, байт	4Nnq	4Nnq+4nM	1,033

*Отношение характеристик для параметров: M = 1000; N = 100; q = 300; n = 2.

Как видно из таблицы, предлагаемый алгоритм требует лишь на 4 % больше ресурсов (процессор, память) чем однослойный персептрон.

Экспериментальные результаты

Рассмотрим результаты компьютерного моделирования однослойного и двухслойного персептронов, а также проведем их сравнение. На представленных ниже рис. 4 и 5 по оси ординат отложена вероятность ошибки P - вероятность того, что искаженный эталонный вектор будет идентифицирован неверно. На всех рисунках данные соответствующие однослойному персептрону обозначены тонкой линией с ромбовидными маркерами (кривые, лежащие выше всех), остальные кривые соответствуют двухслойному персептрону для различных значений параметров n и q.

Если количество образов M, их размерность N и параметр шума a (вероятность того, что компонента входного бинарного вектора искажена) определяются решаемой задачей, то количество q-нарных нейронов и количество их состояний n внутреннего слоя могут варьироваться с тем, чтобы добиться удовлетворительной надежности.

Рис. 4а. Вероятности ошибки P от числа запомненных образов M, параметры: N = 100; a = 0; q = 100; n = 2	Рис. 4б. Вероятности ошибки P от размерности задачи N, параметры: M = 1000; a = 0; q = 50; n = 3

Сначала рассмотрим, как меняется ошибка при фиксированных параметрах n и q от M и N - рис. 4а и 4б. Как и ожидалось, увеличение размерности запомненных векторов N, либо понижение их количества M приводит к экспоненциальному понижению ошибки P. Так же видим, что введение дополнительного слоя позволяет понизить вероятность ошибки более чем на один порядок (до двух и более). Выигрыш тем существеннее, чем меньше ошибка на исходной однослойной сети.

Помехоустойчивость двухслойной сети также выше – кривая с маркерами, соответствующая однослойной сети, лежит существенно выше (рис. 5а, параметры: M = 1000; N = 100; n = 2 и q = 200).

Рис. 5а. Зависимость вероятности ошибки P от уровня шума a; параметры: M = 1000; N = 100	Рис. 5б. Зависимость вероятности ошибки P от параметра nq; параметры: M = 1000; N = 100; a = 0

Рис. 5а содержит несколько зависимостей ошибки двуслойной сети P от уровня шума a для различных комбинаций внутренних параметров n и q, при этом произведение nq = const. Верхняя пунктирная кривая соответствует n = 40 и q = 10, ниже идет кривая для n = 8 и q = 50, далее n = 4 и q = 100 и комбинация параметров n = 2 и q = 200 (жирная линия), показывающая наименьшую ошибку. Таким образом, получается, что с точки зрения надежности, во втором слое лучше использовать небольшое количество надежных (избыточных) нейронов. Однако такие сети не устойчивы к разрушениям самой нейросети.

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

Сеть с параметрами n = 40 и q = 10 отличается от сети с параметрами n = 2 и q = 200 принципами, обеспечивающими правильное распознавание. В первом случае ключевую роль играет второй слой, накапливающий информацию с большого количества ненадежных элементов. (Вероятность правильного распознавания однослойного персептрона с такими параметрами равна нулю.) Во втором случае второй слой лишь изредка (рис. 5а, тонкая кривая с маркерами) корректирует ошибки первого слоя.

Последний рис. 5б демонстрирует, как зависит ошибка P от внутренних параметров n и q. Жирная линия соответствует ошибке двухслойной сети с параметрами n = 2 и q = 200÷500, а треугольные маркеры – n = 2÷5 и q = 200, т. е. обе сети имеют одинаковую вычислительную сложность и требования к оперативной памяти.

Моделирование показывает, что:

1) увеличение обоих параметров ведет к экспоненциальному понижению ошибки;

2) обе сети имеют одинаковую ошибку в области nq ≤ 800 (достаточно неожиданный результат), что опять же говорит в пользу вывода, сделанного выше.

Предлагаемый алгоритм обладает еще одним преимуществом, которым не обладает однослойный персептрон. Если выстроить образы в порядке убывания соответствующих им компонент локального поля H (см. табл. 2, столбец «сумма»), то фактически выстроим паттерны в порядке их близости к входному вектору, где элемент на первом месте мы считаем ответом системы. Однако мы можем еще увеличить надежность системы, если вычислим скалярные произведения входного вектора с первыми K наиболее близкими паттернами и уже по максимуму величины скалярного произведения определить окончательный ответ системы. На рис. 5б пунктирной линии соответствуют результаты моделирования для K = 2. Видим, что этот трюк позволяет дополнительно уменьшить ошибку P еще на два порядка (см. nq = 800).

Заключение

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

Работа поддержана проектами ОНИТ РАН № 1.8 и № 2.1.

Список литературы

1.  Wu F. Y. The Potts model. //Review of Modern Physics, 19Р. 235-268.

2.  Kanter I. Potts-glass models of neural networks. //Physical Review A, 1988. v.37(7). Р. .

3.  Kryzhanovsky B., Mikaelyan A.//Doklady Mathematics, 2002. v.65. No.2. Р. 286-288. On the Recognition Ability of a Neural Network on Neurons with Parametric Transformation of Frequencies.

4.  Austin J., Turner A., Lees K. Chemical Structure Matching Using Correlation Matrix Memories.// International Conference on Artificial Neural Networks, Edinburgh, UK, September 7-10, 1999; IEE Conference Publication 470, published by IEE, London.

5.  Крыжановский диссертация «Исследование векторных нейронных сетей с бинаризованными синаптическими коэффициентами для задач обработки информации и принятия решения», НИИСИ РАН, 2010.

6.  Vladimir Kryzhanovsky, Irina Zhelavskaya and Anatoliy Fonarev. Vector Perceptron Learning Algorithm Using Linear Programming // A. E.P. Villa et al. (Eds.): ICANN, 2012. Part II. LNCS 7553. Р. 197-204, 2012. (Springer-Verlag Berlin Heidelberg 2012)

7.  Podolak I T, Biel S Hierarchical classi_er. // Wyrzykowski R (ed) Parallel Processing and Applied Mathematics, 2006. LNCS 3911. Р. 591-598.

8.  Podolak I. T. Hierarchical classifier with overlapping class groups. //Expert Systems with Applications, 20Р. 673–682.