автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Исследование векторных нейронных сетей с бинаризованными синаптическими коэффициентами для задач обработки информации и принятия решения

Учреждение Российской академии паук Научпо-псследовательский институт системных исследований РАН

На правах рукописи УДК 004.032.26

Крыжаиовскин Владимир Михайлович

ИССЛЕДОВАНИЕ ВЕКТОРНЫХ НЕЙРОННЫХ СЕТЕЙ С БИНАРИЗОВАННЫМИ СИНАПТИЧЕСКИМИ КОЭФФИЦИЕНТАМИ ДЛЯ ЗАДАЧ ОБРАБОТКИ ИНФОРМАЦИИ И ПРИНЯТИЯ РЕШЕНИЯ

05.13.01 - Системный анализ, управление и обработка информации (по математическим отраслям и информатике)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

^ ОДШ 2010

ч

Москва - 2010

004602400

Работа выполнена в Учреждении Российской академии наук Научно-исследовательском институте системных исследований РАН.

Научный руководитель: академик РАН, доктор технических наук, профессор

Микаэлян Андрей Леонович

Официальные оппоненты: доктор физико-математических наук, профессор

Ососков Геннадий Алексеевич

кандидат физико-математических наук Казапович Яков Борисович

Ведущая организация: Учреждение Российской академии наук

Вычислительный центр имени А.А.Дородницына РАН

Защита диссертации состоится «26» мая 2010 года в 16 часов на заседании диссертационного совета Д 002.265.01 при НИИСИ РАН по адресу: 117218, Москва, Нахимовский прт., д. 36, корп. 1, конференц-зал.

С диссертацией можно ознакомиться в библиотеке НИИСИ РАН (комн.13-21А)

Автореферат разослан «23» апреля 2010 г.

л

/Г

Ученый секретарь „ ]

диссертационного совета

кандидат физико-математических наук, /Я, у'

доцент V-'' В.Б. Демидович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Нейросетевой подход к обработке информации в последние полстолетия бурно развивается. На базе нейронных сетей возможно построение ассоциативной памяти, находящей свое применение в задачах принятия решений на основе прецедентов. Одной из наиболее известных и хорошо изученных скалярных нейронных сетей (НС), реализующих ассоциативную память, является модель Хопфилда. Интерес к ней обусловлен тем, что впервые было введено понятие энергии, позволяющее описать работу НС (восстановление эталона по его искаженному варианту), как спуск по энергетической поверхности к ближайшему локальному минимуму. Однако, емкость памяти такой модели мала и она мало пригодна для практических целей: число М эталонных образов, восстанавливаемых этой сетью, не превышает 15% от количества нейронов N (М » N !2lnN).

В 1988 году И. Кантер предложил так называемую «Потгс-стехольную модель» нейронной сети, нейроны которой, по аналогии с физической моделью спинового магнетика Поггса, могут иметь более двух различных состояний. Каждое состояние нейрона описывается вектором Q -мерного пространства, принадлежащему набору из Q специальных (поттсовских) векторов, где Q>2 - число различных состояний нейрона. Емкость ее памяти, описываемая выражением М =NQ(Q-l)/4ln(NQ), в Q(Q-V)/2 раз больше, чем у модели Хопфилда.

Позднее под руководством академика АЛ. Микаэляна разрабатывается модель векторной ассоциативной памяти, ориентированная на реализацию в виде оптоэлектронного устройства. Емкость памяти этой модели, описываемая выражением М = NQ(Q -1) / 2 In(NQ), того же порядка, что и в модели Поттса.

Обе эти векторные модели вполне пригодны для практического использования, поскольку по емкости ассоциативной памяти значительно превосходят скалярные модели нейронных сетей. Однако их моделирование сопряжено со значительными затратами оперативной памяти компьютера (RAM ~ 4N2Q2 байт). При этом нужно учитывать, что в естественных биологических нейронных сетях градация величин синаптических связей не столь велика, как в традиционных матрицах связей искусственных нейросетей. В связи с этим большой интерес проявляется к исследованиям свойств нейросетей с бинарными матрицами синаптических коэффициентов.

Бинаризация синаптических коэффициентов - это замена положительных и отрицательных элементов матрицы синаптических коэффициентов на +1 и -1 соответственно, при этом нулевые элементы сохраняются неизменными. Бинаризация позволяет выделить под хранение элемента синаптической связи всего 2 бита оперативной памяти, что в 16 раза меньше объема требуемого под небинаризованный элемент. Учет бинарности элементов при реализации модели позволяет ускорить алгоритм более чем в 16 раз. Кроме того, в некоторых случаях процесс бинаризации увеличивает емкость ассоциативной памяти и устраняет негативные эффекты коррелированности эталонных векторов.

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

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

В рамках диссертационной работы были решены следующие задачи:

1. Разработан метод оптимальной бинаризации квадратичного функционала, к минимизации которого формально сводится работа систем ассоциативной памяти.

2. Исследовано влияние бинаризации синаптических коэффициентов на распознающие характеристики следующих моделей векторных нейронных сетей: полносвязной фазовой ВНС; полносвязной бесфазовой ВНС; фазового векторного перцептрона; бесфазового векторного перцептрона.

3. Предложен метод отображения бинарных векторов в 2-нарные, позволяющий применять ВНС для распознавания бинарных векторов, значительно расширяя область применения векторных моделей.

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

Методы исследований. При решении поставленных задач в данной работе были использованы методы системного анализа, вычислительной математики, комбинаторики, математической статистики и теории вероятностей.

Научная новизна. Основные результаты работы являются новыми и заключаются в следующем:

1. Впервые разработана оптимальная процедура бинаризации квадратичного функционала, при которой направления градиентов исходного и бинаризованного функционалов совпадают с большой вероятностью (более 83%) в любой точке конфигурационного пространства.

1. Исследованы свойства ВНС с бинарными элементами матрицы синаптических связей. Впервые показано, что емкость памяти и помехоустойчивость бинаризованной сети не уступают, а в ряде случаев превосходят аналогичные характеристики исходных (небинаризованных) моделей. При этом требования к объему оперативной памяти снижаются в 16 раз и более чем в 16 раз возможно ускорение алгоритма.

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

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

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

6. Показано, что бинаризация значительно снижает негативное влияние коррелированности эталонных образов на емкость памяти ВНС.

Практическая ценность. Разработанные алгоритмы и методы бинаризации

найдут свое применение в прикладных системах обработки информации и

принятия решений на основе векторных нейронных сетей.

