Advanced Machine Learning
(CS60073)

Instructor: Pabitra Mitra CSE, pabitra@cse.iitkgp.ac.in, Phone: 03222-282356

Teaching Assistants:
Anirban Santara (nrbnsntr@gmail.com)
Shyantani Maiti (shyantani.maiti@gmail.com)
Avirup Saha (saha.avirup@gmail.com)


Course Outline:
Advanced Machine Learning will include topics on theoretical foundations. Topics to be discussed consist the following:

    Learnability, PAC Learning, Uniform Learnability
    Vapnik-Chervonenkis dimension, Growth Functions
    Structural Risk Minimization
    Weak Learnability and Boosting
    Online Learning Models

Books:

1. Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David, Cambridge University Press (referred as UML)
2. Foundations of Machine Learning, by Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar, MIT Press
3. An Introduction to Computational Learning Theory, by Michael J. Kearns and Umesh Vazirani, MIT Press (referred as COLT)

Lecture Schedule:

Topic
Notes
Additional Readings
Introduction, Sample complexity bound for
learning axis parallel rectangles.
Chapter 1 of Kearnes Vazirani book (COLT book)

Definition of PAC Learning
Chapter 1-2 of Shai Shalev-Shwartz and Shai Ben-David book (UML book)
A Theory of the Learnable - Valiant
PAC Learnability of Finite Hypothesis Classes, Empirical Risk Minimization
Chapter 3 of UML book

Agnostic PAC Learnability of Finite Hypothesis Class, Uniform Convergence
Chapter 4 of UML book

No Free Lunch Theorem
Chapter 5 of UML book

VC dimension, Sauer Lemma, Growth Function
Chapter 6 of UML book

Fundamental Theorem of Statistical Learning Theory
Chapter 6 of UML book

Nonuniform Learnability, Structural Risk Minimization
Chapter 7 of UML book

Weak Learnability, Adaboost
Chapter 10 of UML book
Adaboost by Prof. Robert Schapire
Online Learning, Mistake Bounds
Chapter 21 of UML book
Talk by Prof. Avrim Blum
Littlestone Dimension, Regret Bounds
Chapter 21 of UML book

Expert Advice, Weighted Majority Rule
Chapter 21 of UML book

Perceptron Learning
Chapter 21,of UML book



Homework Assignments:

Homework 1
Homework 2
Homework 3
Homework 4

Exams:   Midsem Endsem