Hopfield Network

Discrete Hopfield Nerual Network (DHNN)

一般来说每个节点状态为

也有的网络节点状态是

其状态取值取决于节点的阈值

一个存储在网络中的初始状态为 , 表示第 个节点的状态

同时对于 , 存储在网络中的边权 (相互作用) 为

当 , 存储的边权为

当 , 存储的边权为

也就是 , 如果两个节点状态相同则为 , 相反为

并且

当网络训练好, 就不再改变

此时对于一个任意初始化的状态 , 那么运行网络来更改这些 :

也即:

图来自 wikipedia [5]

上图是一个存储了字母 的网络上运行 收敛到 的过程

对于 hopfield network 的收敛性质与证明, 见 [6]

同时定义一个势能函数

那么最后 一定会收敛到 的一个局部极小值点

Continuous Hopfield Nerual Network (CHNN)

在 DHNN 能量函数基础上加了一项非线性函数:

对于为什么加这一项, 实际原文是构造了一个 模拟电路, 并且使用了一个非线性映射 , 一般为 sigmoidal 函数

这样的电路对时间连续

这样可以得出能量对时间求导:

可以证明 $$ –>

具体见 [8]

TSP

问题解分析

一共有 种排列, 但是由于一个解是有向环, 所以有 种起始位置选法和 种方向

所以一共有 种可能的解

转换为 HN

对于一个优化问题, 如果将目标函数转换为 HN 的能量函数, 那么就可以让 HN 来求解这个优化问题

最经典的是使用 HN 解决 TSP 问题

具体地, 对于 个节点的 TSP 问题, 需要 个神经元, 排成一个方阵

其中 表示第 个城市在第 位被访问

这样的方阵代表一组解, 例如

表示

并且要求每一行, 每一列都恰好有一个 , 其余为

这张图 (来自 [7]) 展示了 个城市的 TSP 问题在 HN 中收敛的过程

能量函数

首先定义一个约束能量函数:

其中 为充分大的常数

第一项可以为 当且仅当每一行不多于一个

第二项可以为 当且仅当每一列不多于一个

第三项可以为 当且仅当一共有 个

所以满足这样约束的状态能量是最低的

之后加入距离能量函数:

其中 是模 后的

之后定义边权值

前三项是约束, 避免同一行, 同一列连接

最后一项是数据项

同时有偏置量

Hebbian learning rule

给出 个二进制模板 , 表示我们要学习的初始状态

那么边权值更新为

其中 是来自模板 的第 位

例如我们可以给出 张图片, 让 HN 学习

注意, 学习后的网络可能不会收敛到这 张图片的任意一张, 而是收敛到另一个能量极小值点

特别地, 对于每个存储的模板 , 它的逆 也是一个能量最小值点

例如, 上面字母 的反图也是能量最小值点

对于满足 的模板 ,

Ising Model

一个自旋系统有许多每个旋转点 , 两两之间有相互作用

所以可以看成一个图

能量公式为

其中 是相互作用, 是外部磁场强度

是 Hamiltonian function

也可以写成

即第一项任意两对 只统计一次

Ferromagnetic

如果 , 称这个相互作用为铁磁相互作用

如果 , 称这个相互作用为反铁磁相互作用

Max Cut

如果外部磁场强度为 , 那么能量公式变成

假设 将整个图的点集 分成了

所以

第一项是常数

取 , 那么最小化 相当于最大化

即转化成了 Max Cut Problem

Transformer

---

参考:

1. HOPFIELD NETWORKS IS ALL YOU NEED

2. Transformers Are Secretly Collectives of Spin Systems

3. Neural networks and physical systems with emergent collective computational abilities

4. An Energy-Based Perspective on Attention Mechanisms in Transformers

5. wikipedia

6. On the Convergence Properties of the
   Hopfield Model

7. “Neural” Computation of Decisions in Optimization Problems