Положения, выносимые на защиту:

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

2. Фазовая и бесфазовая модели векторных нейронных сетей с бинаризованными синаптическими коэффициентами и результаты исследований свойств этих моделей для различных архитектур: полносвязные сети, векторные перцептроны, комитеты векторных перцептронов.

3. Метод отображения бинарных векторов в ß-нарные с введением меры близости между состояниями нейрона, позволяющий обрабатывать большие массивы бинарных векторов методами ВНС.

Апробация. Основные положения работы докладывались на следующих

конференциях [10-18]:

1. II Всероссийская научная конференция «Методы и средства обработки информации» МСО-2005, Москва, 2005 г.

2. VIII Всероссийская научно-техническая конференция «Нейроинформатика-2006», Москва, 2006 г.

3. International Joint Conference on Neural Networks (IJCNN), Montreal, 2005 r.

4. Международная научно-техническая конференция «Многопроцессорные вычислительные и управляющие системы», Таганрог, 2007 г.

5

5. 18th International Conference on Artificial Neural Networks ICANN'08, Прага, 2008 г. (2 доклада).

6. XI Всероссийская научно-техническая конференция «Нейроинформатика-2009», Москва, 2009 г.

7. 19th International Conference on Artificial Neural Networks ICANN'09, Кипр, Греция, 2009 г.

8. XII Всероссийская научно-техническая конференция «Нейроинформатика-2010», Москва, 2010 г.

Публикации. По теме диссертации опубликовано 18 печатных работ, из них 13 в соавторстве, 5 в изданиях из перечня ВАК [1-3, 6-7].

Структура и объем диссертации. Работа состоит из введения, семи глав, заключения, списка литературы и трех приложений. Общий объем диссертации составляет 168 страниц. Список литературы содержит 106 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Задачи бинарной оптимизации - это класс задач, решение которых сводится к минимизации квадратичного функционала

N N N

,=i j=1 ы

построенного на заданной Л^хЛ^-матрице Ту в N-мерном конфигурациошгом

пространстве состояний с бинарными переменными st = ±1, i = \,N.

В диссертации рассмотрено два варианта бинаризации: прямой и центрированный. Здесь мы рассмотрим лишь вариант центрированной бинаризации, как наиболее эффективной. Суть предлагаемой процедуры заключается в том, что процесс минимизации функционала Е подменяется минимизацией бинаризованного функционала

N N N

i=l j*i i=\

где

г,у=/0+55п [Тц~Т0) (3)

Здесь Г0 - среднее значение элементов матрицы Ту, а величины /"0 и 6, -

свободные параметры задачи, оптимальный вид которых предстоит определить.

