Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond

Contents ... 8
Preface ... 16
1 A Tutorial Introduction ... 20
1.1 Data Representation and Similarity ... 20
1.2 A Simple Pattern Recognition Algorithm ... 23
1.3 Some Insights From Statistical Learning Theory ... 25
1.4 Hyperplane Classi?ers ... 30
1.5 Support Vector Classi?cation ... 34
1.6 Support Vector Regression ... 36
1.8 Empirical Results and Implementations ... 40
I CONCEPTS AND TOOLS ... 42
2 Kernels ... 44
2.1 Product Features ... 45
2.2 The Representation of Similarities in Linear Spaces ... 48
2.2.1 Positive De?nite Kernels ... 49
2.2.2 The Reproducing Kernel Map ... 51
2.2.3 Reproducing Kernel Hilbert Spaces ... 54
2.2.4 The Mercer Kernel Map ... 55
2.2.5 The Shape of the Mapped Data in Feature Space ... 59
2.2.6 The Empirical Kernel Map ... 61
2.2.7 A Kernel Map De?ned from Pairwise Similarities ... 63
2.3 Examples and Properties of Kernels ... 64
2.4 The Representation of Dissimilarities in Linear Spaces ... 67
2.4.1 Conditionally Positive De?nite Kernels ... 67
2.4.2 Hilbert Space Representation of CPD Kernels ... 69
2.4.3 Higher Order CPD Kernels ... 72
2.5 Summary ... 74
2.6 Problems ... 74
3 Risk and Loss Functions ... 80
3.1 Loss Functions ... 81
3.1.1 Binary Classi?cation ... 81
3.1.2 Regression ... 83
3.2 Test Error and Expected Risk ... 84
3.2.1 Exact Quantities ... 84
3.2.2 Approximations ... 85
3.3 A Statistical Perspective ... 87
3.3.1 Maximum Likelihood Estimation ... 87
3.3.2 Ef?ciency ... 90
3.4 Robust Estimators ... 94
3.4.1 Robustness via Loss Functions ... 95
3.4.2 Ef?ciency and the -Insensitive Loss Function ... 97
3.4.3 Adaptive Loss Functions ... 99
3.4.4 Optimal Choice of ... 100
3.5 Summary ... 102
3.6 Problems ... 103
4 Regularization ... 106
4.1 The Regularized Risk Functional ... 107
4.2 The Representer Theorem ... 108
4.3 Regularization Operators ... 111
4.4 Translation Invariant Kernels ... 115
4.4.1 B n -Splines ... 117
4.4.2 Gaussian Kernels ... 118
4.4.3 Dirichlet Kernels ... 120
4.4.4 Periodic Kernels ... 122
4.4.5 Practical Implications ... 124
4.5 Translation Invariant Kernels in Higher Dimensions ... 124
4.5.1 Basic Tools ... 126
4.5.2 Regularization Properties of Kernels in R N ... 126
4.5.3 A Note on Other Invariances ... 128
4.6 Dot Product Kernels ... 129
4.6.1 Conditions for Positivity and Eigenvector Decompositions ... 130
4.6.2 Examples and Applications ... 131
4.7 Multi-Output Regularization ... 132
4.8 Semiparametric Regularization ... 134
4.9 Coef?cient Based Regularization ... 137
4.9.1 Ridge Regression ... 138
4.9.2 Linear Programming Regularization ... 139
4.9.3 Mixed Semiparametric Regularizers ... 139
4.10 Summary ... 140
4.11 Problems ... 141
5 Elements of Statistical Learning Theory ... 144
5.1 Introduction ... 144
5.2 The Law of Large Numbers ... 147
5.3 When Does Learning Work: the Question of Consistency ... 150
5.4 Uniform Convergence and Consistency ... 150
5.5 How to Derive a VC Bound ... 153
5.5.1 The Union Bound ... 153
5.5.2 Symmetrization ... 154
5.5.3 The Shattering Coef?cient ... 155
5.5.4 Uniform Convergence Bounds ... 155
5.5.5 Con?dence Intervals ... 157
5.5.6 The VC Dimension and Other Capacity Concepts ... 158
5.6 A Model Selection Example ... 163
5.7 Summary ... 165
5.8 Problems ... 165
6 Optimization ... 168
6.1 Convex Optimization ... 169
6.2 Unconstrained Problems ... 173
6.2.1 Functions of One Variable ... 173
6.2.2 Functions of Several Variables: Gradient Descent ... 176
6.2.3 Convergence Properties of Gradient Descent ... 177
6.2.4 Functions of Several Variables: Conjugate Gradient Descent ... 179
6.2.5 Predictor Corrector Methods ... 182
6.3 Constrained Problems ... 184
6.3.1 Optimality Conditions ... 185
6.3.2 Duality and KKT-Gap ... 188
6.3.3 Linear and Quadratic Programs ... 191
6.4 Interior Point Methods ... 194
6.4.1 Suf?cient Conditions for a Solution ... 194
6.4.2 Solving the Equations ... 195
6.4.3 Updating ... 196
6.4.4 Initial Conditions and Stopping Criterion ... 196
6.5 Maximum Search Problems ... 198
6.5.1 Random Subset Selection ... 198
6.5.2 Random Evaluation ... 200
6.5.3 Greedy Optimization Strategies ... 201
6.6 Summary ... 202
6.7 Problems ... 203
II SUPPORT VECTOR MACHINES ... 206
7 Pattern Recognition ... 208
7.1 Separating Hyperplanes ... 208
7.2 The Role of the Margin ... 211
7.3 Optimal Margin Hyperplanes ... 215
7.4 Nonlinear Support Vector Classi?ers ... 219
7.5 Soft Margin Hyperplanes ... 223
7.6 Multi-Class Classi?cation ... 230
7.6.1 One Versus the Rest ... 230
7.6.2 Pairwise Classi?cation ... 231
7.6.3 Error-Correcting Output Coding ... 232
7.6.4 Multi-Class Objective Functions ... 232
7.7 Variations on a Theme ... 233
7.8 Experiments ... 234
7.8.1 Digit Recognition Using Different Kernels ... 234
7.8.2 Universality of the Support Vector Set ... 238
7.8.3 Other Applications ... 240
7.9 Summary ... 241
7.10 Problems ... 241
8 Single-Class Problems: Quantile Estimation and Novelty Detection ... 246
8.1 Introduction ... 247
8.2 A Distribution’s Support and Quantiles ... 248
8.3 Algorithms ... 249
8.4 Optimization ... 253
8.5 Theory ... 255
8.6 Discussion ... 260
8.7 Experiments ... 262
8.8 Summary ... 266
8.9 Problems ... 267
9 Regression Estimation ... 270
9.1 Linear Regression with Insensitive Loss Function ... 270
9.2 Dual Problems ... 273
9.2.2 More General Loss Functions ... 275
9.2.3 The Bigger Picture ... 278
9.3 -SV Regression ... 279
9.4 Convex Combinations and 1 -Norms ... 285
9.5 Parametric Insensitivity Models ... 288
9.6 Applications ... 291
9.7 Summary ... 292
9.8 Problems ... 293
10 Implementation ... 298
10.1 Tricks of the Trade ... 300
10.1.1 Stopping Criterion ... 300
10.1.2 Restarting with Different Parameters ... 304
10.1.3 Caching ... 305
10.1.4 Shrinking the Training Set ... 306
10.2 Sparse Greedy Matrix Approximation ... 307
10.2.1 Sparse Approximations ... 307
10.2.2 Iterative Methods and Random Sets ... 309
10.2.3 Optimal and Greedy Selections ... 310
10.2.4 Experiments ... 312
10.3 Interior Point Algorithms ... 314
10.3.1 Solving the Equations ... 315
10.3.2 Special Considerations for Classi?cation ... 316
10.3.3 Special Considerations for SV Regression ... 317
10.3.4 Large Scale Problems ... 318
10.4 Subset Selection Methods ... 319
10.4.1 Chunking ... 319
10.4.2 Working Set Algorithms ... 320
10.4.3 Selection Strategies ... 321
10.5 Sequential Minimal Optimization ... 324
10.5.1 Analytic Solutions ... 324
10.5.2 Classi?cation ... 326
10.5.3 Regression ... 327
10.5.4 Computing the Offset b and Optimality Criteria ... 329
10.5.5 Selection Rules ... 330
10.6 Iterative Methods ... 331
10.6.1 Gradient Descent ... 334
10.6.2 Lagrangian Support Vector Machines ... 337
10.6.3 Online Extensions ... 339
10.7 Summary ... 346
10.7.1 Topics We Did Not Cover ... 346
10.7.2 Topics We Covered ... 347
10.7.3 Future Developments and Code ... 348
10.8 Problems ... 348
11 Incorporating Invariances ... 352
11.1 Prior Knowledge ... 352
11.2 Transformation Invariance ... 354
11.3 The Virtual SV Method ... 356
11.4 Constructing Invariance Kernels ... 362
11.4.1 Invariance in Input Space ... 363
11.4.2 Invariance in Feature Space ... 367
11.4.3 Experiments ... 371
11.5 The Jittered SV Method ... 373
11.6 Summary ... 375
11.7 Problems ... 376
12 Learning Theory Revisited ... 378
12.1 Concentration of Measure Inequalities ... 379
12.1.1 McDiarmid’s Bound ... 379
12.1.2 Uniform Stability and Convergence ... 380
12.1.3 Uniform Stability of Regularization Networks ... 382
12.2 Leave-One-Out Estimates ... 385
12.2.1 Theoretical Background ... 385
12.2.2 Lagrange Multiplier Estimates ... 388
12.2.3 The Span Bound for Classi?cation ... 389
12.2.4 The Span Bound for Quantile Estimation ... 391
12.2.5 Methods from Statistical Physics ... 395
12.3 PAC-Bayesian Bounds ... 400
12.3.1 Gibbs and Bayes Classi?ers ... 400
12.3.2 PAC-Bayesian Bounds for Single Classi?ers ... 402
12.3.3 PAC-Bayesian Bounds for Combinations of Classi?ers ... 405
12.3.3 PAC-Bayesian Bounds for Combinations of Classi?ers ... 405
12.3.4 Applications to Large Margin Classi?ers ... 408
12.4 Operator-Theoretic Methods in Learning Theory ... 410
12.4.1 Scale-Sensitivity and the Fat Shattering Dimension ... 410
12.4.2 Entropy and Covering Numbers ... 411
12.4.3 Generalization Bounds via Uniform Convergence ... 413
12.4.4 Entropy Numbers for Kernel Machines ... 415
12.4.5 Discrete Spectra of Convolution Operators ... 419
12.4.6 Covering Numbers for Given Decay Rates ... 421
12.5 Summary ... 422
12.6 Problems ... 423
III KERNEL METHODS ... 424
13 Designing Kernels ... 426
13.1 Tricks for Constructing Kernels ... 427
13.2 String Kernels ... 431
13.3 Locality-Improved Kernels ... 433
13.3.1 Image Processing ... 433
13.3.2 DNA Start Codon Recognition ... 435
13.4 Natural Kernels ... 437
13.4.1 Natural Kernels ... 437
13.4.2 The Natural Regularization Operator ... 439
13.4.3 The Feature Map of Natural Kernels ... 440
13.5 Summary ... 442
13.6 Problems ... 442
14 Kernel Feature Extraction ... 446
14.1 Introduction ... 446
14.2 Kernel PCA ... 448
14.2.1 Nonlinear PCA as an Eigenvalue Problem ... 448
14.2.2 Properties of Kernel PCA ... 450
14.2.3 Comparison to Other Methods ... 453
14.3 Kernel PCA Experiments ... 456
14.4 A Framework for Feature Extraction ... 461
14.4.1 Principal Component Analysis ... 461
14.4.2 Kernel PCA ... 462
14.4.3 Sparse Kernel Feature Analysis ... 462
14.4.4 Projection Pursuit ... 464
14.4.5 Kernel Projection Pursuit ... 464
14.4.6 Connections to Supervised Learning ... 465
14.5 Algorithms for Sparse KFA ... 466
14.5.1 Solution by Maximum Sear ... 466
14.5.2 Sequential Decompositions ... 466
14.5.3 A Probabilistic Speedup ... 468
14.5.4 A Quantile Trick ... 469
14.5.5 Theoretical Analysis ... 469
14.6 KFA Experiments ... 469
14.7 Summary ... 470
14.8 Problems ... 471
15 Kernel Fisher Discriminant ... 476
15.1 Introduction ... 476
15.2 Fisher’s Discriminant in Feature Space ... 477
15.3 Ef?cient Training of Kernel Fisher Discriminants ... 479
15.4 Probabilistic Outputs ... 483
15.5 Experiments ... 485
15.6 Summary ... 486
15.7 Problems ... 487
16 Bayesian Kernel Methods ... 488
16.1 Bayesics ... 489
16.1.1 Likelihood ... 489
16.1.2 Prior Distributions ... 491
16.1.3 Bayes’ Rule and Inference ... 493
16.1.4 Hyperparameters ... 494
16.2 Inference Methods ... 494
16.2.1 Maximum a Posteriori Approximation ... 495
16.2.2 Parametric Approximation of the Posterior Distribution ... 497
16.2.3 Connection to Regularized Risk Functionals ... 498
16.3 Gaussian Processes ... 499
16.3.1 Correlated Observations ... 499
16.3.2 De?nitions and Basic Notions ... 500
16.3.3 Simple Hypotheses ... 502
16.3.4 Regression ... 503
16.3.5 Classi?cation ... 505
16.3.6 Adjusting Hyperparameters for Gaussian Processes ... 506
16.4 Implementation of Gaussian Processes ... 507
16.4.1 Laplace Approximation ... 507
16.4.2 Variational Methods ... 509
16.4.3 Approximate Solutions for Gaussian Process Regression ... 510
16.4.4 Solutions on Subspaces ... 511
16.4.5 Implementation Issues ... 513
16.4.6 Hardness and Approximation Results ... 514
16.4.7 Experimental Evidence ... 516
16.5 Laplacian Processes ... 518
16.5.1 Data Dependent Priors ... 518
16.5.2 Samples from the Prior ... 520
16.5.3 Prediction ... 520
16.5.4 Con?dence Intervals for Gaussian Noise ... 522
16.5.5 Data Independent Formulation ... 523
16.5.6 An Equivalent Gaussian Process ... 524
16.6 Relevance Vector Machines ... 525
16.6.1 Regression with Hyperparameters ... 526
16.6.2 Finding Optimal Hyperparameters ... 527
16.6.3 Explicit Priors by Integration ... 528
16.6.4 Classi?cation ... 529
16.6.5 Toy Example and Discussion ... 529
16.7 Summary ... 530
16.7.2 Key Issues ... 531
16.8 Problems ... 532
17 Regularized Principal Manifolds ... 536
17.1 A Coding Framework ... 537
17.1.1 Quantization Error ... 537
17.1.2 Examples with Finite Codes ... 538
17.1.3 Examples with In?nite Codes ... 539
17.2 A Regularized Quantization Functional ... 541
17.2.1 Quadratic Regularizers ... 543
17.2.2 Examples of Regularization Operators ... 543
17.2.3 Linear Programming Regularizers ... 544
17.3 An Algorithm for Minimizing R reg [ f ] ... 545
17.3.1 Projection ... 546
17.3.2 Adaptation ... 546
17.3.3 Initialization ... 547
17.4 Connections to Other Algorithms ... 548
17.4.1 Generative Models ... 548
17.4.2 The Generative Topographic Mapping ... 549
17.4.3 Robust Coding and Regularized Quantization ... 550
17.5 Uniform Convergence Bounds ... 552
17.5.1 Metrics and Covering Numbers ... 552
17.5.2 Upper and Lower Bounds ... 553
17.5.3 Bounding Covering Numbers ... 554
17.5.4 Rates of Convergence ... 555
17.6 Experiments ... 556
17.7 Summary ... 558
17.8 Problems ... 559
18 Pre-Images and Reduced Set Methods ... 562
18.1 The Pre-Image Problem ... 563
18.1.1 Exact Pre-Images ... 563
18.1.2 Approximate Pre-Images ... 565
18.2 Finding Approximate Pre-Images ... 566
18.2.1 Minimizing the Projection Distance ... 566
18.2.2 Fixed Point Iteration Approach for RBF Kernels ... 567
18.2.3 Toy Examples ... 568
18.2.4 Handwritten Digit Denoising ... 570
18.3 Reduced Set Methods ... 571
18.3.1 The Problem ... 571
18.4 Reduced Set Selection Methods ... 573
18.4.1 RS Selection via Kernel PCA ... 574
18.4.2 RS Selection via 1 Penalization ... 576
18.4.3 RS Selection by Sparse Greedy Methods ... 577
18.4.4 The Primal Reformulation ... 578
18.4.5 RS Selection via SV Regression ... 579
18.5 Reduced Set Construction Methods ... 580
18.5.1 Iterated Pre-Images ... 580
18.5.2 Phase II: Simultaneous Optimization of RS Vectors ... 580
18.5.3 Experiments ... 581
18.6 Sequential Evaluation of Reduced Set Expansions ... 583
18.7 Summary ... 585
18.8 Problems ... 586
A Addenda ... 588
A.1 Data Sets ... 588
A.2 Proofs ... 591
B Mathematical Prerequisites ... 594
B.1 Probability ... 594
B.1.1 Probability Spaces ... 594
B.1.2 IID Samples ... 596
B.1.3 Densities and Integrals ... 597
B.1.4 Stochastic Processes ... 599
B.2 Linear Algebra ... 599
B.2.1 Vector Spaces ... 599
B.2.2 Norms and Dot Products ... 602
B.3 Functional Analysis ... 605
B.3.1 Advanced Topics ... 608
References ... 610
Index ... 636