Nuit Blanche

Friday, December 20, 2013

k-Sparse Autoencoders

The spectrum of algorithm and hardware to approximate the identity was recently featured in a Quick Panorama of Sensing from Direct Imaging to Machine Learning and one of the main issue as we go toward indirect imaging is the ability to perform certain operations Faster Than a Blink of an Eye. Here is a new attempt at using a relatively simple model of neural network borrowing operations performed from compressive sensing.

k-Sparse Autoencoders by Alireza Makhzani, Brendan Frey

Recently, it has been observed that when representations are learnt in a way that encourages sparsity, improved performance is obtained on classification tasks. These methods involve combinations of activation functions, sampling steps and different kinds of penalties. To investigate the effectiveness of sparsity by itself, we propose the k-sparse autoencoder, which is a linear model, but where in hidden layers only the k highest activities are kept. When applied to the MNIST and NORB datasets, we find that this method achieves better classification results than denoising autoencoders, networks trained with dropout, and restricted Boltzmann machines. k-sparse autoencoders are simple to train and the encoding stage is very fast, making them well-suited to large problem sizes, where conventional sparse coding algorithms cannot be applied.

Looks like a simple implementation that really seems to follow the steps of an actual IHT implementation with sparse constraints on the coefficient during the iteration and this reminds me of [1]. Let us note that the scores to beat for fine tuned implementations are:

for the MNIST dataset: 0.23%
for the NORB dataset: 2.53%

both records held by the same group. More on that later.

[1] Convergence of a Neural Network for Sparse Approximation using the Nonsmooth Łojasiewicz Inequality by Aurele Balavoine, Christopher Rozell, Justin Romberg

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

The loneliness of the long distance blogger

Larry tells us that Normal Deviate ends. As we all know, it's not the destination that matters, it's the journey:

“…il faut imaginer Sisyphe heureux…’

Related: Manjhi's Myth

#NIPS2013 sweet aftertastes

The final sunset of #NIPS2013. Thanks Tahoe, you've been a great host. See everyone at the 7pm reception tonight. pic.twitter.com/wRX9iyr97m
— NIPS (@NipsConference) December 11, 2013

So NIPS2013 is finished, let's see what was interesting and picked by others:

Blog coverage:

Sebastien Bubeck wrote a rather long entry on some NIPS presentations in A good NIPS!
Hein talks about Zygmunt Zając who wrote about “13 NIPS Papers that caught our eye”
Memming NIPS 2013

I also found these links of interest

As well as well as these tweets and their interesting links suggested on the #NIPS2013 tag on twitter (here is google docs list of all the tweets):

Animesh Garg ‏@Animesh_Garg

Approximate Bayesian Image Interpretation using Generative Probabilistic Graphics Programs Vikash K. Mansinghka, Tejas D. Kulkarni, Yura N. Perov, Joshua B. Tenenbaum

Il Memming Park ‏@memming

A simple example of Dirichlet process mixture inconsistency for the number of components[PDF]

Suvash Sedhain ‏@suvsh

Deep content based recommendation #NIPS2013 http://media.nips.cc/nipsbooks/nipspapers/paper_files/nips26/1239.pdf … and my answer in Quora

brendan o'connor ‏@brendan64

since i keep telling people at #nips2013 about @redpony's notes on adagrad, here they are, they are handy => http://www.ark.cs.cmu.edu/cdyer/adagrad.pdf …

Notes on AdaGrad by Chris Dyer

Andreas Mueller ‏@t3kcit

Great tutorial by Rob Fergus on Deep Learning for Vision at #NIPS2013. Slides up soon, for now read their paper: http://arxiv.org/pdf/1311.2901v3.pdf …

brendan o'connor ‏@brendan64

#NIPS2013 I really love Pearl's 2009 review http://ftp.cs.ucla.edu/pub/stat_ser/r350.pdf … I imagine this tutorial is hard to understand w/o reading that first ...

.@brendan642 #NIPS2013

