Shalev-Shwartz Shai, Ben-David Shai. Understanding Machine Learning: From Theory to Algorithms

Cambridge University Press, 2014. — 409 p. — ISBN13: 978-1107057135.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.Foundations:
A gentle start
A formal learning model
Learning via uniform convergence
The bias-complexity trade-off
The VC-dimension
Non-uniform learnability
The runtime of learning
From Theory to Algorithms:
Linear predictors
Boosting
Model selection and validation
Convex learning problems
Regularization and stability
Stochastic gradient descent
Support vector machines
Kernel methods
Multiclass, ranking, and complex prediction problems
Decision trees
Nearest neighbor
Neural networks
Additional Learning Models:
Online learning
Clustering
Dimensionality reduction
Generative models
Feature selection and generation
Advanced Theory:
Rademacher complexities
Covering numbers
Proof of the fundamental theorem of learning theory
Multiclass learnability
Compression bounds
PAC-Bayes
Appendix A. Technical lemmas
Appendix B. Measure concentration
Appendix C. Linear algebra.