Cliques, computation, and computational tractability
We describe a class of computations that is motivated by a model of line and edge detection in primary visual cortex, although the computations here are expressed in general, abstract terms. The model consists of a collection of processing units (artificial neurons) that are organized into cliques of tightly inter-connected units. Our analysis is based on a dynamic analog model of computation, a model that is classically used to motivate gradient descent algorithms that seek extrema of energy functionals. We introduce a new view of these equations, however, and explicitly use discrete techniques from game theory to show that such cliques can achieve equilibrium in a computationally efficient manner. Furthermore, we are able to prove that the equilibrium is the same as that which would have been found by a gradient descent algorithm. The result is a new class of computations that. while related to traditional gradient-following computations such as relaxation labeling and Hopfield artificial neural networks, enjoys a different and provably efficient dynamics. The implications of the model extend beyond efficient artificial neural networks to (i) timing considerations in iological neural networks; (ii) to building reliable networks from less-reliable elements; (iii) to building accurate representations from less-accurate components; and, most generally, to (iv) demonstrating an interplay between continuous "dynamical systems" and discrete "pivoting" algorithms. (C) 2000 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
game theory relaxation labeling dynamical system energy minimization linear complementarity problem early vision polymatrix games complexity