PaperlayerView exact revision on arXiv

Source-linked AI summary

k-Sparse Autoencoders

Alireza Makhzani, Brendan Frey

arXiv:1312.5663v2cs.LG

TL;DR

Sparse coding methods can be computationally expensive, while existing sparse autoencoders often combine several mechanisms rather than isolating sparsity. The paper introduces a linear k-sparse autoencoder that keeps only the k highest hidden activities and reports better classification results than several competing methods on MNIST and NORB. Its representations also support fast sparse coding and pre-training, although very low k can create dead hidden units and theoretical guarantees rely on assumptions such as dictionary incoherence.

  • Problem

    Sparse coding is computationally expensive, and prior sparse autoencoders combine activation functions, sampling steps, and penalties rather than testing sparsity by itself.

  • Method

    The paper introduces a linear, tied-weight autoencoder that enforces exact sparsity by retaining only the k largest hidden activities.

  • Results

    The method achieves better classification results than RBMs, denoising autoencoders, and dropout methods on MNIST and NORB, with best settings of k = 25, α = 3 on MNIST and k = 150, α = 2 on NORB.

  • Takeaways & Limitations

    K-sparse autoencoders provide a fast sparse coding method whose representations can be used for classification and pre-training shallow and deep supervised architectures.

  • Takeaways & Limitations

    Very low sparsity can leave hidden units dead, while the stated recovery guarantee assumes an incoherent dictionary and bounded sparsity conditions.

Abstract

from arXiv · show

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 an autoencoder with linear activation function, 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 RBMs. 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.

1. Introduction

The paper targets computationally expensive sparse coding and tests whether sparsity alone can produce effective representations. It introduces k-sparse autoencoders and evaluates their classification and pre-training performance against established methods.

  • Motivation: Sparse coding is computationally expensive because dictionary learning and sparse encoding require iterative optimization procedures.Encoding commonly uses pursuit methods, while dictionary updates may require matrix inversion or SVD computations.
  • Motivation: Existing sparse autoencoders combine activation functions, sampling steps, and penalties, and may not produce sparse representations for every input.Lifetime sparsity penalties encourage sparse hidden-unit marginals rather than enforcing exact per-input sparsity.
  • Contributions: K-sparse autoencoders use sparsity as the sole regularizer and nonlinearity, while retaining linear autoencoder components.The method keeps only the k largest hidden activities and sets the others to zero.
  • Contributions: The paper explores how different sparsity levels k affect learned representations and classification performance.This isolates the effect of sparsity level as an experimental variable.
  • Contributions: K-sparse autoencoders are reported to outperform RBMs, denoising autoencoders, and dropout methods, while achieving results comparable to the state of the art on MNIST and NORB.The paper also presents them as efficiently learnable and usable for sparse coding and pre-training.

2. Description of the Algorithm

The k-sparse autoencoder uses a linear, tied-weight autoencoder whose hidden representation retains only the k largest activities. A related encoding variant can retain αk activities for downstream classification when validation indicates improved performance.

  • Basic Autoencoder: A basic autoencoder maps x to z = f(Px+b), then reconstructs the input linearly as x̂ = Wz + b′.Training minimizes mean square reconstruction error, often with tied weights P = W^T.
  • K-Sparse Autoencoder: The k-sparse autoencoder computes z = W^T x + b and keeps only the k largest hidden activities, setting the rest to zero.The support of the resulting representation is supp_k(W^T x+b).
  • K-Sparse Autoencoder: The k active units can be selected by sorting activities or by adaptively thresholding ReLU hidden units.Both procedures identify the same top-k support used for reconstruction and backpropagation.
  • Classification Encoding: For downstream classification, the encoder may retain the αk largest hidden units with α ≥ 1 instead of exactly k.The paper reports that this mismatch between training and classification encodings can yield slightly better performance, with α selected using validation data.
  • Optimization: Training backpropagates the error through the selected top-k activations while ignoring the remaining hidden units.The procedure computes the feedforward code, selects the largest activations, reconstructs the input, and iterates.

