This is the second part of our comparison between convolutional competitive learning and convolutional or fully-connected sparse autoencoders. To understand our motivation for this comparison, have a look at the first article.

We decided to compare two specific algorithms that tick most of the features we require: K-Sparse autoencoders, and Growing-Neural-Gas-with-Utility (GNG-U) (Fritzke1997). The latter has proven ability to learn statistically optimal representations even given nonstationary input, under certain conditions.

K-Sparse Autoencoders

We found the K-Sparse Autoencoder scheme of Makhzani and Frey (Makhzani2013) particularly appealing due to the simple manner of achieving the desired sparsity: They simply find k cells with the highest hidden layer activity, and then mask to zero the activity of the remaining hidden cells. It is also possible to directly target any desired sparsity. One downside of the first paper is that the only mechanism to ensure high cell utilization is to train very slowly, with good weight initialization. In their follow-up paper, Winner-Take-All Convolutional Sparse Autoencoders (Makhzani2015), they introduced the concept of lifetime sparsity: Cells that aren’t used often are trained on the most fitting batch samples to ensure high cell utilization over time.

In fact, the realization that you can pretty much use any method you want to include or exclude cells from the active population in the hidden layer means that the k-sparse scheme is a very flexible algorithm and could potentially exploit this flexibility to deal with nonstationary data.

A nice feature of the k-sparse autoencoder is that the completeness of the models learned by the algorithm depend on the sparsity; with greater sparsity, cells represent more complete patterns. With less sparsity, cells learn to represent stable parts of patterns (see figure).

The complexity of features encoded by individual cells increases with reducing sparsity, k. At k=10 cells represent entire digits, whereas at higher k cells represent the strokes that make up each digit. Various subsets of cells effectively share the responsibility for representing an input digit-form. Source: (Makhzani2013)

Convolutional Growing Neural Gas with Utility (GNG-U)

This section describes how we can make GNG or GNG-U a convolutional algorithm. For readers who are unfamiliar with GNG, the first part of this article gives an introduction and links to relevant sources.

Receptive Field Geometry

We can use conventional convolutional geometry for a GNG network layer. The number of cells available to the GNG is Z, the depth of the layer. This is also known as the number of filters in a normal convolutional network. We can define a fixed receptive field and field tiling / stride as normal. The GNG is applied to each convolutional x,y location and the content of the receptive field at these locations is computed as normal. The output of the GNG at each location is two vectors of Z elements each:

• e the sum-square-error of each GNG cell and
• m a ternary mask indicating the winner (m[winner]=2) and runner-up cell (m[runnerup]=1), with other cells having value m[i]=0.

The GNG is trained at each convolutional location, albeit with a proportionally reduced learning rate to account for the number of training steps per image (note: Batch training with a higher learning rate would likely be superior but was not implemented). A winner and runner up are selected at each convolutional location, producing a 3-D ternary matrix with fixed sparsity.

We can build a stack of convolutional GNG layers using interleaved convolutional and pooling layers. In our experiments, we tested 1, 2 and 3 convolutional + pooling layers. Note that for simultaneous online training, this assumes that the GNG(U) can handle nonstationary input.

Example decoding of an input MNIST digit (‘5’) by a convolutional GNG-U algorithm. Note that due to encoding, the specific 5 has been transformed into a generic ‘5’. One of the limitations of Conv-GNG-U is the limited distribution and interaction of cells when representing input, which has the effect of turning input digits into generic exemplars. While this is useful, it breaks down when digits have very unusual forms.

Pooling functions

GNG is inherently a winner-take-all algorithm, or perhaps, a k=2 -sparse algorithm (it selects a “winner” and a “runner up”, which are modelled as neighbours for training). Normally, the hidden layer activity in convolutional networks is used as an input and output to pooling; we take the max value for each z in the x,y locations being pooled.

However, with GNG we only have the sum-square-error values e and the ternary mask indicating the winners. Neither is obviously equivalent to hidden layer activity in autoencoders or convolutional networks; sum-square-error becomes smaller when the cell is “better”, and is not sparse. The winner and runner-up ternary mask is very sparse, and it is not clear how we should represent the difference in error between the two (sometimes they have similar error, but not always).

Choosing a good output function is a balance between signal loss and noise removal. It is important to produce an output that is stable under reasonable conditions, enabling additional layers to learn. We investigated sparse binary outputs, sparse ternary outputs, functions derived from sum square error and functions, functions derived from cell ranking at each location, and nonlinear functions of sum square error (see table below).

The headline image at the top of this article shows convolutional GNGU receptive fields as yellow crosses, with the  red matrix underneath displaying the output of the pooling input function for each GNGU cell. Winning cells have blue outlines.

In all cases, we define a function f( e, m ) that returns a pooling input value v[z] for each cell z at each receptive field position x,y. These values are then pooled using a max operator over all spatial locations for a given z index.

Convolutional parameters

These parameters were developed from a series of ad-hoc tests and with reference to successful configurations used in conventional convolutional networks applied to MNIST.

To ensure the results are comparable to the autoencoder algorithms, we tried to conserve the number of “cells” at approximately 1000 and the number of learned weights at approximately:

• Layer 1: Z=64 with 6x6x1 receptive field = 2,304 parameters
• Layer 2: Z=256 with 3x3x64 receptive field = 147,456 parameters
• Total: 149,760 learned parameters

This is a small number of parameters compared to modern deep networks, but the MNIST test problem also has small images.

