Answers.Body: <p>See the paper <a href="http://www.paradise.caltech.edu/CNS188/bruck90-conv.pdf" rel="noreferrer">On the Convergence Properties of the Hopfield Model</a> (1990), by Jehoshua Bruck.</p>
  
  <p>In the first section of the paper, J. Bruck describes the Hopfield network (popularized by J. J. Hopfield in 1982 in his paper <a href="https://www.its.caltech.edu/~bi250c/papers/Hopfield-1982.pdf" rel="noreferrer">Neural networks and physical systems with emergent collective computational abilities</a>, hence the name of the network), then he describes the notation that is used throughout the paper and he gives some examples where a simple Hopfield network (with two nodes) converges to stable states (of the network) and cycles (of which the author also gives a definition).</p>
  
  <p>The usual proofs of the convergence properties of Hopfield networks involve the concept of an <strong>energy function</strong>, but, in this paper, J. Bruck uses an approach (based on an equivalent formulation of the Hopfield network as an undirected graph) that does not involve an energy function, and he unifies three apparently different convergence properties related to Hopfield networks (described in part <span class="math-container">$C$</span> of the section <em>Introduction</em>). More specifically, finding the global maximum of the energy function associated with the Hopfield network operating in a serial mode (which is defined in part <span class="math-container">$A$</span> of the <em>Introduction</em> section of the paper) is equivalent to find a <a href="https://en.wikipedia.org/wiki/Minimum_cut" rel="noreferrer">minimum cut</a> in the undirected graph associated with this Hopfield network. </p>
  
  <p>Furthermore, note that the proofs of convergence of the Hopfield networks actually depend on the structure of the network (more specifically, its weight matrix). For example, if the weight matrix <span class="math-container">$W \in \mathbb{R}^{n \times n}$</span> (where <span class="math-container">$n$</span> is the number of nodes in the network) associated with the Hopfield network is a symmetric matrix with the elements of the diagonal being non-negative, then the network will always converge to a stable state.</p>
  
  <p>See also the chapter <a href="https://page.mi.fu-berlin.de/rojas/neural/chapter/K13.pdf" rel="noreferrer">13 The Hopfield Model</a> of the book <a href="https://page.mi.fu-berlin.de/rojas/neural/" rel="noreferrer">Neural Networks - A Systematic Introduction</a> (1996) by Raul Rojas.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T21:51:47.427Z
Answers.Text: Thank you for your answer. Sorry I if was not clear but I intend my question the way I asked it. I understand why Hopfield net  (the proof) converge to a local minima, a stable state etc... Precisely I already read the resources that you mentionned and they only deal with that issue (I found Rojas book very useful thou!)
Answers.UserDisplayName: lolodino77
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T21:53:38.780Z
Answers.Text: @ladangvu Ok, so what's your question? What do you want more than this? The resources I provided are already quite rigorous, so I really don't get your question.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T21:55:09.740Z
Answers.Text: What I am looking for is a demonstration for finding all these stable states. Of course everybody states that they are the patterns learned, their opposite (negative counterpart) and spurious states. But nowhere did I find proof that the patterns learned are local minima of the energy function.
Answers.UserDisplayName: lolodino77
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T21:58:36.700Z
Answers.Text: @ladangvu What do you mean by "demonstration for finding all these stable states"? Have you read the mentioned paper "On the Convergence Properties of the Hopfield Model"? Even in the initial examples, the author gives examples of states that are the local minimum of the energy function (that is, where the Hopfield network reaches a stable state)? Also, have you read the part of my answer where I say "_note that the proofs of convergence of the Hopfield networks actually depend on the structure of the network_".
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T22:14:34.827Z
Answers.Text: A mathematical demonstration (as we regularly do in multivariable functions optimization) for determining the local minimizer and minimum of the energy function E. A demonstration like any function that we would like to minimize, for example from my course : f(x,y) = x^3+y^3-3cxy where c belongs to IR*. After calculate the partial derivatives, finding the critical points and and calculate the determinant of the hessian at these points, we found that :
  (0,0) is a saddle point and (c,c) a local maximizer if c < 0 or a local minimizer if c > 0.