.. also good are Cosma Shalizi's book chapters: http://www.stat.cmu.edu/~cshalizi/uADA/12/lectures/ch22.pdf … http://www.stat.cmu.edu/~cshalizi/uADA/12/lectures/ch23.pdf … http://www.stat.cmu.edu/~cshalizi/uADA/12/lectures/ch24.pdf …

Shane Conway ‏@statalgo

"Approximate Dynamic Programming Finally Performs Well in the Game of Tetris" http://media.nips.cc/nipsbooks/nipspapers/paper_files/nips26/881.pdf … #ADP #NIPS2013

Alexandre Passos ‏@atpassos_ml

New blog post: #NIPS2013 reading list http://atpassos.me/post/67560831508/nips-2013-reading-list …

Gilles Louppe ‏@glouppe

My step for #OpenScience: code+demo for our #NIPS2013 paper "Understanding variable importances in random forests" https://github.com/glouppe/paper-variable-importances …

Animesh Garg ‏@Animesh_Garg

Distributed Submodular Maximization: Simple effective and very few assumptions on functions win-win #NIPS2013 http://bit.ly/1gNBNVb

Richard ‏@RichardSocher

Demo of our website to make machine learning for text classification easily accessible: http://etcml.com at #NIPS2013

Gilles Louppe ‏@glouppe

Just presented "Scikit-Learn: Machine Learning in the Python ecosystem" at MLOSS #NIPS2013 Find the notebook at http://nbviewer.ipython.org/github/glouppe/talk-sklearn-mloss-nips2013/blob/master/oral/sklearn-mloss.ipynb …

Andreas Mueller ‏@t3kcit

ClowdFlows looks like a great way to design data pipelines and do interactive exploration via the web http://www.clowdflows.org/ #NIPS2013

Olivier Grisel ‏@ogrisel

Decision Jungles: memory efficient alternative to randomized trees http://papers.nips.cc/paper/5199-decision-jungles-compact-and-rich-models-for-classification … /cc @glouppe @pprett via @Chris_Said #NIPS2013

Andreas Mueller ‏@t3kcit

As a consequence of #NIPS2013 I'm finally installing pylearn2 http://deeplearning.net/software/pylearn2/ … Probably the best way to get started with deep learning

Chandra ‏@sekhardrona

Deep learning algorithms could make smart drugs http://goo.gl/Mm2Qq5 via @physorg_com #NIPS2013 #MachineLearning

Dave Sullivan ‏@_DaveSullivan

FastML: 13 #NIPS2013 papers that caught our eye http://fastml.com/13-nips-papers-that-caught-our-eye/ …

Dirk Gorissen ‏@elazungu

Interesting paper from #NIPS2013 "able to predict >95% of the weights of a deep NN without any drop in accuracy" http://media.nips.cc/nipsbooks/nipspapers/paper_files/nips26/1053.pdf …

Adam Stankiewicz ‏@astankiew

NIPS 2013 Workshop on Data Driven Education http://lytics.stanford.edu/datadriveneducation/index.html#panel … #nips2013 via @jonathanhuang11

eliana feasley ‏@eli_awry

Announced KA data sharing plans at #NIPS2013 . We're working on a whitepaper with more details, but initial info at http://khanacademy.org/r/research

Chandra ‏@sekhardrona

explain my data: NIPS and the Zuckerberg Visit http://goo.gl/CrRbif #NIPS2013 #DeepLearning

Michael Witbrock ‏@witbrock

My latest : Cyc and Semantic Construction Grammar #NIPS2013… on @slideshare http://www.slideshare.net/witbrock/cyc-and-semantic-construction-grammar-nips-2013-ket-workshop … via @SlideShare

Tim van Erven ‏@tverven

Blog post: Wrote a PAC-Bayes mini-tutorial on the plane to #NIPS2013 to relate to standard concentration inequalities http://www.timvanerven.nl/blog/2013/12/pac-bayes-mini-tutorial-a-continuous-union-bound/ …

joseph reisinger ‏@josephreisinger

