This page intentionally left blank Phase Transitions in Machine Learning Phase transitions typically occur in combinatorial computational problems and have important consequences, especially with the current spread of statistical relational learning and of sequence learning methodologies. In Phase Transi- tions in Machine Learning the authors begin by describing in detail this phe- nomenon and the extensive experimental investigation that supports its presence. They then turn their attention to the possible implications and explore appropri- ate methods for tackling them. Weaving together fundamental aspects of computer science, statistical physics, and machine learning, the book provides sufficient mathematics and physics background to make the subject intelligible to researchers in the artifi- cial intelligence and other computer science communities. Open research issues, suggesting promising directions for future research, are also discussed. LORENZA SA I TTA is Full Professor of Computer Science at the University of Piemonte Orientale, Italy. ATT I L I O G IORDANA is Full Professor of Computer Science at the Univer- sity of Piemonte Orientale, Italy. ANTO INE CORNU E´ JOL S is Full Professor of Computer Science at the AgroParisTech Engineering School, Paris. Phase Transitions in Machine Learning LORENZA SAITTA University of Piemonte Orientale, Italy ATTILIO GIORDANA University of Piemonte Orientale, Italy ANTOINE CORNUE´ JOLS AgroParisTech Engineering School, Paris, France CAMBR IDGE UN IVERS I TY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sa˜ o Paulo, Delhi, Tokyo, Mexico City Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521763912 ⃝C L. Saitta, A. Giordana and A. Cornue´jols 2011 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2011 Printed in the United Kingdom at the University Press, Cambridge A catalogue record for this publication is available from the British Library ISBN 978-0-521-76391-2 Hardback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Contents Preface page ix Acknowledgments xiii Notation xiv 1 Introduction 1 2 Statistical physics and phase transitions 12 2.1 Basic notions of statistical physics 12 2.2 Ensemble of states 19 2.3 Phase transitions 23 2.4 Ising models 26 2.5 Mean field theory 32 2.6 Quenched disorder and self-averaging 33 2.7 Replica method 37 2.8 Cavity method 39 2.9 Comments 42 3 The satisfiability problem 43 3.1 General framework 43 3.2 Random graphs 45 3.3 The SAT problem 49 3.4 The random (2 + p)-SAT 62 3.5 Solving the SAT problem 63 3.6 Comments 68 4 Constraint satisfaction problems 70 4.1 Algorithms for solving CSPs 73 4.2 Generative models for CSPs 79 4.3 Phase transition in a CSP 81 4.4 Comments 89 v vi Contents 5 Machine learning 92 5.1 Concept learning 93 5.2 Representation languages 106 5.3 Comments 122 6 Searching the hypothesis space 124 6.1 Guiding the search in the hypothesis space 125 6.2 FOIL: information gain 131 6.3 SMART+: beam search 132 6.4 G-Net: genetic evolution 133 6.5 PROGOL: exhaustive search 134 6.6 Plateaus 135 6.7 Comments 139 7 Statistical physics and machine learning 140 7.1 Artificial neural networks 140 7.2 Propositional learning approaches 152 7.3 Relational learning 163 7.4 Comments 167 8 Learning, SAT, and CSP 168 8.1 Reducing propositional learning to SAT 168 8.2 Phase transitions and local search in propositional learning 175 8.3 The FOL covering test as a CSP 178 8.4 Relation between CSP and SAT 179 8.5 Comments 183 9 Phase transition in FOL covering test 184 9.1 Model RL 185 9.2 The search algorithm 195 9.3 Experimental analysis 198 9.4 Comparing model RL with other models for CSP generation 202 9.5 Smart algorithms for the covering test 214 9.6 Comments 217 10 Phase transitions and relational learning 220 10.1 The experimental setting 221 10.2 Experimental results 229 10.3 Result interpretation 235 10.4 Beyond general-to-specific learning strategies 247 10.5 Comments 255 Contents vii 11 Phase transitions in grammatical inference 258 11.1 Learning grammars 258 11.2 Grammatical inference by generalization 269 11.3 A phase transition in learning automata? 274 11.4 The covering test: random sampling in H 275 11.5 Learning, hypothesis sampling, and phase transitions 278 11.6 Consequences of the behavior of the learning algorithms: how bad is it? 293 11.7 Comments 298 12 Phase transitions in complex systems 300 12.1 Complex systems 301 12.2 Statistical physics and the social sciences 304 12.3 Communication and computation networks 309 12.4 Biological networks 310 12.5 Comments 311 13 Phase transitions in natural systems 313 13.1 Comments 317 14 Discussion and open issues 319 14.1 Phase transitions or threshold phenomena? 320 14.2 Do phase transitions occur in practice? 327 14.3 Blind spot 329 14.4 Number of examples 331 14.5 Machine learning and SAT or CSP solvers 331 14.6 Relational learning and complex networks 333 14.7 Relational machine learning perspective 334 Appendix A Phase transitions detected in two real cases 339 A.1 Mutagenesis dataset 339 A.2 Mechanical troubleshooting datasets 347 Appendix B An intriguing idea 351 References 355 Index 375