EECE515 Machine Learning, Spring 2010

Announcements

February 27
- Won't be much different from last year's!
- Some handouts will be updated!.
- Expect more homework assignments than last year! (Don't be scared!)
March 2
- Current lecture slides are old ones.
- If you are not patient, you can go ahead and read old ones.
- Handout #00 has been updated!
March 15
- Exam 1 in class, Monday, March 22.
- A few problems will be selected from exercises in Chapter 1 and 2 in Bishop's PRML.
- Hwk #1 has been posted!

Primary Textbook

Pattern Recognition and Machine Learning (by C. Bishop, 2006)

Lectures

Dates and Titles	Topics	Lecture Slides	Suggested Further Readings
Lecture 1 Introduction to machine learning	Superised learning Unsupervised learning Probability primer	handout #00 (introduction) handout #01 (probability primer)	Chapter 1 and 2 in Bishop's PRML. The Matrix Cookbook (useful formulas for matrix computation and calculus) Nuances of Probability Theory by Tom Minka.
Lecture 2 Density estimation	Maximum likelihood estimation MAP estimation Bayesian estimation	handout #02 (density estimation)	My note on MLE example My note on Kullback matching
Lecture 3 Clustering I	k-means clustering Mixture of Gaussians (MoG)	handout #03 (k-means and MoG)	Chapter 9.1 and 9.2 in Bishop's PRML.
Lecture 4 Expectation Maximization	Jensen's inequality Information theory preliminaries EM optimization Generalized EM Incremental EM EM for exponetial families	handout #04 (EM)	Chapter 9.3 and 9.4 in Bishop's PRML. A. P. Dempster, N. M. Laird, and D. B. Rubin (1977) "Maximum likelihood from incomplete data via the EM algorithm (with discussion)," Journal of the Royal Statistical Society B, vol. 39, pp. 1-38, 1977. R. M. Neal and G. E. Hinton(1999) "A view of the EM algorithm that justifies incremental, sparse, and other variants," Learning in Graphical Models (edited by M. Jordan), pp. 355-368, 1999.
Lecture 5 Latent variable models	Maximum likelihood factor analysis Probabilistic PCA Mixture of factor analyzers Mixture of probabilistic principal component analyzers SVD	handout #05 (EM-FA, EM-MFA) handout #06 (SVD)	Chapter 12.1 and 12.2 in Bishop's PRML. C. M. Bishop (1999), "Latent variable models," In M. I. Jordan (Ed.), Learning in Graphical Models, 1999. M. E. Tipping and C. M. Bishop (1999), "Probabilistic principal component analysis," Journal of the Royal Statistical Society, Series B, vol. 21, pp. 611-622, 1999. M. E. Tipping and C. M. Bishop (1999), "Mixtures of probabilistic principal component analyzers," Neural Computation, vol. 11, pp. 443-482, 1999. Z. Ghahramani and G. E. Hinton (1996), "The EM algorithm for mixtures of factor analyzers," University of Toronto Technical Report CRG-TR-96-1. S. Roweis (1997), "EM algorithms for PCA and SPCA," NIPS-1997.
Lecture 6 Clustering II	Spectral clustering Nonnegative matrix factorization	handout #07 (spectral) handout #08 (NMF)	J. Shi and J. Malik (2000), "Normalized Cuts and Image Segmentation", IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, 2000. U. von Luxburg (2007), "A tutorial on spectral clustering," Statistics and Computing, vol. 17, no. 4, pp. 395-416, 2007. See my note on extremal properties of eigenvalues. D. D. Lee and H. S. Seung (1999), "Learning the Parts of Objects by Non-negative Matrix Factorization", Nature, vol. 401, pp. 788-791, 1999. C. Ding, T. Li, W. Peng, and H. Park (2006), "Orthogonal nonnegative matrix tri-factorizations for clustering," KDD-2006. A. Cichocki, H. Lee, Y.-D. Kim, and S. Choi (2008), "Nonnegative matrix factorization with alpha-divergence," Pattern Recognition Letters, vol. 29, no. 9, pp. 1433-1440, July 2008.
Lecture 7 Regression	Regression Linear models for regression Least suares and RLS Bias-variance dilemma Bayesian linear regression	handout #09 (linear models for regression)	Chapter 3 in Bishop's PRML.
Lecture 8 Linear models for classification	Bayes decision theory Fisher's linear discriminant analysis Logistic regression Perceptron Support vector machine	handout #10 (Bayes decision) handout #11 (FLD) handout #12 (logistic regression) handout #15 (SVM)	Chapter 4 in Bishop's PRML. C. Burges (1998), "A tutorial on support vector machines for pattern recognition," Data Mining and Knowledge Discovery, vol. 2, pp. 121-167, 1998.
Lecture 9 Neural networks	Perceptron Multilayer perceptron (MLP) Radial basis functoin (RBF) network	handout #13 (MLP) handout #14 (RBF)	Chapter 5 in Bishop's PRML.
Lecture 10 Mixture of experts	Mixture of experts (MoE)	handout #16 (MoE)	Chapter 14.5 in Bishop's PRML.
Lecture 11 Kernel methods	Kernel PCA (KPCA)	handout #17 (KPCA)	Chapter 12.3 in Bishops' PRML.
Lecture 12 Hidden Markov models	Hidden Markov models (HMMs)	handout #18 (HMM)	Chapter 13.2 in Bishops' PRML.

Homework Assignments

Hwk 1

Run your own hard/soft k-means clustering algorithm on toy data sets.
- Download data sets ( Data 1 ) ( Data 2 ) ( Data 3 )
- Each data set contains two 2-dimensional data points, x an y.
- Run your algorithms and describe what you found.
Image segementation with hard/soft k-means.
- Download Berkeley Segmentation data set ( Tiger ) ( Airplane )
- Try your k-means with at least 5 different values of k (e.g., k=2,3,5,7,13)
- Describe what you found.
Due March 29 (Mon)

Hwk 2

Do detailed derivation of EM algorithm for MoG, in the case of arbitrary covariance matrices.
Apply your MoG to the same tasks as homework #1.
Due Apr 5 (Mon)

Hwk 3

Derive EM algorithms for probabilistic PCA (PPCA) and mixture of PPCA (you should show all your work).
Implement PPCA and mixture of PPCA.
You should verify that your codes are working properly using Iris and Wine data sets.
Bonus: Apply your codes to any interesting applications.
Due April 21 (Wed)

Hwk 4

Summarize the normalized cut method.
Apply your spectral clustering to two-moons data (available in e-class).
Apply your spectral clustering to image segmentation.
- You might want to see J. Shi's web site.
- You should not use his code directly. This is just for your reference.
- I would like to see your own algorithm!
- Implement Nystrom approximation for spectral clustering, then you will get extra points.
  Method Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik (2004),
  "Spectral grouping using the Nystrom method," IEEE TPAMI, vol. 26, no. 2, 2004.
Due May 10 (Mon)

Hwk 5

Summarize FLD and LFDA.
Compare the performance of FLD and LFDA using Iris and Wine data sets.
You may use the simple NN-classifier.
Evaluate the performance using 5-fold cross validation.
To this end, you partition the dataset into 5 folds.
Then you use 4 folds for training and evaluate classification performance with the remaining fold.
This is repeated 5 times and averaged classifcation accuracy is computed over 5 trials.
Due May 31 (Mon)

Hwk 6

Derive the IRLS algorithm for logistic regression.
Implement IRLS and test it on any two data sets in UCI machine learning repository .
For extra credit, dito for multinomial logistic regression.
Due Midnight, June 13 (Sunday)