CSE 250B Winter 2011

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
UNIVERSITY OF CALIFORNIA, SAN DIEGO

CSE 250B: Principles of Artificial Intelligence: Learning

Winter 2011

Please ask questions on this message board.

Lectures are in room 2154 in the CSE building. Please be sure to arrive in class on time. There is a quiz at the start of class every Thursday.

OVERVIEW

CSE 250B is a graduate course devoted to the basic concepts and algorithms of supervised and unsupervised learning from data. 250B is open to Ph.D. and M.S. students in computer science, engineering, cognitive science, and related areas. Other prospective participants, including enthusiastic undergraduates, are welcome, but should contact the instructor at elkan@cs.ucsd.edu. The prerequisite for 250B is graduate status at UCSD, or consent of the instructor for undergraduates. CSE 250A (taught by Prof. Lawrence Saul) and 250B are complementary. Students may take one or both courses: neither is a prerequisite for the other, and there will be little overlap.

The specific topics discussed in CSE 250B will include, not necessarily in this order,

nearest neighbor methods
perceptron methods
logistic regression and log-linear models
stochastic gradient descent training
support vector machines (SVMs)
estimating well-calibrated conditional probabilities
kernel methods
performance evaluation: precision, recall, cross-validation
the problem of overfitting, Occam's razor, and regularization
making optimal decisions given costs and probabilities
unsupervised learning and clustering
generative models, especially multivariate Gaussians
expectation-maximization (EM)
dimensionality reduction: principal component analysis
learning to predict structured outputs, especially sequences

The instructor is Charles Elkan, Professor. For office hours, please send email to arrange an appointment. The teaching assistant is Aditya Menon, who has office hours
from 4pm tp 6pm on Wednesdays in room B240A (basement of the CSE building).

LECTURES

Lectures will be on Tuesdays and Thursdays from 2pm to 3:20pm in the CSE building, room 2154. For lecture notes from the previous version of 250B, see http://www.cs.ucsd.edu/users/elkan/250Bwinter2010. The last lecture will be on Thursday March 10.

January 4	Nearest neighbor (kNN) classification method
January 6	Euclidean distance. Bayes error and a guarantee for 1NN
January 11	Linear regression and learning distance metrics for NN
January 13	Loss functions, regularization
January 18	Overfitting, cross-validation, selecting parameters for algorithms
January 20	Maximum likelihood
January 25	Conditional likelihood, logistic regression model, likelihood derivatives
January 27	Stochastic gradient descent
February 1	Regularized logistic regression, decision theory
February 3	Structured-label supervised learning, log-linear models
February 8	Conditional random fields (CRFs)
February 10	Viterbi algorithm
February 15	Forward and backward vectors and computing expectations, stochastic gradient training
February 17	Perceptron training algorithm. Multinomial distribution
February 22	Bag-of-words representation, topic models
February 24	Latent Dirichlet allocation (LDA)
March 1	Gibbs sampling and the Dirichlet distribution
March 3	Derivation of Gibbs sampling for LDA
March 8	Learning a mixture model via expectation-maximization (EM)
March 10	Expectation-maximization in general

Clickable links in the table above are to lecture notes in PDF. Notes for days or topics without a link are included in the notes for an earlier topic. The quizzes and assignment descriptions are included in the PDF lecture notes.

TEXTBOOKS

The course will not be based on any single book. The following textbooks are recommended as references:

Pattern Recognition and Machine Learning by Christopher M. Bishop, 2006, ISBN 0387310738.
Kernel Methods for Pattern Analysis by John Shawe-Taylor and Nello Cristianini, 2004, ISBN 0521813972.
Introduction to Machine Learning by Ethem Alpaydin, MIT Press, 2004, ISBN 0262012111.

For a price comparison among web booksellers use addall.com with the ISBN numbers. Some topics discussed in class will not be in any textbook, and many will be explained differently, so coming to lectures and taking notes carefully is important. Examinations will be based mainly on the online lecture notes.

ASSIGNMENTS AND GRADING

Instead of a midterm exam, there will be a five-minute in-class quiz at the start of every Thursday lecture (10% of your overall grade), a final examination (30%), and four project assignments (15% each). You should do each project with one partner, so individual work will count for 40% of your grade and joint work for 60%. You are free to change partners, or not, between projects.

Each project will last between two and three weeks and will require coding, experimenting with data, and writing a report. Using a high-level environment such as Matlab or R is encouraged. Projects will be graded based exclusively on the written report; see this writing advice. Each pair of partners should hand in their joint report at the start of class on the day that the report is due. Each day that a report is late will cost 20% of the maximum score available for the project. Reports will be evaluated using grading criteria similar to those in this form. Complete academic honesty is always required.

The first project is due on Thursday January 20, 2011. Later projects are due on Thursday February 8, Tuesday March 1, and Thursday March 17. The final exam will be in the same room CSE 2154 on Thursday March 17 at 3pm. The graduate course and faculty evaluation will be in class on March 1.

There is no a priori correspondence between letter grades and numerical scores on the assignments or on the exam. You can evaluate your performance in the class by comparing your scores with the means and standard deviations, which will be announced. However there is also no fixed correspondence between letter grades and standard deviations above or below the mean. If all students do well in the absolute, then all students will get a good grade.

You should not drop CSE 250B just because you are unhappy with the score that you receive on a project. Instead, you should make an appointment to discuss with the instructor how you can do better on following projects.

Most recently updated on March 10, 2011 by Charles Elkan, elkan@cs.ucsd.edu.