"Machine learning is a complex ecosystem"— Max Welling on the whole "Zuck at #nips2013" thing http://scientificpearlsofwisdom.blogspot.com/2013/12/i-was-conference-chair-for-nips-2013.html …

Erin LeDell ‏@ledell

Now anyone that can query a database can do Bayesian inference http://probcomp.csail.mit.edu/bayesdb/index.html … #BayesDB
Dropout (neural networks/Geoffrey Hinton) as adaptive regularization in GLMs #NIPS2013 http://media.nips.cc/nipsbooks/nipspapers/paper_files/nips26/246.pdf …

Erin LeDell ‏@ledel

Compressive feature learning can reduce text feature space by two orders of magnitude compared to k-grams #NIPS2013 http://media.nips.cc/nipsbooks/nipspapers/paper_files/nips26/1342.pdf …

Join the CompressiveSensing subreddit or the Google+ Community and post there !

CSJob: Post-Doc position at Université libre de Bruxelles (ULB) Compressive sensing for multi-antenna traffic radar

Francois Horlin just sent me the following postdoc announcement (all job announcements are with the CSjobs tag or listed as [job] in the compressive sensing study group on LinkedIn):

Post-Doc position at Université libre de Bruxelles (ULB)

Compressive sensing for multi-antenna traffic radar

Duration: 24 months

Today most of the radars used to monitor road traffic are only capable of estimating the speed and distance of the vehicles moving in the direction of the receive antenna. This is performed by analyzing the response of the channel to multiple impulses successively transmitted on a set of equally spaced carrier frequencies. It has recently been proposed to make use of an antenna array at the receiver to further detect the signal direction of arrival. The signals received at the different antennas are constructively combined using a beamforming algorithm taking the direction of arrival into account. New radars are therefore capable of monitoring the vehicle targets in the distance/angle/speed space. Even if recently designed radars are shown to perform well, their resolution in the three dimensions is limited by the finite bandwidth used to scan the spectrum and by the limited number of antennas in the array. The aim of the project is to significantly increase the resolution of the radar by using the compressive sensing technology. It relies on the fact that only a small fraction of the distance/angle/speed cells are occupied by objects of interest in most radar scenes. Compressive sensing makes it possible to reconstruct a sparse signal from an underdetermined linear system of equations and to increase therefore significantly the radar resolution.

Contact:

Prof. Ph De Doncker (pdedonck@ulb.ac.be)

Prof. Fr Horlin (fhorlin@ulb.ac.be)

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Thursday, December 19, 2013

Matheon Workshop 2013 on Compressed Sensing and its Applications

Last April, we announced the Matheon Workshop 2013 on Compressed Sensing and its Applications. It was held last week and the attendant booklet is here. Here is the program:

Monday, 9. 12.

9:00-10:00 Volker Mehrmann (Technische Universität Berlin, Germany) Reduced order modeling of parameter dependent nonlinear eigenvalue bifurcation problems
10:00-10:30 Coffee break (Room H 3004)
10:30-11:05 Rémi Gribonval (Centre de Recherche INRIA Rennes, France) Fundamental performance limits of decoders in high-dimensional linear inverse problems
11:05-11:40 Petros Boufounos (Mitsubishi Electric Research Laboratory, USA) On the representation and coding of signal distances
11:40-12:15 Mark Davenport (Georgia Institute of Technology, USA) Compressive sensing in the analog world
12:15-14:00 Lunch break
14:00-15:00 Ali Pezeshki (Colorado State University, USA) Compressed sensing and high-resolution image inversion
15:00-15:30 Coffee break (Room H 3004)
15:30-16:05 David Gross (Universität Freiburg, Germany) A partial derandomization of PhaseLift using spherical designs
16:05-16:40 Chris Rozell (Georgia Institute of Technology, USA) On the move: Dynamical systems for modeling, measurement and inference in compressed sensing
16:40-17:15 Waheed Bajwa (Rutgers University, USA) Low-complexity subspace unmixing

