Sparse Representations

An image can contain many raw pixel values, but those values 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 input through those features.

The idea is easiest to compare with text. A document already has a natural vocabulary: its words. A document can be represented by coordinates indicating which dictionary words occur, and a linear predictor can use those word-based features to help predict a label. Images do not arrive with an equally obvious vocabulary. Dictionary learning tries to discover a similar collection of reusable features for data whose meaningful building blocks are not supplied in advance.

For object recognition, one possible learned feature could correspond to the presence of an eye. The important point is not that an image literally contains words. The point is that a collection of reusable features may describe the image more usefully than treating every raw value as an unrelated coordinate.

A sparse representation describes an instance with many zero entries and only a limited number of nonzero entries. In dictionary learning, the nonzero entries identify the small number of dictionary atoms being used to describe that instance.

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 creates the code, and the decoder interprets that code as a reconstruction.

Training seeks an encoder and decoder whose reconstructions are close to the original inputs. For each input, the decoder receives the encoder's representation and produces the reconstructed version. The learning objective measures the total squared difference between each original input and its reconstruction.

In a sparse dictionary interpretation, the encoder decides which dictionary coordinates are active. The decoder then uses the active coordinates and their values to combine the corresponding dictionary atoms. A useful dictionary is one whose compact code still preserves enough information for reconstruction and can also serve as a feature representation for later learning tasks.

Small reconstruction error is important, but it is not enough by itself. If the representation has the same dimensionality as the input and the encoder and decoder simply return their inputs, reconstruction can be perfect. Yet the representation has not supplied a meaningful restriction or transformation; it has only copied the data.

A natural first attempt at dictionary learning is to cluster the training instances. Each cluster can act like a dictionary word. An input is assigned to a cluster, and its representation contains an indicator for that cluster.

This gives a very simple dictionary-based description, but it has a limitation: every member of one cluster receives the same dictionary representation. A linear predictor using that representation must therefore assign the same target value to all instances in that cluster. When clusters come from distances to class centers, the resulting predictor is piece-wise constant over the input space.

The k-means connection appears in the code itself. In k-means, the encoder produces an especially sparse code: exactly one coordinate is nonzero, identifying the closest centroid. A broader sparse construction allows at most s nonzero coordinates instead of exactly one. The decoder can then combine the corresponding dictionary atoms using the values in those active coordinates.

This trace captures the central mechanism. The encoder decides which dictionary coordinates are active. The decoder uses those coordinates to rebuild the input. Learning must balance two demands: the code should be restricted enough to avoid a trivial copy, but it must preserve enough information for a low-error reconstruction.