Пятковский О.И. Интеллектуальные информационные системы (нейронные сети)

Подождите немного. Документ загружается.

Рис. 8.6. Образ может быть распознан по небольшому фрагменту.

А Б

Рис. 8.7. (A) - Пример релаксации к ложному образу. (Б) - Добавление

информации к левой картинке (А) приводит к правильному распознаванию.

Образ на Рис. 8.4.(А) был выбран для тестирования адекватности пове-

дения на идеальной задаче, когда пред'явленное изображение точно соотвест-

вует информации в памяти. В этом случае за один шаг было достигнуто ста-

ционарное состояние. Образ на Рис. 8.4.(Б) характерен для задач распознава-

ния текста независимо от типа шрифта. Начальное и конечное изображения

безусловно похожи, но попробуйте это об'яснить машине!

Задания на Рис. 8.5 характерны для практических приложений. Нейро-

сетевая система способна распознавать практически полностью зашумленные

образы. Задачи, соответствующие Рис. 8.6. и 8.7.(Б), демонстрируют замеча-

тельное свойство сети Хопфилда ассоциативно узнавать образ по его неболь-

шому фрагменту. Важнейшей особенностью работы сети является генерация

ложных образов. Пример релаксации к ложному образу показан на Рис. 8.7.(А).

Ложный образ является устойчивым локальным экстремумом энергии,

но не соответствует никакому идеальному образу. Он является в некотором

смысле собирательным образом, наследующим черты идеальных собратьев.

Ситуация с ложным образом эквивалентна нашему "Где-то я уже это видел".

В данной простейшей задаче ложный образ является "неверным" реше-

нием, и поэтому вреден. Однако, можно надеяться, что такая склонность сети

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

личении об'ема полезной информации (сравните Рис. 8.7.(А) и (Б)), исходное

состояние попадает в область притяжения требуемого стационарного состоя-

ния, и образ распознается.

__________________________

Несмотря на интересные качества, нейронная сеть в классической модели

Хопфилда далека от совершенства. Она обладает относительно скромным

об'емом памяти, пропорциональным числу нейронов сети N, в то время как сис-

темы адресной памяти могут хранить до 2

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

битов. Кроме того, нейронные сети Хопфилда не могут решить задачу распо-

знавания, если изображение смещено или повернуто относительно его исходно-

го запомненного состояния. Эти и другие недостатки сегодня определяют об-

щее отношение к модели Хопфилда, скорее как к теоретическому построению,

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

скому средству.

На следующих лекциях мы рассмотрим развитие модели Хопфилда, мо-

дификации правила Хебба, увеличивающие об'ем памяти, а также приложения

вероятностных обобщений модели Хопфилда к задачам комбинаторной опти-

мизации.

3.6 Обобщения и применения модели Хопфилда.

Вероятностные обобщения модели Хопфилда и стати-

стическая машина Больцмана. Двунаправленная ассоциатив-

ная память Коско. Представление информации в сети Хоп-

филда, решающей задачу комбинаторной оптимизации. Ней-

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

вычислительных процессов в нейроЭВМ.

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

Ограничения емкости синаптической памяти, а также проблема ложной

памяти классической нейронной сети в модели Хопфилда, обученной по прави-

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

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

правил обучения.

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

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

обучающей выборки является весьма благоприятным обстоятельством, так как

в этом случае можно показать их устойчивое сохранение в памяти. В случае

точной ортогональности достигается максимальная емкость памяти, равная N -

максимально возможному числу ортогональных образов из N компонент

На этом свойстве ортогональных образов и основан один из наиболее

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

в нейронной сети исходные образы следует ортогонализовать. процедура орто-

гонализации приводит к новому виду матрицы памяти:

ij i j

−

−−

−

∑

∑∑

∑

ξξ

ξ ξ

ξξ

αα

α µ

µµ

αµ

αµαµ

αµ

αα

α µ

µµ

( ) ( )

где B

-1

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

i i

αµ

αµαµ

αµ

αα

α µ

µµ

ξξ