Tuesday, 10. 12. 8:00-9:00 Registration (Room H 3004)

9:00 – 10:00 Guillermo Sapiro (Duke University, USA) Learning to cluster and classify
10:00-10:30 Coffee break (Room H 3004)
10:30-11:05 Rebecca M. Willett (Duke University, USA) Minimax optimal rates for photon-limited compressed sensing
11:05-11:40 Volkan Cevher (EPFL, Switzerland) Composite self-concordant minimization
11:40-12:15 Christof Schütte (Freie Universität Berlin & Zuse-Institut Berlin (ZIB), Germany) Sparsity in molecular dynamics
12:15-14:00 Lunch break
14:00-17:15 Poster Session & Coffee (Atrium of the main building)

Wednesday, 11. 12. 8:00-9:00 Registration (Room H 3004)

9:00-10:00 Babak Hassibi (California Institute of Technology, USA) Recovering structured signals from noisy measurements: Where least-squares meets compressed sensing
10:30-11:05 Holger Rauhut (RWTH Aachen, Germany) Interpolation via weighted l1-minimization
11:05-11:40 Anders Hansen (University of Cambridge, UK) Compressed sensing in the real world - The need for a new theory
11:40-12:15 Matthew Fickus (AFIT, USA) Equiangular tight frames and the restricted isometry property

Thursday, 12. 12. 8:00-9:00 Registration (Room H 3004)

9:00-10:00 Martin Vetterli (EPFL, Switzerland) Inverse problems regularized by sparsity
10:30-11:05 Reinhold Schneider (Technische Universität Berlin, Germany) Numerical methods for low rank recovery of hierarchical tensors
11:05-11:40 Shmuel Friedland (University of Illinois at Chicago, USA) Compressive sensing of sparse tensors
11:40-12:15 Massimo Fornasier (Technische Universität München, Germany) Quasi-linear compressed sensing and applications in asteroseismology
12:15-14:00 Lunch break
14:00-15:00 Richard Baraniuk (Rice University, USA) Video compressive sensing
15:00-15:30 Coffee break (Room H 3004)
15:30-16:05 Dustin Mixon (AFIT, USA) A new approach to derandomize compressed sensing matrices
16:05-16:40 Rachel Ward (University of Texas at Austin, USA) Stochastic gradient descent with importance sampling
16:40-17:15 Felix Krahmer (Universität Göttingen, Germany) Dimension reduction techniques for efficient subspace approximation

Friday, 13. 12. 8:00-9:00 Registration (Room H 3004)

9:00-10:00 Helmut Bölcskei (ETH Zürich, Switzerland)
Signal recovery, uncertainty relations, and Rényi information dimension
10:00-10:30 Coffee break (Room H 3004)
10:30-11:05 Miguel Rodrigues (University College London, UK) Fundamental limits on the performance of compressive classification: A characterization inspired by dualities between classification and wireless communications problems
11:05-11:40 Peter Jung (Technische Universität Berlin, Germany)
Low-complexity model uncertainties in compressed sensing with application to
sporadic communication
11:40-12:15 Philipp Walk (Technische Universität München, Germany)
Stable embedding of sparse convolutions
12:15-12:30 Closing remarks

Join the CompressiveSensing subreddit or the Google+ Community and post there !

If you don't think knowing the future is a great advantage ...

I was watching Don Valentine from Sequoia Capital on "Target Big Markets" for an MBA crowd at Stanford. It's as if I had used his argument in writing Predicting the Future: The Steamrollers. Check it out at 34 minutes,

"only one metric that matters is cash flow....I didn't tell you early on, I had a special advantage going into the VC business....I knew the future, if you don't think knowing the future is a great advantage, it's a phenomenal advantage...made it easy for us to invest in Atari, all microprocessors driven...Apple...aim the entrepreneurs at things that were silicon intensive..."

It is still an advantage.

Related: The Business Side of Sensors, Part Deux

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Optimization for Compressed Sensing: the Simplex Method and Kronecker Sparsification - implementation -

