Header

UZH-Logo

Maintenance Infos

Solving constraint-satisfaction problems with distributed neocortical-like neuronal networks


Rutishauser, Ueli; Slotine, Jean-Jacques; Douglas, Rodney J. (2018). Solving constraint-satisfaction problems with distributed neocortical-like neuronal networks. Neural Computation, 30(5):1359-1393.

Abstract

Finding actions that satisfy the constraints imposed by both external inputs and internal representations is central to decision making. We demonstrate that some important classes of constraint satisfaction problems (CSPs) can be solved by networks composed of homogeneous cooperative-competitive modules that have connectivity similar to motifs observed in the superficial layers of neocortex. The winner-take-all modules are sparsely coupled by programming neurons that embed the constraints onto the otherwise homogeneous modular computational substrate. We show rules that embed any instance of the CSP's planar four-color graph coloring, maximum independent set, and sudoku on this substrate and provide mathematical proofs that guarantee these graph coloring problems will convergence to a solution. The network is composed of nonsaturating linear threshold neurons. Their lack of right saturation allows the overall network to explore the problem space driven through the unstable dynamics generated by recurrent excitation. The direction of exploration is steered by the constraint neurons. While many problems can be solved using only linear inhibitory constraints, network performance on hard problems benefits significantly when these negative constraints are implemented by nonlinear multiplicative inhibition. Overall, our results demonstrate the importance of instability rather than stability in network computation and offer insight into the computational role of dual inhibitory mechanisms in neural circuits.

Abstract

Finding actions that satisfy the constraints imposed by both external inputs and internal representations is central to decision making. We demonstrate that some important classes of constraint satisfaction problems (CSPs) can be solved by networks composed of homogeneous cooperative-competitive modules that have connectivity similar to motifs observed in the superficial layers of neocortex. The winner-take-all modules are sparsely coupled by programming neurons that embed the constraints onto the otherwise homogeneous modular computational substrate. We show rules that embed any instance of the CSP's planar four-color graph coloring, maximum independent set, and sudoku on this substrate and provide mathematical proofs that guarantee these graph coloring problems will convergence to a solution. The network is composed of nonsaturating linear threshold neurons. Their lack of right saturation allows the overall network to explore the problem space driven through the unstable dynamics generated by recurrent excitation. The direction of exploration is steered by the constraint neurons. While many problems can be solved using only linear inhibitory constraints, network performance on hard problems benefits significantly when these negative constraints are implemented by nonlinear multiplicative inhibition. Overall, our results demonstrate the importance of instability rather than stability in network computation and offer insight into the computational role of dual inhibitory mechanisms in neural circuits.

Statistics

Citations

Dimensions.ai Metrics
3 citations in Web of Science®
3 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

40 downloads since deposited on 08 Mar 2019
39 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Neuroinformatics
Dewey Decimal Classification:570 Life sciences; biology
Language:English
Date:May 2018
Deposited On:08 Mar 2019 12:58
Last Modified:25 Sep 2019 00:27
Publisher:MIT Press
Series Name:Neural computation
Number of Pages:35
ISSN:0899-7667
OA Status:Green
Publisher DOI:https://doi.org/10.1162/neco_a_01074
Related URLs:https://arxiv.org/abs/1801.04515
PubMed ID:29566357

Download

Green Open Access

Download PDF  'Solving constraint-satisfaction problems with distributed neocortical-like neuronal networks'.
Preview
Content: Accepted Version
Filetype: PDF
Size: 8MB
View at publisher