Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks
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 mod...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
MIT Press - Journals
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120124 https://orcid.org/0000-0002-7161-7812 |
| _version_ | 1826188864763461632 |
|---|---|
| author | Rutishauser, Ueli Douglas, Rodney J. Slotine, Jean-Jacques E |
| author2 | Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences |
| author_facet | Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences Rutishauser, Ueli Douglas, Rodney J. Slotine, Jean-Jacques E |
| author_sort | Rutishauser, Ueli |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:05:52Z |
| format | Article |
| id | mit-1721.1/120124 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:05:52Z |
| publishDate | 2019 |
| publisher | MIT Press - Journals |
| record_format | dspace |
| spelling | mit-1721.1/1201242022-09-23T10:54:42Z Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks Rutishauser, Ueli Douglas, Rodney J. Slotine, Jean-Jacques E Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences Massachusetts Institute of Technology. Department of Mechanical Engineering Slotine, Jean-Jacques E 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. 2019-01-24T18:26:18Z 2019-01-24T18:26:18Z 2018-04 2019-01-03T15:15:21Z Article http://purl.org/eprint/type/JournalArticle 0899-7667 1530-888X http://hdl.handle.net/1721.1/120124 Rutishauser, Ueli, Jean-Jacques Slotine, and Rodney J. Douglas. “Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks.” Neural Computation 30, no. 5 (May 2018): 1359–1393. © 2018 Massachusetts Institute of Technology https://orcid.org/0000-0002-7161-7812 http://dx.doi.org/10.1162/NECO_A_01074 Neural Computation Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf MIT Press - Journals MIT Press |
| spellingShingle | Rutishauser, Ueli Douglas, Rodney J. Slotine, Jean-Jacques E Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks |
| title | Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks |
| title_full | Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks |
| title_fullStr | Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks |
| title_full_unstemmed | Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks |
| title_short | Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks |
| title_sort | solving constraint satisfaction problems with distributed neocortical like neuronal networks |
| url | http://hdl.handle.net/1721.1/120124 https://orcid.org/0000-0002-7161-7812 |
| work_keys_str_mv | AT rutishauserueli solvingconstraintsatisfactionproblemswithdistributedneocorticallikeneuronalnetworks AT douglasrodneyj solvingconstraintsatisfactionproblemswithdistributedneocorticallikeneuronalnetworks AT slotinejeanjacquese solvingconstraintsatisfactionproblemswithdistributedneocorticallikeneuronalnetworks |