Machine Learning: Theory and Algorithms
Responsable / In charge of : Neglia Giovanni (Giovanni.NEGLIA@inria.fr)
Résumé / Abstract :
The course introduces the mathematical foundations of machine learning.
Its first goal is to formalize the main questions behind machine learning: What is learning? How can a machine learn? Is learning always possible? How do we quantify the resources needed to learn? To this purpose, the course presents the probablyapproximately correct (PAC) learning paradigm. Its second goal is to present several key machine learning algorithms and show how they follow from general machine learning principles.
Prérequis / Prerequisite :
The course has a theoretical focus, and the student is assumed to be comfortable with basic notions of probability, linear algebra, analysis, and algorithms.
Objectifs / Objectives :
 Formalize mathematically the learning problem
 Present key machine learning algorithms
Contenu / Contents :

What Is Learning? When Do We Need Machine Learning? Types of Learning

The Statistical Learning Framework

Empirical Risk Minimization

Probably Approximately Correct (PAC) Learning, agnostic and nonagnostic case

Uniform Convergence

The BiasComplexity Tradeoff

The NoFreeLunch Theorem

The VCDimension

The Fundamental Theorem of PAC learning

Nonuniform Learnability, Structural Risk Minimization and minimum Description Length

Linear Predictors, Linear Regression, Logistic Regression

Boosting, Weak Learnability, AdaBoost

Model Selection and Validation

Convex Learning Problems, Surrogate Loss Functions
Références / References :
• Shai ShalevShwartz and Shai BenDavid, Understanding Machine Learning: From Theory to Algorithms, available at https://www.cs.huji.ac.il/w~shais/UnderstandingMachineLearning/understan... theoryalgorithms.pdf
• Video lecture from https://www.youtube.com/channel/UCR4_akQ1HYMUcDszPQ6jh8Q
• Lecture notes from Shai ShalevShwartz https://www.cs.huji.ac.il/w~shais/IML2014.html
Acquis / Knowledge :
 Know the fundamental limits of machine learning
 Know how to select machine learning models with the right complexity
Evaluation / Assessment :
30% classwork (a 10minute test at every lesson, only 5 best marks will be considered), 30% a midcourse home assignement, 40% final exam.