patternMinor
Derivation of the energy function of a hopfield network
Viewed 0 times
theenergyfunctionnetworkhopfieldderivation
Problem
Can someone please point me towards a rigorous derivation of the energy function of a discrete Hopfield network. What I want, is the derivation must start out with the structure of the network and prove that the critical points of the dynamical system can be obtained by minimization of some function (possibly by constructing the Lyapunov function of the dynamical system). I cannot seem to find such a rigorous proof. Thankyou!
Solution
I believe what you want to show is that the energy function is monotonically decreasing from time $t$ to time $t+1$ given the state update rules. Since there is only a finite number of states, this means the state must converge to a equilibrium under the given dynamics.
To this end let $\mathbf{s}(t) \in \{0,1\}^n$ be the state of the network at time $t$. We update the network state by picking a unit $s_i(t)$ and updating the state according to
$$
s_i(t+1) = \left\{\begin{array}{r l} 1:& \sum_{j} w_{ij} s_j(t) > 0\\ 0:& \text{otherwise}\end{array}\right.
$$
and define the energy function as
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_i\sum_jw_{ij}s_i(t)s_j(t),
$$
where $w_{ij}$ is the weight between unit $i$ and $j$, $w_{ij} = w_{ji}$ and $w_{ii} = 0$ for al $i$.
WLOG assume we will update the $i^{th}$ unit. First, because of the restrictions on the weights, we may rewrite $E(\mathbf{s}(t))$ as the difference of 2 terms
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t) - s_i(t)\sum_jw_{ij}s_j.
$$
Let $c_t = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t)$ be the part of the energy function that does not depend on $s_i(t)$. Now if $s_i(t+1) = s_i(t)$ then clearly we have $E(\mathbf{s}(t+1)) = E(\mathbf{s}(t))$, so we only need to consider the 2 other cases.
Case 1: If $s_i(t+1) = 1$ and $s_i(t) = 0$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t > 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} - \Delta_t = c_t - \Delta_t < c_t = E(\mathbf{s}(t)).
$$
Case 2: If $s_i(t+1) = 0$ and $s_i(t) = 1$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t \le 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} = c_t \le c_t - \Delta_t = E(\mathbf{s}(t)).
$$
Having considered each case we can conclude that $E(\mathbf{s}(t+1)) \le E(\mathbf{s}(t))$ and is therefore monotonically decreasing.
To this end let $\mathbf{s}(t) \in \{0,1\}^n$ be the state of the network at time $t$. We update the network state by picking a unit $s_i(t)$ and updating the state according to
$$
s_i(t+1) = \left\{\begin{array}{r l} 1:& \sum_{j} w_{ij} s_j(t) > 0\\ 0:& \text{otherwise}\end{array}\right.
$$
and define the energy function as
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_i\sum_jw_{ij}s_i(t)s_j(t),
$$
where $w_{ij}$ is the weight between unit $i$ and $j$, $w_{ij} = w_{ji}$ and $w_{ii} = 0$ for al $i$.
WLOG assume we will update the $i^{th}$ unit. First, because of the restrictions on the weights, we may rewrite $E(\mathbf{s}(t))$ as the difference of 2 terms
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t) - s_i(t)\sum_jw_{ij}s_j.
$$
Let $c_t = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t)$ be the part of the energy function that does not depend on $s_i(t)$. Now if $s_i(t+1) = s_i(t)$ then clearly we have $E(\mathbf{s}(t+1)) = E(\mathbf{s}(t))$, so we only need to consider the 2 other cases.
Case 1: If $s_i(t+1) = 1$ and $s_i(t) = 0$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t > 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} - \Delta_t = c_t - \Delta_t < c_t = E(\mathbf{s}(t)).
$$
Case 2: If $s_i(t+1) = 0$ and $s_i(t) = 1$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t \le 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} = c_t \le c_t - \Delta_t = E(\mathbf{s}(t)).
$$
Having considered each case we can conclude that $E(\mathbf{s}(t+1)) \le E(\mathbf{s}(t))$ and is therefore monotonically decreasing.
Context
StackExchange Computer Science Q#13132, answer score: 6
Revisions (0)
No revisions yet.