Нейронная сеть Хопфилда

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

Архитектура сети

Схема сети Хопфилда с тремя нейронами

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

$y_i = \left\{\begin{matrix} 1, \\ -1\end{matrix}\right.$

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

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

$E= \frac{1}{2}\sum_{i,j=1}^{N}w_{ij}x_ix_j$

где $w_{ij}$ — элемент матрицы взаимодействий $W$, которая состоит из весовых коэффициентов связей между нейронами. В эту матрицу в процессе обучения записывается М «образов» — N-мерных бинарных векторов: $S_m=(s_{m1}, s_{m2}, ..., s_{mN})$

В сети Хопфилда матрица связей является симметричной ($w_{ij}=w_{ji}$), а диагональные элементы матрицы полагаются равными нулю ($w_{ii}=0$), что исключает эффект воздействия нейрона на самого себя и является необходимым для сети Хопфилда, но не достаточным условием, устойчивости в процессе работы сети. Достаточным является асинхронный режим работы сети. Подобные свойства определяют тесную связь с реальными физическими веществами, называемыми спиновыми стёклами.

Обучение сети

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

$X_i=WX_i$

поскольку именно при этом условии состояния сети $X_i$ будут устойчивы — попав в такое состояние, сеть в нём и останется.

Некоторые авторы относят сеть Хопфилда к обучению без учителя. Но это неверно, так как обучение без учителя предполагает отсутствие информации о том, к каким классам нужно относить стимулы. Для сети Хопфилда без этой информации нельзя настроить весовые коэффициенты, поэтому здесь можно говорить лишь о том, что такую сеть можно отнести к классу оптимизирующих сетей (фильтров). Отличительной особенностью фильтров является то, что матрица весовых коэффициентов настраивается детерминированным алгоритмом раз и навсегда, и затем весовые коэффициенты больше не изменяются. Это может быть удобно для физического воплощения такого устройства, так как на схемотехническом уровне реализовать устройство с переменными весовыми коэффициентами на порядок сложнее. Примером фильтра без обратных связей может служить алгоритм CC4 (Cornel classification), автором которого является S.Kak.

В сети Хопфилда есть обратные связи и поэтому нужно решать проблему устойчивости. Веса между нейронами в сети Хопфилда могут рассматриваться в виде матрицы взаимодействий $W$. В работе Cohen, Grossberg^[1] показано, что сеть с обратными связями является устойчивой, если её матрица симметрична и имеет нули на главной диагонали. Имеется много устойчивых систем, например, все сети прямого распространения, а также современные рекуррентные сети Джордана и Элмана, для которых не обязательно выполнять условие на симметрию. Но это происходит вследствие того, что на обратные связи наложены другие ограничения. В случае сети Хопфилда условие симметричности является необходимым, но не достаточным, в том смысле, что на достижение устойчивого состояния влияет ещё и режим работы сети. Ниже будет показано, что только асинхронный режим работы сети гарантирует достижение устойчивого состояния сети, в синхронном случае возможно бесконечное переключение между двумя разными состояниями (такая ситуация называется динамическим аттрактором, в то время как устойчивое состояние принято называть статическим аттрактором).

Запоминаемые векторы должны иметь бинарный вид. После этого происходит расчёт весовых коэффициентов по следующей формуле:

$w_{ij}=\frac{1}{N}\sum_{d=1..m}X_{id}X_{jd}$

где $N$ — размерность векторов, $m$ — число запоминаемых выходных векторов, $d$ — номер запоминаемого выходного вектора, $X_{ij}$ — i-я компонента запоминаемого выходного j-го вектора.

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

$W=\frac{1}{N}\sum_{i}X_{i}X_{i}^{T}$

где $X_i$ — i-й запоминаемый вектор-строка.

Расчёт этих весовых коэффициентов и называется обучением сети.

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

$X_{i+1}=F(WX_i)$

где $F$ — активационная функция, $X_i$ и $X_{i+1}$ — текущее и следующее состояния сети, до тех пор, пока состояния $X_i$ и $X_{i+1}$ не совпадут (или, в случае синхронного режима работы, не совпадут состояния $X_{i-1}$ с $X_{i+1}$ и одновременно $X_{i-2}$ с $X_i$). Именно этот процесс называется конвергенцией сети. Полученное устойчивое состояние $X_i$ (статический аттрактор), или, возможно, в синхронном случае пара {$X_i, X_{i+1}$} (динамический аттрактор), является ответом сети на данный входной образ.

Работа сети в режиме фильтрации (восстановление повреждённых образов)

Пороговая функция, реализуемая нейроном сети Хопфилда.

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

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

$~X(t+1)=F(WX(t))$

где F — активационная функция, $X(t)$ и $X(t+1)$ — текущее и следующее состояния сети, до тех пор, пока состояния $X(t)$ и $X(t+1)$ не совпадут (или, в случае синхронного режима работы, не совпадут состояния $X(t-1)$ с $X(t+1)$ и одновременно $X(t-2)$ с $X(t)$). Именно этот процесс называется конвергенцией сети.

Это же можно описать так называемым локальным полем $a_{i}$ действующим на нейрон $x_{i}$ со стороны всех остальных нейронов сети: $a_{i}(t)=\sum_{j=1,j\neq \;i}^{N}w_{ji}x_j(t-1)$.

После расчёта локального поля нейрона $a_{i} (t)$ это значение используется для расчёта значения выхода через функцию активации, которая в данном случае является пороговой (с нулевым порогом). Соответственно, значение выхода нейрона і в текущий момент времени $x_i(t)$ рассчитывается по формуле: $x_i(t) = sign\left(\sum_{j=1, j\neq \;i}^{N} w_{ji} x_j(t-1)\right)$, где $w_{ij}$ — весовой коэффициент между нейронами i и j, $x_j(t-1)$ — значения выходов нейрона j в предыдущий момент времени.

Во время работы сети Хопфилда признаком нахождения решения является момент, когда достигается аттрактор, статический (когда на каждом следующем шаге повторяется устойчивое состояние $X(t)$) или, возможно, динамический (когда до бесконечности чередуются два разных состояния {$X(t), X(t+1)$}). Это конечное состояние сети и является её реакцией на данный образ.

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

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

Синхронный режим работы сети

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

При реально параллельном моделировании, этот режим фактически означает, что время передачи $\tau_{ij}$ для каждой связи между элементами $u_i$ и $u_j$ одинаково для каждой связи, что приводит к параллельной работе всех связей, они одновременно меняют свои состояния, основываясь только на предыдущем моменте времени. Наличие таких синхронных тактов, которые можно легко выделить и приводит к пониманию синхронного режима. При синхронном режиме возможно (хотя и далеко не всегда наблюдается) бесконечное чередование двух состояний с разной энергией — так называемый динамический аттрактор. Поэтому синхронный режим практически для сети Хопфилда не используется, и рассматривается лишь как основа для понимания более сложного асинхронного режима.

Асинхронный режим работы сети

Если моделировать работу сети как последовательный алгоритм, то в асинхронном режиме работы состояния нейронов в следующий момент времени меняются последовательно: вычисляется локальное поле для первого нейрона в момент $t$, определяется его реакция, и нейрон устанавливается в новое состояние (которое соответствует его выходу в момент $t + 1$), потом вычисляется локальное поле для второго нейрона с учётом нового состояния первого, меняется состояние второго нейрона, и так далее — состояние каждого следующего нейрона вычисляется с учетом всех изменений состояний рассмотренных ранее нейронов.

По сути при последовательной реализации сети Хопфилда явно не видно, в чём заключается асинхронность, но это видно, если сеть Хопфилда реализовать с параллельными вычислениями. В этом случае асинхронный режим сети Хопфилда упрощен, и носит частный случай по сравнению с общим видом асинхронных сетей, где время передачи $\tau_{ij}$ для каждой связи между элементами $u_i$ и $u_j$ своё, но постоянное. Чтобы рассмотреть работу сети при параллельной реализации, необходимо ввести понятие такта — как минимальное время, за которое происходит передача сигнала по связи, то есть при $\tau_{ij} = 1$. Тогда за промежуток времени между $t$ и $t + 1$ происходит определённое количество тактов N. И именно в пределах времени из N тактов происходит асинхроность протекания сигналов и выполнения расчётов. То есть, например, когда нужно рассчитать состояние нейрона №3, необходимо рассчитать состояние нейрона №1 и состояние нейрона №2 и умножить это на соответствующие веса $w_{13}$ и $w_{23}$. Но, как оказывается, чтобы рассчитать состояние нейрона №2, нужно знать обновлённое состояние нейрона №1 и старое состояние нейрона №3, умножить их на веса $w_{12}$ и $w_{32}$. Понятно, что физически невозможно рассчитать состояние нейрона №1 и состояние нейрона №2 за одно и то же время, так как состояние нейрона №2 зависит от состояния нейрона №1. Поэтому связь между нейроном №1 и нейроном №3 имеет время передачи $\tau_{ij} = 2$, и достигает нейрона №3 за два такта. Именное такое разное время передачи $\tau_{ij}$ и позволяет говорить о сети Хопфилда как о сети с асинхронным режимом.

В асинхронном режиме невозможен динамический аттрактор: вне зависимости от количества запомненных образов и начального состояния сеть непременно придёт к устойчивому состоянию (статическому аттрактору).

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

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

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

Рисунок 1а	Рисунок 1б

Устойчивость сети в процессе работы

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

Определить, устойчиво или нет состояние нейрона, можно на основании так называемой искусственной энергии нейрона в данном поле $E_i=-s_ih_i$. Если знак выхода (+1 или −1) нейрона совпадает с направлением локального поля ($E_i<0$), то его положение энергетически устойчиво и в следующий момент времени состояние нейрона остаётся неизменным. В противном случае ($E_i>0$) положение нейрона неустойчиво и он меняет свой знак, переходя в состояние $s_i(t+1)=-s_i(t)$ с энергией $E_i(t+1) < E_i(t)$.

Устойчивость при асинхроном способе достигается потому, что выполняется условие на общую энергию сети $E(t+1) \leq E(t)$. В синхронном случае условие несколько изменяется, а именно: $E(t+1) \leq E(t-1)$. В ситуации, когда происходят бесконечные циклические переходы, энергия двух разных состояний соответственно равна $E(t)$ и $E(t+1)$. При этом состояния $t+1$ и $t-1$, а также $t$ и $t+2$ — совпадают. Если образуется такое состояние, то его называется динамическим аттрактором. Если же совпадают состояния $t$ и $t+1$, аттрактор называют статическим. В большинстве случаев динамические аттракторы являются нежелательными, так как не соответствуют какому-либо определённому ответу сети.

Ассоциативная память

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

Задачи минимизации

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

Решение задачи о коммивояжёре

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

1. Сеть должна состоять из $N=n \times n$ нейронов, которые мы будем рассматривать как квадрат из $n$ строк и $n$ столбцов.
2. Ответ сети должен содержать только один активный нейрон в каждой строке и каждом столбце.
3. Активный нейрон в первом столбце задаёт первый город маршрута, во втором столбце — второй город маршрута, и так далее.

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

• для выполнения условия 2 веса сети должны быть построены таким образом, чтобы каждый нейрон препятствовал активации других нейронов в своей строке и в своём столбце;
• для минимизации длины пути необходимо, чтобы нейрон в $i$-м столбце тем активнее препятствовал активации нейронов в $i+1$-м и $i-1$-м столбцах, чем больше расстояние между ними;
• для того, чтобы сеть Хопфилда вообще работала, необходимо, чтобы веса сети не были все отрицательными.

Всем этим условиям удовлетворяет следующая формула вычисления веса между нейроном, соответствующим городу $x$ на позиции в маршруте $i$, и нейроном, соответствующим городу $y$ на позиции $j$:

$W_{xi,yj}= -A \delta_{xy}(1-\delta_{ij}) - B \delta_{ij}(1-\delta_{xy}) - C d(x,y) (\delta_{i,j+1} + \delta_{i,j-1}) + D$

где A, B, C, D — некоторые константы, $d(x,y)$ - расстояние между городами $x$ и $y$, $\delta_{xy}$ - символ Кронекера, принимающий значение 1, если x=y и значение 0 в противном случае. Как легко видеть, первый член равен $-A$ для всех связей в той же строке ($x=y$), кроме связи нейрона с самим собой (при $i=j$). Второй член равен $-B$ для всех связей в том же столбце ($i=j$), кроме связи с самим собой ($x=y$). Третий член пропорционален расстоянию между городами $x$ и $y$, если эти города соседние в маршруте ($i=j-1$ или $i=j+1$).

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

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

Ограничения сети

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

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

$M\approx \;\frac{N}{2\log_2 N}$

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

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

См. также

В Википедии есть портал «Искусственный интеллект»

• Перцептрон
• Рекуррентные нейронные сети

Примечания

1. ↑ Cohen M. A., Grossberg S. G. 1983. Absolute stability of global pattern formation and parallel memory storage by compatitive neural networks. IEEE Transactions on Systems, Man and Cybernetics 13:815-26.
2. ↑ Lau, K.M., Chan, S.M., Xu, L. Comparison of the Hopfield scheme to the hybrid of Lagrange and transformation approaches for solving the travelling salesman problem. Proceedings of Intelligence in Neural and Biological Systems, 1995.

Литература

• J. J. Hopfield, «Neural networks and physical systems with emergent collective computational abilities», Proceedings of National Academy of Sciences, vol. 79 no. 8 pp. 2554–2558, April 1982. PNAS Reprint (Abstract) PNAS Reprint (PDF)

• J. J. Hopfield Neural with graded response have collective computational properties like those of two-state neurons.. — 1984.

• J. J. Hopfield Learning algorithms and probability distributions in feed-forward and feed-back networks. — 1987.

• Уоссермен, Ф. Нейрокомпьютерная техника: Теория и практика = Neural Computing. Theory and Practice. — М.: Мир, 1992. — 240 с. — ISBN 5-03-002115-9

• McEliece R.J., Posner E.C., Rodemich E.R., Venkatesh S.S., The capacity of the Hopfield associative memory, IEEE Transactions on Information Theory, Volume 33, Issue 4 (July 1987), 461-482.
• B.V.Kryzhanovsky, L.B.Litinskii, A.L.Mikaelian. «Vector-neuron models of associative memory», Proc. of Int. Joint Conference on Neural Networks IJCNN-04, Budapest-2004, pp.909–1004.
• B.V.Kryzhanovsky, B.M.Magomedov, A.L.Mikaelian. «A Domain model of neural network», Doklady Mathematics vol.71, pp.310–314 (2005).