Tuesday, December 4, 2012

Eftychios Pnevmatikakis: Dec 5

Tomorrow at 1PM I'm going to present some overview of the recent work on approximate message passing algorithms (AMP) with applications to compressed sensing (CS). 
I'm going to start with a brief overview of message passing algorithms [1] and then show how it was used in [2] to derive an AMP algorithm for the standard CS setup (basis pursuit, lasso). 
The time permitting I'm going to briefly present some extensions of this methodology to the case of more general graphical models [3]. 

Material will be drawn from the following sources:

[1] Kschischang, Frank R., Brendan J. Frey, and H-A. Loeliger. "Factor graphs and the sum-product algorithm." Information Theory, IEEE Transactions on 47.2 (2001): 498-519.
[2] Donoho, David L., Arian Maleki, and Andrea Montanari. "Message-passing algorithms for compressed sensing." Proceedings of the National Academy of Sciences 106.45 (2009): 18914-18919.
[3] Rangan, Sundeep, et al. "Hybrid approximate message passing with applications to structured sparsity." arXiv preprint arXiv:1111.2581 (2011).

Wednesday, November 28, 2012

Josh Merel: Nov 28th

Tensor decompositions for learning latent variable models

Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, Matus Telgarsky

This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models---including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation---which exploits a certain tensor structure in their low-order observable moments (typically, of second- and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin's perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models.

Thursday, November 8, 2012

Emanuel Ben-David: Nov 7th

High dimensional Bayesian inference for Gaussian directed acyclic graph models

Recent methodological work by Letac & Massam (2007) and others have introduced classes
of flexible multi-parameter Wishart distributions for high dimensional Bayesian inference
for undirected graphical models. A parallel analysis that universally extends these results
to the class of DAGs or Bayesian networks, arguably one of the most widely used classes of
graphical models, is however not available. The parameter space of interest for Gaussian
undirected graphical models is the space of sparse inverse covariance matrices with fixed zeros corresponding to the missing entries of an undirected graph, whereas for Gaussian DAG models it is the space of sparse lower triangular matrices corresponding to the Cholesky parameterization of inverse covariance matrices. Working with the latter space, though very useful, does not allow a comprehensive treatment of undirected and directed graphical models simultaneously. Moreover, this traditional approach does not lead to well-defined posterior covariance and inverse covariance Bayes estimates which respect the conditional independences encoded by a DAG, since these quantities lie on a curved manifold. In this
paper we first extend the traditional priors that have been proposed in the literature for Gaussian DAGs to allow multiple shape parameters. We then use a novel approach and proceed to define new spaces that retain only the functionally independent elements of covariance and inverse covariance matrices corresponding to DAG models. These spaces can be considered as projections of the parameter space of interest of DAG models on lower dimensions. We demonstrate that this parameter reduction bears several dividends for high dimensional Bayesian posterior analysis. By introducing new families of DAG Wishart and inverse DAG Wishart distributions on these projected spaces we succeed in

a) deriving closed form analytic expressions for posterior quantities that would normally
only be available through intractable numerical simulations,
 b) simultaneously providing a unifying treatment of undirected and directed Gaussian graphical model priors and comparisons thereof,
 c) posterior covariance and inverse covariance Bayes estimates which actually correspond to DAG models.

Tuesday, October 23, 2012

Giovanni Motta: Oct. 24th

Fitting evolutionary factor models to multivariate EEG data

Current approaches for fitting stationary (dynamic) factor models to multivariate time series are based on principal components analysis of the covariance (spectral) matrix. These approaches are based on the assumption that the underlying process is temporally stationary which appears to be restrictive because, over long time periods, the parameters are highly unlikely to remain constant. Our alternative approach is to model the time-varying covariances (auto-covariances) via nonparametric estimation, which imposes very little structure on the moments of the underlying process. Because of identification issues, only parts of the model parameters are allowed to be time-varying. More precisely, we consider two specifications: First, the latent factors are stationary while the loadings are time-varying. Second, the latent factors admit a dynamic representation with time-varying autoregressive coefficients while the loadings are constant over time. Estimation of the model parameters is accomplished by application of evolutionary principal components and local polynomials. We illustrate our approach through applications to multichannel EEG data.

Ari Pakman: Oct. 10th

Ari will present the paper "The Horseshoe Estimator for Sparse Signals"

Abstract:
This paper proposes a new approach to sparse-signal detection called the horseshoe estimator. We show that the horseshoe is a close cousin of the lasso in that it arises from the same class of multivariate scale mixtures of normals, but that it is almost universally superior to the double-exponential prior at handling sparsity. A theoretical framework is proposed for understanding why the horseshoe is a better default “sparsity” estimator than those that arise from powered-exponential priors. Comprehensive numerical evidence is presented to show that the difference in performance can often be large. Most importantly, we show that the horseshoe estimator corresponds quite closely to the answers one would get if one pursued a full Bayesian model-averaging approach using a “two-groups” model: a point mass at zero for noise, and a continuous density for signals. Surprisingly, this correspondence holds both for the estimator itself and for the classification rule induced by a simple threshold applied to the estimator. We show how the resulting thresholded horseshoe can also be viewed as a novel Bayes multiple-testing procedure.

Alex Ramirez: Oct. 3rd

Alex will give a brief introduction to the method of generalized cross validation.


I'll give an introductory review on a method for model selection known as Generalized cross-validation (GCV) (see linked paper).  When dealing with linear predictor models, GCV provides a computationally convenient approximation to "leave-one-out" cross-validation.  I'll discuss this connection between cross-validation and GCV in more detail.  I'll then discuss attempts in the literature made at extending the idea behind GCV to more general models in the exponential family.  

Josh Merel: Sep. 26th

Josh will present two recent papers on unsupervised learning:
http://web.eecs.umich.edu/~honglak/cacm2011-researchHighlights-convDBN.pdf
http://research.google.com/pubs/pub38115.html