PCA as a Representation Method

From Raw Values to Useful Features

An image may be presented to a learning algorithm as a long list of pixel values. Those values are the input, but they do not automatically form the most useful description for predicting a label. Dictionary learning addresses this gap by searching for reusable features, sometimes called words or atoms, and representing each instance through those learned features.

The idea is related to text processing. A document can be represented by coordinates indicating which dictionary words occur in it. Text already supplies the dictionary. Images and other complicated data do not come with an equally direct vocabulary, so dictionary learning tries to discover a useful collection of features instead.

Tracing an Auto-Encoder

An auto-encoder learns two functions. The encoder, written as ψ, maps an input from the original d-dimensional space into a k-dimensional representation. The decoder, written as φ, maps that representation back into the original space. The encoder therefore produces the code, while the decoder uses the code to reconstruct the input.

For a collection of inputs, learning seeks encoder and decoder functions that make the total squared difference between each original input and its reconstruction small. This objective encourages the code to retain information that the decoder needs for rebuilding the input.

Why Reconstruction Needs Constraints

Reconstruction alone is not a sufficient definition of a useful representation. If k equals d and the encoder and decoder simply return their inputs, the reconstruction is perfect, but the representation has not provided a meaningful restriction or transformation. The functions must therefore be constrained in some way so that copying every input is not the easiest solution.

Sparse Codes and Dictionary Atoms

The encoder decides which dictionary coordinates are active. The decoder then combines the corresponding dictionary atoms using the values in those active coordinates. The resulting reconstruction is useful when a compact code preserves enough information about the input.

The K-Means Connection

A first dictionary-learning attempt is to cluster the training instances. Each cluster acts like a dictionary word, and an input receives an indicator for its assigned cluster. This representation is very sparse because only one coordinate is active.

In k-means, the encoder produces exactly one nonzero coordinate identifying the closest centroid. A natural extension permits at most s nonzero coordinates instead of exactly one. The decoder can then combine the corresponding dictionary atoms using their representation values.

Common Reasoning Mistakes

• Treating the learned dictionary as if it were a vocabulary supplied in advance.

  Text supplies a natural dictionary, but images do not come with an equally direct vocabulary.

  Fix: Explain that dictionary learning searches for reusable features when meaningful entries are not obvious beforehand.

• Assuming that every cluster member receives a different representation.

  A simple cluster representation gives every member of one cluster the same dictionary representation.

  Fix: Recognize that this can force a linear predictor to assign the same target value to all instances in that cluster.

• Concluding that perfect reconstruction automatically means useful learning.

  The pair can reconstruct perfectly without providing a meaningful restriction or transformation.

  Fix: Ask what restriction prevents the functions from copying every input.

• Confusing sparsity with using every dictionary atom weakly.

  A sparse representation has many zero entries and only a limited number of nonzero entries.

  Fix: Focus on the small active set selected by the encoder.

• Describing sparse coding as identical to k-means.

  K-means uses one active indicator, while the extended sparse construction permits at most s active coordinates.

  Fix: State whether the representation selects one centroid or a small set of dictionary atoms.

Practice and Summary

1. Dictionary learning creates a feature vocabulary for data that lacks an obvious vocabulary. An auto-encoder learns an encoder that produces a representation and a decoder that reconstructs the input from it. Reconstruction error encourages information preservation, but restrictions are necessary to prevent simple copying. Sparse codes use only a few active dictionary atoms, and k-means appears as the special case in which exactly one coordinate identifies the selected centroid.