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

Overview

This directory contains Matlab code to solve constraint satisfaction problems with networks of winner-take-all networks. This is achieved by translating a description of the problem to be solved (the constraints) into a network of winner-take-all modules (WTAs) implemented as a collection of continously valued simulated neurons. This network is then numerically integrated to derive a solution.

The purpose of this released code is to reproduces key aspects of this paper:

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

Abstract of above paper to summarize the overall aim:

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.

The key theoretical concepts used to make these networks work are explained in this paper:

U. Rutishauser, JJ. Slotine, RJ. Douglas. Computation in dynamically bounded asymmetric systems. PLOS Computational Biology, 11(1): e1004039 (2015). Fulltext

Also see this page for code related to our earlier WTA papers.

This work is the result of a long-standing collaboration between Ueli Rutishauser, Jean-Jacques Slotine, and Rodney Douglas. The work is (c) by Caltech, MIT, ETH Zurich/University Zurich, and Cedars-Sinai.

This code is released as-is for academic purposes. Feel free to use and re-use as you see fit. Uploaded January 2019, Ueli Rutishauser. www.rutishauserlab.org

How to get started

Download the entire repository. Then, adjust and run setpath_graph.m to set the path. Then, execute one of the main functions listed below.

List of key functions (main)

mainSimpleRecurrence.m Simple example that illustrates how two coupled WTAs can hold a state after offset of input.

simpleRecurrence_DBcells_twoWinnersOnly_Fig2.m Simple example that illustrates the concept of negative constraint cells (also called "DB cells" in the code). This function reproduces Figure 2 of the paper.

mainWTA_graphColoring_Fig3.m Simple graph coloring example (4 nodes). Reproduces Figure 3 of the paper.

mainWTA_graphColoring_Fig4.m 4-coloring of random planar graphs of arbitrary size. Reproduces Figure 4 of the paper.

mainWTA_graphColoring_Fig5.m Solving the MIS problem with graph coloring. Reproduces Figure 5 of the paper.

mainWTA_graphColoring_Fig6.m Solves sudoku problems. Reproduces Figure 6 of the paper.

List of key functions (internal, called from others)

mainWTA_graphColoring_run1.m The main function. Setups up the network, executes it (using runN_*, see below), and evaluates the result.

runN_WTA_withDBs_optimized_shunt.m Function that does the numerical integration of the network.

3rd Party tools used

Apart from Matlab, the following 3rd Party tools are used.

Required (included in release for convenience):

1. Boost Graph Library, MatlabBGL version
2. GraphViz2Mat

Optimal:

1. JFLAP (+Java) (http://jflap.org)
2. graphviz

XML Graph format

The WTA code stores and reads arbitrarily generated random planar graphs (or the sudoku graph) stores as JFF files. JFF files are XML files that describe a graph. A convenient way to edit and view these graphs is JFLAP, a java utility.

Graph files that are used:

1. sudoku_s1.jff
2. maxIndpSet_Fig5A.jff (Fig 5A graph)
3. graph3.jff (Fig 3A graph)
4. exportRand_*.jff (Fig 4 and 5 randomly generated planar graphs)

Layouting of graphs

Two ways to layout (plot) the resulting graph coloring solutions are implemented: Using the boost graph library (matlab_bgl) or by exporting a .dot file and running graphviz (dot).