Задача сводится к оптимизации процедуры бинаризации, т.е. к поиску параметров /0 и 6, (г = при которых будет максимальной вероятность

Р = Рг[#Д > 0] (4)

совпадения направлений локальных полей Н1 = -8Е / и А,- = -де / 65,-.

Выражение для вероятности (4) приведено в диссертационной работе, где при вычислении величины Р матричные элементы Ту рассматривались как независимые случайные величины, подчиняющиеся некоторому распределению (например, нормальному или равномерному) с средним Т0 и стандартным уклонением ат. Показано, что правильный выбор величин /0 и 6,- позволяет увеличить корреляцию локальных полей и, следовательно, величину вероятности Р . Из условий дР / 36, = 0 и дР / 3/0 = 0 найдены оптимальные значения этих параметров:

В,

Л>=-

(7)

где -Г0|) - среднее модуля ¡Гу-Т0|по 1-й строке. В этом случае

выражение для коэффициента корреляции величин Я, и ^ примет вид:

(В)

Как видим, с ростом величины ¡Г0| корреляция локальных полей в целом возрастает. Одновременно растет и величина вероятности Р (рис. 1). В работе показано, что минимальное значение вероятности Р и 0.83 достигается при Г0 = 0 и В( = 0 (при прямой бинаризации минимальное значение вероятности Р »0.8). С ростом параметров |Г0| и |5,.| минимально

возможное значение величины Р монотонно возрастает. В этом главное отличие процедур «прямой» и «центрированной» бинаризации: при равных условиях вероятность Р выше в

Рис. 1 Центрированная бинаризация. Зависимость вероятности Р от величины Го: сплошные кривые - теория; маркер -экспериментальные точки. Кривые построены для значении В, = ± к-Шат, где к = 0,1,2,6. Пунктир - кривая для случая В, =0 при прямой бинаризации.

случае применения процедуры «оптимальной» бинаризации.

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

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

Положительная сторона бинаризации в том, что она позволяет снизить требования к оперативной памяти в 16 раз и более чем в 16 раз увеличить быстродействие алгоритма. Более того, при надлежащем учете бинарности элементов матрицы г,у можно заменить операции умножения операциями логического умножения и еще на два порядка ускорить работу оптимизационного алгоритма. Отрицательная сторона в том, что применение процедуры бинаризации снижает эффективность минимизации (относительное изменение величины Е) по сравнению с эффективностью, достигаемой при минимизации функционала Е. Снижение эффективности минимизации (не более чем на 20%) имеет место только при нулевом пороге. В случае |5/(>о-н, когда компоненты порогового вектора сравнимы или больше величины флуктуации локального поля Н1, снижение эффективности практически незаметно.

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

случайные матрицы с гауссовским или равномерным распределением матричных элементов, матрицы 20-модели Изинга. Размерность задачи варьировалась в пределах от N = 64 до N = 1024. Установлено, что применение бинаризованного функционала е однозначно приводит к минимизации функционала Е. Ее эффективность выше 80% и не изменялась с ростом размерности задачи.

Третья глава посвящена исследованию влияния процесса бинаризации синаптических коэффициентов на распознающие характеристики фазовой полносвязной ВНС.

Фазовая ВНС - полносвязная нейронная сеть, состоящая из N связанных друг с другом фазовых векторных нейронов. Фазовый векторный нейрон -объект, принимающий 2(2 различных дискретных состояний (£Э>1). Состояние

/-го нейрона описывается вектором х,- = хрк, ¿ = 1,2, где ек - один из ортов 0~ мерного пространства, а амплитуда может принимать два значения х, =±1. Состояние сети как целого задается ЛГ-мерным 2-нарным вектором X = (х1,х2,-..,ху), в котором 1-й компоненте х1 соответствует состояние /-го нейрона в образе. Энергия такой сети задается в следующем виде:

о)

Ы >1

где Т^- - величина связи между г'-м и у'-м нейронами, определяемая 6 х 2 -матрицей

и

(10)

построенной по аналогии с обучающим правилом Хэбба на М эталонных образах ХИ = (х^.х^.-.х^).

Алгоритм работы сети заключается в следующем: в каждый момент времени / вычисляются проекции вектора локального поля

Н,(0=1Т?Х; (11)

М

на все орты 2-мерного пространства и находится максимальная по модулю проекция (пусть, например, это будет проекция на некий орт ег). Тогда под воздействием локального поля /-й нейрон в момент времени /+1 ориентируется вдоль орта ег, если егЬДг) > 0, или в противоположном ег направлении, если ■ егЬ/0)<0, то есть состояние /-го спина-нейрона в последующий момент времени задается решающим правилом:

хД/ + 1) = е,в8п(егН((0)- (12)

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

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

и >1

где матрица Ту получена бинаризацией исходной матрицы Т^ :

м ___

т$>-.впГ^-.р.Е*^, а,0 = 1,а, и = (14)

Пусть на вход сети подан образ X, соответствующий искаженному эталону образу Хт, Ма компонент которого имеют искажения по знаку (х^^ =-1), а

М» компонент имеют искажения по направлению =0). Сеть правильно

восстановит образ Х„, если в процессе итераций каждый _/-й спин сориентируется вдоль у'-го спина эталонного образа, так что в результате итераций мы перейдем в стабильное состояние, в котором ху = хту

9

(У = 1,2,...,//). Условие правильной ориентации /-го спина заключается в одновременном выполнении Q неравенств:

хт^г>0, >|ецЬг| пpиVei*xmj, (15)

где

= (16) >1

В диссертации показано, что вероятность ошибочного восстановления эталона можно описать оценочным выражением:

где

у42ж

N(1 - ¿)2 (1 - 2а)2 (w0 + W) )2 (l-6)[l-w,-(w0+wi)2] + fc(l-w0)'

(17)

(18)

Q2-1 Q2

^u-fiu-l-k

1

-1).

у г* Г**1

1

2(2г-1).

В таблице 1 приведены выражения для емкости памяти А/тах бинаризованной фазовой ВНС в двух предельных случаях, выраженные через параметры у0 и Ма, соответствующие небинаризованной фазовой ВНС:

и М0=-^-(1-2а)2(1-6)2. (19) М 21п(АГ2)

Как видим, в одной области параметров бинаризация приводит к двукратному увеличению емкости памяти, в другой - к уменьшению в яг/2 раз.

__Таблица 1.

В области параметров, где Л/0 < Q2 В области параметров, где Мй > Q2

У1 - ¿То Г2=М К

Мтах = 2М0 и 2М° Мтах = Ж

Качество работы нейросети практически полностью определяется одним параметром - соотношением «сигнал/шум» (величиной у У бинаризованной сети и величиной у0 у стандартной небинаризованной модели). Чем больше этот параметр, тем больше емкость памяти и надежнее производится распознавание образов. Соответственно, лучше работает та сеть, у которой этот параметр больше. На рис. 2 представлена зависимость отношения у1уц от

параметра M/Q2. Вид представленной на рис. 2 кривой практически не зависит от значения величины Q (графики для разных значений Q сливаются в единую кривую). Хорошо видно, что в точке MIQ2 — 2.45 имеет место

соотношение у = у0, то есть эту точку можно считать критической. При значениях параметра MIQ2<2A5 бинаризованная сеть работает лучше небинаризованной и, наоборот, при значениях M/Q2 > 2.45 бинаризованная сеть работает немного хуже.

Эти выводы хорошо согласуются с результатами численных экспериментов. На рис. 3 представлены результаты одного из таких экспериментов, позволяющего сравнить два типа сетей - сеть с бинаризованной матрицей (14) и стандартную сеть с хеббовской матрицей (10). В ходе эксперимента измерялась зависимость ошибки восстановления Р от величины загрузки (M/N). Хорошо видно, что в левой части графика, где выполняется соотношение М0 <2.5Q2, ошибка сети с бинаризованной матрицей меньше, чем у стандартной сети. И, наоборот, в области значений М0 > 2.5Q1 бинаризованная сеть восстанавливает образы с большей ошибкой. г,

Рис. 2. Зависимость отношения у/у0от параметра М02 . Здесь у и -величины «сигнал/шум» для бинаризованной и небинаризованной моделей фазовой ВНС.

25 И/У

Рис. 3 Зависимость вероятности ошибки распознавания Р от загрузки MIN. Сплошные линии — небинаризованная матрица, маркер - бинаризованная матрица. Параметры эксперимента; ЛГ=20, 2=16, а=0,0.2,0.3.

Связав оценочное выражение для емкости памяти одним из неравенств М > 2.522 или М < 2.5(?2, получим критический размер сети, задаваемый выражением

Яс=51п (ад. (20)

При малом числе нейронов N < Л'с (когда А/>2.52*) бинаризация приводит к увеличению параметра «сигнал/шум», т.е. к увеличению емкости памяти и к способности восстанавливать более сильно искаженные образы. И наоборот, бинаризация сети большого размера (/V > Л^) приводит к уменьшению отношения «сигнал/шум», т.е. к уменьшению емкости памяти и восстанавливающей способности сети. При изменении 2 в разумных пределах (15 2-400) величина Ыс изменяется в весьма небольшом диапазоне 10 < Л^ < 50. Это означает, что критический размер сети, как правило, мал.

11

Четвертая глава посвящена исследованию влияния процесса бинаризации синаптических коэффициентов на распознающие характеристики бесфазовой полносвязной ВНС.

Бесфазовая векторная нейронная сеть - полносвязная НС, состоящая из N связанных друг с другом бесфазовых векторных нейронов. Бесфазовый векторный нейрон - объект, принимающий Q различных дискретных состояний (0>2). Состояние г-го нейрона описывается вектором д:, =ек, к = 1,2, где ек - один из ортов £)-мерного пространства. Состояние сети как целого задается Л'-мерным 2-нарным вектором X = (х(,х2,...,хдг), в котором г'-й компоненте х, соответствует состояние г'-го нейрона в образе. Величина связи между ¡-м и_/-м нейронами задается ¡2x2 -матрицей

м

Л=1

построенной по аналогии с обучающим правилом Хэбба на М эталонных

образах Х^, = (хя1,х^2,...,хр№), х^ € {е*}®, где показатель Q означает

количество элементов в множестве.

Алгоритм работы сети заключается в следующем: в каждый момент времени / вычисляются проекции вектора локального поля

МО-IV; (22)

м

на все орты 2-мерного пространства и находится максимальная из проекций. Пусть, например, это будет проекция на некий орт ег. Тогда под воздействием локального поля 1-й нейрон в момент времени (+1 ориентируется вдоль орта ег:

*,е+1)=с„. (23)

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

Посмотрим, какими свойствами будет обладать описанная выше модель, если бинаризовать ее синаптические связи:

м _ _

=5В17^=8еп2»£у, сд? = 1,е, и = (24)

/1=1

В диссертации показано, что вероятность ошибки восстановления описывается выражением:

Р„=1-(1-Р,Ув~т, (25)

где

А/-1 ргрг . ■ .д.

= • ^0=1-1/6- (26) г=0 у

Хорошее согласие оценки (23) с экспериментом можем видеть на рис. 4, где представлены зависимости ошибки восстановления Ри от загрузки нейронной

сети М/ИОг для двух значений параметра Q = S^, 16. Пунктирные линии с маркерами соответствуют экспериментальным данным, а сплошные кривые построены с использованием выражения (23).

ЩИ)'

(1.19 0.1»

Ц13 0,1» 0,К!

м%

о.ог ш

/

/

..........

ЙЕ5

/ ,■*

Рис. 4. Зависимость вероятности ошибки Рц от загрузки нейронной сети \ilNQг: сплошная линия - оценка (25), маркированная пунктирная линия -эксперимент. Параметры эксперимента'. ЛИ00;£>=8, 16.

Емкость памяти рассматриваемой модели описывается оценочным выражением

г

Рис. 5. Зависимости емкости памяти М от размера нейросети N при 0=16: маркеры - эксперимент, тонкая линия - численное решение уравнения Ри=1/М\ жирная линия - оценка (27).

1 + -

N

2 ЫЩ/Рт)

(27)

где Ршах - задаваемая пользователем верхняя граница ошибки идентификации, т.е. при Л/ < Л/тах вероятность ошибочного восстановления Р < Рт2Х . Выражение (27) хорошо описывает результаты эксперимента. На рис. 5. представлена зависимость величины М от размера нейронной сети N. Можем видеть, что численное решение уравнения РЫ=ММ в пределах погрешности совпадает с экспериментом, а оценка (22) описывает эксперимент с небольшой ошибкой в 15-20%.

Для сравнения приведем выражение для емкости памяти исходной (небинаризированной) бесфазовой модели:

Л/0 =

4(1 + ВД1п №1Ртм)

(28)

Сравнивая (28) и (27), видим (см. рис. 6), что бинаризация приводит к увеличению объема нейросетевой памяти от 2 до 30 раз.

На рис. 7 представлено сравнение емкости памяти М бинаризованной модели с емкостью памяти Мр модели Поггса. Как видим, существует большая область значений параметров N и (), в которой М > Мр. Более того, при

высоких значениях параметров N и б (область выше кривой 1) моделирование сети Поттса невозможно из-за естественных ограничений на объем оперативной памяти, в то время как моделирование бинаризованной сети все еще остается возможным.

КО 1ЯО UDO 3 000 2S00 N

Рис. 6. Соотношение М/Мо при различных значениях параметра Q, где M и Ma - емкость памяти бинаризованной и небинаризованной бесфазовой ВНС соответственно.

Рис. 7. Соотношение М/Мр при различных значениях параметра (); М и Мр - емкость памяти бинаризованной бесфазовой ВНС и модели Поттса соответственно.

Бинаризация бесфазовой ВНС позволяет в 32 раза снизить размер требуемой оперативной памяти, а учет бинарности элементов позволяет более чем в 16 раз ускорить алгоритм. При этом емкость ассоциативной памяти только возрастает.

Пятая глава посвящена исследованию распознающих характеристик векторного перцептрона (ВП) с бинаризованными синаптическими коэффициентами. Структура ВП представлена на рис. 8. Он состоит из двух слоев векторных нейронов, где каждый нейрон входного слоя связан со всеми нейронами выходного слоя. Первый слой состоит из N С?-нарных векторных нейронов. Второй слой состоит из л д-нарных векторных нейронов (2 ^ д). Векторный перцептрон может быть построен на фазовых, бесфазовых и поттсовских нейронах.

Каждому образу X,, из множества эталонных векторов {Хи}м однозначным образом поставлен в соответствие вектор-ключ При предъявлении некоторого входного вектора X ВП формирует на выходе ключ У

Х1-

%2-

принадлежащий

Хм-

эталонному вектору Хи, имеющему

минимальное (среди эталонных векторов Рис. 8. Схема векторного перцептрона. множества {Хя}м) Хеммингово расстояние с входным вектором X.

Синаптические связи между у'-м входным и ¿-выходным нейронами определяется выражением

м

ТНЕУ,^- (29)

Алгоритм определения состояний выходных нейронов для фазового и бесфазового ВП описан в главах III и IV соответственно. Основные выражения, на основе которых оценивается емкость памяти и вероятность ошибочной идентификации фазового и бесфазового ВП, выводятся аналогично тому, как это было сделано для полносвязных векторных нейросетей в главах III и IV. Поэтому здесь мы представим только конечные формулы, описывающие следующие характеристики: емкость памяти М, необходимый для моделирования НС объем оперативной памяти RAM и вычислительная сложность алгоритма идентификации ОР. Результаты для различных моделей ВП сведены в Таблице 2, в которой введены следующие обозначения:

NQq(\-bf

R = AnNQq

М° 41п (яд/О

где Рт

(30)

Of=nqN , Nc =10(1 -в b)'1 In(«g/2Pmu) - задаваемая пользователем верхняя граница ошибки идентификации.

Название модели Емкость памяти М RAM, байт Вычислительная сложность ОР

ВП с небинаризованными синаптическими коэффициентами

Фазовый ВП 2 1д 4 >

Бесфазовый ВП М0 1 + NIQ R Ор

Бесфазовый ВП с линейным членом м0 R О,

Перцептрон Поггса М0 R 2Q-Op

ВП с бинаризованными синаптическими коэффициентами

Фазовый ВП N <NC М,, и. 64

N>NC Мо к

Бесфазовый ВП N<±NC 2 М0 32 °Р

N>±Nc

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

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

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

Пусть комитет образуют К перцептронов (рис. 9). Тогда каждый перцептрон обучается на т=М/К эталонах, где М- обшее количество эталонов. Снижение нагрузки на каждый перцептрон экспоненциально есК, где с »1) понижает вероятность ошибочной идентификации. Таким образом, варьируя количество перцептронов, образующих комитет, можно добиться требуемой надежности идентификации.

Рис. 9. Схема комитета векторных перцептронов.

Обучение комитета векторных перцептронов выполняется следующим образом:

1) множество эталонов {хм \М разбивается случайным образом на К частей;

2) создается К перцептронов, обученных на собственных непересекающихся выборках эталонов мощностью т=М!К, где М- это общее число эталонов.

Идентификация входного вектора X выполняется последовательно:

1) все перцептроны инициализируются входным вектором X;

2) вычисляются состояния выходных нейронов \к всех перцептронов, к = \,К\

