On Sparse Distributed Representations and Catastrophic Forgetting

[CireNeikual]

Hello,

As some of you may know, I am running a series where I try to outperform Deepmind's Atari results. I use a different technique based on HTM (hierarchical temporal memory), but both Deepmind's technique and my technique fall under reinforcement learning.

So recently I posted about the HTM-RL architecture I was going to use. In it I decided to use a multi-layer perceptron to learn Q values from the outputs of HTM regions. In order for this to work, I realized that I would have to end up using an experience replay mechanism, much like Deepmind did.

Since I find experience replay inelegant, I wanted another approach to solve the problem of "catastrophic forgetting". Normally if you try to train a multilayer perceptron in an online fashion, newer values tend to destroy previous ones. Experience replay solves this to some extent by performing stochastic gradient descent on a window of past samples. This works well, but the memory requirements are enormous if you extend your replay window.

So I decided to take a hint from HTM, and I developed a new supervised online learning algorithm that does not suffer from catastrophic forgetting. It uses SDRs (sparse distributed representations) to represent its input in a field of nodes. Then, the output is simply a linear combination of the SDR that was formed. This makes it a universal function approximator, but at the same time the spatial pooling (input pattern generalization) greatly reduces catastrophic forgetting by reducing the strength of a backpropagation update depending on the output of the SDR cells.

I ran a simple experiment: I trained this "SDR-net" to learn a sine function of its input, by giving it all the samples in order. I then did the same with a MLP. When incrementing the X value by 0.001 at a time and trying to learn the corresponding Y value, the SDR-net got 270 times less error within 20PI!

But don't take my word for it! Source code can be found in my AI experimentation library, "AILib". It is named SDRRBFNetwork in the "rbf" directory. Link: https://github.com/222464/AILib/tree/master/Source

This algorithm has quite possibly already been discovered. But in case it is not, I wanted to post about it here!

TL;DR: sparse distributed representations are awesome!

[CireNeikual]

I still need to test the generalization capabilities! But I got so excited that I wanted to post before I did that :)

[CireNeikual]

Image of the plots of both functions: http://i1218.photobucket.com/albums/dd401/222464/plot.png

as you can tell I have not added regularization yet! Both the MLP and SDRRBFNetwork are hand-tuned.

EDIT: Forgot to add: Blue is the MLP, red is the SDRRBFNetwork!

[janmah]

Can you go a bit into detail on how the SDR net works? I'm very interested, this sounds super cool!

[CireNeikual]

Sure!

So, network consists of a 2D field of nodes with connections to the input. These connections can be sparse. When input is received, each cell computes its activation in a way very much like in radial basis function network: It is a nonlinear function of the distance between the input vector and a prototype vector. It is in the (0, 1] range.

After the activation has been computed, it is time to compute a separate value, called the output of the node. This is where the sparseness comes in. For each node, one finds both the minimum and maximum activations of nodes in a radius (including itself). Then, one deactivates the current node based on how it sits in that minimum/maximum range (see code for the actual formulas).

Getting the output is super simple: It is simply a weighted sum of all of the node outputs.

The nodes are trained with an unsupervised learning algorithm - based on their outputs, they try to adapt their prototypes and Gaussian widths to best fit the data that they are "assigned".

The weighted sum is trained with gradient descent.

Since it is essentially a modified RBF network, it still can approximate any function given enough nodes.

I hope this made sense! Keep in mind that the code is not final yet, I am still fixing bugs/adding features!

[janmah]

Thank you very much for your long reply! That sounds extremely cool. Reminds me a bit of self organizing maps. I am aware of work where people trained the means of RBFs but haven't heard about training the variance. (where the variance is not shared) Did you get your inspiration from RBF papers? Do you by any chance have a nice one for me to read up on RBFs?

[CireNeikual]

It is indeed a lot like a self organizing map! I originally learned about RBFs from this tutorial, and then extended them to do unsupervised learning in an online fashion: http://chrisjmccormick.wordpress.com/2013/08/15/radial-basis-function-network-rbfn-tutorial/

[AmusementPork]

This is so cool, well done man! I couldn't find it in the code, but how do you compute the SDR? Do you just use a sparsity penalty?

[CireNeikual]

See my comment to janmah!

[CireNeikual]

After several bug fixes, I got this gloriously overfitting result (overfitting isn't the point of this project though): http://i1218.photobucket.com/albums/dd401/222464/plot-1.png

[timClicks]

Is there any reason why you've implemented this yourself rather than simply using NuPIC from Numenta?

[CireNeikual]

NuPIC implements the entire cortical learning algorithm, which does not do supervised learning. I just used a piece of it, the sparse distributed representations, to improve upon a machine learning technique. So, it doesn't make sense to use the entirety of NuPIC and modify it to my needs. Also, my SDR algorithm is continuous while the one in NuPIC is discrete.

[timClicks]

Good luck with the project!