This is an online companion for the paper An Empirical Evaluation of Deep Architectures on Problems with Many Factors of Variation by Hugo Larochelle, Dumitru Erhan, Aaron Courville, James Bergstra and Yoshua Bengio, to appear in the proceedings of the International Conference on Machine Learning (2007). A camera-ready version of this paper can be downloaded from here. This document provides additional information regarding the generation of the datasets, details of our experiments and downloadable versions of the datasets that we used. It overlaps partly with the paper itself, but it is meant to be used in conjunction with the paper in order to get a deeper (pun somewhat intended) understanding of our experiments.
Recently, several learning algorithms relying on models with deep architectures have been proposed. Though they have demonstrated impressive performance, to date, they have only been evaluated on relatively simple problems such as digit recognition in a controlled environment, for which many machine learning algorithms already report reasonable results. Here, we present a series of experiments which indicate that these models show promise in solving harder learning problems that exhibit many factors of variation. These models are compared with well established algorithms such as Support Vector Machines and single-layer feed-forward neural networks.
For more details on the motivation of this work, we redirect the reader to the first sections of the paper behind this web page: An Empirical Evaluation of Deep Architectures on Problems with Many Factors of Variation.
We define a shallow model as a model with very few layers of composition, e.g. linear models, one-hidden layer neural networks and kernel SVMs:
On the other hand, deep architecture models are such that their output is the result of the composition of some number of computational units, and the number of needed computational units is not exponential in the characteristics of the problem such as the number of factors of variation or the number of inputs. These units are generally organized in layers so that the many levels of computation can be composed. Also, they can only be approximated appropriately by a shallow model with a large (i.e. possibly exponential) number of computational units. In other words, these models are able to implement very complex functions with relatively few parameters.
Here are the deep architecture models that we considered in our paper. More details about the corresponding training algorithms can be found in the paper and pseudo-codes can be found in the appendix of the technical report for Greedy Layer-Wise Training of Deep Networks.
In the experimental results section, we compare these models with shallow architectures such as single-layer feed-forward networks and Support Vector Machines.
In order to study the capacity of these algorithms to scale to learning problems with many factors of variation, we have generated datasets where we can identify some of these factors of variation explicitly. We focused on vision problems, mostly because they are easier to generate and analyze. In all cases, the classification problem has a balanced class distribution.
In one series of experiments, we construct new datasets by adding additional factors of variation to the MNIST images.
The generative process used to generate the datasets is the following:
Introducing multiple factors of variation leads to the following benchmarks:
In this task, a learning algorithm needs to recognize whether a rectangle contained in an image has a larger width or length. The rectangle can be situated anywhere in the 28 x 28 pixel image. We generated two datasets for this problem:
The convex sets consist of a single convex region with pixels of value 255. Candidate convex images were constructed by taking the intersection of a number of half-planes whose location and orientation were chosen uniformly at random. The number of intersecting half-planes was also sampled randomly according to a geometric distribution with parameter 0.195. A candidate convex image was rejected if there were less than 19 pixels in the convex region.
Candidate non-convex images were constructed by taking the union of a random number of convex sets generated as above, but with the number of half-planes sampled from a geometric distribution with parameter 0.07 and with a minimum number of 10 pixels. The number of convex sets was sampled uniformly from 2 to 4. The candidate non-convex images were then tested by checking a convexity condition for every pair of pixels in the non-convex set. Those sets that failed the convexity test were added to the dataset.
The parameters for generating the convex and non-convex sets were balanced to ensure that the mean number of pixels of value 255 is the same in the two datasets.
In order to explore the space of learning problems standing between mnist-back-rand and mnist-back-images, we set up an experiment where we could vary the amount of background pixel correlation. We are hence assuming that background correlation is the main characteristic that distinguishes mnist-back-images from mnist-back-random.
Correlated pixel noise was sampled from a zero-mean multivariate Gaussian distribution of dimension equal to the number of pixels: . The covariance matrix, , was defined as a convex combination of an identity matrix and a Gaussian kernel function. Representing the position of the th pixel with the vector , we have:
with kernel bandwidth . The Gaussian kernel induced a neighborhood correlation structure among pixels such that nearby pixels are more correlated that pixels further apart. For each sample from , the pixel values (ranging from 0 to 1) were determined by passing elements of through an error function:
We generated six datasets with varying degrees of neighborhood correlation by setting the mixture weight to the values . The marginal distributions for each pixel is uniform(0,1) for each value of .
All the datasets are provided as zip archives. Each archive contains two files -- a training (and validation) set and a test set. We used the last 2000 examples of the training sets as validation sets in all cases but for rectangles (200) and, in the case of SVMs, retrained the models with the entire set after choosing the optimal parameters on these validation sets. Data is stored at one example per row, the features being space-separated. There are 784 features per example (=28*28 images), corresponding to the first 784 columns of each row. The last column is the label, which is 0 to 9 for the MNIST variations and 1 or 0 for the rectangles, rectangles-images and convex datasets.
IMPORTANT New versions of the datasets containing rotations have been generated. There was an issue in the previous versions with the way rotated digits were generated, which increased the range of values a digit pixel could have. For instance, this issue made it easier to discern digits from the image background in the MNIST rotated+back-image dataset. New results for these datasets have been generated and are reported along with the other benchmark results.
Link to dataset | Size | File description |
---|---|---|
MNIST basic | 23M packed; 144M + 599M unpacked | 12000 train, 50000 test |
MNIST + background images | 88M packed; 144M + 599M unpacked | 12000 train, 50000 test |
MNIST + random background | 219M packed; 144M + 599M unpacked | 12000 train, 50000 test |
Rotated MNIST digits | 56M packed; 56M + 338M unpacked | 12000 train, 50000 test |
Old version: | | |
Rotated MNIST digits + background images | 115M packed; 144M + 599M unpacked | 12000 train, 50000 test |
Old version: | | |
Rectangles | 2.7M packed; 15M + 599M unpacked | 1200 train, 50000 test |
Rectangles images | 82M packed; 144M + 599M unpacked | 12000 train, 50000 test |
Convex-nonconvex sets | 3.4M packed; 96M + 599M unpacked | 8000 train, 50000 test |
MNIST noise variation sets | 304M packed; 1008M unpacked | 6x12000 train, 6x2000 test |
Attached is an archive that contains the scripts needed to generate the datasets, along with a README. Please contact us should you have any questions about the scripts.
We conducted experiments with two deep architecture models: a 3 hidden layer Deep Belief Network (noted DBN-3) and a 3 hidden layer Stacked Autoassociator Network (noted SAA-3). In order to compare their performance, we also trained:
In all cases, the model selection was performed using a validation set. For NNet, the best combination of number of hidden units (varying from 25 to 700), learning rate (from 0.0001 to 0.1) and decrease constant (from 0 to ) of stochastic gradient descent and weight decay penalization (from 0 to ) was selected using a grid search.
For DBN-3 and SAA-3, because these models can necessitate more than a day to train, we could not perform a full grid search in the space of hyper-parameters. For both models, the number of hidden units per layer must be chosen, in addition to all other optimization parameters (learning rates for the unsupervised and supervised phases, stopping criteria of the unsupervised phase, etc.). We chose an approximate search procedure that we believed finds a reasonable minima for the following grid search:
Hyper-parameter | Size of first hid. layer | Size of second hid. layer | Size of third hid. layer | Learning rate of sup. phase | Learning rate of unsup. phase |
---|---|---|---|---|---|
Range | [ 500, 3000 ] | [ 500, 4000 ] | [ 1000, 6000 ] | [ 0.0001, 0.1 ] | [ 0.0001, 0.1 ] |
The hyper-parameter search procedure we used alternates between fixing a neural network architecture and searching for good optimization hyper-parameters similarly to coordinate descent. More time would usually be spent on finding good optimization parameters, given some empirical evidence that we found indicating that the choice of the optimization hyper-parameters (mostly the learning rates) has much more influence on the obtained performance than the size of the network. We used the same procedure to find the hyper-parameters for DBN-1, which are the same as those of DBN-3 expect the second hidden layer and third hidden layer sizes. We also allowed ourselves to test for much larger first-hidden layer sizes, in order to make the comparison between DBN-1 and DBN-3 fairer.
We usually started by testing a relatively small architecture (between 500 and 700 units in the first and second hidden layer, and between 1000 and 2000 hidden units in the last layer). Given the results obtained on the validation set (compared to those of NNet for instance) after selecting approriate optimization parameters, we would then consider growing the number of units in all layers simultaneously. The biggest networks we eventually tested had up to 3000, 4000 and 6000 hidden units in the first, second and third hidden layers respectively.
As for the optimization hyper-parameters, we would proceed by first trying a few combinations of values for the stochastic gradient descent learning rate of the supervised and unsupervised phases (usually between 0.1 and 0.0001). We then refine the choice of tested values for these hyper-parameters. The first trials would simply give us a trend on the validation set error for these parameters (is a change in the hyper-parameter making things worse of better) and we would then consider that information in selecting appropriate additional trials. One could choose to use learning rate adaptation techniques (e.g. slowly decreasing the learning rate or using momentum) but we did not find these techniques to be crucial.
For all neural networks, we used early stopping based on the error of the model on the validation set. If for 5 consecutive epochs we don't improve on the best validation error, then training is stopped. As for the unsupervised phase stopping criteria, with SAA-3, we stopped greedily training a layer when the autoassociator reconstruction cost did not improve more than 1% on the training set after an epoch of 10000 samples, or 10% for a training set of 1000 samples. With DBN-3, we did not use early stopping, because the RBM training criterion is not tractable. Instead, we tested 50 or 100 unsupervised learning epochs for each layer and selected the best choice based on the final accuracy of the model on the validation set.
The experiments with the NNet, DBN-1, DBN-3 and SAA-3 models were conducted using the PLearn library, an Open Source C++ library for machine learning which was developed and is actively used in our lab.
In the case of SVMs with Gaussian kernels, we performed a two-stage grid search for the width of the kernel and the soft-margin parameter. In the first stage, we searched through a coarse logarithmic grid ranging from to and to . In the second stage, we performed a more fine-grained search in the vicinity of that tuple that gave the best validation error. For example, if the optimal tuple was , we would examine tuples from . In the case of the polynomial kernel, the strategy was the same, except that we searched through all possible degrees of the polynomial up to 20 (no fine-grained search on this parameter, obviously).
Throughout the experiments we used the publicly available library libSVM version 2.83 (note that in the meantime the library has been updated. The results reported below are those obtained with version 2.83).
The confidence intervals on the mean test error are computed using the following formula: , where is the estimated test error, is 0.05 and , with being the inverse zero-mean unit-variance Gaussian CDF at .
For convenience, we provide two tables of results, one being the transpose of the other. The test errors with (*) are the lowest for a given dataset (or whose margins overlap with the confidence margin of the lowest).
Dataset / algorithm | SVM RBF | SVM Poly | NNet | DBN-3 | SAA-3 | DBN-1 |
---|---|---|---|---|---|---|
Convex | 19.13 ± 0.34% | 19.82 ± 0.35% | 32.25 ± 0.41% | 18.63 ± 0.34% (*) | 18.41 ± 0.34% (*) | 19.92 ± 0.35% |
MNIST back-image | 22.61 ± 0.37% | 24.01 ± 0.37% | 27.41 ± 0.39% | 16.31 ± 0.32% (*) | 23.00 ± 0.37% | 16.15 ± 0.32% (*) |
MNIST back-random | 14.58 ± 0.31% | 16.62 ± 0.33% | 20.04 ± 0.35% | 06.73 ± 0.22% (*) | 11.28 ± 0.28% | 09.80 ± 0.26% |
MNIST basic | 03.03 ± 0.15% (*) | 03.69 ± 0.17% | 04.69 ± 0.19% | 03.11 ± 0.15% (*) | 03.46 ± 0.16% | 03.94 ± 0.17% |
MNIST rotated | 11.11 ± 0.28% | 15.42 ± 0.32% | 18.11 ± 0.34% | 10.30 ± 0.27% (*) | 10.30 ± 0.27% (*) | 14.69 ± 0.31% |
MNIST rotated+back-image | 55.18 ± 0.44% | 56.41 ± 0.43% | 62.16 ± 0.43% | 47.39 ± 0.44% (*) | 51.93 ± 0.44% | 52.21 ± 0.44% |
Old version: | | | | | | |
Old version: | | | | | | |
Rectangles | 02.15 ± 0.13% (*) | 02.15 ± 0.13% (*) | 07.16 ± 0.23% | 02.60 ± 0.14% | 02.41 ± 0.13% (*) | 04.71 ± 0.19% |
Rectangles-images | 24.04 ± 0.37% | 24.05 ± 0.37% | 33.20 ± 0.41% | 22.50 ± 0.37% (*) | 24.05 ± 0.37% | 23.69 ± 0.37% |
Clicking on column headings sorts the columns and thereby provides a ranking of test errors for a given dataset.
Algorithm / dataset | MNIST basic | MNIST rotated | Old version: | MNIST back-image | MNIST back-random | MNIST rotated+back-image | Old version: | Rectangles | Rectangles im | Convex |
---|---|---|---|---|---|---|---|---|---|---|
SVM RBF | 03.03 ± 0.15% (*) | 11.11 ± 0.28% | | 22.61 ± 0.37% | 14.58 ± 0.31% | 55.18 ± 0.44% | | 02.15 ± 0.13% (*) | 24.04 ± 0.37% | 19.13 ± 0.34% |
SVM Poly | 03.69 ± 0.17% | 15.42 ± 0.32% | | 24.01 ± 0.37% | 16.62 ± 0.33% | 56.41 ± 0.43% | | 02.15 ± 0.13% (*) | 24.05 ± 0.37% | 19.82 ± 0.35% |
NNet | 04.69 ± 0.19% | 18.11 ± 0.34% | | 27.41 ± 0.39% | 20.04 ± 0.35% | 62.16 ± 0.43% | | 07.16 ± 0.23% | 33.20 ± 0.41% | 32.25 ± 0.41% |
DBN-3 | 03.11 ± 0.15% (*) | 10.30 ± 0.27% (*) | | 16.31 ± 0.32% (*) | 06.73 ± 0.22% (*) | 47.39 ± 0.44% (*) | | 02.60 ± 0.14% | 22.50 ± 0.37% (*) | 18.63 ± 0.34% (*) |
SAA-3 | 03.46 ± 0.16% | 10.30 ± 0.27% (*) | | 23.00 ± 0.37% | 11.28 ± 0.28% | 51.93 ± 0.44% | | 02.41 ± 0.13% (*) | 24.05 ± 0.37% | 18.41 ± 0.34% |
DBN-1 | 03.94 ± 0.17% | 14.69 ± 0.31% | | 16.15 ± 0.32% (*) | 09.80 ± 0.26% | 52.21 ± 0.44% | | 04.71 ± 0.19% | 23.69 ± 0.37% | 19.92 ± 0.35% |
Classification error of SVM RBF, SAA-3 and DBN-3 on MNIST examples with progressively less pixel correlation in the background
There are several conclusions which can be drawn from these results:
We presented a series of experiments which show that deep architecture models tend to outperform other shallow models such as SVMs and single-layer feedforward neural networks. We also analyzed the relationships between the performance of these learning algorithms and certain properties of the problems that we considered. In particular, we provided empirical evidence that these techniques compare favorably to other state-of-the-art learning algorithms on learning problems with many factors of variation, but only up to a certain point where the data distribution becomes too complex and computational constraints become an important issue.
An Empirical Evaluation of Deep Architectures on Problems with Many Factors of Variation | Larochelle, H., Erhan, D., Courville, A., Bergstra, J., Bengio, Y. | ICML 2007 |
Learning Deep Architectures for AI | Bengio, Y., Technical report | link |
Scaling Learning Algorithms towards AI | Bengio, Y. and LeCun, Y. | Book chapter in "Large-Scale Kernel Machines" |
A fast learning algorithm for deep belief nets | Hinton, G. E., Osindero, S. and Teh, Y. | Neural Computation (2006) | pdf ps.gz html |
To recognize shapes, first learn to generate images | Hinton, G. E. | Technical Report (2006) |
Greedy Layer-Wise Training of Deep Networks | Bengio, Y., Lamblin, P., Popovici, P., Larochelle, H. | NIPS 2006 | pdf tech-report-pdf |
Reducing the dimensionality of data with neural networks | Hinton, G. E. and Salakhutdinov, R. R | Science 2006 | pdf support-pdf code |
Learning a Nonlinear Embedding by Preserving Class Neighbourhood Structure | Salakhutdinov, R. R. and Hinton, G. E. | AISTATS 2007 |
Representational Power of Restricted Boltzmann Machines and Deep Belief Networks | Le Roux, N. and Bengio, Y. | Technical Report |
Exponential Family Harmoniums with an Application to Information Retrieval | Welling, M., Rosen-Zvi, M. and Hinton, G. E. | NIPS 2004 | pdf ps |