3) для каждого перцептрона оценивается достоверность идентификации

** =4(31)

пИ м

где Л!"4*- это максимальная из проекций локального поля /'-ого выходного нейрона ¿-ого перцептрона;

4) определяется номер перцептрона с максимальной достоверностью идентификации (стратегия «победитель получает все»);

5) номер перцептрона победителя и значения его выходных нейронов У однозначно определяют эталон, искажением которого является входной вектор.

Рис. 10. Зависимость емкости памяти комитета М от числа перцептронов К. Маркеры -эксперимент; тонкая сплошная линия - теория (31). Комитет формируют перцептроны с параметрами: ЛИ00; 0=д=&, 16,32; л=2. Уровень искажений 6=60%.

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

Вероятность ошибочной идентификации оценивается выражением вида:

Р = (32)

XV 2л

где п — число выходных векторных нейронов перцептрона; д - число состояний выходных векторных нейронов; у - отношение «сигнал/шум»:

(33)

2 М

Здесь Ъ - уровень искажений, @ ~ количество состояний входных нейронов.

Максимальное число эталонов Мт № которое может надежно идентифицировать комитет перцептронов с ошибкой, меньшей заданного значения Ртах, определяется выражением, полученным из трансцендентного уравнения Р = Р^:

-ь)2

(34)

