Generative Model
Sparse Coding
Neural Network
Machine Learning

Sparse Coding Simplified

Aleksandr P

5 min readJul 22, 2020

Sparse coding is an unsupervised type of representation learning. In a nutshell it aims to find a sparse representation of a given data. Technically it’s a linear factor model, so we need to describe that term first.

Linear Factor Model

In this article most of the input data examples are toy images, like MNIST dataset. However, linear factor models per se are mostly used in a financial sector. So to describe this one, I’m going to use stock market example. The general equation looks like this:

Press enter or click to view image in full size

x — vector of size u

Weights — matrix of size (k, u), estimated model parameter

factors — vector of size k, random variables

bias — vector of size u, estimated model parameter, usually standard Gaussian

noise — vector of size u, random variables, zero-centered

Let’s say you have a set of assets, i.e. stocks: x₁..xᵤ (vector x), where scalar value is RoI (return on investment). It’s a set of random variables, each of which we want to model through a set of factors. Every stock xᵢ can be represented through a set of fixed factors. To do so we need to learn standard linear model parameters: weights & biases. Our model won’t be able to predict actual values with 100% accuracy, hence we also have noise which represents unexplained variance. We learn a single weight for each factor and for each asset. That’s why our Weights matrix isk*u, where k — number of factors, u — stocks in our portfolio.

It’s important to mention a couple of key assumptions in a linear factor model:

noise is not correlated with the factors.

2. noise components are not correlated with each other. Recall that each item of noise vector (noiseᵢ) corresponds to single asset (xᵢ).

Also worth to notice, that RoI on our portfolio (all xᵢ together) can also be estimated through a linear factor model of the same factors: just sum up all biases, corresponding weights, and noises.

Get Aleksandr P’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Why do we need linear factor model? In our case it can be used to sample data. We sample our factors, and then use our model to sample a required x given factors.

Sparse coding

As I mentioned, sparse coding is a unsupervised representation learning. In other words for our input (i.e. dataset) we try to find another representation. If we treat our dataset item (i.e. image) as a vector of some dimensionality, those vectors form some distribution in that space. By learning new representation, we are looking for another distribution, more useful one. To learn this representation, we set two objectives:

there should be a linear function that translates any image from learned representation to original one
new representation should be sparse

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). Let’s look at a practical example. Take a MNIST image, handwritten b/w digit: it’s original input is 28x28 scalar values. Vector of these values represent s intensity of every pixel, and is quite dense: for each image high percentage of pixels are not equal to zero. With natural images almost all pixels are not close to 0. If we try to sample such image given this representation, we will end up getting a random noise, because we actually don’t know underlying distribution that produced this dataset. But if we learn sparse representation of our dataset, where each image (handwritten digit from 0 to 9) is represented(not zero value) only by few features, it can actually become useful, because now we know what distribution those features come from. For instance, classification models can benefit from such input.

Top: observed images. Bottom: learned set of features, that can be used to sparsely encode observed dataset.

But more importantly we’ll be able to generate new images which will look like they were sampled from the original dataset. Although in most of the cases they won’t look like real Arabic numerals. But still it will be way more meaningful sample, than random noise.

As an optimization problem we need to find such factors, that with a sparsity constraint can precisely model our original dataset, we also need to learn representation coefficients for each sample of our dataset to minimize the difference between modeled sample and original one (observed).

Note that we are learning a model to transform our sparse representation into original one. Given any image in a sparse representation, we can always decode it to original one by using our learned/fixed factors. However, to encode image into sparse representation, we need to do optimization again to come up with good coefficients for our factors. That’s definitely a limitation of this algorithm. We can’t just freely transform representations back and forth.

If we approach this problem from probability theory, treating our input dataset as a sample from unknown distribution, we can model this distribution using our factors:

Our goal to find such factorsf_i that this model will produce distribution as close as possible to our observed one (given dataset). We assume that r_i comes from Laplace distribution with high distribution. In other words, very “tall”, where most of the value are around zero ← hence sparse. We also assume Gaussian noise. By doing minimization of log-likelihood, we will end up having the same equation as above. From probabilistic prospective, after finding good set of f_i‘s we can sample r_i‘s to generate new images from our learned sparse representation. That’s right, we don’t need an encoder to do that.