Ассоциативная память нейронных сетей

Ассоциативная память нейронных сетей

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

Термин «нейронные сети» сформировался к середине 50-х годов ХХ века. Основные результаты в этой области связаны с именами У. Маккалоха, Д. Хебба, Ф. Розенблатта, М. Минского, Дж. Хопфилда.

Глубокое изучение ИНС требует знания нейрофизиологии, науки о познании, психологии, физики (статистической механики), теории управления, теории вычислений, проблем искусственного интеллекта, статистики/математики, распознавания образов, компьютерного зрения, параллельных вычислений и аппаратных средств (цифровых и аналоговых). С другой стороны, ИНС также стимулируют эти дисциплины, обеспечивая их новыми инструментами и представлениями. Этот симбиоз жизненно необходим для исследования нейронных сетей.

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

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

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

Впервые термин «ассоциация» был введен Дж. Локком в 1698 г. и определен как «связь, возникающая при определенных условиях между двумя или более психическими образованиями  ощущениями, актами, восприятиями, идеями».

Принято говорить, что у человека возникла ассоциация, если при получении некоторой неполной информации он может подробно описать объект, к которому, по его мнению, относится эта информация. Достаточно хорошим примером может служить описание малознакомого человека. К примеру, при высказывании: "Слушай, а что за парень, с которым ты вчера разговаривал на вечеринке, такой высокий блондин?"- у собеседника возникает образ вчерашнего собеседника, не ограничивающийся ростом и цветом волос. В ответ на заданный вопрос он может рассказать об этом человеке довольно много. При этом следует заметить, что содержащейся в вопросе информации явно недостаточно для точной идентификации собеседника. Более того, если вчерашний собеседник был случайным, то без дополнительной информации его и не вспомнят.

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

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

Одновременно рассмотренные примеры позволяют сформулировать решаемые ассоциативной памятью задачи:

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

2.      Отфильтровать из входной информации недостоверную, а на основании оставшейся решить первую задачу.

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

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

Ассоциативный способ доступа к информации обеспечивает:

• практически одновременный доступ ко всей хранящейся в памяти информации;

• относительную независимость времени поиска информации от емкости памяти;

• внесение элементов обработки информации непосредственно в процесс самого доступа;

• обработку информации непосредственно в среде ее хранения.

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

2.1.1. Ассоциации

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

• логико-запоминающей среды, являющейся носителем информации;

• множества записанных в памяти информационных объектов;

• структуры взаимосвязей между информационными объектами;

• механизма информационных взаимодействий в логико-запоминающей среде.

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

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

2.1.2. Модели ассоциативной памяти

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

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

• соотнесение поисковой информации с хранимой и дополнение ее (инициализация) до точного описания объекта, т.е. всей информации, которая доступна ассоциативной памяти;

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

Одна из простейших моделей ассоциативной памяти для отображения таких отношений показана на рис. 2.1. Модель состоит из ассоциативной логико-запоминающей среды (нейронной сети), связанной с двумя каналами ввода и одним каналом вывода информации. На этапе записи (обучения) из первого канала ввода на вход К подается входная информация, а по второму каналу  признаковая информация С, представляющая контекст, в котором входная информация записывается в память.

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

Рис. 2.1. Модель ассоциативной памяти

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

Рис. 2.2. Модель ассоциативной памяти

с образной связью

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

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

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

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

Модели ассоциативной памяти, реализуемые нейронными сетями, могут быть гораздо сложнее. Кроме того, память может иметь несколько входов и выходов, состоять из нескольких подсистем. Данные в одном канале могут порождать контекстную информацию для другого канала. Этап записи может выполняться отдельно от выборки или быть совмещенным и т. д.

3.      Архитектура, алгоритм Функционирования и режимы работы сети Хопфилда

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

Рис. 1. - Схема сети Хопфилда

Сеть Хопфилда состоит из N искусственных нейронов. Граница ёмкости памяти для сети (то есть количество образов, которое она может запомнить) составляет приблизительно 15% от числа нейронов в слое Хопфилда (N*0,15).  При этом запоминаемые образы не должны быть сильно коррелированны.

Размерности входных и выходных сигналов в сети ограничены при программной реализации только возможностями вычислительной системы, на которой моделируется нейронная сеть, при аппаратной реализации — технологическими возможностями. Размерности входных и выходных сигналов совпадают.

Каждый нейрон системы может принимать одно из двух состояний (что аналогично выходу нейрона с пороговой функцией активации):

Благодаря своей биполярной природе нейроны сети Хопфилда иногда называют спинами.

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

где wij элемент матрицы взаимодействий W, которая состоит из весовых коэффициентов связей между нейронами. В эту матрицу в процессе обучения записывается М «образов» — N-мерных бинарных векторов: Sm = (sm1,sm2,...,smN).

В сети Хопфилда матрица связей является симметричной (wij = wji), а диагональные элементы матрицы полагаются равными нулю (wii = 0), что исключает эффект воздействия нейрона на самого себя и является необходимым для сети Хопфилда.

Рассмотрим общий алгоритм работы сети:

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

Где i и j ()–индексы,соответственно, предсинаптического (входного) и постсинаптического (выходного) нейронов; wij — i-й синаптический вес j-го нейрона; xik, xjk – i-ый и j-ый элементы вектора k-ого образца.

2.      На входы сети подаётся неизвестный сигнал. Фактически его ввод осуществляется непосредственной установкой значений:

yj(0) = xj , j = 0...n-1,

где yj — аксон (т.е. выход) j-го нейрона. Поэтому обозначение на схеме сети входных синапсов в явном виде носит чисто условный характер. Ноль в скобке справа от yj означает нулевую итерацию в цикле работы сети.

3.  Рассчитывается новое состояние нейронов и новые значения аксонов:

,

