Understanding Machine Learning: From Theory to Algorithms

Download Understanding Machine Learning tutorial, a complete eBook created by Shai Shalev-Shwartz and Shai Ben-David.

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.

Table of contents

• Introduction
• What Is Learning?
• When Do We Need Machine Learning?
• Types of Learning
• Relations to Other Fields
• How to Read This Book
• Possible Course Plans Based on This Book
• Notation
• Part I Foundations
• A Formal Learning Model
• PAC Learning
• A More General Learning Model
• Releasing the Realizability Assumption – Agnostic PAC
• Learning
• The Scope of Learning Problems Modeled
• Summary
• Bibliographic Remarks
• Exercises
• Learning via Uniform Convergence
• Uniform Convergence Is Sufficient for Learnability
• Examples
• Threshold Functions
• Intervals
• Axis Aligned Rectangles
• Finite Classes
• VC-Dimension and the Number of Parameters
• The Fundamental Theorem of PAC learning
• Proof of Theorem
• Characterizing Nonuniform Learnability
• Structural Risk Minimization
• Minimum Description Length and Occam’s Razor
• Occam’s Razor
• Other Notions of Learnability – Consistency
• Discussing the Different Notions of Learnability
• The No-Free-Lunch Theorem Revisited
• Summary
• Bibliographic Remarks
• Exercises
• The Runtime of Learning
• Learning -Term DNF
• Efficiently Learnable, but Not by a Proper ERM
• Hardness of Learning*
• Bibliographic Remarks
• Exercises
• Part II From Theory to Algorithms
• Linear Regression
• Least Squares
• Linear Regression for Polynomial Regression Tasks
• Logistic Regression
• Bibliographic Remarks
• Exercises
• The VC-Dimension of L(B, T)
• AdaBoost for Face Recognition
• Bibliographic Re
• xii Contents
• k-Fold Cross Validation
• Train-Validation-Test Split
• What to Do If Learning Fails
• Bibliographic Remarks
• Exercises
• Controlling the Fitting-Stability Tradeoff
• Bibliographic Remarks
• Exercises
• Stochastic Gradient Descent
• Gradient Descent
• Analysis of GD for Convex-Lipschitz Functions
• Stochastic Gradient Descent (SGD)
• Analysis of SGD for Convex-Lipschitz-Bounded Functions
• Learning with SGD
• SGD for Risk Minimization
• Analyzing SGD for Convex-Smooth Learning Problems
• SGD for Regularized Loss Minimization
• Bibliographic Remarks
• Exercises
• Support Vector Machines
• Margin and Hard-SVM
• Bibliographic Remarks
• Exercises
• Kernel Methods
• Embeddings into Feature Spaces
• The Kernel Trick
• Kernels as a Way to Express Prior Knowledge
• Characterizing Kernel Functions*
• Implementing Soft-SVM with Kernels
• Summary
• Bibliographic Remarks
• Exercises
• Multiclass, Ranking, and Complex Prediction Problems
• One-versus-All and All-Pairs
• Linear Predictors for Ranking
• Bipartite Ranking and Multivariate Performance Measures
• Linear Predictors for Bipartite Ranking
• Bibliographic Remarks
• Exercises
• Nearest Neighbor
• Analysis
• A Generalization Bound for the -NN Rule
• Feedforward Neural Networks
• Learning Neural Networks
• The Expressive Power of Neural Networks
• Geometric Intuition
• The Sample Complexity of Neural Networks
• The Runtime of Learning Neural Networks
• SGD and Backpropagation
• Contents xv
• Online Learnability
• Online Classification in the Unrealizable Case
• Weighted-Majority
• Online Convex Optimization
• The Online Perceptron Algorithm
• Summary
• Bibliographic Remarks
• The k-Means Algorithm
• Spectral Clustering
• Graph Cut
• Graph Laplacian and Relaxed Graph Cuts
• Unnormalized Spectral Clustering
• Information Bottleneck*
• Maximum Likelihood Estimation for Continuous Random Variables
• Maximum Likelihood and Empirical Risk Minimization
• Linear Discriminant Analysis
• Latent Variables and the EM Algorithm