ξ ξ

ξξ

∑

∑∑

∑

( ) ( )

Такая форма матрицы памяти обеспечивает воспроизведение любого на-

бора из p<N образов. Однако, существенным недостатком этого метода являет-

ся его нелокальность: обучение связи между двумя нейронами требует знания

состояний всех других нейронов. Кроме того, прежде чем начать обучение, не-

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

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

ходных биологических оснований сети Хопфилда-Хебба, хотя на практике при-

водит к заметным улучшениям ее функционирования.

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

Другим подходом для улучшения правила Хебба является отказ от сим-

метрии синаптических соединений. Матрица памяти может выбираться в сле-

дующей форме:

(

((

( )

))

)

ij i j ij





































⋅

⋅⋅

⋅ −

−−

−

∑

∑∑

∑

ξξ

ξ ξ

ξξ

αα

α α

αα

( ) ( )

Элементы матрицы P

∈{0,1} управляют наличием или отсутсвием связи

от нейрона i к нейрону j.

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

тигнуто за счет появления новых степеней свободы, связанных с матрицей P. В

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

Следует также отметить, что динамическая система с несимметричной матри-

цей не обязана быть устойчивой

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

Возможность забывания ненужной, лишней информации является одним

из замечательных свойств биологической памяти. Идея приложения этого свой-

ства к искусственной нейросети Хопфилда “удивительно” проста: при запоми-

Набор из N ортогональных образов составляет базиз пространства образов с N компонентами (см. лекцию 2).

нании образов обучающей выборки вместе с ними запоминаются и ложные об-

разы. Их-то и следует “забыть”.

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

Суть их сводится к следующему.

На первой фазе происходит обучение сети по стандартному правилу Хеб-

ба. Память наполняется истинными образами и множеством ложной информа-

ции. На следующей фазе (фазе разобучения) сети пред’является некоторый

(случайный) образ λ

(0)

. Сеть эволюционирует от состояния λ

(0)

к некоторому со-

стоянию λ

(f)

, которое при большом об’еме обучающей выборки чаще всего ока-

зывается ложным. Теперь матрица связей может быть поправлена, с целью

уменьшить глубину минимума энергии, отвечающего этому ложному состоя-

нию:

t W t

ij ij i

( ) ( )

+ =

= −

−−

− ⋅

⋅⋅

⋅1

εε

ε λ

λλ

λ λ

λλ

В качестве степени забывания ε выбирается некоторое малое число, что

гарантирует незначительное ухудшение полезной памяти, если состояние λ

(f)

не

окажется ложным. После нескольких “сеансов забывания” свойства сети улуч-

шаются (J.J.Hopfield et al, 1983).

Данная процедура далека от формального теоретического обоснования

однако на практике приводит к более регулярной энергетической поверхности

нейронной сети и к увеличению об’ема бассейнов притяжения полезных обра-

зов.

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

Дальнейшее развитие нейросетевые архитектуры ассоциативной памяти

получили в работах Барта Коско (B.Kosko, 1987). Им была предложена модель

гетероассоциативной памяти, в которой запоминаяются ассоциации между па-

рами образов. Запоминание происходит так, что при пред’явлении сети одного

из образов восстанавливается второй член пары.

Запоминание образов через ассоциаций между ними весьма характерно

для памяти человека. Вспоминание (воспроизведение) нужной информации

может происходить путем построения цепочки ассоциаций. Так, например, на-

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

что оставили дома чайник на включенной плите.

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

(слой A и слой B). Связи между слоями устроены таким образом, что каждый

нейрон одного слоя связан с каждым нейроном другого слоя. Внутри слоев свя-

Трудности при построении теоретического обоснования увеличесния об’ема памяти связаны, по-видимому, с

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

щие состояния.

зи между нейронами отсутствуют, число нейронов на каждом слое может быть

различным. Для запоминания предназначаются пары образов (ξ

,ξ

)

(

)

, α=1..p.

Обучение задается правилом Хебба:

(

((

( )

))

) (

((

( )

))

)

ij j





































