Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgments
- Notation
- 1 Introduction
- 2 Statistical physics and phase transitions
- 3 The satisfiability problem
- 4 Constraint satisfaction problems
- 5 Machine learning
- 6 Searching the hypothesis space
- 7 Statistical physics and machine learning
- 8 Learning, SAT, and CSP
- 9 Phase transition in FOL covering test
- 10 Phase transitions and relational learning
- 11 Phase transitions in grammatical inference
- 12 Phase transitions in complex systems
- 13 Phase transitions in natural systems
- 14 Discussion and open issues
- Appendix A Phase transitions detected in two real cases
- Appendix B An intriguing idea
- References
- Index
14 - Discussion and open issues
Published online by Cambridge University Press: 05 August 2012
- Frontmatter
- Contents
- Preface
- Acknowledgments
- Notation
- 1 Introduction
- 2 Statistical physics and phase transitions
- 3 The satisfiability problem
- 4 Constraint satisfaction problems
- 5 Machine learning
- 6 Searching the hypothesis space
- 7 Statistical physics and machine learning
- 8 Learning, SAT, and CSP
- 9 Phase transition in FOL covering test
- 10 Phase transitions and relational learning
- 11 Phase transitions in grammatical inference
- 12 Phase transitions in complex systems
- 13 Phase transitions in natural systems
- 14 Discussion and open issues
- Appendix A Phase transitions detected in two real cases
- Appendix B An intriguing idea
- References
- Index
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.
- Type
- Chapter
- Information
- Phase Transitions in Machine Learning , pp. 319 - 338Publisher: Cambridge University PressPrint publication year: 2011