Analog neural networks with local competition. I. Dynamics and stability

A deterministic annealing algorithm for approximating a solution of the linearly constrained nonconvex quadratic minimization problem

A deterministic annealing algorithm is proposed for approximating a solution of the linearly constrained nonconvex quadratic minimization problem. The algorithm is derived from applications of a Hopfield-type barrier function in dealing with box constraints and Lagrange multipliers in handling linear equality constraints, and attempts to obtain a solution of good quality by generating a minimum point of a barrier problem for a sequence of descending values of the barrier parameter. For any given value of the barrier parameter, the algorithm searches for a minimum point of the barrier problem in a feasible descent direction, which has a desired property that the box constraints are always satisfied automatically if the step length is a number between zero and one. At each iteration, the feasible descent direction is found by updating Lagrange multipliers with a globally convergent iterative procedure. For any given value of the barrier parameter, the algorithm converges to a stationary point of the barrier problem. Preliminary numerical results show that the algorithm seems effective and efficient.

A deterministic annealing algorithm for the minimum concave cost network flow problem

The existing algorithms for the minimum concave cost network flow problems mainly focus on the single-source problems. To handle both the single-source and the multiple-source problem in the same way, especially the problems with dense arcs, a deterministic annealing algorithm is proposed in this paper. The algorithm is derived from an application of the Lagrange and Hopfield-type barrier function. It consists of two major steps: one is to find a feasible descent direction by updating Lagrange multipliers with a globally convergent iterative procedure, which forms the major contribution of this paper, and the other is to generate a point in the feasible descent direction, which always automatically satisfies lower and upper bound constraints on variables provided that the step size is a number between zero and one. The algorithm is applicable to both the single-source and the multiple-source capacitated problem and is especially effective and efficient for the problems with dense arcs. Numerical results on 48 test problems show that the algorithm is effective and efficient.

A deterministic annealing algorithm for approximating a solution of the min-bisection problem

The min-bisection problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and an algorithm is proposed for approximating its solution. The algorithm is derived from the introduction of a logarithmic-cosine barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases from a sufficiently large positive number to zero. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds are always satisfied automatically if the step length is a number between zero and one. We prove that the algorithm converges to at least a local minimum point of the problem if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with a limit of zero. Numerical results show that the algorithm is much more efficient than two of the best existing heuristic methods for the min-bisection problem, Kernighan-Lin method with multiple starting points (MSKL) and multilevel graph partitioning scheme (MLGP).

Clustering of stored memories in an attractor network with local competition

In this paper we study an attractor network with units that compete locally for activation and we prove that a reduced version of it has fixpoint dynamics. An analysis, complemented by simulation experiments, of the local characteristics of the network's attractors with respect to a parameter controlling the intensity of the local competition is performed. We find that the attractors are hierarchically clustered when the parameter of the local competition is changed.

Optimization via Intermittency with a Self-Organizing Neural Network

One of the major obstacles in using neural networks to solve combinatorial optimization problems is the convergence toward one of the many local minima instead of the global minima. In this letter, we propose a technique that enables a self-organizing neural network to escape from local minima by virtue of the intermittency phenomenon. It gives rise to novel search dynamics that allow the system to visit multiple global minima as meta-stable states. Numerical experiments performed suggest that the phenomenon is a combined effect of Kohonen-type competitive learning and the iterated softmax function operating near bifurcation. The resultant intermittent search exhibits fractal characteristics when the optimization performance is at its peak in the form of 1/f signals in the time evolution of the cost, as well as power law distributions in the meta-stable solution states. The N-Queens problem is used as an example to illustrate the meta-stable convergence process that sequentially generates, in a single run, 92 solutions to the 8-Queens problem and 4024 solutions to the 17-Queens problem.

The concave-convex procedure

The concave-convex procedure (CCCP) is a way to construct discrete-time iterative dynamical systems that are guaranteed to decrease global optimization and energy functions monotonically. This procedure can be applied to almost any optimization problem, and many existing algorithms can be interpreted in terms of it. In particular, we prove that all expectation-maximization algorithms and classes of Legendre minimization and variational bounding algorithms can be reexpressed in terms of CCCP. We show that many existing neural network and mean-field theory algorithms are also examples of CCCP. The generalized iterative scaling algorithm and Sinkhorn's algorithm can also be expressed as CCCP by changing variables. CCCP can be used both as a new way to understand, and prove the convergence of, existing optimization algorithms and as a procedure for generating new algorithms.

CCCP algorithms to minimize the Bethe and Kikuchi free energies: convergent alternatives to belief propagation

This article introduces a class of discrete iterative algorithms that are provably convergent alternatives to belief propagation (BP) and generalized belief propagation (GBP). Our work builds on recent results by Yedidia, Freeman, and Weiss (2000), who showed that the fixed points of BP and GBP algorithms correspond to extrema of the Bethe and Kikuchi free energies, respectively. We obtain two algorithms by applying CCCP to the Bethe and Kikuchi free energies, respectively (CCCP is a procedure, introduced here, for obtaining discrete iterative algorithms by decomposing a cost function into a concave and a convex part). We implement our CCCP algorithms on two- and three-dimensional spin glasses and compare their results to BP and GBP. Our simulations show that the CCCP algorithms are stable and converge very quickly (the speed of CCCP is similar to that of BP and GBP). Unlike CCCP, BP will often not converge for these problems (GBP usually, but not always, converges). The results found by CCCP applied to the Bethe or Kikuchi free energies are equivalent, or slightly better than, those found by BP or GBP, respectively (when BP and GBP converge). Note that for these, and other problems, BP and GBP give very accurate results (see Yedidia et al., 2000), and failure to converge is their major error mode. Finally, we point out that our algorithms have a large range of inference and learning applications.

