Understanding Machine Learning: From Theory to Algorithms

Machine learning is one of the fastest growing areas of computer science, with far-reaching applications. The aim of this textbook is to introduce machine learning, and the algorithmic paradigms it offers, in a principled way. The book provides an extensive theoretical account of the fundamental ideas underlying machine learning and the mathematical derivations that transform these principles into practical algorithms. Following a presentation of the basics of the field, the book covers a wide array of central topics that have not been addressed by previous textbooks. These include a discussion of the computational complexity of learning and the concepts of convexity and stability; important algorithmic paradigms including stochastic gradient descent, neural networks, and structured output learning; and emerging theoretical concepts such as the PAC-Bayes approach and compression-based bounds. Designed for an advanced undergraduate or beginning graduate course, the text makes the fundamentals and algorithms of machine learning accessible to students and non-expert readers in statistics, computer science, mathematics, and engineering.

Table of Contents

Chapter 1 Introduction

Part 1 Foundations
Chapter 2 A Gentle Start
Chapter 3 A Formal Learning Model
Chapter 4 Learning Via Uniform Convergence
Chapter 5 The Bias-Complexity Tradeoff
Chapter 6 The Vc-Dimension
Chapter 7 Nonuniform Learnability
Chapter 8 The Runtime Of Learning

Part 2 From Theory to Algorithms
Chapter 9 Linear Predictors
Chapter 10 Boosting
Chapter 11 Model Selection And Validation
Chapter 12 Convex Learning Problems
Chapter 13 Regularization And Stability
Chapter 14 Stochastic Gradient Descent
Chapter 15 Support Vector Machines
Chapter 16 Kernel Methods
Chapter 17 Multiclass, Ranking, And Complex Prediction Problems
Chapter 18 Decision Trees
Chapter 19 Nearest Neighbor
Chapter 20 Neural Networks

Part 3 Additional Learning Models
Chapter 21 Online Learning
Chapter 22 Clustering
Chapter 23 Dimensionality Reduction
Chapter 24 Generative Models
Chapter 25 Feature Selection And Generation

Part 4 Advanced Theory
Chapter 26 Rademacher Complexities
Chapter 27 Covering Numbers
Chapter 28 Proof Of The Fundamental Theorem Of Learning Theory
Chapter 29 Multiclass Learnability
Chapter 30 Compression Bounds
Chapter 31 Pac-Bayes

Appendix A Technical Lemmas
Appendix B Measure Concentration
Appendix C Linear Algebra