Constraint satisfaction problems and neural networks: A statistical physics perspective.

By M. M'ezard, Thierry Mora. 2008

131 citations recorded by the source corpus.

A new field of research is rapidly expanding at the crossroad between statistical physics, information theory and combinatorial optimization. In particular, the use of cutting edge statistical physics concepts and methods allow one to solve very large constraint satisfaction problems like random satisfiability, coloring, or error correction. Several aspects of these developments should be relevant for the understanding of functional complexity in neural networks. On the one hand the message passing procedures which are used in these new algorithms are based on local exchange of information, and succeed in solving some of the hardest computational problems. On the other hand some crucial inference problems in neurobiology, like those generated in multi-electrode recordings, naturally translate into hard constraint satisfaction problems. This paper gives a non-technical introduction to this field, emphasizing the main ideas at work in message passing strategies and their possible relevance to neural networks modelling. It also introduces a new message passing algorithm for inferring interactions between variables from correlation data, which could be useful in the analysis of multi-electrode recording data.

Subfields: Artificial Intelligence, Cognitive Neuroscience, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Cognitive Neuroscience

In Computer Networks and Communications

Citations in the corpus

Protein 3D Structure Computed from Evolutionary Sequence Variation (2011, neutral): “optimization problem are of the form [11,45,49]:”
Direct-coupling analysis of residue coevolution captures native contacts across many protein families (2011, methodology): “[1] we used a message-passing algorithm originally proposed in [5], [6] uses improved Monte Carlo sampling, [7–”
Dissecting the Specificity of Protein-Protein Interaction in Bacterial Two-Component Signaling: Orphans and Crosstalks (2011, methodology): “We previously described a sequence-based computational approach, referred to as Direct-Coupling Analysis (DCA) [15,16] and based on a message-passing algorithm [17].”
Inverse statistical problems: from the inverse Ising problem to data science (2017, methodology): “This approach, termed susceptibility propagation, was developed by Welling and Teh [221, 222] for the forward problem and independently and by M´ezard and Mora [8, 131] for the inverse Ising problem, where also the couplings are updated at each step.”
Inference of direct residue contacts in two-component signaling. (2010, methodology): “…in the second section is given in detail in Weigt et al. (2009) and based on standard Belief Propagation methods described in Kschischang et al. (2001), Mezard and Mora (2009), and Yedidia et al. (2001), we will dispense with the derivation and describe only implementation in concrete terms.”
Spin glass models for a network of real neurons (2009, methodology): “For larger systems, this “inverse Ising problem” or Boltzmann machine learning, as it is known in computer science [49], is a hard computational problem that has to be solved by approximate schemes [14, 15, 21].”
Are Biological Systems Poised at Criticality? (2010, methodology): “The distribution was approximately fitted to the data using mean field techniques [37, 59].”