Machine Learning: Theory and Algorithms (MALTA), 2022-2023
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.
The course has a theoretical focus, and the student is assumed to be comfortable with basic notions of probability, linear algebra, analysis, and algorithms.
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, available here.
There are also video lessons from Shai Ben-David, and lecture notes from Shai Shalev-Shwartz (together with videos in Hebrew if you prefer it to English).
Evaluation
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.
Lessons
Lessons will be on Fridays from 14.00 to 17.15 in O+106 Templiers, unless otherwise specified.
For each lesson, the corresponding sections of the book and the corresponding videos of Shai Ben-David's course are listed.
First lesson (September 16): introduction, what is machine learning, when it should be used, and how it relates to statistics, artificial intelligence, and computer science,
types of learning (supervised, unsupervised, reinforcement, active vs passive learners, helpfulness of the teacher, online vs batching),
inductive bias [chapter 1, video lecture 1 up to 1:07:00];
formal model for learning, empirical and expected loss, empirical risk minimization, introduction to PAC learnability,
proof that a finite class is PAC-learnable [chapter 2, videos lectures 1, 2, and 3 up to 0:27:45].
Second lesson (September 23): formal definition of PAC learnability and agnostic PAC learnability [chapter 3, videos lecture 3 and lecture 4 up to 0:56:35], proof that there exists a PAC-learnable class with infinite size [section 6.1, video lecture 6 up to 0:52:50], uniform convergence [section 4.1, video lecture 4].
Third lesson (September 30): uniform convergence is sufficient for agnostic PAC learnability, finite classes have the uniform convergence property [sections 4.1-4.2, video for lecture 5], the no-free-lunch theorem [section 5.1, video for lecture 8 up to 0:46:00]
Fourth lesson (October 7): bias-complexity tradeoff [section 5.2, video lecture 6 from 1:15:14], VC-dimension [sections 6.2-6.3, lecture 7], the fundamental theorem of statistical learning [section 6.4, lecture 8 from 0:57:31 up to 1:11:54 and lecture 9 from 1:01:41], linear predictors [section 9.1, lecture 8 from 1:11:54]
Fifth lesson (October 14): section 5.2, chapter 10 (without proofs), videos for lectures 17 (from minute 45), 18, and 19 (up to 0:35:10).
Sixth lesson (October 21): section 12.1.1, beginning of section 12.2, sections 12.3, 9.2, 9.3, videos for lectures 19 (from 0:57:43), 20, 21, and 22 (you can skip between 0:14:30 and 0:48:20).
Seventh lesson (October 28): sections 7.1-7.3 (without proofs), chapter 11, videos for lectures 12 (from 0:44:40), 13, 14, and 15 (up to 0:35:00). Note that the videos do not cover sections 11.2 and 11.3.
Assignment
Exam
The exam will be on November 17th in room O+106, Amphi Est Templiers, from 14.00 to 17.00.
Last modified: 13 October, 2022