3. Analysis of the k-Sparse Autoencoder

The analysis interprets the k-sparse autoencoder as an approximation to iterative thresholding with inversion and dictionary learning. Its first-step support recovery depends on dictionary incoherence, which also supports robustness and invariant sparse features.

  • Iterative thresholding with inversion: In the first ITI step, the support is estimated by selecting the k largest entries of W^⊺x, then restricting W to those selected columns.The selected subdictionary WΓ is used to estimate the non-zero coefficients.
  • Sparse coding interpretation: The k-sparse autoencoder approximates sparse coding by combining ITI-based support recovery with a dictionary update stage.The autoencoder jointly approximates inversion and dictionary updates rather than explicitly solving the full sparse-coding procedure.
  • Support recovery: Unlike fixed-dictionary sparse recovery, an adapted learned dictionary can make the first ITI iteration sufficient to find the support set.With a fixed dictionary, ITI generally requires a fixed number of iterations for perfect reconstruction.
  • Iterative thresholding with inversion: The inversion step uses the pseudo-inverse of WΓ to estimate non-zero coefficients, while a single gradient-descent step approximates this computationally expensive operation.Back-propagation through the encoder approximates the corresponding pseudo-inverse update.
  • Importance of incoherence: If the dictionary is sufficiently incoherent, small noise, translation, or rotation perturbations can preserve sparse features while retaining perfect reconstruction.Dictionary incoherence is linked to a unique sparse representation within an attraction ball around the signal.
  • Importance of incoherence: Under the theorem's assumptions, support recovery from suppk(W^⊺x) is guaranteed when kµ ≤ z_k/(2z_1).The dictionary columns have unit ℓ2-norm, and the non-zero coefficients are ordered z_1 ≥ z_2 ≥ ... ≥ z_k.

4. Experiments

The experiments evaluate k-sparse autoencoders in unsupervised learning and in shallow and deep discriminative learning tasks.

  • The evaluation covers both unsupervised learning and discriminative learning.The discriminative settings include shallow and deep tasks.
  • Shallow discriminative learning is included as an evaluation setting.
  • Deep discriminative learning is included as an evaluation setting.

4.1. Datasets

The study evaluates MNIST, NORB, and CIFAR-10 image patches, using dataset-specific splits, resizing, and preprocessing procedures.

  • MNIST provides 60,000 training images and 10,000 test images, with 50,000 training cases and 10,000 validation cases.
  • NORB contains 24,300 training and 24,300 test examples from 50 toys across five categories.Images use two 96 × 96 channels, cropped to 64 × 64 and resized to 32 × 32, producing 2048-dimensional vectors.
  • CIFAR-10 supplies 1,000,000 randomly extracted 8×8 natural-image patches from 50,000 32×32 images.
  • CIFAR-10 patches are locally contrast-normalized and ZCA-whitened using the preprocessing pipeline of Coates et al. (2011).

4.2. Training of k-Sparse Autoencoders

Training uses stochastic gradient descent with momentum, while sparsity scheduling addresses dead hidden units that can arise when k is very small.

  • Scheduling of the Sparsity Level: Too much sparsity can leave hidden units unused because greedy early assignments prevent their weights from receiving gradient updates.The issue is reported for low sparsity levels such as k=15 on MNIST.
  • Scheduling of the Sparsity Level: Sparsity scheduling starts with k=100 and linearly decreases to k=15 during the first half of training.The target k=15 is then maintained during the second half of training.
  • Optimization: Model parameters are optimized using stochastic gradient descent with momentum.
  • Optimization: MNIST unsupervised training uses σ = 0.01, m_k = 0.9, η_k = 0.01, and 5000 epochs.Hyperparameters vary by task and dataset, with validation used for selection.
  • Optimization: The supervised NORB schedule decreases the learning rate from 0.01 to 0.001 over 200 epochs.
  • Computational properties: K-sparse autoencoders require matrix multiplications and sorting rather than matrix inversion or SVD in learning and encoding.Sorting can be replaced by recursive thresholding in a parallel distributed implementation.

