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]:
This is an interesting paper I would like to comment on and ask the authors some questions. The paper studies auto-encoders where the internal representation is approximated online by a vector whose number of non-vanishing coordinates is restricted (in other words, the internal representation is projected onto the set of all vectors with a certain L0 pseudo-norm). The proposed model, 'k-sparse autoencoders', is put in context with Arian Maleki's 'iterative thresholding with inversion' algorithm for inference of sparse code words, and a criterion is given to identify the case when one iteration is enough for perfect inference. Experiments on MNIST and small NORB show that superior classification performance (wrt. RBMs, dropout, denoising auto-encoders) can be achieved when using the proposed model to generate features and processing them with logistic regression, and that the classification performance is competitive when all the models were additionally fine-tuned. This is a cool result, since the only non-linearity used for the features is the projection.

We have done something similar, see Section 3 of the paper available at http://jmlr.org/papers/v14/thom13a.html, by using projections onto sets on which certain sparseness measures (including the L0 pseudo-norm) attain a constant value as neural transfer function in a hybrid of an auto-encoder and an MLP. Inference of the internal representation can be understood here as carrying out the first iteration of a projected Landweber algorithm. Perhaps the authors would like to discuss the relationship between both approaches?

The last sentence in the discussion after the proof of Theorem 3.1 is a bit puzzling. The theorem shows that if mu is small, then the supports of z and W^T*x are identical. The aforementioned sentence says that these supports are identical, hence mu must be small. I believe this is the converse of the theorem's statement and has not been proven, since there may be reasons other than mu being small.

The description of the k schedule in Section 4.2.1 is ambiguous. Does this mean that when we have 100 epochs, say, that k follows a linear function for epochs 1 thru 50, and then remains at the minimum level for epochs 51 to 100, or does it mean that in each epoch for the first halve of the presented samples k is adjusted and stays at the minimum for the remaining samples of the epoch, and then the schedule starts all over again in the next epoch? There are still some dead hidden units in the figures on page 6, even for k = 70 on MNIST. Would it help to increase the initial k value in the schedule, or maybe add some small random numbers to z (with some annealed variance) after setting the small entries to zero, such that backprop adjusts all the hidden units?

Just a few things I noticed while reading through the manuscript:
  - The formulation of the claim of Theorem 3.1 could be altered to be more succinct, e.g. 'supp_k(z) = supp_k(W^T*x)'. In the proof, i should be from {1, ..., k}, since i = 0 doesn't seem to make sense here.
  - Typo on page 3, left column: 'tarining'