E0 270: Machine Learning

January - April 2012

Department of Computer Science & Automation
Indian Institute of Science



[Announcements]  [Course Description]  [Assignments]  [Academic Honesty]  [Tutorials/Discussions]  [Schedule] 

Course Information

Class Meetings

Lectures: Tu-Th 11:30am-1:00pm, CSA 117 (Lecture Hall)
First lecture: Tue Jan 10

Tutorial/discussion sessions will be scheduled on an on-going basis.

Instructors

Dr. Shivani Agarwal (shivani@csa)
Dr. Indrajit Bhattacharya (indrajit@csa)

TAs

Adway Mitra (adway@csa)
Arun Rajkumar (arun_r@csa)
Raman Sankaran (ramans@csa)
Goutham Tholpadi (gtholpadi@gmail.com)

Mailing list

http://groups.google.com/group/iisc-csa-e0270-2012-class

Office Hours

[Check regularly for updates]

  Mon Tue Wed Thu Fri
Week of Jan 9     RS
11:30 am - 12:30 pm, CSA 251
SA
2:15-3:00pm, CSA 201
AR
3:00 - 4:00 pm, CSA 230
Week of Jan 16       SA
2-3pm, CSA 201
AR
3-4pm,CSA 230
Week of Jan 23     GT
2-3pm, CSA 251
RS
2-3pm, CSA 251
AR
3-4pm,CSA 230
Week of Jan 30       RS
2-3pm, CSA 251
SA
2-3pm, CSA 201

AR
3-4pm,CSA 230
Week of Feb 6       SA
3-4pm, CSA 201
GT
2-3pm, CSA 251
AR
3-4pm, CSA 230
Week of Feb 13         GT
10-11am, CSA 251
Week of Feb 20       GT
2-3pm, CSA 251
 
Week of Mar 05   GT
2-3pm, CSA 251
     



Announcements


Course Description

With the increasing amounts of data being generated in diverse fields such as astronomical sciences, health and life sciences, financial and economic modeling, climate modeling, market analysis, and even defense, there is an increasing need for computational methods that can automatically analyze and learn predictive models from such data. Machine learning, the study of computer systems and algorithms that automatically improve performance by learning from data, provides such methods; indeed, machine learning techniques are already being used with success in a variety of domains, for example in computer vision to develop face recognition systems, in information retrieval to improve search results, in computational biology to discover new genes, and in drug discovery to prioritize chemical structures for screening. This course aims to provide a sound introduction to both the theory and practice of machine learning, with the goal of giving students a strong foundation in the subject, enabling them to apply machine learning techniques to real problems, and preparing them for advanced coursework/research in machine learning and related fields.

Syllabus (Tentative)

Introduction to machine learning. Classification: nearest neighbour, decision trees, perceptron, support vector machines, VC-dimension. Regression: linear least squares regression, support vector regression. Additional learning problems: multiclass classification, ordinal regression, ranking. Ensemble methods: boosting. Probabilistic models: classification, regression, mixture models (unconditional and conditional), parameter estimation, EM algorithm. Beyond IID, directed graphical models: hidden Markov models, Bayesian networks. Beyond IID, undirected graphical models: Markov random fields, conditional random fields. Learning and inference in Bayesian networks and MRFs: parameter estimation, exact inference (variable elimination, belief propagation), approximate inference (loopy belief propagation, sampling). Additional topics: semi-supervised learning, active learning, structured prediction.

References

Prerequisites

Anyone taking the course for credit must have taken E0 232: Probability and Statistics (or equivalent course elsewhere) and earned a grade of B or higher. In addition, some background in linear algebra and optimization will be helpful.

Grading


Assignments

Assignment Policy

The following assignment policy will be strictly followed: * Except in the case of a documented medical/personal emergency, which must be supported by a medical certificate or signed letter submitted to the instructors and to the CSA office.

Submission Instructions

Assignment solutions must be prepared in LaTeX using the assignment report template below, and the compiled PDF file together with any code must be submitted both electronically and as a hard copy in class, before the start of class on the due date. A link for electronic submission is included in the assignment files below.

Assignment report template [tex] [pdf] [figure]    [LaTeX tutorial 1] [LaTeX tutorial 2]

Academic Honesty

As students of IISc, we expect you to adhere to the highest standards of academic honesty and integrity.

Assignments in the course are designed to support your learning of the subject. Copying will not help you (in the exams or in the real world), so don't do it. If you have difficulties learning some of the topics or lack some background, try to form study groups where you can bounce off ideas with one another and try to teach each other what you understand. You're also welcome to come to any of our office hours and we'll be glad to help you.

If any assignment/exam is found to be copied, it will automatically result in a zero grade for that assignment/exam and a warning note to your advisor. Any repeat instance will automatically lead to a failing grade in the course.


