k-Sparse Autoencoders
Authors: Alireza Makhzani, Brendan Frey
ICLR 2014

Abstract: 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.


Peer review:
[Review]:
* Brief summary of the paper:

The paper investigates a very simple heuristic technique for a simple autoencoder to learn a sparse encoding: the nonlinearity consists in only retaining the top-k linear activations among the hidden units and setting the others to zero. With the thus trained k-sparse autoencoers, the authors were able to outperform (on MNIST and NORB) features learned with denoising autoencoders, RBMs or dropout, as well as deep networks pre-trained with those techniques and fine-tuned. 

* Assessment:

This is an interesting investigation of a very simple approach to obtaining sparse representations that empirically seem to perform very well. It does have a number of weaknesses:

- I find it misleading to call this a *linear model* as in the abstract. A piecewise linear function is *not* a linear function. The model does use a non-linear sparsification operation.
- For such a simple approach, I find the actual description of the algorithm (especially in the algorithm box) disappointingly fuzzy, unclear, confusing and probably wrong:
  What is the exact objective being optimized? Is is always squared reconstruction error? It is not written in the box. Also do you really reconstruct x^ from a z that has not been sparsified (as is written in step 1)?? This is contrary to my understanding from reading the rest of the paper. I believe it would be much clearer to introduce an explicit sparsification step before the reconstruction. Similarly, with your definition of supp, it looks like the result of your sparse encoding h is a *set of indices* rather than a sparse vector. Is this intended? Wouldn't it be clearer to define an operation that returns a sparse vector rather than a set of indices? The algorithm box should be rewritten more formally, removing any ambiguity.
- Section 3.3: While I find the discussion on the importance of decoherence interesting, I do not believe you can formally draw your conclusion from it, since you do not have the strict equality x = Wz (perfect reconstruction) that your theorem depends on but only an approximate reconstruction. So I would mitigate the final claims. 
- I wonder how thoroughly you have explored the hyper-parameter space for the other pre-training algorithms you compare yourself with, especially those that are expected to influence sparsity or control capacity somehow, as e.g. the noise level for denoising autoencoders and dropout?? Did you but try a single a-priori chosen value? If so the comparisons might be a little unfair since you hyper-optimized your alpha on the validation set.

* Pros and Cons:

Pros: 
+ interesting approach due to its simplicity 
+ very good empirical classification performance.

Cons:
- confusing description of the algorithm (in algorithm box); 
- possibly insufficient exploration of hyper-parameters of competing algorithms (relative to the amount of tweakings of the proposed approach).