%mm6/8/99 \documentclass[12pt]{article} %au queries \newcommand{\query}[1]{\marginpar{\raggedright\scriptsize #1}} %operators \def\operator#1{\mathop{\rm#1}\nolimits} %\newcommand{\min}{{\operator{min}}} %\newcommand{\max}{{\operator{max}}} \newtheorem{proposition}%[theorem] {Proposition} \newtheorem{defn}{Definition} \newcommand{\qed}{\hspace*{\fill} \vrule width.25cm height.25cm depth0cm} %.2cm.2cm0cm %\newcommand{\proof}{\noindent\bf Proof : \rm } %MM made proof style consistent \newenvironment{proof} {\begin{trivlist}\item[\hskip\labelsep{\textbf{Proof}}]} {\leavevmode\unskip\nobreak \qed %\quad\hspace*{\fill}\QED \end{trivlist}} \newlength{\captionwidth} \setlength{\captionwidth}{0.85\textwidth} \newlength{\digitwidth} %width of a digit.% \settowidth{\digitwidth}{8} \newcommand{\floor}[1]{\mbox{$\lfloor #1 \rfloor$}} \newcommand{\NEW}[1]{{\em #1}} \renewcommand{\NEW}[1]{#1} \title{\bf Hopfield Neural Networks and Self-Stabilization} \author{ Arun Jagota\\ Department of Computer Science \\ University of California, Santa Cruz\\ {\tt http://www.cse.ucsc.edu/$\tilde{~}$jagota} } \date{6 August 1999} \begin{document} \def\registered{\({}^{\ooalign% {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}% \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)} \begin{titlepage} \pagenumbering{roman} \null\vfil\vskip 60pt \begin{center} {\Huge\bf Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science\par} \vskip 3em {\huge\it The MIT Press\par} \end{center} \par\vskip 1.5em {\Large \begin{center} Volume 1999, Article 6\\ \textit{Hopfield Neural Networks and Self-Stabilization} \end{center} } \par\noindent ISSN 1073--0486\@. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; \emph{journals-orders@mit.edu, journals-info@mit.edu}\@. Published one article at a time in \LaTeX\ source form on the Internet\@. Pagination varies from copy to copy\@. For more information and other articles see: \begin{itemize} \item \emph{http://mitpress.mit.edu/CJTCS/} \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/} \item \emph{ftp://mitpress.mit.edu/pub/CJTCS} \item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs} \end{itemize} \par\noindent The \emph{Chicago Journal of Theoretical Computer Science} is abstracted or indexed in \emph{ Research Alert,\registered SciSearch, \registered Current Contents\registered/Engineering Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered} \par\noindent\copyright 1999 The Massachusetts Institute of Technology\@. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to ensure fair attribution to authors and the journal, and to prohibit use in a competing commercial product\@. See the journal's World Wide Web site for further details\@. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; \emph{journals-rights@mit.edu}\@.\pagebreak[2] \par\noindent The \emph{Chicago Journal of Theoretical Computer Science} is a peer-reviewed scholarly journal in theoretical computer science\@. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science\@. \par \begin{trivlist} \item[\emph{Editor-in-Chief:}] Janos Simon \item[\emph{Consulting Editors:}] Joseph Halpern, Eric Allender, Raimund Seidel \item[\emph{Editors:}] \begin{tabular}[t]{lll} Martin Abadi & Greg Frederickson & John Mitchell \\ Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\ Georg Gottlob & Gil Neiger & Tetsuo Asano \\ Vassos Hadzilacos & David Peleg & Laszl\'o Babai \\ Juris Hartmanis & Andrew Pitts & Eric Bach \\ Maurice Herlihy & James Royer & Stephen Brookes \\ Ted Herman & Alan Selman & Jin-Yi Cai \\ Stephen Homer & Nir Shavit & Anne Condon \\ Neil Immerman & Eva Tardos & Cynthia Dwork \\ Howard Karloff & Sam Toueg & David Eppstein \\ Philip Klein & Moshe Vardi & Ronald Fagin \\ Phokion Kolaitis & Stuart Kurtz & Jennifer Welch \\ Lance Fortnow & Stephen Mahaney & Pierre Wolper \\ Steven Fortune & Michael Merritt \end{tabular} \vspace{1ex} \item[\emph{Managing Editor:}] Michael J.\ O'Donnell \vspace{1ex} \item[\emph{Electronic Mail:}] \emph{chicago-journal@cs.uchicago.edu} \end{trivlist} \vfil\null \end{titlepage} \maketitle \pagenumbering{arabic} \begin{abstract} This paper studies Hopfield neural networks from the perspective of self-stabilizing distributed computation. Known self-stabilization results on Hopfield networks are surveyed. Key ingredients of the proofs are given. Novel applications of self-stabilization---associative memories and optimization---arising from the context of neural networks are discussed. Two new results at the intersection of Hopfield nets and of distributed systems are obtained: One involves convergence under a fine-grained implementation; the other is on perturbation analysis. Some possibilities for further research at the intersection of these two fields are discussed. \end{abstract} \section{Introduction} Study of stability issues in systems began centuries ago, and convergence properties of differential equations have long been examined. In modern times these have been expanded to include studies on other kinds of dynamical systems (difference equations, numerical algorithms, and so on). Control theory and numerical analysis are two other examples of important fields in which stability issues have been of fundamental importance since the early part of the twentieth century. Convergence is also an important issue in statistical physics, where a central question is whether a spin system will settle into a low-energy state. \NEW{In distributed computing, studies of stability issues are regarded as having begun} around 1974 when Edgar W. Dijkstra \cite{cj99-06-04} introduced the concept of self-stabilization. At an abstract level Dijkstra's concept was not much different from usual notions of convergence invented earlier in various fields. At the concrete level of the distributed computing system, however, it was a new development. First, distributed computing systems usually involve different kinds of computational primitives than those in classical fields (differential equations, dynamical systems, statistical physics). Consequently, the design and analysis of self-stabilizing algorithms for them require new techniques. Second, convergence results in classifical fields hold at a high level. In contrast, in distributed computing systems, one can address the issue of stabilization at various levels (coarse-grained to fine-grained implementation) and also for various structures (network topologies). Paying attention to the level and structure raises new and important questions. In 1982, John J. Hopfield \cite{cj99-06-12} independently studied a globally convergent neural network model that fits nicely within the framework of Dijkstra's self-stabilization. Self-stabilization results and applications of this neural network model can be easily interpreted in the context of distributed systems, thereby raising the possibility for an exchange of ideas in the two fields. This paper introduces this neural network model, surveys its results involving self-stabilization, and explains key ingredients of the proofs. Variations of the self-stabilization concept appropriate in the neural networks context are presented. These are compared in some cases to analogous variants invented in the distributed systems field. The paper is organized as follows. Section 2 presents basic definitions, including those of the self-stabilization concept and its variants. Section 3 presents a two-state version of the Hopfield network, its self-stabilization results (Sections 3.1, 3.2, and 3.3), the notion of attraction domains (Section 3.4), and new applications of self-stabilization arising from this context (Section 3.5). Section 4 presents a randomized version of the two-state Hopfield network, together with a kind of probabilistic self-stabilization result for it. Section 5 presents a continuous-state version of the Hopfield network and a form of asymptotic self-stabilization result for it. Section 6 investigates what happens to self-stabilization of the two-state network of Section 3 under a fine-grained implementation. Section 7 performs some perturbation analysis on the two-state network of Section 3. Section 8 summarizes the contributions of this paper and presents possibilities for further research at the intersection of these two fields. \section{Basic definitions} The concepts used in this paper are at the intersection of the fields of distributed computing and neural networks. A {\em distributed system} is a set of $n$ processes $V=\{1,\ldots,n\}$ interconnected pairwise by a set of edges $E$ to form an undirected graph $G=(V,E)$.\footnote{In neural networks it is customary to think of a distributed system as being composed of processors rather than processes.} Each process $i$ has a {\em set of states} $\alpha_i$. The {\em set of system states} is \[ \Sigma = \alpha_1 \times \alpha_2 \times \cdots \times \alpha_n \] and a subset of this set $L \subseteq \Sigma$ is called the set of {\em legal states}. A distributed system computes as follows. A process examines its current state and received messages to determine its next state. Following its state transition, a process may send messages to (some of) its neighbors. Messages travel only on edges of the underlying graph $G$. A distributed system is called {\em self-stabilizing} to a set of system states $L \subseteq \Sigma$ if, starting from any initial state $S \in \Sigma$, (i) the system eventually enters a state in $L$ and (ii) the subsequent state changes (if any) confine the system state to remain within $L$. Dijkstra \cite{cj99-06-04} introduced this concept for the design of distributed mutual-exclusion algorithms. One useful property of self-stabilizing systems is that they are inherently fault-tolerant. For example, if a transient fault in the state of some process ``kicks'' the system state out of the legal region $L$, the system eventually reenters $L$ on its own. Thus, the system recovers from such faults autonomously, without external intervention. In the context of neural networks, the following refinement is also useful. A distributed system is called {\em $k$-bounded self-stabilizing} to a set of system states $L \subseteq \Sigma$ partitioned into sets $L^1_k, L^2_k, \ldots$ of cardinality at most $k$ if, starting from any initial state $S \in \Sigma$, (i) the system eventually enters a state in $L^j_k$ for some $j$ and (ii) thereafter remains confined within $L^j_k$. A $k$-bounded self-stabilizing system is self-stabilizing, but the opposite is not necessarily true. A 1-bounded self-stabilizing system converges to a fixed point.\footnote{Convergence of a system to fixed points has also been studied in the distributed systems community; see \cite{cj99-06-24}.} The set $L$ and its partitioning into $L^1_k,L^2_k,\ldots$ is either implicit or prespecified from an application. A distributed system is called {\em serial} if, at any given time, at most one process carries out its computation (determining its next state from its current state and received messages; sending messages to its neighbors). The process to carry out its computation is assumed to be selected {\em fairly}. Only a relatively mild version of fairness is assumed: In any infinite sequence of chosen processes, each process appears infinitely often. A distributed system is called {\em parallel} if, at any given time, all processes carry out their computations simultaneously. \section{The two-state Hopfield network} Hopfield's \cite{cj99-06-12} 1982 neural network model sparked interest in the neural network and statistical physics communities. The model has been implemented repeatedly in specialized hardware: digital, analog, optical, or hybrid (see \cite{cj99-06-11}). The model is defined as follows. There are $n$ vertices, representing neurons, connected pairwise by a complete undirected graph $G$ with loops. An integer-valued weight $w_{ij}$ is placed on each edge $\{i,j\}$ of the graph $G$, an integer valued $w_{ii} \geq 0$ on every loop $\{i,i\}$ of the graph, and an integer valued $w_i$ on each vertex $i$ of the graph $G$. The graph is assumed to be complete for notational convenience only. The true connectivity graph underlying a given network is one that contains edges only for the nonzero edge weights $w_{ij}$. Each vertex $i$ has the same state-set $\alpha_i = \{-1,1\}$.\footnote{An alternate formulation has the state set $\alpha_i = \{0,1\}$.} Let $s_i$ denote the state of process $i$. The Hopfield network employs the following state-update rule for the process $i$. \begin{equation} \label{Hop} s_i(t+1) := \left\{ \begin{array}{ll} 1 & \mbox{if $w_i + \sum_{j=1}^n w_{ij} s_j(t) \geq 0$} \\ -1 & \mbox{otherwise.} \end{array} \right. \end{equation} \subsection{The serial case} When (\ref{Hop}) is applied serially, the Hopfield model 1-bounded self-stabilizes to a set of system states $L_{fp}$, called the fixed points of the network.\footnote{The terms ``serially'' and ``1-bounded self-stabilizes'' are used here precisely as defined in Section 2.} Hopfield \cite{cj99-06-12} proved this result by using the energy function \begin{equation} \label{E} E(S) = -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n w_{ij} s_i s_j - \sum_i w_i s_i, \end{equation} which is bounded from below, and by showing that whenever a process {\em changes} its state following the application of (\ref{Hop}), the energy $E$ decreases by a fixed minimum amount. This result holds for networks with arbitrary connectivity graphs, arbitrary edge weights $w_{ij}$, arbitrary vertex weights $w_i$, and nonnegative loop weights $w_{ii}$. Counterexamples, when even one loop weight is negative or when even one edge in the connectivity graph is directed (i.e., when $w_{ij} \neq w_{ji}$ for some $i \neq j$), are easy to construct (see, e.g., \cite[Chap. 8]{cj99-06-22}). The serial Hopfield network is easily realizable in a serial distributed system, as defined in Section 2, which is hence 1-bounded stabilizing. \subsection{The parallel case} When (\ref{Hop}) is applied in parallel, the Hopfield model 2-bounded self-stabilizes to a set of system states $L \supseteq L_{fp}$, which, in addition to the fixed points $L_{fp}$ of the network, includes pairs of states that form 2-cycles (refer to \cite{cj99-06-07}). The proof once again relies on the energy function approach. Goles et al.\ \cite{cj99-06-07} defined the following interesting energy function, which depends not only on the current system state but also on the previous one: \[ F(S(t),S(t-1)) = -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n w_{ij} s_i(t) s_j(t-1) - \sum_i w_i (s_i(t) + s_i(t-1)). \] They showed that $F$ is bounded from below and decreases by some minimum amount whenever $S(t) \neq S(t-1)$ and $S(t) \neq S(t-2)$, and is zero otherwise, implying convergence to a fixed point or to an oscillation between two states (2-cycle). This result holds under the same conditions on the network as does the serial 1-bounded self-stabilization result. Counterexamples showing the conditions to be tight are once again easy to construct (see \cite[Chap. 8]{cj99-06-22}). Goles et al.\ \cite{cj99-06-07} also proved that when the weight matrix $W$ is symmetric, has nonnegative diagonal elements, and is positive-definite on the set $\{-1,0,1\}^n$, the parallel network is 1-bounded self-stabilizing. \subsection{Number of state changes to stabilization} How may one calculate the maximum number $\tau$ of state changes within which a network stabilizes? The energy function is useful here, too. Let $\Delta = \mbox{max}_{S,T \in \Sigma}(E(S)-E(T))$ denote the maximum difference between the energies at two system states. Let $\delta$ denote the minimum amount by which energy decreases when a state changes. Then $\Delta/\delta$ is an upper bound on $\tau$. Using this idea, Fogelman-Soulie et al.\ \cite{cj99-06-06} obtained upper bounds on $\tau$ for the serial case. This description is summarized from \cite{cj99-06-18} where it differed, in minor ways, from the original version. Let $M$ denote the sum of the $\floor{n^2/4}$ largest coefficients $|w_{ij}|$, $i \neq j$, and let $w=\mbox{min}_i w_{ii}$. For the serial case, the result is that \[ \tau \leq \frac{2(M + \sum_i |w_i|)}{1 + 2w}. \] If $|w_{ij}| \in \{0,1\}$ for all $i, j$, then the result is $\tau \leq 5 n^2/2$. Goles et al.\ \cite{cj99-06-07} obtained the analogous bound on $\tau$ for the parallel case. If $W$ is positive-definite on the set $\{-1,0,1\}^n$, then the result is \[ \tau \leq \frac{M + \sum_i |w_i|}{\lambda_{\min}}, \] where $\lambda_{\min}$ is the smallest eigenvalue of $W$. In the general case, the result is that \[ \tau \leq 4 \sum_{i=1}^{n} \sum_{j > i} |w_{ij}| + 2 \sum_i w_{ii} + 4 \sum_i |w_i|. \] If $|w_{ij}| \in \{0,1\}$ for all $i,j$, then the result is $\tau \leq 6 n^2$. Floreen \cite{cj99-06-05} obtained a small improvement to the unrestricted serial result and a somewhat larger improvement to the unrestricted parallel result. It should be noted that though all the above results are based on the simple idea of computing $\Delta/\delta$, the actual calculations are often tricky, because a good upper bound on $\Delta$ is not easy to compute for this family of neural networks. Finally, we remark that the notion of ``number of state changes to stabilization'' is, in essence, the same as the {\em convergence span} of the distributed systems community (refer to \cite{cj99-06-09,cj99-06-24}). \subsection{Attraction domains} For a deterministic distributed system that is 1-bounded self-stabilizing, the system-state set $\Sigma$ may be partitioned into sets $AD(S_1), AD(S_2), \ldots$ where $S_1,S_2,\ldots$ are all the fixed points in $L_{fp}$. The set $AD(S_f)$ is called the {\em attraction domain} of the fixed point $S_f$ and is defined as the set of initial states from which the system eventually converges to $S_f$ (see \cite{cj99-06-18}). Although this definition is easily generalized to the $k$-bounded case, it is most natural to study it in the $k=1$ case. In particular, it arises naturally in the context of one of the application areas of the Hopfield network---associative memories---described in the next section. In this context, $B(S_f)$ represents the set of ``cues'' from which a given memory $S_f$ can be retrieved. The larger the set $B(S_f)$ is, the more effective the model is for memory $S_i$. The attraction domains of memories stored in the parallel two-state Hopfield network, and variants, have been studied extensively under certain conditions (refer to \cite{cj99-06-21,cj99-06-18}). Unfortunately, this issue is quite complicated, since the attraction domains depend on the following: \begin{enumerate} \item[(i)] The storage mechanism employed: how the weights $w_{ij}$, $w_{ii}$, and $w_i$ are derived from the given memories \item[(ii)] The assumptions on the memories: whether they are chosen randomly or are chosen to draw out worst-case behavior \item[(iii)] The number of memories \end{enumerate} The attraction domain results cannot be interpreted meaningfully without a detailed discussion of these issues. Since these are less central to the theme of the current paper, we omit their discussion and, hence, detailed presentation of attraction domain results. \subsection{Applications} In his seminal 1982 paper, Hopfield proposed this neural network as a model for {\em associative memory} \cite{cj99-06-12}. We explain this briefly as follows. Hopfield suggested that a set of memories $P$ could be stored in a network by constructing its edge-weight matrix $W$ and vertex-weight vector $w$ in such a way that the resulting set $L_{fp}$ of fixed points coincides with the set $P$. Thus each fixed point of the network represents a memory from the set $P$. To retrieve a memory $S_f \in L_{fp}$ from a cue $S_i \in \Sigma$, the serial operation is used, with the initial state set to $S_i$. (Recall that, unlike the parallel operation, the serial operation always converges to a fixed point from an arbitrary initial state.) To construct the matrix $W$ and vector $w$ from a given set of memories $X_1,\ldots,X_p$, $X_i \in \{-1,1\}^n$ for $i=1,\ldots,p$, Hopfield \cite{cj99-06-12} proposed the {\em Hebb rule}, which sets \[ W := \sum_{i=1,\ldots,p} X_i X^T_i, \] where $T$ denotes transpose. The vector $w$ is set to zero. Unfortunately, the Hebb rule does not work very well in general ($L_{fp}$ can differ greatly from $P$). In fact, not surprisingly, it is impossible to construct a perfect network (i.e., with $L_{fp} = P$) for an arbitrary pattern set $P$, no matter how one chooses $W$ and $w$ (see \cite{cj99-06-02}). A considerable amount of research has concentrated on alternatives to the Hebb rule for storing memories in the Hopfield model. We omit the details here; interested readers may examine, for example, \cite{cj99-06-02,cj99-06-21,cj99-06-03,cj99-06-11}. In 1985, Hopfield and Tank \cite{cj99-06-14} proposed another application area, {\em quadratic optimization}, for this neural network. We illustrate the case of combinatorial optimization. To solve a combinatorial optimization problem (usually approximately) in a Hopfield network, one first maps the problem to a quadratic objective function on $-1/1$ variables with symmetric coefficients. One then identifies this objective function with the energy function of the network in such a way that the minima of the energy function correspond to optima of the objective function. One then derives the edge-weight matrix $W$ and the vertex-weight vector $w$ from the energy function, yielding the network. Finally, one operates the network in serial mode from some initial state. Since serial operation always reduces energy monotonically, it eventually settles into a local minimum of the energy function (hence local optimum of the mapped problem). Here is a sketch of an example. Consider the {\em maximum clique problem}, the problem of finding the largest fully connected subgraph of a given graph on $n$ vertices. To express this problem in terms of an appropriate objective function, we first choose $n$ variables $x_i \in \{0,1\}$. We then make the correspondence $U(x)=\{i | x_i = 1\}$ between a vector $x$ and a subset $U(x)$ of the vertex set $V$ of the graph. We write out the objective function \[ F(x) = \sum_{i=1,\ldots,n} x_i ~+~f(x), \] where the first term encodes the size of the set $U(x)$ and the second term is chosen so as to enforce the constraint that $U$ be a clique. The resulting $F(x)$ must be expressible as \[ F(x) = \sum_{i,j} a_{ij} x_i x_j + \sum_i a_i x_i, \] where $a_{ij} = a_{ji}$. We identify $F$ with the energy function $E$ of (\ref{E}) to derive the weights $w_{ij}$ and $w_i$. And then we operate the resulting network serially to retrieve a fixed point (local minimum of $E$) $x^*$ from which we can extract the clique. In \cite{cj99-06-15} it is shown that there is a one-to-one correspondence between maximal cliques of the graph and fixed points of the network for one such encoding. In \cite{cj99-06-17} an extensive experimental study is conducted on heuristically solving the maximum clique problem by this method. This general approach is not without its difficulties. For many combinatorial problems, good encodings are not known (see \cite{cj99-06-26}). (An encoding is bad, for instance, if some of the network's fixed points do not constitute feasible solutions of the original problem.) This has led to a fair amount of research on characterizing optimization problems that map well to the Hopfield model (see \cite{cj99-06-19,cj99-06-15}). There is also considerable work on using other variants of the Hopfield model on this problem (e.g., the randomized and continuous versions; see Sections 4 and 5). Notwithstanding the difficulties of finding good encodings and the fact that the network performs only local optimization, this approach is attractive from the point of view of distributed computing and new applications of self-stabilization. Indeed, in theory, every problem in NP may be mapped to the Hopfield network. (And many have been mapped in practice.) Thus a self-stabilizing meta-algorithm exists, in principle, for locally optimal versions of every NP problem. Here is a partial list of combinatorial problems that have been encoded and approximately solved in Hopfield networks: % \query{au: Please check editing this paragraph.} We have already mentioned the maximum clique problem, an NP-hard problem; see \cite{cj99-06-17,cj99-06-10}. The traveling salesperson problem was studied in \cite{cj99-06-14,cj99-06-11}, the graph coloring problem in \cite{cj99-06-19,cj99-06-16}, and the graph bipartitioning problem in \cite{cj99-06-23}. Virtually all of the above works simulate the networks on sequential machines. In most cases the neural net algorithms are not entirely competitive with state-of-the-art conventional ones. However, the former algorithms offer the potential benefits of distributed computing and self-stabilization, which deserve further study. \section{A locally randomized version} The processes in the two-state Hopfield network of the previous section employ a deterministic state transition function. In this section, the processes employ a certain randomized state transition function (refer to \cite{cj99-06-11}). Let \[ h_i = w_i + \sum_{j=1}^n w_{ij} s_j(t). \] Then the state transition function is \begin{equation} \label{Hop_SA} \mbox{Prob}(s_i := \pm 1) = g_T(h_i), \end{equation} where \[ g_T(h_i) = \frac{1}{1 + e^{\mp h_i/T}}. \] Here $T$ is a ``temperature'' parameter that controls the amount of randomness. When $T \rightarrow 0$, (\ref{Hop_SA}) reduces to the deterministic version (\ref{Hop}), which always decreases energy. When $T \rightarrow \infty$, the events $s_i := 1$ and $s_i := -1$ are equally probable; thus energy-increasing state-transitions are also admissible. The state transition function $g_T(h_i)$ is the same one employed in simulated annealing; its choice is dictated by the fact that this governs the evolution of the network in accordance with the principles of statistical mechanics. Indeed, if $T$ is annealed during the evolution of the randomized Hopfield network, then the network emulates simulated annealing. In the context of this section, the following definition is useful. Assume that the state set $\alpha_i$ of the process $i$ contains numeric quantities. Let $\langle s_i \rangle$ denote the expected value of the state of the process $i$. A distributed system is called {\em 1-bounded self-stabilizing on average} if, starting from any initial state $S \in \Sigma$, the system eventually reaches a point after which the system state does not change on average, namely, that the $n$-tuple $(\langle s_1 \rangle, \ldots, \langle s_n \rangle)$ remains fixed. Note that this definition is rigorous; the question of what time scale over which to measure ``average'' is an operational one. This definition is different from that of {\em probabilistic self-stabilization} introduced in the distributed systems community (see \cite{cj99-06-24}). A probabilistically self-stabilizing distributed system, started from an arbitrary initial state, eventually enters $L$ with probability approaching 1 and once inside $L$ never escapes it. By contrast, a 1-bounded self-stabilizing on average system does not enter any region $L$ at all. One way to interpret this is to say that a fixed region $L$ has been replaced by a certain statistic on it---in our case, the average value of each state. It is the statistic that should converge, not the state. It is known that the locally randomized Hopfield network is 1-bounded self-stabilizing on average in the serial and parallel cases (see \cite{cj99-06-01}, \cite[p. 33]{cj99-06-11}). Indeed, in essence, this may be surmised from the well-known fact that the simulated annealing algorithm converges in the average sense. Is it enough to say that a locally randomized Hopfield network merely emulates simulated annealing when $T$ is annealed? It is useful to add the following. The network constitutes a {\em distributed} implementation of simulated annealing. On the negative side, this implementation works only for (quadratic) cost functions that can be mapped to the energy function $E$ of the previous section. \section{A continuous-state version} In 1984, Hopfield introduced a version of the network that employs contin\-u\-ous-valued process states \cite{cj99-06-13}. The state set of each process is $\alpha_i \in [0,1]$. The evolution of the network is governed by the following system of $n$ nonlinear coupled differential equations: \begin{equation} \label{CT} \frac{d s_i}{d t} = -s_i + g_T(h_i), \end{equation} where $g_T(h_i)$ and $h_i$ were defined in the previous section. In practice, a network cannot be evolved according to (\ref{CT}). And distributed systems, as studied in computer science, work in discrete time steps. For these two reasons, the following discrete-time (but still continuous-state) version of (\ref{CT}), an Euler approximation, is more natural to study: \begin{equation} \label{DT} s_i(t+1) := s_i(t) + \gamma_i (-s_i(t) + g_T(h_i)), \end{equation} where $\gamma_i$ is the Euler step size taken by the process $i$. To discuss stability results for continuous networks, the following definition, cast in terms of distributed systems, is useful. For this definition, the state space $\Sigma$ must be a metric space. A distributed system is called {\em asymptotically 1-bounded self-stabilizing} to a set $L_{fp} \subseteq \Sigma$ if, starting from any initial system state $S_i \in \Sigma$, the network converges in infinite time to some state $S_f \in \Sigma$, that is, \[ \lim_{t \rightarrow \infty} S(t) = S_f. \] In other words, for any $\epsilon > 0$ there exists a $\delta$ such that the system enters an $\epsilon$-neighborhood of $S_f$ within the time $\delta$. Hopfield showed that, for a slightly different system of equations than (\ref{CT}) but with the same set of fixed points, the continuous-time network is asymptotically 1-bounded self-stabilizing, in both serial and parallel operations.\footnote{See \cite{cj99-06-13,cj99-06-11}. The system of equations is not explicitly described here because it adds little new information but requires considerable explanation.} The proof works also for the system of equations (\ref{CT}). Note that, in parallel operation, the {\em continuous}-state continuous-time Hopfield model is 1-bounded self-stabilizing, whereas the {\em two}-state model is 2-bounded self-stabilizing. This difference is significant because both the associative memory and the optimization applications of the Hopfield model rely on convergence to fixed points only. Hopfield proved this result by using the energy function \[ H(S) = -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n w_{ij} s_i s_j - \sum_i w_i s_i + \sum_i \int_{0}^{s_i} g_T^{-1}(s) d s, \] which differs from $E(S)$ only in the last term. The function $H(S)$ is bounded from below, and Hopfield showed that $d H/dt \leq 0$ during the evolution of the network, according to the variant of (\ref{CT}) mentioned above, with equality holding if and only if the network state is at a fixed point. As noted earlier, in practice, the continuous-valued Hopfield network is usually evolved via (\ref{DT}). What happens in this case? When the step sizes $\gamma_i \rightarrow 0$ for all $i$, (\ref{DT}) behaves like (\ref{CT}), preserving asymptotic 1-bounded self-stabilization. When the step sizes $\gamma_i = 1$ for all $i$, Marcus and Westervelt \cite{cj99-06-20} showed that the network is in general no longer 1-bounded self-stabilizing in parallel mode---it converges instead to fixed points or to 2-cycles, in analogous fashion to the two-state parallel network. Herz and Marcus \cite{cj99-06-27} generalized these results to what they called the distributed update mode in which, at time $t$, an arbitrary set of neurons is chosen to update its states. (This so-called distributed mode is still at the coarse-grained level, unlike our analysis in Section 6.) Recently, Wang et al.\ \cite{cj99-06-25} studied the general case of (\ref{DT}). They showed that serial evolution of (\ref{DT}) is asymptotically 1-bounded self-stabilizing over all values of $\gamma_i \in [0,1]$. They obtained a sufficient (in many cases also necessary) condition for a network evolved in parallel via (\ref{DT}) to be asymptotically 1-bounded self-stabilizing. The condition requires that a certain matrix derived from the weight matrix $W$, the Euler step-sizes $\gamma_i$, and the temperature $T$ be positive-definite. Special cases of this condition include the Goles et al.\ \cite{cj99-06-07} condition for the two-state case and the Marcus and Westervelt \cite{cj99-06-20} condition when $\gamma_i = 1$ for all $i$. In an expanded version of this paper, they also obtained self-stabilization results for the distributed dynamics of Herz and Marcus applied to (\ref{DT}) for arbitrary $\gamma_i \in [0,1]$. Finally, a version of the continuous-time update (\ref{CT}) has been studied that, in a sense, is more asynchronous. Wang, Li, and Blum \cite{cj99-06-32} permitted each neuron $s_i$ to have its own local time (there was no global time) at which it updated itself. They also incorporated transmission time-delays in their update algorithm. In principle, their approach captures the main ingredients of a fine-grained implementation. However, (i) the analysis is only for the continuous-time case and (ii) it imposes strong conditions to assure convergence. The continuous Hopfield network is applicable to the discrete associative memory and discrete optimization applications of the two-state network (refer to \cite{cj99-06-11}), as a continuous algorithm with the usual caveats. The continuous Hopfield network is also applicable to a continuous version of the associative memory problem, as well as to continuous optimization problems (see \cite{cj99-06-11}). All applications, once again, rely on convergence to fixed points only. In an ideal continuous-time implementation, this property is preserved even during parallel evolution of the network, which turns out to be an advantage, in one sense, over the two-state network. An ideal implementation is, however, not realizable. In practice, the network must be evolved in discrete time. Our results, which provide a sufficient condition for asymptotic 1-bounded self-stabilization of the parallel discrete-time network, are therefore potentially useful in the context of these applications. We have noted \cite{cj99-06-25}, for example, that a certain family of networks commonly used in associative memory applications meets our sufficient condition and therefore converges to fixed points under parallel operation. \section{Convergence under fine-grained atomicity} The various convergence results of the previous sections rely on the assumption that the operation given by (\ref{Hop}) is atomic. In this section we examine what happens to convergence under finer-grained atomicity. Each process's code at a fine level is as follows: \begin{tabbing} $n+1$.\hspace{1em}\= \kill Process $i$ \\ {\tt loop} \> \\ 1. \> Read $s_1(t)$ \\ 2. \> Read $s_2(t)$ \\ \> $\ldots$ \\ $n$. \> Read $s_n(t)$ \\ $n+1$. \> Compute next state $s_i(t+1)$ \\ {\tt forever} \end{tabbing} What can we say about convergence when individual instructions of different processes can get interleaved in time? We now examine this issue in the context of the two-state Hopfield model. One natural question to ask in this context is: Will convergence to fixed points continue to hold, like it did under coarse-grained atomicity, for any fair schedule? The answer is No. Consider the schedule in which, in phase I, processes are activated in cyclic order (e.g., $1$ through $n$), and each of them executes its steps $1$ through $n$. Once this is finished, in phase II, each process executes step $n+1$ (i.e., computes its next state). This schedule simulates parallel operation at the coarse level, which is known to converge to 2-cycles. (Examples illustrating 2-cycle behavior are easy to construct.) On the other hand, there are at least some fair, deterministic schedules under which convergence to fixed points is assured. Here is one: In phase I, activate processes cyclically as before, but this time make each of them execute steps 1 through $n+1$ (instead of 1 through $n$). This schedule simulates fair sequential operation at the coarse level, which is convergent to fixed points. The deterministic schedule used above essentially reverts back to coarse-grained atomicity. A more realistic situation would be one in which processes activate themselves autonomously at arbitrary times. Fortunately, by a simple modification of each process's program, we can accomodate autonomous operation of the distributed system while preserving convergence to a fixed point (although in infinite time instead of finite time as in the coarse-grained case). Each process's modified program is the following: \begin{tabbing} Process \= $i$ \\ 0. \> With \= probability $p$ \\ 0.'\> \> sleep for $\delta$ time-units; \\ 0.''\> \> goto 0; \\ 1. \> Read $s_1$ \\ 2. \> Read $s_2$ \\ \> $\ldots$ \\ $n$. \> Read $s_n$ \\ $n+1$. \> Compute new state $s_i$ \\ \end{tabbing} Process $i$ activates itself autonomously at an arbitrary time (there is no global clock) and begins executing from step 0. % With probability $p$ % it sleeps for $\delta$ time-units; then it goes back to step 0. % (With % \query{au: Is ``(With \ldots step 1.)'' correct?} % probability $p$ it goes to step 1.) The pauses are all before step 1, because it suffices to pause only before any of the states of the other processes are read. We assume, furthermore, that the total time any process takes to execute its steps $1$ through $n+1$ (including communication time to read the states of other processors) is bounded by some function $\Delta(n)$ of $n$. This is quite a mild assumption. The parameter $\delta$ controls the extent of the sleep time, and its setting is governed by the communication delays. The parameter $p$ probabilistically allows different processes to sleep for different amounts of time, breaking any pathological synchronies. More precisely, the combination of these parameters allows one to show that the event $E_v$ used in the proof below occurs asymptotically with probability 1. The boundedness assumption $\Delta(n)$ ensures that $p$ and $\delta$ can be chosen appropriately (see proof below). We are now ready to show that this distributed system almost surely stabilizes to a fixed point in infinite time. \begin{defn}[Adapted from \cite{cj99-06-24}] A distributed system is called {\em 1-bounded probabilistically self-stabilizing} if, started from an arbitrary initial state $S \in \Sigma$, the system enters a fixed point with probability approaching $1$ as time $t$ approaches infinity. Furthermore, once the system enters a fixed point, it remains there. \end{defn} \begin{proposition} The distributed system described above is 1-bounded probabilistically self-stabilizing. \end{proposition} \begin{proof} Consider the sequence \[ E_v(t_0) \equiv (1,0,\ldots,0, 2,0,\ldots,0, \ldots, n,0,\ldots,0)^{2^{n+1}} \] denoting the event that, starting at some time $t_0$, processes activate themselves in order $1$ through $n$ cyclically $2^{n+1}$ times. In this event, at a time $t$ when a process activates itself, no other process activates itself. Furthermore, there is a gap (indicated by the 0's) of at least $\Delta(n)$ time-units between consecutive activations. Thus, in a $\Delta(n)$ time-interval, only one process is active. The proof hinges on showing the following to be true: \begin{enumerate} \item If event $E_v(t_0)$ occurs starting at some time $t_0$, then a fixed point is eventually entered \item In the limit as $t$ goes to infinity, the event $E(t_0)$ occurs with probability approaching 1 starting at some $t_0 \leq t$ \end{enumerate} We first prove item 1. If event $E(t_0)$ occurs, then it simulates serial operation of the two-state Hopfield network (at the coarse-grained level) for its duration. The duration of each inactivity gap, coupled with our boundedness assumption about each process's activity duration, ensures this. The remaining question is whether coarse-grained serial operation is simulated for a sufficiently long duration that a fixed point is necessarily entered. Since a two-state Hopfield model has $2^n$ states, there can be at most $2^n$ state changes during coarse-grained serial operation before a fixed point is entered. (Otherwise, a cycle would be entered, contradicting the coarse-grained convergence result.) It is easy to see that if the cyclic serial operation of the event $E(t_0)$ runs for $2^{n+1}$ coarse-level steps, then there must necessarily have been $2^n$ state-changes. (If in any $n$ contiguous activations there are no state changes, then we must be at a fixed point.) We now prove item 2. It is easy to see that, for any particular $t_0$, the probability of event $E(t_0)$ is lower-bounded by some positive function that depends only on $n$, $p$, and $\delta$. (It is not difficult to estimate this probability more explicitly, but this is not needed.) Therefore, for fixed positive values of $n,p, \delta$, the probability that the event $E(t_0)$ occurs for some $t_0$ between 1 and infinity tends to 1. Finally, it is easily seen that once the system enters a fixed point it remains trapped there forever. (No process changes state no matter what the subsequent order of interleaved operations.) \end{proof} A few remarks are in order. \begin{itemize} \item Like in \cite{cj99-06-24}, though entry into $L$ is probabilistic (with probability approaching 1 as time $t$ approaches infinity), escape from $L$ is impossible. \item In \cite{cj99-06-08,cj99-06-24} there is an investigation of the robustness of self-stabilization across granularity of implementation. Some analogous remarks in the setting of Hopfield networks are in order. On the one hand, the two-state Hopfield model is fragile in going from a coarse- to a fine-grained implementation, since convergence is not preserved for every fair schedule. On the other hand, it is also moderately robust, since there is a reasonable probabilistic schedule under which convergence to a fixed point is assured, almost surely, in infinite time. \item The proof does not appear to be extendible to the continuous-state Hopfield network. The proof seems to rely crucially on the fact that for the two-state Hopfield model, convergence is assured within $2^n$ state changes. \item The proof is quite loose. It is based on an event that has a very low (though nonzero) probability of occurrence. Perhaps tightening this argument will lead to a stronger result. Preliminary computational experiments we conducted on fine-grained implementations of random Hopfield networks of up to a 100 neurons revealed that convergence to fixed points was quite rapid. \end{itemize} \section{Perturbation analysis} In many situations, the guarantee that a system when perturbed out of its legal region will {\em eventually} enter it again is insufficient. If the perturbation is small, one desires the system to return to its legal region quickly. The concept of self-stabilization does not deal with this issue. This has given rise to the notion of systems that not only self-stabilize but also have the {\em fault-containment} property (refer to \cite{cj99-06-31,cj99-06-28,cj99-06-30,cj99-06-29}). Fault-containment, roughly speaking, refers to a self-stabilizing system that, when a few processes get faulty, restabilizes after only a few state changes. A similar issue may be studied in the setting of serial Hopfield networks. Let $S^* \in \{-1,1\}^n$ be a fixed point of a Hopfield network instance operated in serial mode. Perturb $S^*$ by flipping any $k$ of its bits. We want to bound the number of state changes to reconvergence. As in earlier sections, the analysis hinges on energy function arguments. We obtain an upper bound on the energy increase when $k$ bits of a fixed point are flipped. Together with lower bounds on the global energy minimum and on the amount of energy change in any state change, this allows us to place an upper bound on the number of state changes to reconvergence. Assume that $|w_{ij}| \leq W_{\max}$ for all $i,j$ and that $|w_i| \leq w_{\max}$ for all $i$. Denote by $S^*_k$ the vector obtained by flipping any $k$ bits of a fixed point $S^*$. It may be seen that \[ E(S^*_k) \leq E(S^*) + 2 k (n W_{\max} + w_{\max}), \] since flipping any one bit can increase the energy by at most $2 (n W_{\max} + w_{\max})$ because there are $n$ neurons and because of the assumed bounds $W_{\max}$ and $w_{\max}$ on the magnitudes of the weights. Now we write for the fixed point $S^*$ \[ E(S^*) \leq E_{\min} + f(n,W,w), \] where $E_{\min}$ is the global energy minimum of the network; $f$ is some function that upper-bounds the gap between the minimum and maximum energy values of local energy minima and whose value is determined by the network instance $\langle n,W,w\rangle$; $W$ is the matrix of the edge weights; and $w$ the vector of the vertex weights. Therefore \[ E(S^*_k) \leq E_{\min} + 2 k (n W_{\max} + w_{\max}) + f(n,W,w). \] Assume that $\Delta E$, the minimum amount of energy decrease in any one state-changing step, is no less than a positive function $c(n,W,w)$. Then the number of state changes to reconvergence is less than or equal to \begin{equation} \label{PA3} \frac{2 k (n W_{\max}+w_{\max})~+~f(n,W,w)}{c(n,W,w)} . \end{equation} We now apply (\ref{PA3}) to a particular class of networks. In applications of two-state Hopfield nets to combinatorial optimization, many encodings have been found in which $|w_{ij}| \in \{0,1\}$ and $w_{\max}$ and $c(n,W,w)$ are constants (see \cite{cj99-06-19,cj99-06-15}). Furthermore, in many cases, for instance, in an encoding of the maximum clique problem into a Hopfield network (refer to \cite{cj99-06-15}), one can show that $f(n,W,w) = O(n)$. In such cases, from (\ref{PA3}), the number of state changes to reconvergence is thus $O(k n)$. \section{Discussion} This paper describes a self-stabilizing neural network model developed in the early 1980s. The model fits naturally within the usual framework of distributed systems. This paper surveys a large body of research on this model and its variants over the past fifteen years. The survey focuses on the important variants, their self-stabilization results, and novel applications of self-stabilization arising from this neural network setting. Two new results at the intersection of neural networks and distributed systems are also obtained. The first is a probabilistic convergence result for a fine-grained distributed implementation of this network. The second one deals with perturbation analysis. These results may be seen as some indication of the possibility of further research at the intersection of these two fields. It is hoped that this paper spurs cross-fertilization of ideas between the distributed systems and neural network communities in the context of self-stabilization. Perhaps the variants of self-stabilization that naturally arise in the Hopfield network setting (e.g., $k$-bounded self-stabilization, $k$-bounded self-stabilization on average, asymptotic $1$-bounded self-stabilization) are of interest in the distributed systems setting. We suggest that the notion of attraction domains, which plays an important role in Hopfield networks (e.g., in associative memory applications), may be found useful also in the distributed systems setting. Perhaps the associative memory and optimization applications of self-stabilizing neural networks can be extended to the more general setting of self-stabilizing distributed systems. For some preliminary work in this direction, in the context of optimization, see \cite{cj99-06-33}, % \query{au: missing this cite} which shows that a certain kind of self-stabilizing distributed constraint satisfaction is impossible in a Hopfield-type neural network model but is achievable in a more sophisticated self-stabilizing distributed system. It is useful to note that the Hopfield network is the best candidate in the field of neural networks for the study of self-stabilization issues. It is second only to the backpropagation network in its significance within the field. The self-stabilization property applies neither to the backpropagation network nor to virtually any other network except the Hopfield network. Indeed the Hopfield network was designed, in effect, with the self-stabilization property in mind. We close this paper with a few suggestions for further work at the intersection of the two fields. \begin{itemize} \item Proposition 1 establishes only probabilistic convergence in the asymptotic limit. The proof employs a loose argument. Perhaps the result can be strengthened to establish rapid probabilistic convergence. \item It remains necessary to obtain impossibility results for certain problems on the Hopfield model. Some preliminary work along these lines % \query{au: again missing cite} is in \cite{cj99-06-33}. \item Additional research may extend the associative memory and combinatorial optimization applications of the Hopfield model to the more general setting of self-stabilizing distributing systems. \end{itemize} \subsection*{Acknowledgments} The author thanks Rina Dechter for introducing him to this topic and Ajoy Datta for reviving his interest in it. The author thanks an anonymous reviewer for helpful comments, especially for suggesting self-stabilization analysis under a fine-grained implementation, and another anonymous reviewer for pointing out that not every fair deterministic schedule preserves convergence to the network's fixed-point property (Section 3) under the fine-grained implementation (Section 6). \bibliography{cj99-06} \bibliographystyle{alpha} \end{document}