Tutorials/Discussions

  1. Tutorial: MATLAB. Fri Jan 13, 5-6pm, CSA 117. [AR]
  2. Tutorial: Linear algebra/optimization. Fri Jan 20, 5-6pm, CSA 117. [RS]
  3. Discussion: Assignment 1. Fri Jan 27, 5-6pm, CSA 117. [AR/RS]
  4. Tutorial: Optimization (continued). Fri Feb 3, 5-6pm, CSA 117. [RS]
  5. Discussion: Assignment 2. Fri Feb 10, 5-6pm, CSA 117. [GT/AR]
  6. Tutorial: Parameter Estimation. Fri Feb 17, 5-6pm, CSA 117. [GT/AM]

Tentative Schedule

  Date Topic References Notes
Part I: Supervised Learning Problems and Algorithms, Learning Theory
1 Tu Jan 10 Course overview and introduction
Binary classification, nearest neighbor
[slides] Assignment 1 out
2 Th Jan 12 Decision trees [HTF Sec 9.2] / [Bis Sec 14.4] /
[DHS Sec 8.1-8.4] / [Mit Ch 3]*

[MLSS'05 video lecture]
 
3 Th Jan 19 Support vector machines [HTF Ch 12] / [Bis Sec 7.1] /
[DHS Sec 5.11]

[E0 370 lecture notes]
[SVM tutorial]

Fast SVM training:
[Platt, 1999] [Joachims, 1999]
[Joachims, 2006] [Shalev-Shwartz et al, 2011]
 
4 Tu Jan 24 Regression, least squares regression [HTF Sec 3.1-3.4] / [Bis Sec 3.1] Assignment 1 due
Assignment 2 out
5 Th Feb 2 Multiclass classification, ordinal regression, ranking Multiclass SVMs:
[Crammer & Singer, 2001]
[Weston & Watkins, 1999] [Lee et al, 2004]

Support vector ordinal regression:
[Chu & Keerthi, 2007]

Support vector ranking (RankSVM):
[Joachims, 2002] [Herbrich et al, 2000]
[Rakotomamonjy, 2004]
 
6 Tu Feb 7 Generalization error and VC-dimension Generalization error:
[E0 370 lecture 1 notes, Sec 2]
[HTF Sec 2.4 early part] / [Bis Sec 1.5]

VC dimension:
[E0 370 lecture 4 notes, Sec 2 + Cor 3.3]

Confidence intervals/bounds:
[E0 370 lecture 3 notes, App A]

Excess error/consistency:
[E0 370 lecture 10 notes, Sec 1-2]
Assignment 2 due
7 Th Feb 9 PAC learning [E0 370 lecture 11 notes]
[E0 370 lecture 12 notes]
 
  Tu Feb 14 Midterm 1 (in class)    
8 W Feb 15 Boosting [E0370 lecture 15 notes]
[Bis Sec 14.3] / [HTF Ch 10,16] /
[DHS Sec 9.5.2]
 
Part II: Probabilistic Models for Supervised and Unsupervised Learning,
Probabilistic Graphical Models
9 Th Feb 16 Probabilistic models for regression Bis Ch 3, Sec 2.3 Assignment 3 out
10 Tu Feb 21 Generative models for classification Bis Ch 4, Ch 2  
11 Th Feb 23 Discriminative models for classification Bis Ch 4, Ch 2  
12 Fr Feb 24 Mixture Models and the EM algorithm Bis Ch 9  
13 Tu Feb 28 Hidden Markov Models; Forward-Backward Algorithm Bis Ch 13 Assignment 4 out
14 Th Mar 1 Hidden Markov Models contd; Baum Welch Algorithm Bis Ch 13  
15 Tu Mar 6 Intro to Graphical Models; Bayesian Networks Bis Ch 8  
16 Th Mar 8 Markov Random Fields Bis Ch 8  
17 Fr Mar 9 Relation between Directed and Undirected Models; Factor Graphs Bis Ch 8  
18 Tu Mar 13 Exact Inference: Variable Elimination Lecture Notes  
18 Th Mar 15 Exact Inference: Sum-product Algorithm Bis Ch 8  
  Tu Mar 20 Midterm 2 (in class) Solutions    
  Th Mar 22 No Lecture   Assignment 5 out
  Tu Mar 27 No Lecture    
19 Th Mar 29 Discussion: Sampling from standard distributions Bis Ch 11  
20 Tu Apr 3 Approximate Inference using Sampling; MCMC, Gibbs sampling Bis Ch 11  
Part III: Additional Learning Settings and Applications
21 Tu Apr 10 Online learning [E0 370 lecture 18 notes] Assignment 6 out
22 Th Apr 12 Semi-supervised and active learning [Semi-supervised learning literature survey]
[Nigam et al, 2000]

[Active learning literature survey]
[Cesa-Bianchi et al, 2004]
 
23 Tu Apr 17 Guest lecture: Reinforcement learning
Prof. B. Ravindran, IIT Madras
  Assignment 6 due
24 Th Apr 19 Selected topics    
  Fr Apr 27 Final exam (9 am - 12 noon, CSA 117)    

* [HTF = Hastie, Tibshirani, Friedman]; [Bis = Bishop]; [DHS = Duda, Hart, Stork]; [Mit = Mitchell]