PCA as a Representation Method

The decoder, written as φ, maps that representation back into the original space.

Programming

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.

Representation	What its coordinates describe	How the features are obtained
Raw input	Original input values, such as pixel values	Provided directly with the instance
Learned dictionary representation	Reusable features that describe the instance	Discovered by a learning algorithm

A learned representation changes the question from which raw values are present to which reusable features help describe the data.

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.

How does describing an instance with learned features differ from listing its original input values?

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.

How does data move from the original input through a compact representation and back to a reconstruction?

Worked example

Following One Input Through the Pair

Suppose an input image enters an auto-encoder. Trace the role of each stage without assuming that the image is reconstructed perfectly.

1
Encode
The encoder ψ receives the input in its original space and produces a representation in the learned k-dimensional space.
2
Represent
The resulting coordinates indicate how the input is described by the learned representation.
3
Decode
The decoder φ receives those coordinates and maps them back into the original input space.
4
Compare
Learning evaluates the difference between the original input and the decoder's reconstruction, using total squared reconstruction difference.

Result

The encoder chooses a representation and the decoder tests whether that representation preserves enough information to rebuild 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

Setup	Reconstruction result	Representation result
Unconstrained functions with k equal to d	Can be perfect if both functions return their inputs	Does not necessarily provide a meaningful restriction or transformation
Restricted encoder and decoder	Must rebuild the input while obeying the restriction	Is encouraged to capture useful reusable structure

Small reconstruction error is necessary for the auto-encoder objective, but it is not by itself enough to make the representation useful.

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.

What changes when an encoder–decoder pair can copy the input freely instead of being restricted?

Sparse Codes and Dictionary Atoms

Definition

A sparse representation has many zero entries and only a limited number of nonzero entries. In dictionary learning, sparsity means that an instance uses only a small number of dictionary elements to describe itself.

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.

How does one input become a weighted combination of learned dictionary atoms, and what do the coefficients mean?

Worked example

A Small Sparse Representation

Imagine that an input is encoded with three dictionary coordinates. The first coordinate has coefficient c1, the second has coefficient c2, and the third is zero. Trace the reconstruction.

1
Select
The encoder marks the first two dictionary coordinates as active and leaves the third coordinate inactive.
2
Weight
The active coordinates carry coefficients c1 and c2. These coefficients specify the contributions used by the decoder.
3
Combine
The decoder combines the first atom weighted by c1 with the second atom weighted by c2. The third atom contributes nothing because its coefficient is zero.
4
Reconstruct
The combined result is the decoder's reconstruction of the input.

Result

The input is represented through a small set of active atoms rather than through every available dictionary coordinate.

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

Common mistake
Treating the learned dictionary as if it were a vocabulary supplied in advance.
What it looks like
Assuming that images already contain obvious dictionary words in the same way that documents contain words.
Why it fails
Text supplies a natural dictionary, but images do not come with an equally direct vocabulary.
Do this instead
Explain that dictionary learning searches for reusable features when meaningful entries are not obvious beforehand.
Common mistake
Assuming that every cluster member receives a different representation.
What it looks like
Expecting a cluster-based dictionary representation to preserve all distinctions between instances in the same cluster.
Why it fails
A simple cluster representation gives every member of one cluster the same dictionary representation.
Do this instead
Recognize that this can force a linear predictor to assign the same target value to all instances in that cluster.
Common mistake
Concluding that perfect reconstruction automatically means useful learning.
What it looks like
Accepting an encoder and decoder that simply return the input when k equals d.
Why it fails
The pair can reconstruct perfectly without providing a meaningful restriction or transformation.
Do this instead
Ask what restriction prevents the functions from copying every input.
Common mistake
Confusing sparsity with using every dictionary atom weakly.
What it looks like
Calling a representation sparse even though nearly all coordinates are nonzero.
Why it fails
A sparse representation has many zero entries and only a limited number of nonzero entries.
Do this instead
Focus on the small active set selected by the encoder.
Common mistake
Describing sparse coding as identical to k-means.
What it looks like
Saying that a sparse code must always select exactly one atom.
Why it fails
K-means uses one active indicator, while the extended sparse construction permits at most s active coordinates.
Do this instead
State whether the representation selects one centroid or a small set of dictionary atoms.

Practice and Summary

MEDIUM

An encoder produces a representation with many zero coordinates and a few nonzero coordinates. Explain what the nonzero coordinates mean, what the decoder does with them, and how this differs from the one-active-coordinate representation used by k-means.

Hints

Start with the role of the encoder.
Then describe how the decoder combines dictionary atoms.
Finally compare a small active set with a single active indicator.

Your attempt (not saved)

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.

At a glance

Raw input coordinates are not always the most useful features for prediction.
Dictionary learning discovers reusable features, or atoms, and represents instances through them.
An encoder maps an input into a representation, while a decoder maps that representation back into the original space.
Reconstruction error must be combined with restrictions so the auto-encoder cannot simply copy its input.
Sparse coding generalizes k-means from one active centroid indicator to a small set of active dictionary atoms.

Related concepts

More concepts starting with P