4.3. Effect of Sparsity Level

Changing k alters learned feature locality and classification suitability: moderate sparsity produces more global features, while excessive sparsity can make them overly global.

  • Effect of Sparsity Level: Large k values such as k=100 on MNIST produce very local features that are unsuitable for shallow linear classification.The same features may be useful for pre-training deep neural networks.
  • Effect of Sparsity Level: Decreasing sparsity to k=40 on MNIST reconstructs inputs with fewer hidden units and produces more global features.The learned stroke lengths increase as sparsity decreases.
  • Effect of Sparsity Level: Forcing k=10 on MNIST produces features that are too global to factor inputs into parts.
  • CIFAR-10 filters: With 1000 hidden units and k=50, CIFAR-10 patches yield localized Gabor filters.
  • MNIST filters: Figure 1 presents MNIST filters learned with 1000 hidden units across different sparsity levels.
  • NORB filters: Figure 2 presents NORB filters learned with 4000 hidden units across different sparsity levels.

4.4. Unsupervised Feature Learning Results

The study evaluates learned features by fixing them and training logistic regression classifiers, comparing unsupervised methods on NORB. The k-sparse autoencoder performs best among the compared architectures, with dataset-specific settings selected for MNIST and NORB.

  • Features were evaluated by training a logistic regression classifier after fixing representations learned by each unsupervised method.The classifier’s error rate measures feature usefulness.
  • The NORB comparison covers unsupervised learning methods without fine-tuning using 4000 hidden units.
  • The k-sparse autoencoder outperformed the other evaluated algorithms in the classification comparisons.
  • The best MNIST configuration used k = 25, α = 3 with 1000 hidden units, while NORB used k = 150, α = 2 with 4000 hidden units.

4.5. Shallow Supervised Learning Results

The shallow supervised experiments use unsupervised representations to initialize discriminative neural networks, then apply discriminative fine-tuning. The reported comparisons include RBMs, DBNs, DBMs, third-order RBMs, dropout autoencoders, denoising autoencoders, and k-sparse autoencoders.

  • Unsupervised representations are used to initialize the early layers of a multilayer discriminative model.
  • The MNIST shallow-learning comparison uses 1000-hidden-unit unsupervised pre-training followed by model fine-tuning.
  • Discriminative fine-tuning adjusts the last hidden layer and fine-tunes preceding layers using back-propagation.
  • The compared initialization methods include RBMs, DBNs, DBMs, third-order RBMs, dropout autoencoders, denoising autoencoders, and k-sparse autoencoders.

4.6. Deep Supervised Learning Results

Deep supervised models are initialized through greedy layer-wise pre-training with stacked k-sparse autoencoders, followed by staged and joint fine-tuning. Experiments on NORB compare supervised methods pretrained with unsupervised algorithms.

  • A shallow k-sparse autoencoder is trained first, then a second k-sparse autoencoder learns codes on top of its fixed features.
  • The NORB deep-learning comparison uses 4000-hidden-unit unsupervised pre-training followed by fine-tuning.
  • The two autoencoders initialize a discriminative neural network with two hidden layers.
  • Fine-tuning proceeds from a softmax classifier to layer-wise joint training and finally joint optimization of all layers.
  • Both hidden layers retain the αk largest hidden codes, using k = 25, α = 3 on MNIST and k = 150, α = 2 on NORB.

5. Conclusion

The paper concludes that k-sparse autoencoders provide fast sparse coding with exact hidden sparsity. Their representations achieve state-of-the-art classification results using sparsity alone and support pre-training for shallow and deep supervised architectures.

  • The k-sparse autoencoder is presented as a very fast sparse coding method with exact sparsity in hidden representations.
  • State-of-the-art classification results are achieved by enforcing sparsity without additional nonlinearities or regularization.
  • The method can be used for pre-training both shallow and deep supervised architectures.
Loading 1312.5663v2…