From Mlrg
Jump to: navigation, search

Machine Learning Reading Group, Spring 2013

University of Maryland, College Park


Time: Thursdays, 3:00pm - 4:15pm

Location: AVW 4103 (except Mar 28, in 3258)

Topic: Spectral Methods

Mailing List: mlrg@cs.umd.edu (listinfo)


  • Michael Bloodgood, Assistant Research Scientist (CASL)
  • Greg Sanders, 3rd year PhD Student (CS/UMIACS/CLIP)
  • Taesun Moon, Postdoc, (UMIACS)


Week Date Papers Presenter
Clustering and mixture models
01 24 Jan Clustering large graphs via the singular value decomposition (Drineas+al) Michael B
02 31 Jan A spectral algorithm for learning mixtures of distributions (Vempala+Wang) Greg S
03 07 Feb Multiview clustering via canonical correlation analysis (Chaudhuri+al) Abhishek S
HMMs and sequential models
04 14 Feb A spectral learning algorithm for hidden Markov models (Hsu+Kakade+Zhang) Wu Ke
05 21 Feb Reduced-rank hidden Markov models (Siddiqi+Boots+Gordon)
Learning Nonlinear Dynamic Models (Langford+Salakhutdinov+Zhang)
06 28 Feb Local loss optimization in operators models: a new insight into spectral learning (Balle+Quattoni+Carreras) He He
07 07 Mar Spectral learning of general weighted automata via constrained matrix completion (Balle+Mohri) TBD
Tree-structured models and parsing
08 14 Mar Spectral methods for learning multivariate latent tree structure (Anandkumar+al) TBD
09 28 Mar Spectral learning of latent-variable PCFGs (Cohen+al)
Identifiability and unmixing of latent parse trees (Hsu+Kakade+Liang)
10 04 Apr Spectral learning for non-deterministic dependency parsing (Luque+Quattoni+Balle+Carreras) TBD
Collaborative filtering and topic models
11 11 Apr Using mixture models for collaborative filtering (Kleinberg+Sandler) TBD
12 18 Apr Who moderates the moderators? Crowdsourcing abuse detection in user-generated content (Ghosh+Kale+McAfee) TBD
13 25 Apr A Practical Algorithm for Topic Modeling with Provable Guarantees (Arora+Ge+Halpern+Mimno+Moitra+Sontag+Wu+Zhu)
A spectral algorithm for latent Dirichlet allocation (Anandkumar+al)
14 02 May Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders (Arora+al) TBD
15 09 May Randomized algorithms for matrices and data (Mahoney) TBD
16 16 May Tensor decompositions for learning latent variable models (Anandkumar+al) TBD

Paper Summaries

Clustering Large Graphs via the Singular Value Decomposition

P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay. Machine Learning, 56, 9-33, 2004.

Big picture summary of paper:

Discrete Clustering Problem (DCP): Consider partitioning a set of m points in n-dimensional space into k clusters (usually m and n vary, while k is fixed) so as to minimize the sum of squared distances between each point and its cluster center.

They prove that the DCP is NP-hard even for k=2.

Consider a continuous relaxation of the DCP, which they call Continuous Clustering Problem (CCP): find the k-dimensional subspace V that minimizes the sum of squared distances to V of the m points.

The CCP can be solved by computing the SVD of the m x n matrix that represents the m points.

They prove the solution to the CCP can be used to get a 2-approximation algorithm for the DCP.

Also, they discuss why the solution to the CCP is useful in its own right.

They state a problem still remains: for very large matrices, computing the SVD is too expensive to be used in practice.

Main contribution of paper: They present a solution: the SVD of a submatrix chosen according to a suitable probability distribution provides an approximation to the SVD of the whole matrix, yielding a linear time randomized algorithm. The authors expect this algorithm to be the main contribution of this paper, since the algorithm can be applied to very large matrices that arise in modern applications.

Other related papers and background

McSherry - Spectral partitioning of random graphs

Von Luxburg - A tutorial on spectral clustering

Chaudhuri-Chung-Tsiatas - Spectral clustering of graphs with general degrees in the extended planted partition model

Bshouty-Long - Finding planted partitions in nearly linear time using arrested spectral clustering