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

Apr 15: Of interest: MLSIG seminar on learning algorithms for bandit problems, Tue Apr 17, 4-5pm, CSA 252/254.
Apr 10: Assignment 6 out.
Apr 09: Of interest: MLSIG seminar on machine learning applications in critical care medicine, Tue Apr 10, 4-5pm, CSA 252.
Apr 09: Schedule for Part III is up. Last 2 lectures (lectures 23-24) are optional; they will give pointers to additional useful topics in machine learning, but will not be covered on the final exam.
Mar 20: Assignment 5 out.
Feb 28: Assignment 4 out.
Feb 22: Discussion session on Midterm Exam - 1 on Fri Feb 24, 5-6pm, CSA 254 [RS/AR]
Feb 08: Assignment 2 updated with extra practice problems.
Feb 07: Make-up class (lecture 8) on Wed Feb 15, 5-6pm, CSA 232.
Feb 07: Discussion session on Assignment 2 on Fri Feb 10, 5-6pm, CSA 117. [GT/AR]
Feb 02: Optimization tutorial (continued) on Fri Feb 3, 5-6pm, CSA 117. [RS]
Jan 31: Today's class canceled.
Jan 30: Reminder: Midterm 1 on Tue Feb 14 (in class). You are allowed to bring one 2-sided, A4-size, handwritten cheat sheet (this can be used to recall formulae etc).
Jan 27: Assignment 2 updated. Please use the latest version.
Jan 25: Discussion session on Assignment 1 on Fri Jan 27, 5-6pm, CSA 117. [AR/RS]
Jan 19: Linear algebra/optimization tutorial on Fri Jan 20, 5-6pm, CSA 117. [RS]
Jan 12: MATLAB tutorial on Fri Jan 13, 5-6pm, CSA 117. [AR]
Jan 12: No class on Tue Jan 17.
Jan 11: Course mailing list (Googlegroup) is up. All updates will be posted on the group. Please ensure you join the group by Jan 13 (Fri).
Jan 05: Course webpage is up. First class will meet on Tue Jan 10.

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

T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer, 2nd Edition, 2009.
[free download available]
C.M. Bishop, Pattern Recognition and Machine Learning. Springer, 2006.
R.O. Duda, P.E. Hart and D.G. Stork. Pattern Classification. Wiley-Interscience, 2nd Edition, 2000.
T. Mitchell, Machine Learning. McGraw Hill, 1997.
Current literature.

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

5-6 Assignments, ~25%
2 Midterms, ~30%
Final Exam, ~40%
Participation/Attendance, ~5%

Assignments

Assignment Policy

The following assignment policy will be strictly followed:

Assignments are for your learning. You can work in groups, but you must write your own code and solutions. See academic honesty policy below.
You are allowed up to 2 late submissions, late by up to 2 days each (with advance email to TA). No further late submissions will be allowed.*
We will drop your assignment with the lowest grade.

* 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]

Assignment 1, due before class Tue Jan 24. [code files] [computeKernel.m][problem2_dataset] (T.A.s in charge: Raman and Arun)
- Jan 11, 11:50am: Problem 1 updated.
- Jan 20, 4:00pm: Matlab code for kernel computation added.
- Feb 2, 11:00am: Updated data set for problem 2 added.
Assignment 2, due before class Tue Feb 07. [Data and code] (T.A.s in charge: Goutham and Arun)
- Jan 27, 12:20pm: Problem 2 and data updated.
- Feb 08, 01:58pm: Problem on VC-dimension shifted to Practice section; more practice problems.
Assignment 3, due before class Tues Feb 28. [Data and code] (T.A.s in charge: Goutham and Adway)
Assignment 4, due before class Tues March 13. [Data and code] (T.A.s in charge: Goutham and Adway)
- Mar 7, 08:40pm: HMM Data updated.
Assignment 5, due before class Tues April 3. [Data] (T.A.s in charge: Raman and Adway)
Assignment 6, due before class Tues April 17. [Data] (T.A.s in charge: Raman and Arun)

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

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

Tentative Schedule

Part I: Supervised Learning Problems and Algorithms, Learning Theory
	Date	Topic	References	Notes
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 Discriminative vs Generative Models, Tom Mitchell, 2010 On Discriminative vs. Generative classifiers: A comparison of logistic regression and naive Bayes, A. Ng and M. Jordan, NIPS 2001
12	Fr Feb 24	Mixture Models and the EM algorithm	Bis Ch 9 A Gentle Tutorial of the EM algorithm and its application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, J. Bilmes, 1997
13	Tu Feb 28	Hidden Markov Models; Forward-Backward Algorithm	Bis Ch 13 A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, L. Rabiner, 1989	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 Graphical Models, M. I. Jordan. Statistical Science (Special Issue on Bayesian Statistics), 19, 140-155, 2004. A Brief Introduction to Graphical Models and Bayesian Networks, Kevin Murphy, 1998. E0:269 Graphical Models, 2011
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 Exploiting Causal Independence in Bayesian Network Inference, Zhang and Poole, 1996.
18	Th Mar 15	Exact Inference: Sum-product Algorithm	Bis Ch 8 Factor Graphs and the Sum-Product Algorithm, Kschischang et al, 2001. Loopy Belief Progagation (Pointer to E069: Graphical Models. Look under "Additional Reading: Loopy Belief Progagation")
	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 Probabilistic Inference Using Markov Chain Monte Carlo Methods, Radford Neal, 1993. An Introduction to MCMC for Machine Learning C. Andrieu, N. de Freitas, A. Doucet, M. Jordan, 2003
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]