News:

Fall 2009
Department of Statistics and Actuarial Science
University of Waterloo
 

Instructor: Ali Ghodsi
Room: MC 4063
Time: TTh 01:00-02:20
Office Hours:  2:300-3:30 T or by appointment   (MC 6081G)

Readings:

Tutorials:

• Dimensionality Reduction,  A Short Tutorial. A. Ghodsi

• Spectral methods for dimensionality reduction.    L. K. Saul, K. Q. Weinberger, J. H. Ham, F. Sha, and D. D. Lee (2006).

• Geometric methods for feature extraction and dimensional reduction.   C. J. C. Burges.

Kernel PCA:

• Kernel PCA pattern reconstruction via approximate pre-images.  B. SchÄolkopf, S. Mika, A. Smola, G. RÄatsch, and K.-R. MÄuller. (pdf)

• Nonlinear Component Analysis as a Kernel Eigenvalue Problem, Ian Fasel (pdf)

Locally Linear Embedding (LLE):

• Nonlinear dimensionality reduction by locally linear embedding.
  Sam Roweis & Lawrence Saul. Science, v.290 no.5500 , Dec.22, 2000. pp.2323--2326.
  [Abstract] [Full article (html) (pdf)]

• Think Globally, Fit Locally: Unsupervised Learning of Nonlinear Manifolds.  Lawrence Saul and Sam Roweis (pdf)

Isomap:

• A Global Geometric Framework for Nonlinear Dimensionality Reduction. Joshua B. Tenenbaum, Vin de Silva, and John C. Langford Science 22 December 2000 290: 2319-2323

MDS, Landmark MDS and Nystrom Approximation:

•  Multidimensional Scaling. T. Cox and M. Cox., Number 59 in Monographs on Statistics and Applied Probability. Chapman & Hall, 1994.

• FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms

• Sparse multidimensional scaling using landmark points

Maximum Variance Unfolding (MVU)  / Semidefinite Embedding (SDE):

• Learning a kernel matrix for nonlinear dimensionality reduction. ,K. Q. Weinberger, F. Sha, and L. K. Saul (2004).
  In Proceedings of the Twenty First International Conference on Machine Learning (ICML-04). (pdf)

• Unsupervised learning of image manifolds by semidefinite programming. K. Q. Weinberger and L. K. Saul (2004).
  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR-04), (pdf)

Landmark SDE:

• Nonlinear dimensionality reduction by semidefinite programming and kernel matrix factorization.  K. Q. Weinberger, B. D. Packer, and L. K. Saul (2005). In  Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics. (pdf)

Action Respecting Embedding (ARE):

• Action Respecting Embedding. M. Bowling, A. Ghodsi, and D. Wilkinson, In proceedings of The 22nd
  International Conference on Machine Learning (ICML 2005). (pdf)
• Learning Subjective Representations. D. Wilkinson, M. Bowling, and A. Ghodsi.  In proceedings of The 19th International Joint Conference on Artificial Intelligence. (IJCAI 2005) ( pdf )

Clustering (Impossibility Theorem):

• An Impossibility Theorem for Clustering.  J. Kleinberg.  In Proceedings of Advances in Neural Information Processing Systems 15, (NIPS 2003) (pdf)

K-means Clustering:

• The Elements of Statistical Learning: Data Mining, Inference, and Prediction. T. Hastie, R. Tibshirani and J. Friedman (Chapter 14)
•  How Fast is the k-means Method?  Har-Peled and Sadri (pdf)M

Metric Learning:

• Distance metric learning with application to clustering with side-information. E. Xing, A. Ng,  M. Jordan and S. Russell. In Proceedings of  Advances in Neural Information Processing Systems 15 (NIPS 2003) (pdf)

• Improving Embeddings by Flexible Exploitation of Side Information.  A. Ghodsi,  D. Wilkinson and F. Southey.  In proceedings of The 20th International Joint Conference on Artificial Intelligence (IJCAI 2006) (pdf)

Spectral Clustering:

Old Lectures from Fall 2006:

Important Dates:

Papers:

 Register the date of your presentation here

Note: You need to have a Wikicoursenote account.  To obtain a user account, you must request one.

     Nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization ( pdf )

2.  A DIRECT FORMULATION FOR SPARSE PCA USING SEMIDEFINITE PROGRAMMING ( pdf )

3.  Learning Spectral Clustering,With Application To Speech Separation ( pdf )

4. Dimensionality Reduction for Supervised Learning with Reproducing Kernel Hilbert Spaces ( pdf )

5.  Regression on Manifolds Using Kernel Dimension Reduction ( pdf )

6. Visualizing Data using t-SNE ( pdf )

7.  Learning a Nonlinear Embedding by Preserving Class Neighbourhood Structure ( pdf )

8.  Visualizing Similarity Data with a Mixture of Maps ( pdf )

9.  Convex and Semi-Nonnegative Matrix Factorizations ( pdf )

10. Maximum-Margin Matrix Factorization ( pdf )

11. Maximum Margin Matrix Factorization for Collaborative Ranking ( pdf )

12. Kernelized Sorting ( pdf )

13.  Random Projections for Manifold Learning ( pdf )

14.  Learning Distance Functions using Equivalence Relations ( pdf

       Adjustment Learning and Relevant Component Analysis ( pdf )

15.  Neighbourhood Components Analysis ( pdf )

16. Measuring Statistical Dependence with Hilbert-Schmidt Norms ( pdf )

Project Report:

Final project reports (up to 8 pages of PDF) are worth 50% of your final grade .You are encouraged to chose a topic related to your research area. However,  you cannot  borrow part of an existing thesis work, nor can  you re-use a project from another course.  

Academic Dishonesty:

• If you use ideas, plots, text and other intellectual property developed by someone else you have to cite the original source.

• If you copy a sentence or a paragraph from work done by someone else, in addition to citing  the original source you have to use quotation marks to identify the scope  of the copied material. 

 Example:

Plagiarism is an act of “using ideas, plots, text and other intellectual property developed by someone else while claiming it is your original work.”¹

References:

1. Tec Encyclopedia. http://www.answers.com/topic/plagiarism

Evidence of  copying or plagiarism will cause a failing mark in the course.

Please attach this cover page to your report.

I use this marking scheme to mark the projects.