Foundations of Machine Learning, second edition

**A new edition of a graduate-level machine learning textbook that focuses on the analysis and theory of algorithms.**This book is a general introduction to machine learning that can serve as a textbook for graduate students and a reference for researchers. It covers fundamental modern topics in machine learning while providing the theoretical basis and conceptual tools needed for the discussion and justification of algorithms. It also describes several key aspects of the application of these algorithms. The authors aim to present novel theoretical tools and concepts while giving concise proofs even for relatively advanced topics.__Foundations of Machine Learning__is unique in its focus on the analysis and theory of algorithms. The first four chapters lay the theoretical foundation for what follows; subsequent chapters are mostly self-contained. Topics covered include the Probably Approximately Correct (PAC) learning framework; generalization bounds based on Rademacher complexity and VC-dimension; Support Vector Machines (SVMs); kernel methods; boosting; on-line learning; multi-class classification; ranking; regression; algorithmic stability; dimensionality reduction; learning automata and languages; and reinforcement learning. Each chapter ends with a set of exercises. Appendixes provide additional material including concise probability review.This second edition offers three new chapters, on model selection, maximum entropy models, and conditional entropy models. New material in the appendixes includes a major section on Fenchel duality, expanded coverage of concentration inequalities, and an entirely new entry on information theory. More than half of the exercises are new to this edition. 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 A new edition of a graduate-level machine learning textbook that focuses on the analysis and theory of algorithms. This book is a general introduction to machine learning that can serve as a textbook for graduate students and a reference for researchers. It covers fundamental modern topics in machine learning while providing the theoretical basis and conceptual tools needed for the discussion and justification of algorithms. It also describes several key aspects of the application of these algorithms. The authors aim to present novel theoretical tools and concepts while giving concise proofs even for relatively advanced topics. Foundations of Machine Learning is unique in its focus on the analysis and theory of algorithms. The first four chapters lay the theoretical foundation for what follows; subsequent chapters are mostly self-contained. Topics covered include the Probably Approximately Correct (PAC) learning framework; generalization bounds based on Rademacher complexity and VC-dimension; Support Vector Machines (SVMs); kernel methods; boosting; on-line learning; multi-class classification; ranking; regression; algorithmic stability; dimensionality reduction; learning automata and languages; and reinforcement learning. Each chapter ends with a set of exercises. Appendixes provide additional material including concise probability review. This second edition offers three new chapters, on model selection, maximum entropy models, and conditional entropy models. New material in the appendixes includes a major section on Fenchel duality, expanded coverage of concentration inequalities, and an entirely new entry on information theory. More than half of the exercises are new to this edition. "This book is a general introduction to machine learning that can serve as a textbook for graduate students and a reference for researchers. It covers fundamental modern topics in machine learning while providing the theoretical basis and conceptual tools needed for the discussion and justification of algorithms. It also describes several key aspects of the application of these algorithms. The authors aim to present novel theoretical tools and concepts while giving concise proofs even for relatively advanced topics. Foundations of Machine Learning is unique in its focus on the analysis and theory of algorithms. The first four chapters lay the theoretical foundation for what follows; subsequent chapters are mostly self-contained. Topics covered include the Probably Approximately Correct (PAC) learning framework; generalization bounds based on Rademacher complexity and VC-dimension; Support Vector Machines (SVMs); kernel methods; boosting; on-line learning; multi-class classification; ranking; regression; algorithmic stability; dimensionality reduction; learning automata and languages; and reinforcement learning. Each chapter ends with a set of exercises. Appendixes provide additional material including concise probability review. This second edition offers three new chapters, on model selection, maximum entropy models, and conditional entropy models. New material in the appendixes includes a major section on Fenchel duality, expanded coverage of concentration inequalities, and an entirely new entry on information theory. More than half of the exercises are new to this edition--Provided by publisher