новости  материалы  справочник  форум  гостевая  ссылки  
Новости
Материалы
  Логические подходы
  Нейронные сети
  Генетические алгоритмы
  Разное
  Публикации
  Алгоритмы
  Применение
Справочник
Форум
Гостевая книга
Ссылки
О сайте
 

Лекция 9. Обобщения и применения модели Хопфилда


Автор: Сергей А. Терехов
Источник: http://alife.narod.ru/lectures/neural/Neu_index.htm
Дата: 1998
Учебное заведение: Лаборатотория Искусственных Нейронных Сетей НТО-2, ВНИИТФ, Снежинск
Web-страница заведния: http://www.vniitf.ru/~nimfa


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

Модификации правила Хебба.

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

Матрица Хебба с ортогонализацией образов.

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

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

где B-1 - матрица, обратная к матрице B:

Такая форма матрицы памяти обеспечивает воспроизведение любого набора из p<N образов. Однако, существенным недостатком этого метода является его нелокальность: обучение связи между двумя нейронами требует знания состояний всех других нейронов. Кроме того, прежде чем начать обучение, необходимо наперед знать все обучающие образы. Добавление нового образа требует полного переобучения сети. Поэтому данный подход весьма далек от исходных биологических оснований сети Хопфилда-Хебба, хотя на практике приводит к заметным улучшениям ее функционирования.

Отказ от симметрии синапсов.

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

Элементы матрицы Pij из множества {0,1} управляют наличием или отсутсвием связи от нейрона i к нейрону j.

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

Алгоритмы разобучения (забывания).

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

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

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

В качестве степени забывания e выбирается некоторое малое число, что гарантирует незначительное ухудшение полезной памяти, если состояние l(f) не окажется ложным. После нескольких “сеансов забывания” свойства сети улучшаются (J.J.Hopfield et al, 1983).

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

Двунаправленная ассоциативная память.

Дальнейшее развитие нейросетевые архитектуры ассоциативной памяти получили в работах Барта Коско (B.Kosko, 1987). Им была предложена модель гетероассоциативной памяти, в которой запоминаяются ассоциации между парами образов. Запоминание происходит так, что при пред’явлении сети одного из образов восстанавливается второй член пары.

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

Двунаправленная сеть в модели Коско состоит из двух слоев нейронов (слой A и слой B). Связи между слоями устроены таким образом, что каждый нейрон одного слоя связан с каждым нейроном другого слоя. Внутри слоев связи между нейронами отсутствуют, число нейронов на каждом слое может быть различным. Для запоминания предназначаются пары образов (xa, xb)(a), a=1..p. Обучение задается правилом Хебба:

Динамика системы является параллельной и происходит по формулам:

Здесь {aj}, j=1..Na - состояния активности нейронов слоя A, {bi}, i=1..Nb - слоя B. В качестве нейронной функции f может использоваться пороговая функция или сигмоид. В частном случае одинаковых слоев и одинаковых образов в обучающих парах сеть Коско полностью эквивалентна модели Хопфилда.

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

Сеть Коско обладает также и свойством автоассоциативности: если одновременно известны некоторые фрагменты образов на слое A и B, то в процессе динамики будут одновременно восстановлены оба образа пары.

Детерминированная и вероятностная нейродинамика.

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

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

При строго нулевой температуре (T=0) статистический Больцмановский фактор ~exp(-DE/T) делает невозможным увеличение энергии. Переход к ненулевым температурам (T>0) значительно обогащает динамику системы, которая теперь может с ненулевой вероятностью делать переходы с возрастанием E и посещать новые статистические состояния.

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

Si(t+1) = sign( hi(t)-Q), с вероятностью Pi

Si(t+1) = - sign( hi(t)-Q), с вероятностью (1-Pi)

Вероятность перехода в состояние с возрастанием энергии тем меньше, чем больше разница в энергиях конечного E2 и начального E1 состояний. В статистических системах эта вероятность определяется формулой Больцмана:

Нетрудно заметить, что в пределе низких температур (T®0) вероятность P стремится к единице, и динамика переходит в обычную детерминированную нейродинамику.

При высоких температурах (T >> D E) вероятность P=1/2, т.е. изменение состояния нейрона никак не связано ни с его предыдущим состоянием, ни со значением “нейронного поля” h(t). Состояния сети меняются полностью хаотично, и ситуация ничем не напоминает систему с памятью.

