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 as well as sequence learning methodologies. In Phase Transitions in Machine Learning the authors begin by describing in detail this phenomenon, and the extensive experimental investigation that supports its presence. They then turn their attention to the possible implications and explore appropriate 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 AI and other computer science communities. Open research issues are also discussed, suggesting promising directions for future research. Cover......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Contents......Page 7 Preface......Page 11 Acknowledgments......Page 15 Notation......Page 16 1 Introduction......Page 19 2.1 Basic notions of statistical physics......Page 30 2.2.1 Microcanonical ensemble......Page 37 2.2.2 Canonical ensemble and Gibbs distribution......Page 38 2.2.3 Grand canonical ensemble......Page 40 2.3 Phase transitions......Page 41 2.4 Ising models......Page 44 2.4.1 One-dimensional Ising model......Page 45 2.4.2 Two-dimensional Ising model......Page 47 2.5 Mean field theory......Page 50 2.6 Quenched disorder and self-averaging......Page 51 2.6.1 Self-averaging quantities......Page 54 2.7 Replica method......Page 55 2.8 Cavity method......Page 57 2.9 Comments......Page 60 3.1 General framework......Page 61 3.2 Random graphs......Page 63 3.3 The SAT problem......Page 67 3.3.1 SAT problems and the Ising model......Page 71 3.3.2 Structure of the solution space......Page 76 3.3.3 Backbone......Page 78 3.3.4 Backdoors......Page 79 3.4 The random (2+p)-SAT......Page 80 3.5 Solving the SAT problem......Page 81 3.5.1 Exact SAT solvers......Page 82 3.5.3 MaxSAT solvers......Page 83 3.5.4 Survey propagation......Page 84 3.6 Comments......Page 86 4 Constraint satisfaction problems......Page 88 4.1 Algorithms for solving CSPs......Page 91 4.1.1 Generate and test with backtracking......Page 92 4.1.2 Constraint propagation......Page 94 4.1.4 MaxCSP......Page 95 4.1.5 Constraint logic programming......Page 96 4.2 Generative models for CSPs......Page 97 4.3 Phase transition in a CSP......Page 99 4.3.1 Asymptotic behavior......Page 103 4.3.2 New models......Page 104 4.4 Comments......Page 107 5 Machine learning......Page 110 5.1 Concept learning......Page 111 5.1.1 A formal view of concept learning......Page 112 5.1.2 Concept learning in three questions......Page 114 5.1.3 Searching the hypothesis space......Page 116 5.1.4 Hypothesis space with generality relationships......Page 119 5.1.5 Learning in a hypothesis space with a generality relationship......Page 122 5.2 Representation languages......Page 124 5.2.1 Propositional representation......Page 125 5.2.3 The problem setting......Page 129 Data representation as multiple (attribute, value) vectors......Page 130 The Horn clause representation language......Page 131 Multiple vector representations are mapped to sets of ground assertions......Page 132 Concept definitions are mapped to sets of clauses......Page 133 Covering test in first-order logic......Page 136 5.2.4 Sequence or string representation......Page 138 Learning to accomplish sequence tagging......Page 139 5.3 Comments......Page 140 6 Searching the hypothesis space......Page 142 6.1.1 Greedy search guided by information gain......Page 143 6.1.2 Lifting information gain to first order......Page 147 6.2 FOIL: information gain......Page 149 6.3 SMART+: beam search......Page 150 6.4 G-Net: genetic evolution......Page 151 6.5 PROGOL: exhaustive search......Page 152 6.6 Plateaus......Page 153 6.7 Comments......Page 157 7.1 Artificial neural networks......Page 158 7.1.1 The perceptron......Page 163 7.1.2 Multi-layer perceptrons......Page 168 7.2.1 Learning Boolean functions......Page 170 7.2.2 Support vector machines......Page 172 7.2.3 Decision tree induction......Page 174 7.2.4 k-term DNF learning......Page 177 7.2.5 Vector quantization......Page 179 7.3 Relational learning......Page 181 7.3.1 Sequence learning......Page 184 7.4 Comments......Page 185 8.1 Reducing propositional learning to SAT......Page 186 8.2 Phase transitions and local search in propositional learning......Page 193 8.3 The FOL covering test as a CSP......Page 196 8.4 Relation between CSP and SAT......Page 197 8.5 Comments......Page 201 9 Phase transition in FOL covering test......Page 202 9.1 Model RL......Page 203 Control parameters characterizing learning examples......Page 204 9.1.2 Model assumptions......Page 205 9.1.3 Matching problem generation......Page 208 9.2 The search algorithm......Page 213 9.3.1 Probability of solution......Page 216 9.3.2 Search complexity......Page 218 9.4.1 Explaining the findings with model RL......Page 220 9.4.2 Comparison with model B......Page 224 9.4.3 Asymptotic behavior and model RB......Page 231 9.5 Smart algorithms for the covering test......Page 232 9.6 Comments......Page 235 10 Phase transitions and relational learning......Page 238 10.1 The experimental setting......Page 239 10.1.1 Generating artificial learning problems......Page 240 10.1.2 The learners......Page 243 10.2 Experimental results......Page 247 10.2.1 Predictive accuracy......Page 248 10.2.2 Concept identification......Page 249 10.3 Result interpretation......Page 253 10.3.1 Phase transition as an attractor......Page 254 10.3.2 Correct identification of the target concept......Page 258 10.3.3 Backtrack and domain knowledge......Page 261 10.3.4 Correct approximation of the target concept......Page 262 10.4 Beyond general-to-specific learning strategies......Page 265 10.4.1 A stochastic approach......Page 267 10.4.2 Improving the stochastic search algorithm......Page 271 10.5 Comments......Page 273 11.1 Learning grammars......Page 276 11.1.1 The task of inferring grammars......Page 277 11.1.2 An introductory example......Page 279 Basic notions......Page 280 Regular grammars......Page 283 Deterministic finite state automata......Page 284 Language accepted by a finite automaton......Page 285 11.1.4 Learning automata......Page 286 Derived automata......Page 287 A lattice over the space of automata......Page 288 Structural completeness......Page 290 11.3 A phase transition in learning automata?......Page 292 11.4.1 The experimental protocol......Page 293 11.4.2 The findings......Page 295 11.5.1 Evidence for abrupt changes when generalizing......Page 296 11.5.2 The generalization landscape in the NFA case......Page 299 11.5.3 The generalization landscape in the DFA case......Page 303 11.6 Consequences of the behavior of the learning algorithms: how bad is it?......Page 311 11.6.2 The coverage rates of the target and learned automata......Page 312 11.6.3 Generalization error......Page 314 11.6.4 The control strategies and their impact......Page 315 11.7 Comments......Page 316 12 Phase transitions in complex systems......Page 318 12.1 Complex systems......Page 319 12.2 Statistical physics and the social sciences......Page 322 Voter model......Page 323 Social impact theory......Page 324 12.2.2 Social and cultural dynamics......Page 325 12.3 Communication and computation networks......Page 327 12.4 Biological networks......Page 328 12.5 Comments......Page 329 13 Phase transitions in natural systems......Page 331 13.1 Comments......Page 335 14 Discussion and open issues......Page 337 14.1 Phase transitions or threshold phenomena?......Page 338 14.2 Do phase transitions occur in practice?......Page 345 14.3 Blind spot......Page 347 14.5 Machine learning and SAT or CSP solvers......Page 349 14.6 Relational learning and complex networks......Page 351 14.7 Relational machine learning perspective......Page 352 A priori knowledge......Page 354 Abstraction......Page 355 A.1 Mutagenesis dataset......Page 357 A.2 Mechanical troubleshooting datasets......Page 365 Appendix B: An intriguing idea......Page 369 References......Page 373 Index......Page 393 Cover 1 Half-title 3 Title 5 Copyright 6 Contents 7 Preface 11 Acknowledgments 15 Notation 16 1 Introduction 19 2 Statistical physics and phase transitions 30 2.1 Basic notions of statistical physics 30 2.2 Ensemble of states 37 2.2.1 Microcanonical ensemble 37 2.2.2 Canonical ensemble and Gibbs distribution 38 2.2.3 Grand canonical ensemble 40 2.3 Phase transitions 41 2.4 Ising models 44 2.4.1 One-dimensional Ising model 45 2.4.2 Two-dimensional Ising model 47 2.5 Mean field theory 50 2.6 Quenched disorder and self-averaging 51 2.6.1 Self-averaging quantities 54 2.7 Replica method 55 2.8 Cavity method 57 2.9 Comments 60 3 The satisfiability problem 61 3.1 General framework 61 3.2 Random graphs 63 3.3 The SAT problem 67 3.3.1 SAT problems and the Ising model 71 3.3.2 Structure of the solution space 76 3.3.3 Backbone 78 3.3.4 Backdoors 79 3.4 The random (2+p)-SAT 80 3.5 Solving the SAT problem 81 3.5.1 Exact SAT solvers 82 3.5.2 Incomplete SAT solvers 83 3.5.3 MaxSAT solvers 83 3.5.4 Survey propagation 84 3.6 Comments 86 4 Constraint satisfaction problems 88 4.1 Algorithms for solving CSPs 91 4.1.1 Generate and test with backtracking 92 4.1.2 Constraint propagation 94 4.1.3 Local search 95 4.1.4 MaxCSP 95 4.1.5 Constraint logic programming 96 4.2 Generative models for CSPs 97 4.3 Phase transition in a CSP 99 4.3.1 Asymptotic behavior 103 4.3.2 New models 104 4.4 Comments 107 5 Machine learning 110 5.1 Concept learning 111 5.1.1 A formal view of concept learning 112 5.1.2 Concept learning in three questions 114 5.1.3 Searching the hypothesis space 116 5.1.4 Hypothesis space with generality relationships 119 5.1.5 Learning in a hypothesis space with a generality relationship 122 5.2 Representation languages 124 5.2.1 Propositional representation 125 5.2.2 Relational representation 129 5.2.3 The problem setting 129 Data representation as multiple (attribute, value) vectors 130 The Horn clause representation language 131 Multiple vector representations are mapped to sets of ground assertions 132 Concept definitions are mapped to sets of clauses 133 Covering test in first-order logic 136 5.2.4 Sequence or string representation 138 Learning to predict a property of the next item 139 Learning to identify the generative process for a sequence 139 Learning to accomplish sequence tagging 139 The hypothesis space 140 5.3 Comments 140 6 Searching the hypothesis space 142 6.1 Guiding the search in the hypothesis space 143 6.1.1 Greedy search guided by information gain 143 6.1.2 Lifting information gain to first order 147 6.2 FOIL: information gain 149 6.3 SMART+: beam search 150 6.4 G-Net: genetic evolution 151 6.5 PROGOL: exhaustive search 152 6.6 Plateaus 153 6.7 Comments 157 7 Statistical physics and machine learning 158 7.1 Artificial neural networks 158 7.1.1 The perceptron 163 7.1.2 Multi-layer perceptrons 168 7.2 Propositional learning approaches 170 7.2.1 Learning Boolean functions 170 7.2.2 Support vector machines 172 7.2.3 Decision tree induction 174 7.2.4 k-term DNF learning 177 7.2.5 Vector quantization 179 7.3 Relational learning 181 7.3.1 Sequence learning 184 7.4 Comments 185 8 Learning, SAT, and CSP 186 8.1 Reducing propositional learning to SAT 186 8.2 Phase transitions and local search in propositional learning 193 8.3 The FOL covering test as a CSP 196 8.4 Relation between CSP and SAT 197 8.5 Comments 201 9 Phase transition in FOL covering test 202 9.1 Model RL 203 9.1.1 The control parameters 204 Control parameters characterizing learning examples 204 Control parameters depending on the hypothesis description 205 9.1.2 Model assumptions 205 9.1.3 Matching problem generation 208 9.2 The search algorithm 213 9.3 Experimental analysis 216 9.3.1 Probability of solution 216 9.3.2 Search complexity 218 9.4 Comparing model RL with other models for CSP generation 220 9.4.1 Explaining the findings with model RL 220 9.4.2 Comparison with model B 224 9.4.3 Asymptotic behavior and model RB 231 9.5 Smart algorithms for the covering test 232 9.6 Comments 235 10 Phase transitions and relational learning 238 10.1 The experimental setting 239 10.1.1 Generating artificial learning problems 240 10.1.2 The learners 243 10.2 Experimental results 247 10.2.1 Predictive accuracy 248 10.2.2 Concept identification 249 10.2.3 Computational complexity 253 10.3 Result interpretation 253 10.3.1 Phase transition as an attractor 254 10.3.2 Correct identification of the target concept 258 10.3.3 Backtrack and domain knowledge 261 10.3.4 Correct approximation of the target concept 262 10.4 Beyond general-to-specific learning strategies 265 10.4.1 A stochastic approach 267 10.4.2 Improving the stochastic search algorithm 271 10.5 Comments 273 11 Phase transitions in grammatical inference 276 11.1 Learning grammars 276 11.1.1 The task of inferring grammars 277 11.1.2 An introductory example 279 11.1.3 Automata and grammars 280 Basic notions 280 Regular grammars 283 Finite automata 284 Deterministic finite state automata 284 Language accepted by a finite automaton 285 Nondeterministic finite state Automata 286 11.1.4 Learning automata 286 11.2 Grammatical inference by generalization 287 11.2.1 The space of finite automata 287 Derived automata 287 A lattice over the space of automata 288 11.2.2 A structure for the space of finite automata 290 Structural completeness 290 11.3 A phase transition in learning automata? 292 11.4 The covering test: random sampling in H 293 11.4.1 The experimental protocol 293 11.4.2 The findings 295 11.5 Learning, hypothesis sampling, and phase transitions 296 11.5.1 Evidence for abrupt changes when generalizing 296 11.5.2 The generalization landscape in the NFA case 299 11.5.3 The generalization landscape in the DFA case 303 11.6 Consequences of the behavior of the learning algorithms: how bad is it? 311 11.6.1 Experimental setting 312 11.6.2 The coverage rates of the target and learned automata 312 11.6.3 Generalization error 314 11.6.4 The control strategies and their impact 315 11.7 Comments 316 12 Phase transitions in complex systems 318 12.1 Complex systems 319 12.2 Statistical physics and the social sciences 322 12.2.1 Opinion dynamics 323 Voter model 323 Majority rule model 324 Social impact theory 324 12.2.2 Social and cultural dynamics 325 12.3 Communication and computation networks 327 12.4 Biological networks 328 12.5 Comments 329 13 Phase transitions in natural systems 331 13.1 Comments 335 14 Discussion and open issues 337 14.1 Phase transitions or threshold phenomena? 338 14.2 Do phase transitions occur in practice? 345 14.3 Blind spot 347 14.4 Number of examples 349 14.5 Machine learning and SAT or CSP solvers 349 14.6 Relational learning and complex networks 351 14.7 Relational machine learning perspective 352 Propositionalization 354 A priori knowledge 354 Abstraction 355 Appendix A: Phase transitions detected in two real cases 357 A.1 Mutagenesis dataset 357 A.2 Mechanical troubleshooting datasets 365 Appendix B: An intriguing idea 369 References 373 Index 393 Machine generated contents note: Preface; Acknowledgements; 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. Relationships with complex systems; 13. Phase transitions in natural systems; 14. Discussions and open issues; Appendix A. Phase transitions detected in two real cases; Appendix B. An intriguing idea; References; Index. "Phase transitions typically occur in combinatorial computational problems and have important consequences, especially with the current spread of statistical relational learning and as sequence learning methodologies. In Phase Transitions in Machine Learning the authors begin by describing in detail this phenomenon and the extensive experimental investigation that supports its presence. They then turn their attention to the possible implications and explore appropriate methods for tackling them"-- Provided by publisher This state-of-the-art overview describes how phase transitions occur and teaches appropriate methods for tackling the consequent problems. Weaving together fundamental aspects of computer science, statistical physics and machine learning, it provides sufficient mathematics and physics background to make the subject intelligible to researchers in AI and other computer science communities.