understanding machine learning from theory to algorithms pdf
The book is divided into four parts. The first part aims at giving an initial rigorous answer to the fundamental questions of learning. We describe a generalization
of Valiant’s Probably Approximately Correct (PAC) learning model, which is a first
solid answer to the question “What is learning?” We describe the Empirical Risk
Minimization (ERM), Structural Risk Minimization (SRM), and Minimum Description Length (MDL) learning rules, which show “how a machine can learn.”
We quantify the amount of data needed for learning using the ERM, SRM, and MDL
rules and show how learning might fail by deriving a “no-free-lunch” theorem. We
also discuss how much computation time is required for learning. In the second part
of the book we describe various learning algorithms. For some of the algorithms,
we first present a more general learning principle, and then show how the algorithm
follows the principle. While the first two parts of the book focus on the PAC model,
the third part extends the scope by presenting a wider variety of learning models.
Finally, the last part of the book is devoted to advanced theory.
We made an attempt to keep the book as self-contained as possible. However,
the reader is assumed to be comfortable with basic notions of probability, linear
algebra, analysis, and algorithms. The first three parts of the book are intended
for first year graduate students in computer science, engineering, mathematics, or
statistics. It can also be accessible to undergraduate students with the adequate
background. The more advanced chapters can be used by researchers intending to
gather a deeper theoretical understanding.