∑

∑∑

∑

ξξ

ξ ξ

ξξ

αα

α α

αα

( ) ( )

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

b f W a

a f W b

i ji j

j ji i















































































































∑

∑∑

∑

∑∑

∑

Здесь {a

}, j=1..N

- состояния активности нейронов слоя A, {b

}, i=1..N

слоя B. В качестве нейронной функции f может использоваться пороговая

функция или сигмоид. В частном случае одинаковых слоев и одинаковых обра-

зов в обучающих парах сеть Коско полностью эквивалентна модели Хопфилда.

В процессе итерационной динамики состояния нейронов слоя A вызыва-

ют изменения состояний нейронов слоя B, те, в свою очередь, модифицируют

состояния нейронов A, и так далее. Итерации, также как и в сети Хопфилда,

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

ко образа на слое A будет восстановлен также и соотвествующий образ на слое

B, и наоборот.

Сеть Коско обладает также и свойством автоассоциативности: если одно-

временно известны некоторые фрагменты образов на слое A и B, то в процессе

динамики будут одновременно восстановлены оба образа пары.

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

На предыдущей лекции была рассмотрена классическая модель Хопфил-

да с двоичными нейронами. Изменение состояний нейронов во времени описы-

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

однозначно определяли степень возбуждения всех нейронов сети.

Эволюция в пространстве состояний сети Хопфилда завершается в ста-

ционарной точке - локальном минимуме энергии. В этом состоянии любые из-

менения активности любого нейрона запрещены, так как они приводят к увели-

чению энергии сети. Если продолжать проводить аналогию между классиче-

ской нейродинамикой и статистическими (динамическими) системами в физи-

ке, то можно ввести понятие температуры статистичекого ансамбля нейронов.

Поведение сети Хопфилда соответствует нулевой температуре (полному замер-

занию) статсистемы. При строго нулевой температуре (T=0) статистический

Больцмановский фактор ∼exp(-∆E/T) делает невозможным увеличение энер-

гии.

Переход к ненулевым температурам (T>0) значительно обогащает дина-

мику системы, которая теперь может с ненулевой вероятностью делать перехо-

ды с возрастанием E и посещать новые статистические состояния.

Вернемся к нейронным сетям. Для некоторого нейрона возможность пе-

рехода в состояние с большей энергией означает отказ от следования детерми-

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

стояние нейрона определяется вероятностным образом:

(t+1) = sign( h

(t)-Θ ), с вероятностью P

(t+1) = - sign( h

(t)-Θ ), с вероятностью (1-P

)

Вероятность перехода в состояние с возрастанием энергии тем меньше,

чем больше разница в энергиях конечного E

и начального E

состояний. В ста-

тистических системах эта вероятность определяется формулой Больцмана:

(

((

( )

))

)

(

((

( )

))

)

E E

+ −

−−

−

−−

−

2 1

exp

Нетрудно заметить, что в пределе низких температур (T→0) вероятность

P стремится к единице, и динамика переходит в обычную детерминированную

нейродинамику.

При высоких температурах (T >> ∆E) вероятность P=1/2, т.е. изменение

состояния нейрона никак не связано ни с его предыдущим состоянием, ни со

значением “нейронного поля” h(t). Состояния сети меняются полностью хао-

тично, и ситуация ничем не напоминает систему с памятью.

Динамика нейронной системы при ненулевых температурах уже не явля-

ется Ляпуновской, так как энергия сети не обязана теперь уменьшаться со вре-

менем. При этом, вообще говоря, полной стабилизации состояния сети не про-

исходит - состояние быдет продолжать испытывать изменения, при которых ∆E

∝ T.

Если теперь постепенно уменьшать температуру сети, большое увеличе-

ние энергии становится все менее вероятным, и система замерзает в окрестно-

сти минимума. Очень важно отметить, что замерзание с большой вероятностью

будет происходить в чаше самого глубокого и широкого минимума, т.е. сеть

преимущественно достигает глобального минимума энергии.

Процесс медленного остывания и локализации состояния в области низ-

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

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

