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 probably-approximately 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 non-agnostic case

• Uniform Convergence

• The Bias-Complexity Tradeoff

• The No-Free-Lunch Theorem

• The VC-Dimension

• 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 Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, available at https://www.cs.huji.ac.il/w~shais/UnderstandingMachineLearning/understan... theory-algorithms.pdf
• Video lecture from https://www.youtube.com/channel/UCR4_akQ1HYMUcDszPQ6jh8Q
• Lecture notes from Shai Shalev-Shwartz 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 10-minute test at every lesson, only 5 best marks will be considered), 30% a mid-course home assignement, 40% final exam.