Note that although the 2nd layer has a larger number of parameters, the inputs are very sparse given most of the pooling functions evaluated. We did not reduce the width and height of the top unsupervised layer to 1×1 because this function could be performed by the supervised classifier. Although a range of values were tested, the best configuration is shown.

GNG-U parameters

One of the nice qualities of the GNG algorithm is that almost all the hyperparameters are defined in terms of time rather than qualities of the data. In theory, this should make it especially easy to adapt to novel problems. Although a range of values were tested, the best configuration is shown.

Experimental results

We chose to test the convolutional GNG-U algorithm on the MNIST dataset with a variety of pooling functions. For comparison, we implemented and tested a K-Sparse Autoencoder with a Batch-Sparsity constraint (each cell must be trained on at least p samples from each batch, which are selected retrospectively).

The algorithms were tested in 2 phases.

Phase 1 – Unsupervised network training

For both algorithms we performed unsupervised pre-training of the GNG-U and K-Sparse representations for N epochs. Next, we disabled learning and exposed the network to 1 epoch of the MNIST training set (60,000 images) and 1 epoch of the MNIST test set (10,000 images). The output of the deepest layer was recorded as a matrix of features x images, in addition to the vector of image labels.

All layers were trained simultaneously in online fashion.

Phase 2 – Supervised Classifier

Finally, in all cases, a logistic-regression supervised classifier was trained on the unsupervised training-set output and then tested on the unsupervised test-set output. This provides a classification accuracy score. We considered using a more powerful classifier (e.g. nonlinear SVM) but this transfers more of the responsibility to the classifier and reduces our ability to measure the contribution of unsupervised classification, especially on the MNIST dataset where scores are already very high.

Classification Accuracy

The convolutional GNG-U algorithm in conjunction with a logistic regression classifier had a tendency towards consistently high training accuracy (often close to 100%) with more difficulty generalizing to high test accuracy.

* Results from our Java re-implementation of the K-Sparse autoencoder with batch-lifetime-sparsity constraint from the later Conv-WTA paper. Since our implementation is written from scratch in Java without use of thoroughly tested third-party libraries, small numerical issues could account for the slight drop in performance.

Conclusions

The MNIST dataset is very well studied, making it good for comparative results; however, it is also “too easy” which results in good algorithms being clustered in the 98-99% accuracy interval (at some point, higher accuracy just means overfitting to the dataset as maybe 0.1-1% of the digits are extremely distorted and arguably unrecognizable).

Despite a large hyperparameter search, we were unable to get state-of-the-art performance from a convolutional GNG-U algorithm on the MNIST dataset (best result: 97%). Under the same unsupervised training regime with a supervised logistic regression classifier, we were able to reproduce approximately state-of-the-art performance (98.6%) with a k-sparse autoencoder despite a complete re-implementation of the entire backpropagation framework in Java, without optimizations.

The choice of GNG pooling function is critical. The simpler binary or ternary pooling functions probably do not contain enough information to make accurate classifications in ambiguous examples. We attempted to use more sophisticated encodings without introducing data-dependent hyperparameters, with reasonable but inadequate results.

Interestingly, the GNG algorithm family train very rapidly to a good performance level, but do not benefit from slower training over a larger number of epochs. In addition, the training set classification accuracy is very high in many configurations (over 99%), but does not generalize well to test accuracy. We tried dropout and greater regression regularization to reduce overfitting to training data, without improvement.

It is unsatisfying that we were not able to explore why a convolutional GNG-U is unable to benefit from more & slower training, like a convolutional autoencoder using stochastic gradient descent does. However, without promising results we can’t justify further investigation.

One possibility is that the lack of batch-training makes it harder for GNG-U to learn without a strong recency bias. Learning rate is normally balanced against batch size to enable effective training. With our GNG-U implementation we only have one of the two levers to control (learning rate, vs learning rate and batch size).

Another likely possibility is that the pooling functions tested did not effectively capture the available information in the GNG. However, we tried a variety of obvious functions given the available data, attempting to balance signal and noise, without success.

Most likely the root cause of the representational limit is the nature of the GNG-U algorithm which requires a fixed (winner-take-all) sparsity and does not variably distribute representational responsibility between cells like a k-sparse autoencoder does. On the face of it, this seems like a fundamental constraint that limits the flexibility of the approach and might explain the reduced classification performance.

We performed ad-hoc tests of the nonstationary capabilities of GNG-U by initially withholding half the digit classes and confirmed it works as advertised; the algorithm returns to optimal classification performance after all digit classes are restored.

So, can convolutional Growing-Neural-Gas (representing a family of competitive learning algorithms) compete with modern sparse autoencoders? No.

Resources

Source code for the implementations described here can be found in our Java repository on Github:

https://github.com/ProjectAGI/agi

Contributions

David Rawlinson and Gideon Kowadlo wrote the Java code for the algorithm implementations, executed and supervised experiments. Abdelrahman Ahmed set up and executed many of the experiments, and analyzed results.

References

Fritzke1997 – “A self-organizing network that can follow non-stationary distributions”. Bernd Fritzke. Proceedings of International Conference on Artificial Neural Networks, p. 613-618 (1997)

Makhzani2013 – “k-Sparse Autoencoders”. Makhzani, Alireza and Frey, Brendan. arXiv preprint arXiv:1312.5663 (2013)

Makhzani2015 – “Winner-Take-All Autoencoders”. Makhzani, Alireza and Frey, Brendan J. Advances in Neural Information Processing Systems (2015)