Введение отличной от нуля температуры в динамику нейросети улучшает

свойства памяти, так как система перестает “чувствовать” мелкие локальные

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

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

билизации системы в точке минимума.

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

Ассоциативность памяти нейронной сети Хопфилда не является единст-

венным ее достоинством, которое используется на практике. Другим важным

свойством этой архитектуры является уменьшение ее функции Ляпунова в про-

цессе нейродинамики. Следовательно, нейросеть Хопфилда можно рассматри-

вать, как алгоритм оптимизации целевой функции в форме энергии сети.

Класс целевых функций, которые могут быть минимизированы нейрон-

ной сетью достаточно широк: в него попадают все билинейные и квадратичные

формы с симметричными матрицами. С другой стороны, весьма широкий круг

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

Сюда относятся такие традиционные задачи, как дифференциальные уравнения

в вариационной постановке; задачи линейной алгебры и системы нелинейных

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

и другие.

Исследования возможности использования нейронных сетей для решения

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

матику.

Применение нейронных сетей для решения традиционных математиче-

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

системами с предельно высоким уровнем параллельности при обработке ин-

формации. В нашей книге мы рассмотрим использование нейро-оптимизаторов

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

Многие задачи оптимального размещения и планирования ресурсов, вы-

бора маршрутов, задачи САПР и иные, при внешней кажущейся простоте по-

становки имеют решения, которые можно получить только полным перебором

вариантов. Часто число вариантов быстро возрастает с числом структурных

элементов N в задаче (например, как N! - факториал N), и поиск точного реше-

ния для практически полезных значений N становится заведомо неприемлимо

дорогим. Такие задачи называют неполиномиально сложными или NP-

полными

. Если удается сформулировать такую задачу в терминах оптимиза-

ции функции Ляпунова, то нейронная сеть дает весьма мощный инструмент по-

иска приближенного решения.

Рассмотрим классический пример NP-полной проблемы - так называемую

задачу комивояжера (бродячего торговца). На плоскости расположены N горо-

дов, определяемые парами их географических координат: (x

), i=1..N. Некто

должен, начиная с произвольного города, посетить все эти города, при этом в

Более точно, NP-полной называется задача, вычислительные алгоритмы для решения которой требуют за-

трат, возрастающих быстрее, чем любая степень числа переменных или элементов N.

каждом побывать ровно один раз. Проблема заключается в выборе маршрута

путешествия с минимально возможной общей длиной пути.

Полное число возможных маршрутов равно

, и задача поиска крат-

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

ное решение может быть найдено с помощью нейронной сети, для чего, как уже

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

функции Ляпунова (J.J.Hopfield, D.W.Tank, 1985).

Обозначим названия городов заглавными буквами (A, B, C, D...). Произ-

вольный маршрут может быть представлен в виде таблицы, в которой единица

в строке, отвечающей данному городу, определяет его номер в маршруте.

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

Номер

ород

.. .. ..

Сопоставим теперь клетке таблицы на пересечении строки X и столбца i

нейрон S

∈{0,1}. Возбужденное состояние данного нейрона сигнализирует о

том, что город X в маршруте следует посещать в i-тую очередь. Составим те-

перь целевую функцию E(S) задачи поиска оптимального маршрута. Она будет

включать 4 слагаемых:

E S E E E E( ) =

= +

+ +

1 2 3 4

Первые три слагаемых отвечают за допустимость маршрута: каждый го-

род должен быть посещен не более чем один раз (в каждой строке матрицы

имеется не более одной единицы), под каждым номером должено посещаться

не более одного города (в каждом столбце - не более одной единицы) и, кроме

того, общее число посещений равно числу городов N (в матрице всего имеется

ровно N единиц):

E S S

E S N

Xi Xj

j iiX

Xii Yi

Y XXi

= −

−−

−



















































































≠

≠≠

≠

≠≠

≠

∑

∑∑

∑

∑∑

∑

∑∑

∑

αα

ββ

γγ

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

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

