Machine Learning, 10-601

William Cohen and Tom Mitchell
Machine Learning Department
School of Computer Science, Carnegie Mellon University

Spring 2008

Machine Learning is concerned with computer programs that automatically improve their performance through experience (e.g., programs that learn to recognize human faces, recommend music and movies, and drive autonomous robots). This course covers the theory and practical algorithms for machine learning from a variety of perspectives. We cover topics such as datamining, Bayesian networks, decision tree learning, neural network learning, statistical learning methods, and reinforcement learning. The course covers theoretical concepts such as inductive bias, the PAC learning framework, Bayesian learning methods, margin-based learning, and Occam's Razor. Short programming assignments include hands-on experiments with various learning algorithms. Typical assignments include learning to automatically classify email by topic, and learning to automatically classify the mental state of a person from brain image data. Students entering the class with a pre-existing working knowledge of probability, statistics and algorithms will be at an advantage, but the class has been designed so that anyone with a strong numerate background can catch up and fully participate. This class is intended for Masters students and advanced undergraduates.

IF YOU ARE ON THE WAIT LIST: come to class anyway the first week. Perhaps others will drop, providing you an opening. This course is now offered every semester.

Note from the instructors: We want you to enjoy the course, work hard, learn a lot, and become as enthusiastic about this material as we are. If you have suggestions about how to improve any aspect of the course during the semester, please let us know!

Class lectures: Mondays & Wednesdays 3:00pm-4:20pm, Wean Hall 5309

Review sessions: Thursdays 5-6pm, Location: Newell-Simon Hall 1305 starting on Thursday January 17. TA's will cover material from recent lectures and current homeworks, and will answer your questions. These review sessions are optional (but very helpful!).

Thursday, January 24:
- Probability review:
  - Lecture: William's slides.
  - Additional material from Andrew Moore: part1, part2, part3
  - Recitation slides from previous semester
- MATLAB tutorial:
  - Obtaining MATLAB:
    - Use Andrew cluster
    - Download MATLAB for use on-campus (need CMU WebISO authentication)
    - Free, open-source alternative, R
  - CMU MATLAB page
  - Dave Touretzky tutorial:
    - Day 1 (pdf)
    - Day 2 (pdf)
    - Day 3 (pdf)
  - Joseph Gonzalez tutorial:
    - Montior friendly (pdf)
    - Printer friendly (pdf)
    - Demonstration code (zip)

Instructors:

William Cohen, Wean Hall 5317, x8-7664, Office hours: 11am to noon, fridays
Tom Mitchell, Wean Hall 5309, x8-2611, Office hours: 11am to noon, tuesdays (please check with Sharon Cavlovich to be sure Tom's in town)

Teaching Assistants:

Andrew Arnold, Wean Hall 5117, x8-3046, Office hours: Mondays 4:20-5:20pm
Mary McGlohon, Wean Hall 7110, x8-7670, Office hours: Wednesdays 11:00am-noon

Course administrative assistant:

Sharon Cavlovich, Wean Hall 5315, x8-5196

Textbooks:

Textbook (optional): Machine Learning, Tom Mitchell.
Additional (optional, more mathematical) book: Pattern Recognition and Machine Learning , Chris Bishop.
Additional (optional, statistical perspective) book: The Elements of Statistical Learning: Data Mining, Inference, and Prediction , Trevor Hastie, et al.
Additional readings will be made available on this course website.

Announcement emails:

Class announcements such as homework clarifications will be broadcast to a group mailing list, . If you do not receive an email from this list during the first week of the course, please see a TA to add yourself. If you are registered, you should be on the list.

Newsgroup - Bulletin Board: academic.cs.10601

We encourage students to communicate with each other, TA's and Professors, and provide a bulletin board for that purpose
- You can post messages directly to the BBoard by sending e-mail to
- You can access the BBoard on-line via Andrew Webmail (instructions), Outlook (or your favorite IMAP capable e-mail client)

Final grades:

Final grades will be based on homework (30%), midterm (20%), final project (25%), and final exam (25%).

Homework policy:

1. Collaborating on homeworks:

Homeworks will be done individually: each student must hand in their own answers. It is acceptable, however, for students to collaborate in figuring out answers and helping each other solve the problems. If you do collaborate in this way on a homework, you must indicate on your homework with whom you collaborated. We will be assuming that, as participants in an upper-level course, you will be taking the responsibility to make sure you personally understand the solution to any work arising from such collaboration.

2. To cover the possibility that a dog may eat your homework, we will automatically drop your lowest homework grade when calculating your final grade.

3. Late homeworks:

Homework will always be due at the beginning of class on the due date, and is worth full credit at that time.
It is worth half credit for the next 48 hours.
It is worth zero credit after that.
Turn in all late homeworks to Sharon Cavlovich in Wean 5315.

4. Regrading homeworks

If you feel that we have made an error in grading your homework, please turn in your homework with a written explanation to Sharon Cavlovich, and we will consider it. Please note that regrading of a homework may cause your grade to go up or down. All regrading requests must be made within one week of when you receive your graded homework.

Course projects: see the course project page. Proposals are due March 25

Exams:

There will be one midterm exam and a final exam. Both will be open book and open notes. Computers, phones and anything else that is prohibited during airplane flights are not allowed.
Final exam date: Tuesday May 13, 2008, 08:30 am - 11:30 am, Room to be announced (Due to the size of the course, it will be impossible for us to accommodate individual requests to reschedule the midterm or final. Be sure you take this into account as you make travel plans during the semester. If you will be unavailable during the midterm or finals week, then please drop the course and take it during a semester when you can meet the class requirements.)

Homeworks:

HW1: Decision trees and basic probability [Assignment] [Data for Q2]

HW2: Naiive Bayes and Perceptrons [

Assignment

Data

(TEX source if you want, otherwise feel free to ignore)

HW3: Logistic regression and gradient descent [Assignment] [Data] [Data-README]
HW4: Computational learning theory (short assignment) [Assignment] (TEX source if you want, otherwise ignore)
HW5: Bayesian Networks [Assignment] [TeX src] [Solutions]
HW8: HMM's, SVM's, Collaborative Filtering [Assignment] [TeX (pdflatex) and PNG figure]
HW9: Bias-variance, PCA and neural networks [Assignment] [TeX (pdflatex) and figures 1 and 2]

Tentative lecture schedule:

Date	Lecture topic and readings	Lecturer	Homeworks
Mon Jan 14	Introduction to Machine Learning Decision tree learning Reading: Machine Learning, Chapter 3, Decision Trees Slides for Jan 14 and Jan 16: Machine learning and Decision trees (pdf) Decision tree applet (courtesty of Univ. of Alberta, AAAI)	Mitchell
Wed Jan 16	Decision Tree learning, pruning, overfitting, Occam's razor Reading: Machine Learning, Chapter 3, Decision Trees Recitation, January 17 slides	Mitchell	HW1 out [Data for Q2]
Mon Jan 21	No class -- Martin Luther King Day
Wed Jan 23	Fast tour of useful concepts in probability Lecture: William's slides. Additional material from Andrew Moore: part1, part2, part3 Recitation slides from previous semester	Cohen
Mon Jan 28	Naive Bayes I, Conditional independence, Bayes rule, Bayesian classifiers Required reading: Naive Bayes and Logistic Regressiom (sections 1 and 2) Lecture slides: Naive Bayes part I	Mitchell	HW1 due HW2 out Data
Wed Jan 30	Naive Bayes II, Examples: classifying text, classifying mental states from brain images Required reading: Naive Bayes and Logistic Regression (sections 1 and 2) Lecture slides: Naive Bayes part II Recitation slides: Jan 31, MLE, NB, MAP	Mitchell
Mon Feb 4	Perceptrons and linear classifiers Required reading: Linear Classifiers and the Perceptron (notes) Lecture slides: Linear Classifiers and the Perceptron Optional reading: Large Margin Classification Using the Perceptron Algorithm, Freund and Schapire, MLJ 1999.	Cohen
Wed Feb 6	Logistic Regression Required reading: Naive Bayes and Logistic Regression Lecture slides: Gaussian Naive Bayes	Mitchell
Mon Feb 11	Logistic regression, Generative and discriminative classifiers, maximizing conditional data likelihood, MLE and MAP estimates. Lecture slides: Logistic Regression Required reading: Naive Bayes and Logistic Regression (sections 3-6) Optional reading: On Discriminative and Generative Classifiers, Ng and Jordan, NIPS, 2001.	Mitchell	HW2 due HW3 out Data Data Readme
Wed Feb 13	Evaluation, Statistical Estimation, Statistical testing, Cross validation estimates of accuracy Lecture slides: Evaluation Required reading: Machine Learning Chapter 5	Cohen
Mon Feb 18	PAC Learning Lecture slides: Probably Approximately Correct learning Required reading: Machine Learning, Chapter 6. Sidelight on boosting: Slides	Mitchell
Wed Feb 20	Bayes nets, Representation and Inference Lecture slides: PAC Learning: VC dimension Lecture slides: Bayes Nets I	Cohen	HW3 due HW4 out
Mon Feb 25	Bayes nets II. Inference and Learning from fully observed data. Lecture slides: Bayes Nets II Reading (recommended): Chapter 8, Bishop (sample chapter available from author). Reading (optional): A Tutorial on Learning With Bayesian Networks, Heckerman	Cohen	HW4 due HW5 out
Wed Feb 27	Bayes nets III. Learning from partly unobserved data, EM. Lecture slides: Bayes Nets III Lecture slides TAN trees Reading on TAN trees (optional) Bayesian Network Classifiers, Friedman et al.	Cohen
Mon Mar 3	Bayes nets IV. Mixture of Gaussians. Midterm review. Lecture slides: EM, Clustering, and Midterm Review	Mitchell	HW5 due
Wed Mar 5	MIDTERM EXAM In class. Open book, open notes, no internet connectivity.		Midterm solutions
Mar 10, 12	Spring Break!
Mon Mar 17	Hidden Markov Models I. Slides -- see March 19	Mitchell	HW6 (Project proposal) out
Wed Mar 19	Hidden Markov Models II. Lecture slides: Hidden Markov Models Recitation slides (Mar 20): Borrowed from Venu Govindaraju	Mitchell
Mon Mar 24	Collaborative Filtering Reading: Empirical Analysis of Predictive Algorithms for Collaborative Filtering, Breese, Heckerman, Cadie Slides: Tutorial on collaborative filtering	Cohen	HW6 (Project proposal) due HW 7 (Project progress report) out HW8 out
Wed Mar 26	Support vector machines and the "kernel trick" Slides: SVMs and the Kernel Trick	Cohen
Mon Mar 31	Semi-supervised learning I. Slides: learning from labeled and unlabeled data	Mitchell
Wed Apr 2	Semi-supervised learning II. Slides: same as Mar 31 slides. Sidelight: machine learning and studying neural representations Recitation (April 4): based on survey paper by Xiaojin Zhu	Mitchell
Mon Apr 7	Dimensionality reduction, feature selection, PCA, etc. Slides: dimensionality reduction, PCA, Fisher Lin Discriminant Tutorial: A Tutorial on PCA, J. Schlens	Mitchell
Wed Apr 9	Artificial neural networks and supervised dimensionality reduction Slides: artificial neural networks	Mitchell
Mon Apr 14	Regression and the bias-variance tradeoff Slides Readings: Bishop 3.1, 3.2	Cohen	HW 7 (Project progress report) due HW 9 out
Wed Apr 16	Nearest neighbor methods Slides: k-NN methods	Cohen
Mon Apr 21	Reinforcement learning Slides: Reinforcement learning and Markov Decision Processes Other reading (optional): HTML version of Reinforcement Learning, an Introduction by Sutton and Barto	Mitchell	HW9 due
Wed Apr 23	Human and Machine Learning Slides: Human and Machine Learning	Mitchell
Mon Apr 28	Markov Logic Networks, Inductive Logic Programming Slides: Markov logic networks Readings: Unifying Logical and Statistical AI, Domingos et al. AAAI 2006.	Cohen
Wed April 30	Project poster session: NSH 3305 NSH 3305 will be open at 2:30 so you can set up. The poster session will start at 3:00 (the usual start time) and will end by 5:00 . Recitation May 1 in different location: NSH 3002	students!	Project posters due today. Project writeups due ~~May 2~~ 9:00 am Mon May 5
Tue May 13	Final Exam - The exam will 2.5 hours long, starting at 9:00am

Web pages for earlier versions of this course: (include examples of midterms, homework questions, ...)

Course Website (this page):

http://www.cs.cmu.edu/~tom/10601

Note to people outside CMU: Please feel free to reuse any of these course materials that you find of use in your own courses. We ask that you retain any copyright notices, and include written notice indicating the source of any materials you use.

Machine Learning, 10-601

Spring 2008

Date

Lecture topic and readings

Wed Jan 16

Decision Tree learning, pruning, overfitting, Occam's razor

Mon Jan 28

Wed Feb 6