где  j=0...n-1, p – номер (конкретный шаг) итерации,   - новое состояние нейрона;

,

где f – активационная функция в виде скачка, приведённая на рис. 2б.

Рис. 2: а) жёсткая пороговая (передаточная)функция сети Хопфилда;

б) активационная функция сети Хопфилда.

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

5.     Области применения сети

 Сеть Хопфилда  может быть использована как ассоциативная память, для решения некоторых задач оптимизации, а также как фильтр (задачи распознавания образов).

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

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

Рассмотрим пример восстановления повреждённого изображения.

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

Пусть имеется нейронная сеть размерностью N=100 , в матрицу связей записан набор чёрно-белых картинок (-1 — чёрный цвет, +1 — белый), среди которых есть изображение собачки (рис. 3б). Если установить начальное состояние сети близким к этому вектору (рис. 3а), то в ходе динамики нейронная сеть восстановит исходное изображение (рис. 3б). В этом смысле можно говорить о том, что сеть Хопфилда решает задачу распознавания образов (хотя строго говоря, полученное эталонное изображение ещё нужно превратить в номер класса, что в некоторых случаях может быть весьма вычислительно ёмкой задачей).

а)                                  б)

Рис. 3: а) начальное состояние для сети Хопфилда; б) восстановленное изображение. 

 4.     Достоинства, недостатки и модификации Сети хопфилда

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

К сожалению, у нейронной сети Хопфилда есть ряд недостатков:

1. Относительно небольшой объём памяти, величину которого можно оценить выражением:

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

2. Достижение устойчивого состояния не гарантирует правильный ответ сети. Это происходит из-за того, что сеть может сойтись к так называемым ложным аттракторам, иногда называемым "химерой" (как правило, химеры склеены из фрагментов различных образов).

3. При использовании коррелированных векторов-образцов возможно зацикливание сети в процессе функционирования.

4. Наряду с запомненными образами в сети хранятся и их негативы.

У сети Хопфилда существуют модификации. Одна из них предназначена для решения задач оптимизации, в частности задачи распределения работ между исполнителями.

Существует модель сети Хопфилда с бинарными входными сигналами.

Для увеличения ёмкости сети и повышения качества распознавания образов используют мультипликативные нейроны. Сети, состоящие из таких нейронов, называются сетями высших порядков.

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

                                Сеть Хэмминга

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

1. Общие сведения

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

-расстояние0
–расстояние2
– расстояние 5

2. Структура сети

Рис. 1. Структурная схема сети Хэмминга.

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

Первый слой имеет однонаправленное распространение сигналов от входа к выходу и фиксированные значения весов.

Нейроны второго слоя связаны между собой ингибиторными (отрицательными обратными) синаптическими связями. Единственный синапс с положительной обратной связью для каждого нейрона соединен с его же аксоном. Таким образом, второй слой состоит из нейронов, связанных обратными связями по принципу "каждый с каждым", при этом в каждом нейроне слоя существует автосвязь (связь входа нейрона со своим собственным выходом). Разные нейроны в слое связаны отрицательной (тормозящей) обратной связью с весом , при этом величина обычно обратно пропорциональна количеству образов. С собственным входом нейрон связан положительной (возбуждающей) обратной связью с весом, равным +1. Пороговые веса нейронов приняты равными нулю. Нейроны этого слоя функционируют в режиме, при котором в каждой фиксированной ситуации активизируется только один нейрон, а остальные пребывают в состоянии покоя.

Выходной однонаправленный слой формирует выходной вектор, соответствующий входному вектору.

Тип входных сигналов: бинарные векторы.

Тип выходных сигналов: целые числа.

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

Тип передаточной функции: линейная с насыщением.

Число синапсов в сети: (N*M).

3.Алгоритм работы

  Инициализация весовых коэффициентов первого слоя.
,

где Х – запоминаемые образы, i – соответствующий компонент вектора X, j – номер образа, n – размерность вектора X, m – количество запоминаемых образов.

На входы сети подается неизвестный вектор Х{хi:i=0…n-1}, исходя из которого рассчитываются состояния нейронов первого слоя(верхний индекс в скобках указывает номер слоя)

1.              Расчет состояния нейронов первого слоя.
  ,
где X – неизвестный образ, T = n/2 – порог активационной функции

После этого полученными значениями инициализируются значения аксонов второго слоя:

yj(2)=yj(1), j=0…m-1

1.              Вычислить новые состояния нейронов второго слоя.
,
где p – номер итерации, 0 < < 1/m
,
где f – пороговая активационная функция.
,
где F – порог активационной функции. Обычно F выбирается достаточно большим, так, чтобы при любом допустимом значении входа не наступало насыщение. На практике F обычно берется равным количеству примеров.

2.              Проверка условия выхода.

Если выходы не стабилизировались, т.е. изменялись за последнюю итерацию, то переход на шаг 3, иначе конец.

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

Заключение

Область применения

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

Задача оптического распознавания символов (OСR). Действительно, так оно и есть. При решении этой задачи сети Хэмминга активно используются. Но это, так сказать, лежит на поверхности. На практике они используются для восстановления зашумленного исходного сигнала, задачах оптимизации и во многих других случаях.

Нечеткий поиск.

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

А – 00001
Б – 10001
В – 10010
…

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

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

Преимущества

Сеть работает предельно просто и быстро. В модели использован один из самых простых алгоритмов формирования синаптических весов и смещений сети. В отличие от сети Хопфилда, емкость сети Хемминга не зависит от размерности входного сигнала, она в точности равна количеству нейронов (M). Сеть Хопфилда с входным сигналом размерностью 100 может запомнить 10 образцов, при этом у нее будет 10000 синапсов. У сети Хемминга с такой же емкостью будет всего лишь 1000 синапсов.

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

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