следнее, четвертое слагаемое минимизирует длину маршрута:

(

((

( )

))

)

E d S S S

XY Xi Yi Yi

iY XX

4 1 1

= +

+ −

−−

−

≠

≠≠

≠

∑

∑∑

∑

ηη

Здесь за d

обозначено расстояние между городами X и Y. Заметим, что

отрезок пути X-Y включается в сумму только тогда, когда город Y является от-

носительно города X либо предыдущим, либо последующим. Множители α, β,

γ и η имеют смысл относительных весов слагаемых.

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

предыдущую лекцию):

E W S S S

XiYj

Xi Yj

iYX

= −

−−

− +

∑

∑∑

∑ ∑

∑∑

∑

ΘΘ

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

форме функции Ляпунова, если выбрать значения весов и порогов сети в сле-

дующем виде:

(

((

(

)

))

)

(

((

( )

))

)

(

((

( )

))

)

XiYj XY ij

ij XY

XY ji ji

= −

−−

− ⋅

⋅⋅

⋅ ⋅

⋅⋅

⋅ −

−−

− −

−−

−

−−

− ⋅

⋅⋅

⋅ ⋅

⋅⋅

⋅ −

−−

− −

−−

−

−−

− −

−−

−

−−

− ⋅

⋅⋅

⋅ ⋅

⋅⋅

⋅ +

+ −

−−

−

αα

α δ

δδ

δ δ

δδ

ββ

β δ

δδ

δ δ

δδ

γγ

ηη

η δ

δδ

δ δ

δδ

1 1

ΘΘ

= −

−−

−

γγ

Теперь можно заменить обучение Хебба прямым заданием указанных ве-

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

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

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

интерес представляет глобальный минимум энергии.

Хопфилдом и Тэнком изложенная модель была опробована в вычисли-

тельном эксперименте. Нейронной сети удавалось находить близкие к опти-

мальным решения за приемлимые времена даже для задач с несколькими де-

сятками городов. В дальнешем последовало множество публикаций о разнооб-

100

разных применениях нейросетевых оптимизаторов. В завершении лекции рас-

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

Пусть имеется некоторое (достаточно длинное) текстовое сообщение, на-

писанное на некотором языке с использованием алфавита A, B, C ... z и символа

“пробел”, отвечающего за промежуток между словами. Данное сообщение за-

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

некоторый символ из ряда i,j,k, .... Требуется расшифровать сообщение.

Данная задача также относится к числу NP-полных, общее число ключей

шифра имеет факториальную зависимость от числа символов в алфавите. При-

ближенное нейросетевое решение может быть основано на том факте, что час-

тоты появления отдельных символов и конкретных пар символов в каждом

языке имеют вполне определенные значения (например, в русском языке часто-

та появления буквы “а” заметно превосходит частоту появления буквы “у”, слог

“во” появляется довольно часто, а, например, сочетание “йщ” вовсе не возмож-

но).

Частоты появления символов P

и их пар P

в закодированном сообщении

можно вычислить непосредственно. Имея, далее, в распоряжении значения P

частот появления символов языка и их пар P

, следует отождествить их с вы-

численными значениями для кода. Наилучшее совпадение и даст требуемый

ключ

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

гаемых послностью совпадают с тремя первыми членами в выражении для

энергии в задаче о комивояжере. Они определяют допустимость ключа (каждо-

му символу языка соотвествует один символ кода). Остальные слагаемые отве-

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

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

(

((

( )

))

)

(

((

( )

))

)

E S E E E

P P S S

P P S

AB ij Ai Bj

AB ij

A i Ai

( )

= +

+ +

+ −

−−

− +

+ −

−−

−

∑

∑∑

∑

∑∑

∑

1 2 3

χχ

εε

Целевая функция также, как и для задачи комивояжера, приводится к ви-

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

шифровку.

Задачи

Необходимо отметить, что для надежной расшифровки длина закодированного сообщения должна быть дос-

таточно большой. В противном случае расчетные частоты появления символов и пар могут значительно отли-

чаться от средних для данного языка значений.