Optimization for Compressed Sensing: the Simplex Method and Kronecker Sparsification by Robert Vanderbei, Han Liu, Lie Wang, Kevin Lin

In this paper we present two new approaches to efficiently solve large-scale compressed sensing problems. These two ideas are independent of each other and can therefore be used either separately or together. We consider all possibilities.

For the first approach, we note that the zero vector can be taken as the initial basic (infeasible) solution for the linear programming problem and therefore, if the true signal is very sparse, some variants of the simplex method can be expected to take only a small number of pivots to arrive at a solution. We implemented one such variant and demonstrate a dramatic improvement in computation time on very sparse signals.

The second approach requires a redesigned sensing mechanism in which the vector signal is stacked into a matrix. This allows us to exploit the Kronecker compressed sensing (KCS) mechanism. We show that the Kronecker sensing requires stronger conditions for perfect recovery compared to the original vector problem. However, the Kronecker sensing, modeled correctly, is a much sparser linear optimization problem. Hence, algorithms that benefit from sparse problem representation, such as interior-point methods, can solve the Kronecker sensing problems much faster than the corresponding vector problem. In our numerical studies, we demonstrate a ten-fold improvement in the computation time.

The implementation is available here:

http://orfe.princeton.edu/~rvdb/tex/CTS/kronecker_sim.html

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Wednesday, December 18, 2013

The curious case of the GTZAN dataset

Many algorithms are using the GTZAN dataset for music genre recognition, but like they say in Texas: "They ain't recognizing genre"

The GTZAN dataset: Its contents, its faults, their effects on evaluation, and its future use by Bob Sturm

The GTZAN dataset appears in at least 100 published works, and is the most-used public dataset for evaluation in machine listening research for music genre recognition (MGR). Our recent work, however, shows GTZAN has several faults (repetitions, mislabelings, and distortions), which challenge the interpretability of any result derived using it. In this article, we disprove the claims that all MGR systems are affected in the same ways by these faults, and that the performances of MGR systems in GTZAN are still meaningfully comparable since they all face the same faults. We identify and analyze the contents of GTZAN, and provide a catalog of its faults. We review how GTZAN has been used in MGR research, and find few indications that its faults have been known and considered. Finally, we rigorously study the effects of its faults on evaluating five different MGR systems. The lesson is not to banish GTZAN, but to use it with consideration of its contents.

Classification Accuracy Is Not Enough: On the Evaluation of Music Genre Recognition Systems by Bob Sturm

We argue that an evaluation of system behavior at the level of the music is required to usefully address the fundamental problems of music genre recognition (MGR), and indeed other tasks of music information retrieval, such as autotagging. A recent review of works in MGR since 1995 shows that most (82 %) measure the capacity of a system to recognize genre by its classification accuracy. After reviewing evaluation in MGR, we show that neither classification accuracy, nor recall and precision, nor confusion tables, necessarily reflect the capacity of a system to recognize genre in musical signals. Hence, such figures of merit cannot be used to reliably rank, promote or discount the genre recognition performance of MGR systems if genre recognition (rather than identification by irrelevant confounding factors) is the objective. This motivates the development of a richer experimental toolbox for evaluating any system designed to intelligently extract information from music signals.

Bob also has page where one can listen/play excerpts featuring repetitions, potential mislabelings and distortions in the GTZAN dataset. It is here at:

http://imi.aau.dk/~bst/research/GTZANtable2/

of further interest: Formalizing Evaluation in Music Information Retrieval: A Look at the MIREX Automatic Mood Classification Task by Bob Sturm

We develop a formalism to disambiguate the evaluation of music information retrieval systems.We de ne a \system," what it means to \analyze" one, and make clear the aims, parts, design, execution, interpretation, and assumptions of its \evaluation." We apply this formalism to discuss the MIREX automatic mood classi cation task.

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Tuesday, December 17, 2013

Sample Complexity of Dictionary Learning and other Matrix Factorizations