Answers.UserDisplayName: lolodino77
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T22:18:27.743Z
Answers.Text: Yes I read it, I understood these examples. Yes I read it, as I am dealing with Hopfield networks, I assume that W is symetric and with a diagonal full of zero (this is part of the definition of a Hopfield network, the weights w_ij = 0 when i = j.
Answers.UserDisplayName: lolodino77
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T22:44:18.273Z
Answers.Text: $W$ does _not necessarily_ have to be symmetric or the diagonal elements do _not necessarily_ have to be zero (See part $B$ of the Introduction section). However, some proofs assume that e.g. the elements of the diagonal are non-negative (but it doesn't mean that they can't be positive) and the matrix is symmetric (see appendix 5 of the paper).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-25T17:48:10.783Z
Answers.Text: This is a good job @nbro
Answers.UserDisplayName: Nicola Bernini
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T19:35:22.157Z
Answers.LastActivityDate: 2019-07-22T19:52:49.197Z
Answers.LastEditDate: 2019-07-22T19:52:49.197Z
Answers.UserDisplayName: nbro
Body: <p>I am looking for a rigorous mathematical proof for finding the several local minima of the Hopfield networks. I am searching for something rigorous, a demonstration, not just letting the network keep updating its neurons and wait for noticing a stable state of the network.</p>
  <p>I have looked virtually everywhere, but I found nothing.</p>
  <p>Is there a rigorous proof for Hopfield minima? Could you give me ideas or references?</p>
  
Tags: <reference-request><recurrent-neural-networks><proofs><convergence><hopfield-network>
Title: Is there a rigorous proof for finding Hopfield minima?
UserDisplayName: lolodino77
ThreadText: # Is there a rigorous proof for finding Hopfield minima?
  
  (Asked by: username_0 on 2019-07-22)
  
  I am looking for a rigorous mathematical proof for finding the several local minima of the Hopfield networks. I am searching for something rigorous, a demonstration, not just letting the network keep updating its neurons and wait for noticing a stable state of the network.
  
  I have looked virtually everywhere, but I found nothing.
  
  Is there a rigorous proof for Hopfield minima? Could you give me ideas or references?
  
  **Tags:** reference-request, recurrent-neural-networks, proofs, convergence, hopfield-network
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-07-22. Score: 6
  
  See the paper [On the Convergence Properties of the Hopfield Model](http://www.paradise.caltech.edu/CNS188/bruck90-conv.pdf) (1990), by Jehoshua Bruck.
  
  In the first section of the paper, J. Bruck describes the Hopfield network (popularized by J. J. Hopfield in 1982 in his paper [Neural networks and physical systems with emergent collective computational abilities](https://www.its.caltech.edu/~bi250c/papers/Hopfield-1982.pdf), hence the name of the network), then he describes the notation that is used throughout the paper and he gives some examples where a simple Hopfield network (with two nodes) converges to stable states (of the network) and cycles (of which the author also gives a definition).
  
  The usual proofs of the convergence properties of Hopfield networks involve the concept of an **energy function**, but, in this paper, J. Bruck uses an approach (based on an equivalent formulation of the Hopfield network as an undirected graph) that does not involve an energy function, and he unifies three apparently different convergence properties related to Hopfield networks (described in part $C$ of the section *Introduction*). More specifically, finding the global maximum of the energy function associated with the Hopfield network operating in a serial mode (which is defined in part $A$ of the *Introduction* section of the paper) is equivalent to find a [minimum cut](https://en.wikipedia.org/wiki/Minimum_cut) in the undirected graph associated with this Hopfield network.
  
  Furthermore, note that the proofs of convergence of the Hopfield networks actually depend on the structure of the network (more specifically, its weight matrix). For example, if the weight matrix $W \in \mathbb{R}^{n \times n}$ (where $n$ is the number of nodes in the network) associated with the Hopfield network is a symmetric matrix with the elements of the diagonal being non-negative, then the network will always converge to a stable state.
  
  See also the chapter [13 The Hopfield Model](https://page.mi.fu-berlin.de/rojas/neural/chapter/K13.pdf) of the book [Neural Networks - A Systematic Introduction](https://page.mi.fu-berlin.de/rojas/neural/) (1996) by Raul Rojas.
  
  > **Comments:**
  > **username_0**: Thank you for your answer. Sorry I if was not clear but I intend my question the way I asked it. I understand why Hopfield net  (the proof) converge to a local minima, a stable state etc... Precisely I already read the resources that you mentionned and they only deal with that issue (I found Rojas book very useful thou!)  
  > **username_1**: @ladangvu Ok, so what's your question? What do you want more than this? The resources I provided are already quite rigorous, so I really don't get your question.  
  > **username_0**: What I am looking for is a demonstration for finding all these stable states. Of course everybody states that they are the patterns learned, their opposite (negative counterpart) and spurious states. But nowhere did I find proof that the patterns learned are local minima of the energy function.  
  > **username_1**: @ladangvu What do you mean by "demonstration for finding all these stable states"? Have you read the mentioned paper "On the Convergence Properties of the Hopfield Model"? Even in the initial examples, the author gives examples of states that are the local minimum of the energy function (that is, where the Hopfield network reaches a stable state)? Also, have you read the part of my answer where I say "_note that the proofs of convergence of the Hopfield networks actually depend on the structure of the network_".  
  > **username_0**: A mathematical demonstration (as we regularly do in multivariable functions optimization) for determining the local minimizer and minimum of the energy function E. A demonstration like any function that we would like to minimize, for example from my course : f(x,y) = x^3+y^3-3cxy where c belongs to IR*. After calculate the partial derivatives, finding the critical points and and calculate the determinant of the hessian at these points, we found that : (0,0) is a saddle point and (c,c) a local maximizer if c < 0 or a local minimizer if c > 0.  
  > **username_0**: Yes I read it, I understood these examples. Yes I read it, as I am dealing with Hopfield networks, I assume that W is symetric and with a diagonal full of zero (this is part of the definition of a Hopfield network, the weights w_ij = 0 when i = j.  
  > **username_1**: $W$ does _not necessarily_ have to be symmetric or the diagonal elements do _not necessarily_ have to be zero (See part $B$ of the Introduction section). However, some proofs assume that e.g. the elements of the diagonal are non-negative (but it doesn't mean that they can't be positive) and the matrix is symmetric (see appendix 5 of the paper).  
  > **username_2**: This is a good job @username_1  
  
  ---
  
  