A deterministic annealing algorithm for approximating a solution of the max-bisection problem

The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and a deterministic annealing algorithm is proposed for approximating its solution. The algorithm is derived from the introduction of a square-root barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases from a sufficiently large positive number to 0. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds on variables are always satisfied automatically if the step length is a number between 0 and 1. We prove that the algorithm converges to at least an integral local minimum point of the continuous problem if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with zero limit. Numerical results show that the algorithm is much faster than one of the best existing approximation algorithms while they produce more or less the same quality solution.

Superposition of horseshoe-like periodicity and linear tonotopic maps in auditory cortex of the Mongolian gerbil

The segregation of an individual sound from a mixture of concurrent sounds, the so-called cocktail-party phenomenon, is a fundamental and largely unexplained capability of the auditory system. Speaker recognition involves grouping of the various spectral (frequency) components of an individual's voice and segregating them from other competing voices. The important parameter for grouping may be the periodicity of sound waves because the spectral components of a given voice have one periodicity, viz. fundamental frequency, as their common denominator. To determine the relationship between the representations of spectral content and periodicity in the primary auditory cortex (AI), we used optical recording of intrinsic signals and electrophysiological mapping in Mongolian gerbils (Meriones unguiculatus). We found that periodicity maps as an almost circular gradient superimposed on the linear tonotopic gradient in the low frequency part of AI. This geometry of the periodicity map may imply competitive signal processing in support of the theory of "winner-takes-all".

A Lagrange multiplier and Hopfield-type barrier function method for the traveling salesman problem

A Lagrange multiplier and Hopfield-type barrier function method is proposed for approximating a solution of the traveling salesman problem. The method is derived from applications of Lagrange multipliers and a Hopfield-type barrier function and attempts to produce a solution of high quality by generating a minimum point of a barrier problem for a sequence of descending values of the barrier parameter. For any given value of the barrier parameter, the method searches for a minimum point of the barrier problem in a feasible descent direction, which has a desired property that lower and upper bounds on variables are always satisfied automatically if the step length is a number between zero and one. At each iteration, the feasible descent direction is found by updating Lagrange multipliers with a globally convergent iterative procedure. For any given value of the barrier parameter, the method converges to a stationary point of the barrier problem without any condition on the objective function. Theoretical and numerical results show that the method seems more effective and efficient than the softassign algorithm.

Approximating a solution of the s-t max-cut problem with a deterministic annealing algorithm

The s-t max-cut problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and an algorithm is proposed for approximating its solution. The algorithm is derived from an application of a logarithmic barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases to zero from a sufficiently large positive number satisfying that the barrier function is convex. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds are always satisfied automatically if the step length is a number between zero and one. We prove that the algorithm converges to at least a local minimum point if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with zero limit. Numerical results show that the algorithm seems effective and efficient.

Replicator equations, maximal cliques, and graph isomorphism

We present a new energy-minimization framework for the graph isomorphism problem that is based on an equivalent maximum clique formulation. The approach is centered around a fundamental result proved by Motzkin and Straus in the mid-1960s, and recently expanded in various ways, which allows us to formulate the maximum clique problem in terms of a standard quadratic program. The attractive feature of this formulation is that a clear one-to-one correspondence exists between the solutions of the quadratic program and those in the original, combinatorial problem. To solve the program we use the so-called replicator equations--a class of straightforward continuous- and discrete-time dynamical systems developed in various branches of theoretical biology. We show how, despite their inherent inability to escape from local solutions, they nevertheless provide experimental results that are competitive with those obtained using more elaborate mean-field annealing heuristics.

Convergence properties of the softassign quadratic assignment algorithm

The softassign quadratic assignment algorithm is a discrete-time, continuous-state, synchronous updating optimizing neural network. While its effectiveness has been shown in the traveling salesman problem, graph matching, and graph partitioning in thousands of simulations, its convergence properties have not been studied. Here, we construct discrete-time Lyapunov functions for the cases of exact and approximate doubly stochastic constraint satisfaction, which show convergence to a fixed point. The combination of good convergence properties and experimental success makes the softassign algorithm an excellent choice for neural quadratic assignment optimization.

Simple central pattern generator model using phasic analog neurons

Many biological neurons (called phasic or adapting neurons) display neural adaptation: their response to a constant input diminishes with time. A simple method of adding adaptive firing thresholds to existing analog (or graded-response) neural models is described. A half-center central pattern generator is modeled using two mutually inhibitory phasic analog neurons. Hopf bifurcation analysis shows that oscillatory solutions will arise if the mutual inhibition is sufficiently strong, and allows us to characterize the stability of the cycles which arise.

Absence of Cycles in Symmetric Neural Networks

For a given recurrent neural network, a discrete-time model may have asymptotic dynamics different from the one of a related continuous-time model. In this article, we consider a discrete-time model that discretizes the continuous-time leaky integrat or model and study its parallel, sequential, block-sequential, and distributed dynamics for symmetric networks. We provide sufficient (and in many cases necessary) conditions for the discretized model to have the same cycle-free dynamics of the corresponding continuous-time model in symmetric networks.