Динамика нейронной системы при ненулевых температурах уже не является Ляпуновской, так как энергия сети не обязана теперь уменьшаться со временем. При этом, вообще говоря, полной стабилизации состояния сети не происходит - состояние быдет продолжать испытывать изменения, при которых DE µT.

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

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

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

Применения сети Хопфилда к задачам комбинаторной оптимизации.

Ассоциативность памяти нейронной сети Хопфилда не является единственным ее достоинством, которое используется на практике. Другим важным свойством этой архитектуры является уменьшение ее функции Ляпунова в процессе нейродинамики. Следовательно, нейросеть Хопфилда можно рассматривать, как алгоритм оптимизации целевой функции в форме энергии сети.

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

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

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

Многие задачи оптимального размещения и планирования ресурсов, выбора маршрутов, задачи САПР и иные, при внешней кажущейся простоте постановки имеют решения, которые можно получить только полным перебором вариантов. Часто число вариантов быстро возрастает с числом структурных элементов N в задаче (например, как N! - факториал N), и поиск точного решения для практически полезных значений N становится заведомо неприемлимо дорогим. Такие задачи называют неполиномиально сложными или NP-полными. Если удается сформулировать такую задачу в терминах оптимизации функции Ляпунова, то нейронная сеть дает весьма мощный инструмент поиска приближенного решения.

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

Полное число возможных маршрутов равно , и задача поиска кратчайшего из них методом перебора весьма трудоемка. Приемлимое приближенное решение может быть найдено с помощью нейронной сети, для чего, как уже указывалось, требуется переформулировать задачу на языке оптимизации функции Ляпунова (J.J.Hopfield, D.W.Tank, 1985).

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

Таб. 9.1. Маршрут B-A-C-D ...

  Номер
Город 1 2 3 4 ...
A 0 1 0 0 ...
B 1 0 0 0 ...
C 0 0 1 0 ...
D 0 0 0 1 ...
... ... ... ... ... ...

Сопоставим теперь клетке таблицы на пересечении строки X и столбца i нейрон Sxi из {0,1}. Возбужденное состояние данного нейрона сигнализирует о том, что город X в маршруте следует посещать в i-тую очередь. Составим теперь целевую функцию E(S) задачи поиска оптимального маршрута. Она будет включать 4 слагаемых:

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

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

Здесь за dXY обозначено расстояние между городами X и Y. Заметим, что отрезок пути X-Y включается в сумму только тогда, когда город Y является относительно города X либо предыдущим, либо последующим. Множители a , b , g и h имеют смысл относительных весов слагаемых.

Общий вид функции Ляпунова сети Хопфилда дается выражением (см. предыдущую лекцию):

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

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

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

Пусть имеется некоторое (достаточно длинное) текстовое сообщение, написанное на некотором языке с использованием алфавита A, B, C ... z и символа “пробел”, отвечающего за промежуток между словами. Данное сообщение закодировано таким образом, что каждому символу, включая пробел, сопоставлен некоторый символ из ряда i,j,k, .... Требуется расшифровать сообщение.

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

Частоты появления символов Pi и их пар Pij в закодированном сообщении можно вычислить непосредственно. Имея, далее, в распоряжении значения PA частот появления символов языка и их пар PAB , следует отождествить их с вычисленными значениями для кода. Наилучшее совпадение и даст требуемый ключ.

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

Полное выражение для целевой функции имеет вид:

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


Задачи

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

2. Для задачи комивояжера получить представление E(S) целевой функции в форме функции Ляпунова.

3. Вывести энергетическую функцию сети Хопфилда для задачи оптимального размещенния смесей кода и данных в многопроцессорной архитектуре “гиперкуб”.

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

Как и в задаче комивояжера, обозначим процессоры заглавными буквами, а номера смесей - латинскими индексами. Если dXY - расстояние между процессорами, измеренное вдоль ребер гиперкуба (Хеммингово расстояние), а Dij - объем передаваемой информации между смесями i и j, то искомое решение должно минимизировать сумму SUMdXYDij. Поэтому целевая функция представляется в виде:

E(S) = E1 + E2 + E3 + (h/2) SUMi SUMj SUMX SUMY (SXiSYj dXY Dij)

Это выражение далее приводится к форме функции Ляпунова. Численные эксперименты с гиперкубами размерности 3, 4 и 5 показывают, что применение нейросетевого подхода позволяет получить умешение числа информационных обменов (и, соотвественно, повысить производительность ЭВМ) для некоторых задач до 1,5 раз.


Предыдущая Оглавление Следующая