Sparse Coding and Probabilistic Representation Learning
In part 1, we gave an introduction to Representation Learning and a brief overview on it’s 2 main paradigms. Here we will talk about the first one: probabilistic models.
From the probabilistic modeling perspective, feature learning can be interpreted as an attempt to recover a small set of latent random variables h that describe a distribution over the observed data x. We can express as p(x, h) a probabilistic model that describes how both x and h relate. Feature values are obtained as the result of inferring the latent variables given the data, i.e. p(h | x), often referred to as the posterior probability.
Learning is obtained in term of estimating a set of model parameters that (locally) maximizes the regularized likelihood of the training data. The probabilistic graphical model gives us 2 possible modeling paradigms in which we can consider inferring latent variables:
- Directed graphical models
- Undirected graphical models
which differ in how they represent the joint distribution p(x, h), which affects the nature and computational costs of both inference and learning.
Directed Graphical Models
Directed latent factor models separately handle p(x | h) and the prior p(h) to construct the joint distribution, p(x, h) = p(x | h)p(h). Examples of this decomposition include Probabilistic PCA, Sparse coding, and sigmoid belief networks.
Explaining Away
Directed models often leads to one important property: explaining away, i.e., the known independent causes of an event can become non-independent given the observation of the event. Latent factor models can generally be interpreted as latent cause models, where the h activations cause the observed x.
This renders the known independent h to be non-independent. As a consequence, recovering the posterior distribution of h, (which we use as a basis for feature representation), is often computationally challenging and can be entirely intractable, especially when h is discrete.
A classic example that illustrates the phenomenon is to imagine you are on vacation away from home and you receive a phone call from the security system company, telling you that the alarm has been activated. You begin worrying your home has been burglarized, but then you hear on the radio that a minor earthquake has been reported in the area of your home. If you happen to know from prior experience that earthquakes sometimes cause your home alarm system to activate, then suddenly you relax, confident that your home has very likely not been burglarized
The example illustrates how the alarm activation rendered two otherwise entirely independent causes, burglarized and earthquake, to become dependent — in this case, the dependency is one of mutual exclusivity. Since both burglarized and earthquake are very rare events and both can cause alarm activation, the observation of one explains away the other.
Despite the computational obstacles we face when attempting to recover the posterior over h, explaining away promises to provide a less costly p(h | x), which can be an extremely useful characteristic of a feature encoding scheme. If one thinks of a representation as being composed of various feature detectors and estimated attributes of the observed input, it is useful to allow the different features to compete and collaborate with each other to explain the input. This is naturally achieved with directed graphical models.
Sparse Coding
Similar to PCA, sparse coding relates a latent representation h (either a vector of random variables or a feature vector, depending on the interpretation) to the data x through a linear mapping W, which we refer to as the dictionary.
Sparse means most of the values of the vector in the new representation will be zeros. In other words single item (i.e. image) from the dataset will be represented by few features out of our learned dictionary of features (factors).
Example
Let’s take the MNIST dataset. If we learn sparse representation of our dataset, where each image is represented(not zero value) only by few features, it can actually become useful, because now we know what distribution those features come from.
More importantly, we’ll be able to generate new images which will look like they were sampled from the original dataset.
The aim of sparse coding is to find a set of basis vectors ϕᵢ such that we can represent an input vector x as a linear combination of these basis vectors:
While PCA allows us to learn a complete set of basis vectors efficiently, we wish to learn an over-complete set of basis vectors to represent input vectors x∈Rⁿ (i.e. such that k>n). The advantage of having an over-complete basis is that our basis vectors are better able to capture structures and patterns inherent in the input data.
However, with an over-complete basis, the coefficients aᵢ are no longer uniquely determined by the input vector x, i.e., there are many possible ways to reconstruct the same input x. This means the coefficients aᵢ are not unique.
Therefore, in sparse coding, we introduce the additional criterion of sparsity to resolve this. Here, we define sparsity as having few non-zero components or having few components not close to zero. The requirement that our coefficients aᵢ be sparse means that given an input vector, we would like as few of our coefficients to be far from zero as possible.
We define the sparse coding cost function on a set of m input vectors as:
where S(.) is a sparsity cost function which penalizes ai for being far from zero. We want to represent each input vector x(j) as a weighted sum of basis vectors, using coefficients a(j).
Get Chamuditha Kekulawala’s stories in your inbox
Join Medium for free to get updates from this writer.
The cost function has two goals:
- Reconstruction accuracy
This term forces the combination of basis vectors to reproduce the input well.
2. Sparsity of the coefficients
This term encourages most coefficients aᵢ to be zero, so only a few basis vectors are used for each input.
In short:
We are optimizing both the coefficients aᵢ and the basis vectors ϕ to reconstruct each input using as few active features (basis vectors) as possible.
The constant λ is a scaling constant to determine the relative importance of these two contributions.
However, the most direct measure of sparsity is the “L₀” norm. The most direct way to enforce sparsity is:
Learning a set of basis vectors ϕ using sparse coding consists of performing two separate optimizations:
- An optimization over coefficients aᵢ for each training example x.
- An optimization over basis vectors ϕ across many training examples at once.
Assuming an L1 sparsity penalty, learning reduces to solving a L1 regularized least squares problem which is convex in for which several techniques have been developed. If S(.) is differentiable (sparsity penalty is smooth such as the log penalty), gradient-based methods can also be used.
Learning the set of basis vectors ϕ with a L2 norm constraint also reduces to a least squares problem with quadratic constraints which is convex in ϕ.
As described above, a significant limitation of sparse coding is that even after a set of basis vectors have been learnt, in order to “encode” a new data example, optimization must be performed to obtain the required coefficients. This significant “runtime” cost means that sparse coding is computationally expensive to implement even at test time especially compared to typical feedforward architectures.
Advantages of Sparse Coding
Sparse coding uses non-parametric encoding:
- Instead of using a neural network to map x→h,
- It solves an optimization problem to find the best code h∗ for each input.
The sparse coding approach combined with the use of the non-parametric encoder can in principle minimize the combination of reconstruction error and log-prior better than any specific parametric encoder.
Another advantage is that there is no generalization error to the encoder. A parametric encoder must learn how to map x to h in a way that generalizes.
If an input x is very different from training data, the encoder might output a bad code hhh → poor reconstruction.
In contrast, sparse coding:
- Solves a convex optimization for each new input.
- Always finds the optimal sparse code (given the learned dictionary), regardless of how unusual the input is.
So any failure comes from a decoder generalization error (the basis vectors didn’t capture this kind of data), not from the encoder — because the encoder is not learned.
Sparse coding is an excellent example of the power of explaining away. Even with a very overcomplete dictionary, sparse coding finds h∗ which can pick out the most appropriate bases and zero the others, despite them having a high degree of correlation with the input.
This property arises naturally in directed graphical models such as sparse coding. It is not seen in undirected probabilistic models such as the RBM, nor in parametric feature encoding methods such as auto-encoders.
To find the code h∗, sparse coding must solve an optimization problem for every new input, making it much slower than autoencoders or RBMs that compute a code in one forward pass.
That’s it for this article! Thanks for reading 🎉
