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 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
The Bias-Complexity Tradeoff
The No-Free-Lunch Theorem
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.