CMSC828J Advanced Topics in Information Processing:
Subspaces and Manifolds for Computer Vision
and Machine Learning
|
General Information |
|
|
|
Announcements:
Midterm is here. Data for problem 4 is here, with readme. Due on Wed. April 3.
Review for final is here.
Description
Linear subspaces and other manifolds are widely used to represent data. Dimensionality reduction is often a driving motivation. For example, Principal Component Analysis (PCA) represents data by projecting it into a low-dimensional space that best captures the data, providing a representation that captures the intrinsic dimensionality of the data. Many other linear approaches exist, which used supervised information (eg., LDA) or attempt to represent multiple data sets in a common space (eg., CCA, PLS). Manifold learning approaches represent data using low-dimensional, non-linear manifolds. Even when they don’t perform dimensionality reduction, Riemannian manifolds offer the opportunity to make use of non-Euclidean metrics that better capture the relationship between data elements. These approaches have been widely studied and used in machine learning, computer vision and other application areas, such as Natural Language Processing.
In this class we will study these
techniques. The class will be a mix
between lectures, in which we study the mathematics behind linear subspaces and
Riemannian manifolds, and reading and discussion of papers that develop and
apply these methods to various application areas. We will emphasize their use in computer
vision (because that’s what the instructor knows about) but will be happy to
discuss a range of other application areas that may be of interest to the
students of the class.
Prerequisites
Knowledge of and comfort with mathematics
will be very helpful. At a minimum,
students should know multivariable calculus and linear algebra. No knowledge of manifolds, Riemannian
geometry, or differential geometry will be assumed.
Here is my current plan for the workload of the class. This may change during the first two weeks, as the number of students settles down.
1) Reports. There will be some classes in which we discuss research papers. Prior to each of these classes, students must turn in a one page report on the papers to be discussed. I prefer if you turn in a hardcopy to me at the start of class. Late papers will not be accepted, since the goal of these reports is to get you to think about papers before we discuss them. However, each student need not turn in a report on days when they are presenting a paper. The current schedule calls for ten classes with discussions, but this number may change as the semester evolves. Students will be required to turn in no more than 8 reports. 10% of grade
2) Presentations. Students will be divided into six groups. Each group will take charge of one class. They are responsible for selecting papers on a specific topic, presenting these papers and leading a discussion on them. In running a successful class, you will be expected to accomplish four things: 1) Clearly explain material in the papers you have chosen. Your presentation should be clearer than the papers, not just a regurgitation of them. 2) You should bring in material that goes beyond that in the papers chosen for discussion. This may include, for example, re-implementing methods in the papers and describing new experiments with them, or describing relevant work in additional papers. 3) You MUST bring your own insights to the presentation. 4) You must lead a discussion involving the class. All teams should schedule a one hour meeting with me at least one week before the class they are leading, in which they will give a dry run of their presentation. 15 % of grade.
3) Midterm, Final. These will be based on material from the lectures, and required reading for the lectures. Notice that all readings are divided into required and background. Exams will draw from material in the required reading. 50% of grade
4) Project. Student will choose one: 25% of grade
a) For three of the algorithms discussed in class, implement these algorithms and experiment with them on some real data. Talk with me about the algorithms you choose to implement before hand. Algorithms cannot be too easy (ie., implementing PCA in one line of Matlab code won’t really count). The number of algorithms you will implement is negotiable, if you choose some that are particularly complex. For each algorithm, turn in a write-up fully explaining your results, and email me a zip file with your code. The intent is that this should be the equivalent of three medium sized problem sets.
b) Programming/research project: This is meant to be a more open-ended project for students interested in research in topics covered in this course. It should involve implementation of existing or novel algorithms and experiments on a real-world data set.
Please hand in your solution to the problem sets, including: 1) A document, with pictures when appropriate, describing your results; 2) Your code. I would prefer to receive your code by email in a zip file, and a hardcopy of the document, but I'll accept everything by email. Projects are due on the last day of class, May 8.
Class Schedule
This schedule should be considered more of a guideline than a rigid plan.
Lectures
|
Class |
Presenters |
Topic |
Required |
Background |
|
1. 1/23 |
Introduction |
|
|
|
|
2. 1/28 |
Lecture |
Linear Projections: PCA, Mahalanobis distance, LDA, Multidimensional Scaling |
Slides from Olga Veksler: Notes
on MDS, Ali Ghodsi (First section only). Also described in On
a Connection between Kernel PCA and Metric Multidimensional Scaling by Christopher Williams, Section 2.1. Abhishek has written up some more complete notes. |
|
|
3. 1/30 |
Lecture |
Sparse coding, change of basis, Fourier and Wavelet Transforms |
|
|
|
4. 2/4 |
Lecture |
Applications of PCA and LDA in Vision; Analytic Linear Subspaces |
Eigenfaces for Recognition Turk and Pentland Eigenfaces vs. Fisherfaces: recognition using class specific linear projection Belhumeur, Hespanha, and Kriegman Recognition by Linear Combinations of Models Ullman and Basri A Morphable Model for the Synthesis of 3D Faces Blanz and Vetter Lambertian Reflectance and Linear Subspaces Basri and Jacobs |
|
|
5. 2/6 |
Lecture |
Applications (cont’d) |
|
|
|
6. 2/11 |
Lecture |
Random Projections, Johnson-Lindenstrauss theorem, locality sensitive hashing, |
An elementary proof of the Johnson-Lindenstrauss Lemma, by Dasgupta and Gupta (This provides some useful intuitions, you needn’t master the whole proof). Locality sensitive hashing for finding nearest neighbors by Slaney and Casey |
Experiments with Random Projections for Machine Learning, by Fradkin and Madigan Approximate nearest neighbors: towards removing the curse of dimensionality, by Indyk and Motwani. |
|
7. 2/13 |
Lecture |
Sparse methods |
Introduction
to Compressed Sensing, by |
|
|
8. 2/18 |
Lecture |
Catching up |
|
|
|
9. 2/20 |
Lecture – Abhishek Sharma |
Multi-modal projections: CCA, PLS, Bilinear Model |
Overview and recent advances in partial least squares by Rosipal and Kramer Canonical correlation analysis: an overview with applications to learning methods by Hardoon, Szedmak and Shawe-Taylor |
|
|
10. 2/25 |
Papers – Students (Rastegari, Fakhraei,
|
Sparse Methods |
K-SVD: An algorithm for Designing Overcomplete Dictionaries for Sparse Representations by Aharon, Elad and Bruckstein Self-taught
Learning: Transfer Learning from Unlabeled Data by Raina,
|
|
|
11. 2/27 |
Lecture |
Manifolds -- Tangent spaces |
|
An Introduction to Riemannian Geometry by Sigmundur Gudmundsson, chapters 2 and 3. Or Riemannian Geometry by Do Carmo (not available online), chapters 0 and 1. |
|
12. 3/4 |
Lecture |
Riemannian Manifolds, Connections -- Geodesics |
|
|
|
13. 3/6 |
Snow day |
|
|
|
|
14. 3/11 |
Lecture |
Riemannian manifolds cont’d |
|
|
|
15. 3/13 |
Lecture |
Kernel methods and Kernel PCA |
Kernel Principal Component Analysis by Scholkopf, Smola and Muller A tutorial on kernel methods for categorization by Jakel, Scholkopf and Wichmann |
|
|
SPRING BREAK |
|
|
|
|
|
16. 3/25 |
Lecture |
Manifold Learning: Isomap and LLE and relation to kernel PCA |
A global geometric framework for nonlinear dimensionality reduction by Tenenbaum, de Silva and Langford Think globally, fit locally: unsupervised learning of low dimensional manifolds, by Saul and Roweis A kernel view of the dimensionality reduction of manifolds by Ham, Lee, Mika and Scholkopf |
|
|
17. 3/27 |
Papers – Students (Michael, Guangxiao, Arijit,
Jason, Garrett) |
Manifold Learning |
Maximum
Variance Unfolding by Weinberger and Saul. Laplacian eigenmaps for
Dimensionality reduction and data representation by Belkin
and Niyogi Manifold Parzen Windows by Vincent and Bengio |
|
|
18. 4/1 |
Papers –DWJ |
Metric learning |
Distance
metric learning, with application to clustering with side-information, by
Xing, Information
theoretic metric learning, by Davis, Kulis,
Jain, Sra and Dhillon Distance
metric learning for large margin nearest neighbor classification, by
Weinberger and Saul |
|
|
19. 4/3 |
Lecture |
Exponential maps Steifel and Grassmanian manifolds -- Quotient manifolds |
The geometry of algorithms with orthogonality constraints, by Edelman, Arias and Smith. |
|
|
20. 4/8 |
Papers - DWJ |
Manifolds of positive definite matrices |
Human detection via classification on Riemannian manifolds by Tuzel, Porikli and Meer A Riemannian framework for tensor computing, by Pennec, Fillard and Ayache. |
|
|
21. 4/10 |
Finish talking about matrix manifolds; go over midterm |
|
|
|
|
22. 4/15 |
Papers – Students: Jain, Manjunatha, Ng, Vageeswaran, Zhang |
Domain adaptation and cross-modal methods. |
K. Saenko, B. Kulis, M. Fritz and
T. Darrell, "Adapting Visual
Category Models to New Domains" R. Gopalan,
R. Li, and R. Chellappa, "Domain Adaptation for
Object Recognition: An Unsupervised Approach", |
|
|
23. 4/17 |
Papers – Students: Santhanam, Vemulapalli, Zampogiannis |
Manifolds of linear subspaces |
The geometry of algorithms with orthogonality constraints, by Edelman, Arias and Smith. "Affine
Invariance Revisited", E. Begelfor and M. Werman,
|
"Riemannian geometry of Grassmann manifolds with a view on algorithmic computation", P.A.Absil, R. Mahony and R.Sepulchre. |
|
24. 4/22 |
Lecture |
|
Shape Statistics: Procrustes Superimpositions and Tangent Spaces by Rohlf |
|
|
25. 4/24 |
Papers – Students: Ball, Chen (Xi), Li (Hao), Stearns, Yang (Fan) |
Statistical Analysis on Manifolds |
Statistical
Analysis on Stiefel and Grassmann
Manifolds with Applications in Computer Vision by Turaga, Veeraraghavan and Chellappa Population
Shape Regression from Random Design Data by Davis, Fletcher, Bullitt and
Joshi Intrinsic Mean Shift for Clustering on Stiefel and Grassmann Manifolds by Cetingul and Vidal |
Intrinsic
Statistics on Riemannian Manifolds: Basic Tools for Geometric Measurements Summer
School on Manifold Learning in Image and Signal Analysis |
|
26. 4/29 |
Papers – Students: Chen (Ching-Hui), Hara, Li (Ang), Sun, Yang |
Learning on Manifolds |
Sparse Manifold Clustering and Embedding by Elhamifar and Vidal Semi-supervised
Learning on Riemannian Manifolds by Belkin and Niyogi |
Learning
an image manifold for retrieval by He, Ma and Zhang |
|
27. 5/1 |
Papers – DWJ |
Manifolds for shape and intensity comparison. |
Durrleman, Pennec, Trouvé, Thompson and Ayache. Inferring Brain Variability from Diffeormorphic Deformations of Currents: an Integrative Approach On shape of plane elastic curves. Mio, Srivastava, Joshi. A fast illumination and deformation insensitive image comparison algorithm using wavelet-based geodesics. Jorstad, Jacobs and Trouve. |
|
|
28. 5/6 |
Papers – DWJ |
Final Papers |
A Simple Prior-free Method for Non-Rigid Structure-from-Motion Factorization by Dai, Le and He. Diffusion
Kernels on Graphs and Other Discrete Input Spaces by Kondor
and Lafferty |
|
|
29. 5/8 |
Conclusions |
|
|
|
|
5/14 |
Final Exam |
1:30-3:30 |
|
|