4 ЩКщ!Ртт)

Число идентифицируемых образов М растет линейно от количества перцептронов в комитете. Число арифметических операций алгоритма оценивается выражением:

ОР = КпЩ. (35)

Объем оперативной памяти, необходимой для хранения матриц синаптических коэффициентов, определяется выражением:

ЯАМ = 4Шп£>д байт. (36)

В заключение отметим хорошее согласие полученной оценки (34) с экспериментальными данными (рис. 10).

Седьмая глава посвящена разработке и исследованию алгоритма отображения бинарных векторов в 2-нарные векторы, позволяющего использовать высокие распознающие характеристики ВНС для идентификации бинарных образов.

г отображение X векторный К

бинарный Я" -» Я" д-аркый перцептрон 4-аркый

I______________________________.1 I______________________________I

предобработка идентификация

Рис. 11. Двухэтапная схема идентификации бинарных паттернов.

Идентификация образов проводится в два этапа по представленной на рис.11 схеме. На первом этапе производится предварительная обработка входного бинарного сигнала: бинарный ¿-мерный вектор Z отображается в нарный //-мерный вектор X. На втором этапе £?-нарный образ X идентифицируется векторным перцептроном (см. главу V): выходной образ У несет всю необходимую информацию о входном бинарном векторе Ъ.

Под отображением г-> X понимается построение 2-нарного образа X, взаимнооднозначно связанного с входным вектором 2. Алгоритм отображения состоит в следующем. Пусть у нас имеется некий ¿-мерный бинарный вектор Х = (г1,г2,—,2Д), 2, = {0,1}. Мысленно разделим его на N фрагментов, содержащих по г элементов каждый (М = Ь/г); число г > 1 называем параметром отображения. Каждый /-й фрагмент этого вектора можно рассматривать как некое записанное в двоичном коде целое число к1 (¿ = 1,лг),

(0<Лг, <9 — 1, д = 2г). Этому фрагменту поставим в соответствие вектор

x¡=ek¡, где ek e{e,}' - это k-ü орт ^-мерного пространства Rq. Тем самым,

всему образу X в целом ставится в однозначное соответствие набор д-мерных векторов, т.е. образ Х = (x¡, х2,..., xN).

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

Эффективность работы перцептрона описывается выражениями, представленными в таблице 2 и формулами (27), в которых следует сделать соответствующие подстановки:

N = L/r, q = Q = 2r, l-b = (\-Py, n = r~l\og2M-, (37)

где р - вероятность искажения одного бита. Проделав соответствующие подстановки, получим выражения для емкости памяти М, вычислительной сложности ОР и объема оперативной памяти RAM, необходимого для моделирования:

45(s + ímax)log^I г1

22(г+1)

RAM = —— IIog2M байт, (38)

г

где s = r/log2 L, sn„ = [InPm„|/lnL.

Как видим из выражений (35), емкость памяти описываемой системы растет экспоненциально с ростом параметра s. Однако величина s не может возрастать неограниченно. В диссертации показано, что величина s ограничена соотношениями:

5<|1п(1-р)Г' и (39)

log2 L

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

Ту = МгТ(уМ, (40)

где Т,у - описанная в предыдущих главах матрица межсвязей ВНС, a M -матрица мер близости: Ми - мера близости между к-м и 1-й состояниями нейрона. Мера близости в общем случае задается в зависимости от условий

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

М--

[(1-р)2+р2]".

(41)

Как видим, введение меры близости существенно увеличивает область притяжения. На рис. 12 представлены результаты

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

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

1о

!2348в789Г

Рис. 12. Зависимость емкости памяти от параметра отображения г: тонкая линия -стандартное отображение, жирная линия -ВНС с мерой близости. Параметры эксперимента: ¿=1000; р=0.3; Мн=30.

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

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

6 / АЗЧ

5 $ 9

Рис. 13. Эталонные изображения базы данных рукописных цифр ММЗТ.

Устойчивость к корреляциям данных превращает бинаризованные векторные нейронные сети в эффективный инструмент решения конкретных прикладных задач.

Сделанные выводы подтверждаются многочисленными экспериментами. Одним из них было тестирование векторных перцептронов (с обычными и бинаризованными синаптическими связями) на базе данных рукописных цифр МТМБТ (источник: Ы№ ://уапп. lecun.com/exdb/гпшбЬО. состоящей из 60000 различных написаний цифр от 0 до 9 (изображения 28x28 пикселов с 256 градациями серого, рис. 13). На этих данных были обучены поттсовский

20

векторный перцептрон и бесфазовый ВП с бинаризованными коэффициентами. Тестирование показывает, что перцептрон Поттса в 51020 случаях идентифицирует эталоны неправильно, а бинаризованный перцептрон ошибается лишь в 13 случаях. Более того, если на вход бинаризованному перцептрону подавать эталоны, искаженные на 45%, бинаризованный перцептрон ошибется лишь в 57 случаях.

В Заключении приводятся основные результаты работы:

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

2. Показано, что бинаризация фазовой модели при малых размерах сети приводит к увеличению емкости памяти и возрастанию способности восстанавливать более сильно искаженные образы; бинаризация сети большого размера приводит к незначительному уменьшению емкости памяти. Требования к объему оперативной памяти в результате бинаризации снижаются в 16 раз и более чем в 16 раз ускоряется алгоритм.

3. Бинаризация бссфазовой модели ВНС приводит к увеличению объема нейросетевой памяти от 2 до 30 раз в зависимости от размера сети. Бинаризованная бесфазовая модель при N<2Q превосходит по емкости памяти все известные ассоциативные модели нейронных сетей, включая модель Поттса. Требования к объему оперативной памяти в результате бинаризации снижаются в 32 раза, алгоритм ускоряется более чем в 16 раз.

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

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

6. Разработан метод отображения бинарных векторов в ^-парные образы, позволяющий использовать векторные нейросети для идентификации бинарных векторов. Метод использован для построения ВНС с полиномиальной по свободному параметру задачи емкостью памяти.

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

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Alieva D.I., Kryzhanovsky B.V., Kryzhanovsky V.M. Q-valued neural network as a system of fast identification and pattern recognition // Pattern Recognition and Image Analysis - 2005 - v.15, №1- pp. 30-33.

2. Крыжановский Б.В., Крыжановский B.M., Микаэлян А.Л. Применение процедуры клиппирования в задачах бинарной минимизации квадратичного функционала // Доклады АН,- 2007,- Т.413, №6,- сс. 730-733.

3. Крыжановский В.М., Симкина Д.И. Свойства клиппированной модели векторной ассоциативной памяти // Вестник компьютерных информационных технологий - 2007.- №11.— сс. 20-25.

4. Kryzhanovsky B.V., Kryzhanovsky V.M. A Binary Pattern Classification Using Potts Model // Optical Memory and Neural Networks (Information Optics).-2008 - Vol. 17, No. 4,-pp. 308-316.

5. Крыжановский Б.В., Крыжановский B.M. Модифицированная q-нарная модель Потгса с бинаризованными синаптическими коэффициентами // Искусственный интеллект.- 2008 - №3,- сс. 540-547.

6. Крыжановский Б.В., Крыжановский В.М. О возможности ускорения процедуры бинарной оптимизации // Известия РАН. Теория и системы управления,- 2009.- №5,- сс. 62-68.

7. Крыжановский Б.В., Крыжановский В.М. Идентификатор бинарных образов на основе модели Поттса // Вестник информационных компьютерных технологий,- 2009 - №8.- сс. 24-30.

8. Kryzhanovsky V.M. Q-nary pattern identifier based on committee of vector perceptrons // Optical Memory and Neural Networks (Information Optics).-

2009,-Vol. 18, No. 3.-pp. 188-194.

9. Kryzhanovsky В., Kryzhanovskiy V., Litinskii L. Machine Learning in Vector Models of Neural Networks / Dedicated to the memory of Professor Ryszard S. Michalski, Eds.: Koronacki, J., Ras, Z.W., Wierzchon, S.T. (et al.) // Advances in Machine Learning II., Series "Studies in Computational Intelligence", Springer-

2010,- SCI 263,-pp. 427-443.

10. Алиева Д.И., Крыжановский Б.В., Крыжановский В.М. Векторная нейронная сеть с бинарной матрицей связей // Труды второй Всероссийской научной конференции «Методы и средства обработки информации» МСО-2005,-2005,-сс.584-589.

11. Крыжановский В.М., Микаэлян A.JI. Об ограничениях на объем памяти декоррелирующей нейросети // Сборник трудов VIII Всероссийской научно-технической конференции «Нейроинформатика-2006».- М.: МИФИ, 2006-Ч.2.- сс.180-187.

12. Kryzhanovsky B.V., Kryzhanovsky V.M., Fonarev А.В. Decorrelating parametrical neural network // Proc. of International Joint Conference on Neural Networks (UCNN) .-2005.-pp. 1023-1026

13. Крыжановский B.M. Быстрая система идентификации и принятия решения на основе кпиппированной бесфазовой векторной нейросети И Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы».- Таганрог: Изд-во ТТИ ЮФУ, 2007.- Т.2.- сс.56-60.

14. Kryzhanovsky V.M. Modified q-state Potts Model with Binarized Synaptic Coefficients // Proc. of 18th International Conference on Artificial Neural Networks (ICANN'08), Springer, Lecture Notes in Computer Science.- 2008.- v. 5164, Part I.-pp. 72-80.

15. Kryzhanovsky V., Kryzhanovsky В., Fonarev A. Application of Potts-model Perceptron for Binary Patterns Identification // Proc. of 18th International Conference on Artificial Neural Networks (ICANN'08), Springer, Lecture Notes in Computer Science.- 2008,- v. 5163, Part I.-pp. 553-561.

16. Крыжановский Б.В., Крыжановский B.M. Модифицированная q-нарная модель Поттса с бинаризованными синалтическими коэффициентами // Сборник трудов XI Всероссийской научно-технической конференции «Нейроинформатика-2009». - М.: МИФИ, 2009- ч.2,- сс.85-94.

17. Krizhanovsky V.M. Pattern identification by committee of Potts perceptrons // Proc. of 19th International Conference on Artificial Neural Networks (ICANN'09), Springer, Lecture Notes in Computer Science.- 2009, Vol. 5768, Part I.- pp.844-853.

18. Крыжановский B.M. Идентификация коррелированных образов векторным перцептроном с бинаризованными синаптаческими коэффициентами // Сборник трудов XII Всероссийской научно-технической конференции «Нейроинформатика-2010». - М.: МИФИ, 2010,- ч.2,- сс.35-45.

Подписано в печать: 19.04.2010

Заказ № 3597 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

I. ВВЕДЕНИЕ.

§1.1. Обзор литературы.

§1.2. Актуальность темы.

§1.3. Цели и задачи диссертационной работы.

§1.4. Основные положения, выносимые на защиту.

§1.5. Методы исследования.

§1.6. Апробация работы и публикации.

§1.7. Структура и объем диссертации.

II. ОПТИМАЛЬНАЯ ПРОЦЕДУРА БИНАРИЗАЦИИ.

§2.1. Описание проблемы.

§2.2. Описание модели и постановка задачи.

§2.3. Процедура бинаризации.

§2.4. Анализ результатов.

§2.5. Выводы.

III. ФАЗОВАЯ ВЕКТОРНАЯ НЕЙРОННАЯ СЕТЬ.

§3.1. Описание модели.

§3.2. Эффективность восстановления образов.

§3.3. Анализ результатов.

§3.4. Выводы.

IV. БЕСФАЗОВАЯ ВЕКТОРНАЯ НЕЙРОННАЯ СЕТЬ.

§4.1. Описание модели.

§4.2. Эффективность восстановления образов.

§4.3. Сравнительный анализ.

§4.4. Выводы.

V. ВЕКТОРНЫЙ ПЕРЦЕПТРОН.

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

§5.2. Фазовый векторный перцептрон.

§5.3. Бесфазовый векторный псрцептрон с линейным членом.

§5.4. Перцептрон Поттса.

§5.5. Эффективность идентификации.

§5.6. Эффективность бинаризованного перцептрона.

§5.6. Анализ результатов.

§5.7. Выводы.

VI. КОМИТЕТ ВЕКТОРНЫХ ПЕРЦЕПТРОНОВ.

§6.1. Постановка задачи.„,

§6.2. Достоверность идентификации и его применение.

§6.3. Эффективность идентификации.

§6.4. Анализ результатов.

§6.5. Выводы.

VII. РАСПОЗНАВАНИЕ БИНАРНЫХ ОБРАЗОВ.

§7.1. Описание проблемы.

§7.2. Двухэтапная идентификация бинарных образов.

§7.3. Предобработка бинарного вектора.

§7.4. Эффективность двухэтапной идентификации.

§7.5. Ограничения на емкость памяти.

§7.6. Введение меры близости между состояния нейронов.

§7.7. Анализ результатов.

§7.7. Выводы.

VIII. РАСПОЗНАВАНИЕ КОРРЕЛИРОВАННЫХ ОБРАЗОВ.

§8.1. Описание проблемы.

§8.3. Новый векторный формализм.

§8.3. Идентификация случайных эталонов.

§8.4. Идентификация коррелированных эталонов.

§8.5. Эксперимент.

§8.6. Выводы.

Традиционно системы управления для автоматических устройств конструировались на основе описания математических моделей объектов управления [1]. При этом уравнения, описывающие состояние управляемых объектов, и внешние воздействия предполагались известными. Такая полная определенность позволяла использовать аналитический аппарат математики для решения проблем теории управления. Однако область применимости этих подходов оставалась ограниченной, особенно в условиях, когда внешние воздействия, как задающие, так и возмущающие, непрерывно изменяются во времени и не могут быть однозначно определенны, что характерно для реальных ситуаций [2]. В тоже время, учет нелинейных свойств объектов управления, их взаимодействия в сложных системах резко усложняет математические модели объектов и процессов, и во многих случаях делает их построение практически невозможным.

В связи с возникающими трудностями, интерес представляют способы построения систем управления на основе подходов, которые реализуются природой в живых организмах. Действительно, системы управления живыми организмами в природе обеспечивают высокую обучаемость и приспосабливаемость к изменяющимся .условиям среды обитания. Задача восприятия сигналов, их обработки в биологических системах решена развитием нервной системы-мозга, которая обеспечивает управление многоклеточным организмом, независимо от ее формы и среды обитания. В свою очередь, работа мозга основана на ассоциативном: мышлении, которое способно распознавать образы и определять управление. Осознание этого факта и привело к идее создания и применения методов распознавания образов в слабо формализованных областях науки: при распознавание текста, геологии, медицине, химии, биологии и др. Широкое распространение методов распознавания в науке происходит по двум причинам [3]: о для их применения требуется меньшая точность в описании исследуемого объекта, чем при применении других методов математики; о идея принятия решения на основе прецедентности является естественной.

Так, глубокое развитие получили системы распознавания образов в работах академика Ю.И. Журавлева [3-5] и его учеников - К.В. Рудакова [6] и д.р., на основе выдвинутого им "алгебраического подхода". Действительно, проблема решения конкретной модели в рамках заданного множества параметров сводится к поиску их оптимальных значений. Ю.И. Журавлев отметил противоречие этого подхода: если модель содержит "мало параметров", то оптимальный в ней алгоритм не будет иметь высокое качество. Если же модель имеет много "степеней свободы", то сама проблема поиска оказывается настолько трудоемкой, что приходится ограничиваться локальными экстремумами невысокого качества. Идея подхода заключается в следующем: если решение не удается найти в заданном множестве, то его можно построить в соответствующем расширении. Методы такого расширения, полнота, корректность, устойчивость и составляют теорию "алгебраического подхода" [3-5] к решению задач распознавания или классификации.

Другое направление работ связано с появлением математической модели нейрона Маккалока-Питса [7]. Оно привело к созданию нейронных сетей: о решающих задачи классификации - перцелтрон Розенблата [8]; о реализующих ассоциативную память - сети Хопфилда [2], векторные сети и др.

Важную роль для этого направления сыграла работа академика А.Н.Колмогорова [9].

В настоящей работе исследуются векторные нейронные сети (ВНС), реализующие ассоциативную память.

§1.1. Обзор литературы

Вначале дается обзор нейронных сетей, реализующих ассоциативную память, синаптические связи которых вычисляются по правилу Хебба [10]:

Хопфилд в 1982 году предложил полносвязную рекуррентную нейронную модель авто-ассоциативной памяти [11]. Была измерена емкость памяти, величина которой составила 15% от размерности сети N (М = 0.15JV). Впервые было введено понятие энергии нейронной сети, которая в процессе работы нейронной сети монотонно понижается. Хопфилд показал, что эта энергия ограниченна и в силу монотонности ее понижения процесс распознавания конечен, а эталонные векторы, записываемые в нейронную сеть по правилу Хебба, являются локальными минимумами введенного им энергетического функционала. Кроме того, Хопфилд установил изоморфизм между рекуррентной сетью и изинговой моделью (Ising model) системы взаимодействующих спинов, используемой в статистической физике. Эта аналогия породила большое количество модификаций модели Хопфилда с целью увеличения емкости памяти. Однако предложенные модели имели столь же невысокие показатели, как и исходная модель Хопфилда.

В период 1985-1987 гг. Амит, Гудфренд и Шомполинский [12] на основе статфизических методов развивают подход, позволяющий получить аналитическую оценку емкости памяти (М = N/lnN) и вероятности ошибки распознавания модели Хопфилда.

В 1980-1999 г. Пальм активно анализирует различные модели ассоциативных сетей [13-19] с точки зрения информационной емкости и эффективности (количества бит сохраненной информации приходящейся на синапс). Пальм исследует различные бинарные нейроархитектуры - рекуррентную, перцептронную и двунаправленную, а также нейросети с бинарными синапсами и показывает, что сети с бинарными синапсами превосходят по информационной емкости все остальные модели. В своих работах Пальм использует редкое кодирование.

В 1991-1999 г. Фролов и Муравьев различными методами исследуют нейронные сети хопфилдова типа с редким кодированием [20-26]. Анализируют информационную емкость, качество воспроизведения и размер области притяжения. Исследуют асимптотические свойства ассоциативной памяти. Показывают, что оптимальная разреженность близка к уровню нервной активности. Разработали алгоритм, позволяющий моделировать нейронные сети экстремально большой размерности (до 1,5 -105 нейронов).

В 1988 году Кантер [27] по аналогии с физической моделью спинового магнетика Поттса [28,29] выдвигает модель нейронной сети, нейроны которой могут иметь более двух различных состояний. Каждое состояние нейрона описывается вектором Q -мерного пространства, принадлежащему набору из Q специальных (поттсовских) векторов, где Q>. 2 - число различных состояний нейрона. Эта модель получает название «Поттс-стекольной нейросети» (Potts-glass neural network). В своей работе Кантер, применяя подход, развитый группой Амита, получает, что емкость памяти Q{Q-\)i2 раз больше емкости сети Хопфилда (М = NQ(Q -1) / 4 In NQ).

В период 1991-1994 г. начинается активное исследование модели Поттса [30-35], такими авторами как Болле, Ван Моурик, Дюпонт, Вогт, Зипелиус и многим другими.

В 1995 году Накамура [36] исследует модель ассоциативной нейронной сети, в которой состояние нейрона описывается единичным вектором, на направление которого не накладываются никаких ограничений. Исследования показали неудовлетворительные результаты — невысокую емкость памяти (М = 0.07.АГ в случае, когда векторы-состояния лежат на плоскости, и М - 0.04N - в трехмерном пространстве), однако были сформулированы весьма плодотворные идеи относительно представления межсвязей в виде тензорного произведения векторов-состояний.

В 2001 году Микаэлян и Б.Крыжановский разрабатывают нейронную модель ассоциативной памяти [37], ориентированную на реализацию в виде оптоэлектронного устройства. Емкость памяти оптической модели (М = NQ{Q-X)i%\n{NQ))} полученная в рамках «сигнал/шумового» подхода (signal-to-noise approach), оказывается того же порядка, что и емкость памяти модели Поттса.

В 2003 году Микаэлян, Б.Крыжановский и Литинский разрабатывают векторный формализм - простой векторный язык описания оптической нейронной сети, оторванный от оптической постановки задачи [38,39]. Синаптическая связь в таком описании, также как и у Накамуры, представляется в виде тензорного произведения векторов.

В рамках векторного формализма Б.Крыжановский в 2003 году дает простое описание Поттс-стекольной модели [40,41], которое первоначально формулировалось в терминах, чрезвычайно усложнявших понимание модели. Более того, переход к векторному описанию позволил в Q раз ускорить алгоритм.

Далее рассматриваются наиболее интересные публикации, посвященные нейронным сетям с произвольным (не Хеббовским) обучающим правилом.

В период 1984-1987 г. Кохонен [42], Персонас, Гайон и Дрейфус [43], Кантер и Сомполинский [44] исследуют проекционную модель нейронной сети (projector model). Синаптические связи этой модели вычисляются с помощью псевдообратной матрицы, вычисление которой представляет определенную вычислительную сложность. Добавление новых эталонов требует сложного пересчета всех синаптических коэффициентов, в противоположность хеббовскому аддитивному правилу обучения. Проекционная модель способна надежно хранить N — 1 линейно независимых эталонов. На практике эталонные векторы редко линейно независимы, что ухудшает распознающую способность проекционной модели.

Исследования, начатые Гарднер и проводимые с 1965 по 1993 годы, показали, что максимальная емкость памяти модели Хопфилда [45-49] и простого однослойного перцептрона [50-53] при оптимальном правиле обучения (не хеббовском) не превышает 2 N.

В разные годы разными исследователями независимо друг от друга был разработан алгоритм обратного распространения ошибки (back-propagation algorithm), позволяющий обучать многослойные перцептроны. В 1969 году основная идея была опубликована Брайсоном в работе.[54], в 1974 году этот алгоритм описал Вербос в своей кандидатской диссертации, в 1985 опубликована Лекуном [55] и в 1987 Паркером; [56]. Однако наиболее известными стали работы Румельхарта, Хинтона и Вйльямса [57,58] за предложение использовать этот алгоритм для машинного обучения и демонстрацию его работы.

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

В заключение приведем работы, посвященные исследованию нейронных сетей с бинарными синапсами:

Впервые нейронную модель с бинарными синапсами в 1961 году предложил Стейнбах [59]. Сейчас эта модель больше известна как модель Вилшоуа [60]. Исследования, проведенные Пальмом, показали [16], что при редком кодировании эта модель обладает рекордной информационной емкостью.

Бинаризацию синапсов для нейросетевой модели AD ALINE в 1960 году также исследовали Уидроу и Хофф [61], которые показали, что бинаризация синапсов привела к увеличению емкости памяти.

В 80-е годы, в работах [62-64] вновь была описана бинаризация синапсов, только уже для модели Хопфилда. Методами статистической физики, были получены аналитические оценки емкости памяти и восстанавливающей способности сети. Основной недостаток модели Хопфилда - малая емкость памяти. Число эталонов, которое сеть способна хранить и надежно восстанавливать, не превышает 14% от числа нейронов сети. Огрубление синапсов приводит к частичной потере информации, следствием чего является уменьшение емкости памяти, хотя при этом увеличивается информационная эффективность. Исследование сети Хопфилда с бинаризованными синапсами показало, что объем ее памяти в к / 2 раз меньше, чем объем памяти стандартной модели Хопфилда с матрицей Хебба. Поскольку на тот момент еще не существовало способов повышения емкости памяти, дальнейшие исследования в области бинаризации синапсов модели Хопфилда казались нецелесообразными.