Foundations of Machine Learning

Contents......Page 6
Preface......Page 14
1.1 What is machine learning?......Page 18
1.2 What kind of problems can be tackled using machine learning?......Page 19
1.3 Some standard learning tasks......Page 20
1.4 Learning stages......Page 21
1.5 Learning scenarios......Page 23
1.6 Generalization......Page 24
2.1 The PAC learning model......Page 26
2.2 Guarantees for finite hypothesis sets — consistent case......Page 32
2.3 Guarantees for finite hypothesis sets — inconsistent case......Page 36
2.4.1 Deterministic versus stochastic scenarios......Page 38
2.4.2 Bayes error and noise......Page 39
2.6 Exercises......Page 40
3. Rademacher Complexity and VC-Dimension......Page 46
3.1 Rademacher complexity......Page 47
3.2 Growth function......Page 51
3.3 VC-dimension......Page 53
3.4 Lower bounds......Page 60
3.5 Chapter notes......Page 65
3.6 Exercises......Page 67
4.1 Estimation and approximation errors......Page 78
4.2 Empirical risk minimization (ERM)......Page 79
4.3 Structural risk minimization (SRM)......Page 81
4.4 Cross-validation......Page 85
4.5 n-Fold cross-validation......Page 88
4.6 Regularization-based algorithms......Page 89
4.7 Convex surrogate losses......Page 90
4.8 Chapter notes......Page 94
4.9 Exercises......Page 95
5.1 Linear classification......Page 96
5.2 Separable case......Page 97
5.2.1 Primal optimization problem......Page 98
5.2.3 Dual optimization problem......Page 100
5.2.4 Leave-one-out analysis......Page 102
5.3 Non-separable case......Page 104
5.3.1 Primal optimization problem......Page 105
5.3.2 Support vectors......Page 106
5.3.3 Dual optimization problem......Page 107
5.4 Margin theory......Page 108
5.6 Exercises......Page 117
6.1 Introduction......Page 122
6.2.1 Definitions......Page 125
6.2.2 Reproducing kernel Hilbert space......Page 127
6.2.3 Properties......Page 129
6.3.1 SVMs with PDS kernels......Page 133
6.3.3 Learning guarantees......Page 134
6.4 Negative definite symmetric kernels......Page 136
6.5 Sequence kernels......Page 138
6.5.1 Weighted transducers......Page 139
6.5.2 Rational kernels......Page 143
6.6 Approximate kernel feature maps......Page 147
6.7 Chapter notes......Page 152
6.8 Exercises......Page 154
7.1 Introduction......Page 162
7.2 AdaBoost......Page 163
7.2.1 Bound on the empirical error......Page 166
7.2.2 Relationship with coordinate descent......Page 167
7.3.1 VC-dimension-based analysis......Page 171
7.3.2 L1-geometric margin......Page 172
7.3.3 Margin-based analysis......Page 174
7.3.4 Margin maximization......Page 178
7.3.5 Game-theoretic interpretation......Page 179
7.4 L1-regularization......Page 182
7.5 Discussion......Page 184
7.6 Chapter notes......Page 185
7.7 Exercises......Page 187
8. On-Line Learning......Page 194
8.2 Prediction with expert advice......Page 195
8.2.1 Mistake bounds and Halving algorithm......Page 196
8.2.2 Weighted majority algorithm......Page 198
8.2.3 Randomized weighted majority algorithm......Page 200
8.2.4 Exponential weighted average algorithm......Page 203
8.3.1 Perceptron algorithm......Page 207
8.3.2 Winnow algorithm......Page 215
8.4 On-line to batch conversion......Page 218
8.5 Game-theoretic connection......Page 221
8.6 Chapter notes......Page 222
8.7 Exercises......Page 223
9.1 Multi-class classification problem......Page 230
9.2 Generalization bounds......Page 232
9.3.1 Multi-class SVMs......Page 238
9.3.2 Multi-class boosting algorithms......Page 239
9.3.3 Decision trees......Page 241
9.4 Aggregated multi-class algorithms......Page 245
9.4.2 One-versus-one......Page 246
9.4.3 Error-correcting output codes......Page 248
9.5 Structured prediction algorithms......Page 250
9.6 Chapter notes......Page 252
9.7 Exercises......Page 254
10. Ranking......Page 256
10.1 The problem of ranking......Page 257
10.2 Generalization bound......Page 258
10.3 Ranking with SVMs......Page 260
10.4 RankBoost......Page 261
10.4.1 Bound on the empirical error......Page 263
10.4.2 Relationship with coordinate descent......Page 265
10.4.3 Margin bound for ensemble methods in ranking......Page 267
10.5 Bipartite ranking......Page 268
10.5.1 Boosting in bipartite ranking......Page 269
10.5.2 Area under the ROC curve......Page 272
10.6.1 Second-stage ranking problem......Page 274
10.6.2 Deterministic algorithm......Page 276
10.6.3 Randomized algorithm......Page 277
10.7 Other ranking criteria......Page 279
10.8 Chapter notes......Page 280
10.9 Exercises......Page 281
11.1 The problem of regression......Page 284
11.2.1 Finite hypothesis sets......Page 285
11.2.2 Rademacher complexity bounds......Page 286
11.2.3 Pseudo-dimension bounds......Page 288
11.3.1 Linear regression......Page 292
11.3.2 Kernel ridge regression......Page 293
11.3.3 Support vector regression......Page 298
11.3.4 Lasso......Page 302
11.3.6 On-line regression algorithms......Page 306
11.4 Chapter notes......Page 307
11.5 Exercises......Page 309
12.1 Density estimation problem......Page 312
12.1.1 Maximum Likelihood (ML) solution......Page 313
12.2 Density estimation problem augmented with features......Page 314
12.3 Maxent principle......Page 315
12.5 Dual problem......Page 316
12.6 Generalization bound......Page 320
12.7 Coordinate descent algorithm......Page 321
12.8 Extensions......Page 323
12.9 L2-regularization......Page 325
12.10 Chapter notes......Page 329
12.11 Exercises......Page 330
13.1 Learning problem......Page 332
13.3 Conditional Maxent models......Page 333
13.4 Dual problem......Page 334
13.5 Properties......Page 336
13.5.2 Feature vectors......Page 337
13.6 Generalization bounds......Page 338
13.7.2 Logistic model......Page 342
13.8 L2-regularization......Page 343
13.9 Proof of the duality theorem......Page 345
13.10 Chapter notes......Page 347
13.11 Exercises......Page 348
14.1 Definitions......Page 350
14.2 Stability-based generalization guarantee......Page 351
14.3 Stability of kernel-based regularization algorithms......Page 353
14.3.1 Application to regression algorithms: SVR and KRR......Page 356
14.3.2 Application to classification algorithms: SVMs......Page 358
14.4 Chapter notes......Page 359
14.5 Exercises......Page 360
15. Dimensionality Reduction......Page 364
15.1 Principal component analysis......Page 365
15.2 Kernel principal component analysis (KPCA)......Page 366
15.3.1 Isomap......Page 368
15.3.2 Laplacian eigenmaps......Page 369
15.3.3 Locally linear embedding (LLE)......Page 370
15.4 Johnson-Lindenstrauss lemma......Page 371
15.6 Exercises......Page 373
16.1 Introduction......Page 376
16.2 Finite automata......Page 377
16.3 Efficient exact learning......Page 378
16.3.1 Passive learning......Page 379
16.3.2 Learning with queries......Page 380
16.3.3 Learning automata with queries......Page 381
16.4 Identification in the limit......Page 386
16.4.1 Learning reversible automata......Page 387
16.5 Chapter notes......Page 392
16.6 Exercises......Page 393
17.1 Learning scenario......Page 396
17.2 Markov decision process model......Page 397
17.3.1 Definition......Page 398
17.3.3 Optimal policies......Page 399
17.3.4 Policy evaluation......Page 402
17.4.1 Value iteration......Page 404
17.4.2 Policy iteration......Page 407
17.4.3 Linear programming......Page 409
17.5 Learning algorithms......Page 410
17.5.1 Stochastic approximation......Page 411
17.5.2 TD(0) algorithm......Page 414
17.5.3 Q-learning algorithm......Page 415
17.5.5 TD(λ) algorithm......Page 419
17.5.6 Large state space......Page 420
17.6 Chapter notes......Page 422
Conclusion......Page 424
A.1.1 Norms......Page 426
A.1.2 Dual norms......Page 427
A.2.1 Matrix norms......Page 428
A.2.3 Symmetric positive semidefinite (SPSD) matrices......Page 429
B.2 Convexity......Page 432
B.3 Constrained optimization......Page 436
B.4.1 Subgradients......Page 439
B.4.3 Conjugate functions......Page 440
B.5 Chapter notes......Page 443
B.6 Exercises......Page 444
C.2 Random variables......Page 446
C.4 Expectation and Markov’s inequality......Page 448
C.5 Variance and Chebyshev’s inequality......Page 449
C.6 Momentgenerating functions......Page 451
C.7 Exercises......Page 452
D.1 Hoeffding’s inequality......Page 454
D.2 Sanov’s theorem......Page 455
D.3 Multiplicative Chernoff bounds......Page 456
D.5 Binomial distribution tails: Lower bound......Page 457
D.6 Azuma’s inequality......Page 458
D.7 McDiarmid’s inequality......Page 459
D.9 Khintchine-Kahane inequality......Page 460
D.10 Maximal inequality......Page 461
D.12 Exercises......Page 462
E.1 Entropy......Page 466
E.2 Relative entropy......Page 467
E.4 Bregman divergences......Page 470
E.5 Chapter notes......Page 473
E.6 Exercises......Page 474
F. Notation......Page 476
Bibliography......Page 478
Index......Page 492