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 paper should be citing: 'Smooth Sparse Coding via Marginal Regression
for Learning Sparse Representations', by Krishnakumar Balasubramanian, Kai Yu, and Guy Lebanon. In their work, they use a sparse coding subroutine effectively identical to your sparse coding method. The only difference in their encoding step is that they threshold the magnitude-sorted set of potential coefficients by cumulative L1 norm rather than cumulative L0 norm (a minor difference). They also add a regularization term to their objective designed to approximately minimize coherence of the learned dictionary, which may be worth trying as an addition to your current approach.

This general class of techniques, i.e. marginal regression, is reasonably well-known and has been investigated previously as a quick-and-dirty approximation to the Lasso. For more detail, see: 'A Comparison of the Lasso and Marginal Regression', by Genovese et. al. I haven't looked at this paper in a while, but it should contribute to your theory, as they present results similar to yours, but in the context of approximating the Lasso in a linear regression setting.

It might be interesting to try a 'marginalized dropout' encoding at test time, in which each coefficient is scaled by it's probability of being among the top-k coefficients when the full coefficient set is subject to, e.g., 50% dropout. This would correspond to a simple rescaling of each coefficient by its location in the magnitude-sorted list. The true top-k would still be included fully in the encoding, while coefficients outside the true top-k would quickly shrink towards 0 as you move away from the true top-k. The shrinkage factors could be pre-computed for all possible sorted list positions based on the CDF of a Binomial distribution. If 'true' sparsity is desired, the shrunken coefficients could be hard-thresholded at some small epsilon. This would 'smooth' the encoding, perhaps removing aliasing effects that may occur with a hard threshold. This would be a fairly natural encoding to use if dictionary elements were also subject to (unmarginalized) dropout at training time. The additional computational cost would be trivial, as shrinkage and thresholding would be applied simultaneously to the magnitude-sorted coefficient list with a single element-wise vector product.

Paper 1: http://www.cc.gatech.edu/~lebanon/papers/ssc_icml13.pdf
Paper 2: http://www.stat.cmu.edu/~jiashun/Research/Year/Marginal.pdf