Phase transitions in machine learning

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