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 biological 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.