Here is something that touches on the several advanced matrix factorization techniques that have sprung up in the past few years:

Dear Igor,

We have just finalized a paper which considers the sample complexity of DL and other matrix factorizations. The topic might be of interest for the Nuit Blanche readers and we would be delighted if you could advertise our preprint, which is available here

http://arxiv-web3.library.cornell.edu/abs/1312.3790

Thanks a lot and best wishes,

Martin

Prof. Dr. Martin Kleinsteuber

Geometric Optimization & Machine Learning Group

Cluster CoTeSys www.cotesys.de

TU München www.gol.ei.tum.de

Thanks Martin ! Here is the paper: Sample Complexity of Dictionary Learning and other Matrix Factorizations by Rémi Gribonval, Rodolphe Jenatton, Francis Bach,Martin Kleinsteuber, Matthias Seibert

Many modern tools in machine learning and signal processing, such as sparse dictionary learning, principal component analysis (PCA), non-negative matrix factorization (NMF), K-means clustering, etc., rely on the factorization of a matrix obtained by concatenating high-dimensional vectors from a training collection. While the idealized task would be to optimize the expected quality of the factors over the underlying distribution of training vectors, it is achieved in practice by minimizing an empirical average over the considered collection. The focus of this paper is to provide sample complexity estimates to uniformly control how much the empirical average deviates from the expected cost function. Standard arguments imply that the performance of the empirical predictor also exhibit such guarantees. The level of genericity of the approach encompasses several possible constraints on the factors (tensor product structure, shift-invariance, sparsity \ldots), thus providing a unified perspective on the sample complexity of several widely used matrix factorization schemes.

Join the CompressiveSensing subreddit or the Google+ Community and post there !

XNV: Correlated random features for fast semi-supervised learning - implementation -

Following up on Randomization is not a dirty word, Brian McWilliams sent me the following:

Dear Igor,

Your posts over the past few years about random features and randomized algorithms have been very interesting and a great source of ideas.

I'd like to draw your attention to a paper that we had at NIPS this year which leverages random features to perform multi-view regression using canonical correlation analysis which I hope will be of interest to your audience.

In the presence of a large amount of unlabaled data, multi-view CCA regression is a way to leverage two distinct sets of features (or views) of data to perform semi-supervised learning by penalising uncorrelated features in the CCA basis. It was shown by Kakade and Foster (2007) that if a so-called multi-view assumption is fulfilled this leads to a nice bound on the generalisation error due to a potentially large reduction in variance. However, this assumption is rarely fulfilled in practise and so CCA regression has not really taken off. We make the observation that independently generating two sets of random features (we present results using both Nyström and Fourier features) automatically fulfils the multi-view assumption. In the paper we present a simple algorithm to perform semi-supervised learning and extensive results on publicly available datasets.

The paper is available here:

http://arxiv.org/abs/1306.5554

and some basic software is available here:

http://www.inf.ethz.ch/personal/mcbrian/software/ccaregression.zip

Cheers,

Brian

Thanks Brian !

Here is the paper: Correlated random features for fast semi-supervised learning by Brian McWilliams, David Balduzzi, Joachim M. Buhmann

This paper presents Correlated Nystrom Views (XNV), a fast semi-supervised algorithm for regression and classification. The algorithm draws on two main ideas. First, it generates two views consisting of computationally inexpensive random features. Second, XNV applies multiview regression using Canonical Correlation Analysis (CCA) on unlabeled data to bias the regression towards useful features. It has been shown that, if the views contains accurate estimators, CCA regression can substantially reduce variance with a minimal increase in bias. Random views are justified by recent theoretical and empirical work showing that regression with random features closely approximates kernel regression, implying that random views can be expected to contain accurate estimators. We show that XNV consistently outperforms a state-of-the-art algorithm for semi-supervised learning: substantially improving predictive performance and reducing the variability of performance on a wide variety of real-world datasets, whilst also reducing runtime by orders of magnitude.

Join the CompressiveSensing subreddit or the Google+ Community and post there !