14 - Discussion and open issues

Summary

In the long journey undertaken in this book, we have visited statistical mechanics, constraint satisfaction problems and satisfiability, complex networks and natural systems, and, in particular, many facets of machine learning ranging from propositional to relational learning, grammatical inference, and neural networks. The thread that connects all these fields is the emergence of phenomena exhibiting sharp discontinuities. These phenomena are reminiscent of the phase transitions found in physics and, indeed, the methods of statistical physics have been employed with success to analyze them. In this chapter we try to summarize what we have learned from these connections and in particular from the role played by machine learning. Our aim is to point out gaps in the understanding of basic phenomena and to identify open questions that may suggest future research directions.

Phase transitions or threshold phenomena?

In a recent and very interesting paper, which recalls similar arguments put forwards in Percus et al. (2006), Zweig et al. (2010) have challenged the current view of phase transitions in computational problems, wondering whether the abrupt change observed in the probability of solution (the order parameter) in SAT problems is in fact nothing other than a “self-fulfilling” discontinuity, i.e., an existential discontinuity generated by the very definitions of the problem and of the order parameter.

The first argument in support of their claim is that it is easy to produce rather simple models that exhibit phase transition phenomena while, as most of us would agree, the essential ingredients that underly a “true” phase transition are lacking.