Recurrent networks of coupled Winner-Take-All oscillators for solving constraint satisfaction problems
We present a recurrent neuronal network, modeled as a continuous-time dynamical system, that can solve constraint satisfaction problems. Discrete variables are represented by coupled Winner-Take-All (WTA) networks, and their values are encoded in localized patterns of oscillations that are learned by the recurrent weights in these networks. Constraints over the variables are encoded in the network connectivity. Although there are no sources of noise, the network can escape from local optima in its search for solutions that satisfy all constraints by modifying the effective network connectivity through oscillations. If there is no solution that satisfies all constraints, the network state changes in a seemingly random manner and its trajectory approximates a sampling procedure that selects a variable assignment with a probability that increases with the fraction of constraints satisfied by this assignment. External evidence, or input to the network, can force variables to specific values. When new inputs are applied, the network re-evaluates the entire set of variables in its search for states that satisfy the maximum number of constraints, while being consistent with the external input. Our results demonstrate that the proposed network architecture can perform a deterministic search for the optimal solution to problems with non-convex cost functions. The network is inspired by canonical microcircuit models of the cortex and suggests possible dynamical mechanisms to solve constraint satisfaction problems that can be present in biological networks, or implemented in neuromorphic electronic circuits.
Overview: The paper studies a neuro-dynamic 
      system that is able to solve constraint satisfaction problems (CSP). 
      The dynamic equations for neural interaction and synaptic 
      weight-changes are relatively straight-forward (equations 1 and 2), 
      the archictectures of the networks are relatively complex. The 
      elementary computational units Are winner-take-all (WTA) type networks 
      that oscillate. It is stated that a crucial property of the elementary 
      circuits is their sensitivity to input only at specific points of 
      their oscillatory period(s). If the connectivity between such WTA 
      units is chosen to reflect a CSP, it is stated that the dynamics 
      finally settles into a state that represents a solution to the CSP. 
      Simulations of the neuro-dynamics for small and intermediately large 
      CSPs empirically show that the neuro-dynamics can find solutions, and 
      that it can find approximately optimal solutions if there are no fully 
      consistent variable assignments. Evaluation: The 
      paper is generally well written and the main points become clear. The 
      question what computations neural circuits perform and how they are 
      performed is certainly important and interesting. There is also 
      evidence for WTA mechanisms that implement a form of possible 
      competition between neural untis. Also the effectiveness of input 
      during certain points of the phase is an interesting property because 
      a small input differences can be amplified (and response can be 
      normalized). Even if weakly coupled to an input, such networks can be 
      very sensitive. While the general setup is clear, I was missing a 
      more extensive discussion about the parameters of the network. Usually 
      such parameters have to be tuned. It does not become clear how 
      difficult this is for the suggested system. Also a discussion of 
      related neuro-dynamic approaches is missing. Neural dynamics that 
      become sensitive to input in a critical period of their oscillation have 
      been described before, sometimes in the form of sensitivity to initial 
      states. Such networks all have a WTA characteristics and at least some 
      should be discussed (see, e.g., work by O'Reilly, 2001; Spratling and 
      Johnson, 2002; Lucke, Malsburg, 2004). The difference to the here 
      discussed system is the goal: here it is finding solutions to CSPs, 
      the other networks address component finding in data. Finding CSP 
      solutions is a well accepted problem in computer science but it 
      becomes much less clear why biological networks should be optimized 
      for such a problem - please discuss. Still it is interesting from a 
      technical point, and I agree that implementations of inherently 
      parallel neuro-dynamic approaches via analog VLSI are very 
      interesting. In this respect please discuss two questions, however: 
      (1) isn't the complexity of the problem mapped into the complexity of 
      the network architecture? (2) can one be confident that the problem 
      solving dynamics do not break down if the problem sizes are scaled up? 
      What about the total number of variables? The behavior of the 
      network is interesting including the behavior for not fully 
      satisfiable problems. The empirical finding of exponential scaling is 
      not uninteresting but the sampling analogy is taken too far for my 
      taste. The energy function could also be used for the satisfiable 
      problem (Sec. 3.1). But if the network remains in a solution there, it 
      is not spending time proportional to exp(-cE). Additionally, the 
      authors themselves say that the network will probably not explore 
      high-energy states. So there is only a coarse analogy here as far as I 
      can see. Also the criticism of other approaches is too general. Of 
      course there are many approaches on the technical side that have 
      similar properties. Also it is not clear how computationally costly 
      the mechanisms to avoid local optima really are for the studied 
      dynamics - time to find optimal solutions may scale exponentially with 
      problem size - or the architecture does. In response to author 
      feedback: The feedback has clarified most of my questions. I agree 
      that scalability will be exponential in the worst case. What would be 
      interesting, though, is how the average time to find a solution scales 
      with problem size. This should be a point for the revised discussion. 
      I also assume that more care is taken regarding the too broad 
      criticism of other approaches, that it is discussed why CSP solving is 
      interesting for biological systems and about the analogy to sampling. 
      Given these improvements, I remain happy with my initial score.