Learning Multiple Layers of Features from Tiny Images
Alex Krizhevsky

April 8, 2009

Groups at MIT and NYU have collected a dataset of millions of tiny colour images from the web. It
is, in principle, an excellent dataset for unsupervised training of deep generative models, but previous
researchers who have tried this have found it dicult to learn a good set of lters from the images.
We show how to train a multi-layer generative model that learns to extract meaningful features which
resemble those found in the human visual cortex. Using a novel parallelization algorithm to distributethe work among multiple machines connected on a network, we show how training such a model can bedone in reasonable time.
A second problematic aspect of the tiny images dataset is that there are no reliable class labels
which makes it hard to use for object recognition experiments. We created two sets of reliable labels.
The CIFAR-10 set has 6000 examples of each of 10 classes and the CIFAR-100 set has 600 examples ofeach of 100 non-overlapping classes. Using these labels, we show that object recognition is signicantly
improved by pre-training a layer of features on a large set of unlabeled tiny images.

1

Contents
1 Preliminaries

3

1.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Natural images

3

1.3

1.4

1.2.1

The dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2.2

Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

The ZCA whitening transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.1

Motivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.2

Whitening lters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3.3

Whitened data

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

RBMs

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.4.1

Training RBMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.4.2

Deep Belief Networks (DBNs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.4.3

Gaussian-Bernoulli RBMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.4.3.1

Training Gaussian-Bernoulli RBMs

. . . . . . . . . . . . . . . . . . . . .

14

1.4.3.2

Learning visible variances . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

1.4.3.3

Visualizing lters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Feed-forward neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

1.4.4
1.5

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Measuring performance

2 Learning a generative model of images

17

2.1

Motivation

2.2

Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.3

Initial attempts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.4

Deleting directions of variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.5

Training on patches of images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.5.1

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Merging RBMs trained on patches

17. . . . . . . . . . . . . . . . . . . . . . . . . . .

20. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.6

Training RBMs on 32x32 images

2.7

Learning visible standard deviations

2.8

Second layer of features. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3 Object classication experiments

32

3.1

The labeled subset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.2

Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

4 Parallelizing the training of RBMs

36

4.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2

The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

4.3

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

4.3.1

Writer threads. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.3.2

Reader threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.4
4.5

36

Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.4.1

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

Other algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46Communication cost analysis

A The ZCA whitening transformation

48

B Feed-forward neural networks

50
1

C Labeler instruction sheet

52

D CIFAR-100 class structure

54

2Chapter 1

Preliminaries
1.1

Introduction

In this work we describe how to train a multi-layer generative model of natural images. We use a datasetof millions of tiny colour images, described in the next section. This has been attempted by several groups
but without success[3, 7]. The models on which we focus are RBMs (Restricted Boltzmann Machines)
and DBNs (Deep Belief Networks). These models learn interesting-looking lters, which we show are
more useful to a classier than the raw pixels. We train the classier on a labeled subset that we havecollected and call the CIFAR-10 dataset.

1.2

Natural images

1.2.1 The dataset
The tiny images dataset on which we based all of our experiments was collected by colleagues at MIT
and NYU over the span of six months; it is described in detail in [14]. They assembled it by searching the
web for images of every non-abstract English noun in the lexical database WordNet[15, 8]. They used
several search engines, including Google, Flickr, and Altavista and kept roughly the rst 3000 resultsfor each search term. After collecting all the images for a particular search term, they removed perfect
duplicates and images in which an excessively large portion of the pixels were white, as they tended tobe synthetic gures rather than natural images. The search term used to nd an image provides it witha rough label, although it is extremely unreliable due to the nature of online image search technology.
In total, the dataset contains 80 million colour images downscaled to 32 × 32 and spread out across
79000 search terms. Most of our experiments with unsupervised learning were performed on a subset ofabout 2 million images.

1.2.2 Properties
Real images have various properties that other datasets do not. Many of these properties can be madeapparent by examining the covariance matrix of the tiny images dataset. Figures 1.1 and 1.2 show thiscovariance matrix.
The main diagonal and its neighbours demonstrate the most apparent feature of real images: pixels
are strongly correlated to nearby pixels and weakly correlated to faraway pixels. Various other properties
can be observed as well, for example:• The green value of one pixel is highly correlated to the green value of a neighbouring pixel, butslightly less correlated to the blue and red values of the neighbouring pixel.

• The images tend to be symmetric about the vertical and horizontal. For example, the colour of
the top-left pixel is correlated to the colour of the top-right pixel and the bottom-left pixel. Thiskind of symmetry can be observed in all pixels in the faint anti-diagonals of the covariance matrix.
It is probably caused by the way people take photographs  making the ground plane horizontal
and centering on the main object.

3

Figure 1.1: The covariance matrix of the tiny images dataset. White indicates high values, black indicates
low values. All values are positive. Pixels in the 32 × 32 images are indexed in row-major order. The
matrix appears split into nine squares because the images have three colour channels. The rst 1024
indices represent the values of the red channel, the next 1024 the values of the green channel, and thelast 1024 the values of the blue channel.

4Figure 1.2: The covariance matrix of the red channel of the tiny images dataset. This is a magnicationof the top-left square of the matrix in Figure 1.1.

• As an extension of the above point, pixels are much more correlated with faraway pixels in thesame row or column than with faraway pixels in a dierent row or column.

1.3

The ZCA whitening transformation

1.3.1 Motivation
As mentioned above, the tiny images exhibit strong correlations between nearby pixels. In particular,
two-way correlations are quite strong.

When learning a statistical model of images, it might be nice

to force the model to focus on higher-order correlations rather than get distracted by modelling twoway correlations. The hypothesis is that this might make the model more likely to discover interesting1

regularities in the images rather than merely learn that nearby pixels are similar.

One way to force the model to ignore second-order structure is to remove it. Luckily this can be donewith a data preprocessing step that just consists of multiplying the data matrix by a whitening matrix.
After the transformation, it will be impossible to predict the value of one pixel given the value of only
one other pixel, so any statistical model would be wise not to try. The transformation is described inAppendix A.

1.3.2 Whitening lters
Using the notation of Appendix A, where W is the whitening matrix, each row Wi of W can be thoughtof as a lter that is applied to the data points by taking the dot product of the lter Wi and the data
point Xj . If, as in our case, the data points are images, then each lter has exactly as many pixels as
do the images, and so it is natural to try to visualize these lters to see the kinds of transformations they

1 Here when we say pixel, we are really referring to a particular colour channel of a pixel. The transformation we will
describe decorrelates the value of a particular colour channel in a particular pixel from the value of another colour channel
in another (or possibly the same) pixel. It does not decorrelate the values of all three colour channels in one pixel fromthe values of all three in another pixel.

5

(a)

(b)
Figure 1.3: Whitening lters.

(a) lters for the red, green, and blue components of pixel (2, 0). (b)lters for pixel (15, 15).
Although surely impossible to discern on a printed page, the lter in(a) actually has some sup-port on the horizontally opposite side of the image, conrming once again that natural images tend to
exhibit symmetry.

entail. Figure 1.3 shows some whitening lters visualized in this way. As mentioned, they are highly local
because natural images have strong correlations between nearby pixels and weak correlations between
faraway pixels. Figure 1.4 shows the dewhitening lters, which are the rows of W

−1

. Applying theselters to a whitened image yields the original image.

1.3.3 Whitened data
Figure 1.5 shows some images after being transformed by W . Predictably, the transformation preservesedge information but sets to zero pixels in regions of relatively uniform colour.

1.4

RBMs

An RBM (Restricted Boltzmann Machine) is a type of graphical model in which the nodes are partitioned
into two sets: visible and hidden. Each visible unit (node) is connected to each hidden unit, but there
are no intra-visible or intra-hidden connections. Figure 1.6 illustrates this. RBMs are explored in [11, 4].
An RBM with V visible units and H hidden units is governed by the following energy function:E(v, h) = −

V X
H
X

vi hj wij −i=1 j=1VX
i=1vi bvi −HX

hj bhjj=1

where• v is the binary state vector of the visible units,• h is the binary state vector of the hidden units,• vi is the state of visible unit i,• hj is the state of hidden unit j ,• wij is the real-valued weight between visible unit i and hidden unit j ,
6

(1.1)

(a)

(b)
Figure 1.4: The dewhitening lters that correspond to the whitening lters of Figure 1.3.

• bvi is the real-valued bias into visible unit i,• bhj is the real-valued bias into hidden unit j .
A probability is associated with conguration (v, h) as follows:e−E(v,h)p(v, h) = P P −E(u,g) .
u
ge

(1.2)

Intuitively, congurations with low energy are assigned high probability and congurations with highenergy are assigned low probability. The sum in the denominator is over all possible visible and hidden
congurations, and is thus extremely hard to compute when the number of units is large.
The probability of a particular visible state conguration v is derived as follows:

p(v)

=

X

p(v, g)g=

P −E(v,g)ge
P P.
−E(u,g)
u
ge

(1.3)

At a very high-level, the RBM training procedure consists of xing the states of the visible units v atsome desired conguration and then nding settings of the parameters (the weights and biases) such thatp(v) is large. The hope is that the model will use the hidden units to generalize and to extract meaningful
features from the data, and hence p(u) will also be large for u drawn from the same distribution as v.
We now derive a few other distributions that are entailed by equation (1.2). The formula for p(h) is
entirely analogous to that of p(v):P −E(u,h)uePPp(h) =.
−E(u,g)u
ge

7Figure 1.5: The result of whitening.

Figure 1.6: The Restricted Boltzmann Machine architecture.

8

We can also derive some simple conditional expressions:p(v|h)p(v, h)p(h)=e−E(v,h)P −E(u,h)uep(v, h)p(v)=p(h|v)=e−E(v,h)P −E(v,g) .
ge=

We can also derive a closed-form expression for p(vk = 1|h), the probability of a particular visible unit
being on given a hidden conguration. To do this, we introduce the notationp(vk = 1, vi6=k , h)to denote the probability of the conguration in which visible unit k has state 1, the rest of the visible
units have state vi6=k , and the hidden units have state h. Given this, we havep(vk = 1|h)==p(vk = 1, h)p(h)P
vi6=k p(vk = 1, vi6=k , h)p(h)P

vi6=k e−E(vk =1,vi6=k ,h)−E(u,g)uge
P −E(u,h)ue
P P−E(u,g)
u
ge

P P

=

−E(vk =1,vi6=k ,h)vi6=k eP −E(u,h)
ue
P
PV PH
PV
P
v
v PH
h
( H
j=1 hj wkj +bk )+(i6=k
j=1 vi hj wij +i6=k vi bi +j=1 hj bj )vi6=k eP −E(u,h)
ue
h PH
i
P
P
PV PH
P
v
h
( i6=k j=1 vi hj wij + Vi6=k vi bvi + H
j=1 hj bj )e( j=1 hj wkj +bk )
vi6=k e

P
=

=

=

=

=

=

P −E(u,h)
ue
h PH
i
P
v
−E(vk =0,vi6=k ,h)e( j=1 hj wkj +bk )
vi6=k eP −E(u,h)
ue
iP
h PH
v
−E(vk =0,vi6=k ,h)e( j=1 hj wkj +bk )
vi6=k eP
P
−E(uk =1,ui6=k ,h) +−E(uk =0,ui6=k ,h)ui6=k eui6=k eih PHPv
−E(vk =0,vi6=k ,h)e( j=1 hj wkj +bk )
vi6=k e
h PH
i
P
P
v
−E(uk =0,ui6=k ,h) +−E(uk =0,ui6=k ,h)e( j=1 hj wkj +bk )
ui6=k eui6=k e
1

=

.
P
v
−( H
j=1 hj wkj +bk )1+eLikewise,1p(hk = 1|v) =
1+e

.
P
h
−( V
i=1 vi wik +bk )(1.4)

So as can be expected from Figure 1.6, we nd that the probability of a visible unit turning on is
independent of the states of the other visible units, given the states of the hidden units. Likewise, thehidden states are independent of each other given the visible states.

This property of RBMs makes

sampling extremely ecient, as one can sample all the hidden units simultaneously and then all thevisible units simultaneously.

9

1.4.1 Training RBMsc

Given a set of C training cases {v |c ∈ {1, . . . , C}}, the goal is to maximize the average log probabilityof the set under the model's distribution:CXclog p(v ) =

c=1

C
X

P

ge

log P Puc=1

−E(vc ,g)−E(u,g)ge.

We attempt to do this with gradient descent. Dierentiating with respect to a weight wij , we haveC∂ X
log p(vc )∂wij c=1=

P −E(vc ,g)
C
∂ X
ge
P
P −E(u,g)log∂wij c=1
u
ge

=

∂
∂wij

C
X

!
log

X

e

−E(vc ,g)

− log

XX

g

c=1

u

e

−E(u,g)

.

(1.5)

g

First consider the rst term:

C
X
c
∂ X
log
e−E(v ,g)∂wij c=1g

P −E(vc ,g)
∂
C
X
ge
∂wij
P −E(vc ,g)=ge
c=1
P −E(vc ,g) ∂E(vc ,g)
C
X
ge
∂w
P −E(vc ,g) ij
= −
ge
c=1
P −E(vc ,g) c
C
X ge
vi gj
P −E(vc ,g) .
= −
ge
c=1

P −E(vc ,g) c
vi g jgecP
is just the expected value of vi gj given that v is clamped to the−E(vc ,g)geccdata vector v . This is easy to compute since we know vi and we can compute the expected value of gj
using equation (1.4).
Notice that the term

Turning our attention to the second term in equation (1.5):

C
XX
∂ X
log
e−E(u,g)∂wij c=1ug

P P −E(u,g)
∂
C
X
u
ge
∂wij
P P −E(u,g)
=
u
ge
c=1
P
P
−E(u,g) ∂E(u,g)
C
X
u
ge
∂w
P P −E(u,g) ij
= −
e
u
g
c=1
P P −E(u,g)
CX u geui gj
P P −E(u,g) .
= −
u
ge
c=1

(1.6)

P P −E(u,g)
ui gj
u
ge
P
P
is the expected value of ui gj under the model's distribution. We can−E(u,g)u
geccompute ui gj by clamping the visible units at the data vector v , then sampling the hidden units, thenHere, the term

sampling the visible units, and repeating this procedure innitely many times.

After innitely many

iterations, the model will have forgotten its starting point and we will be sampling from its equilibrium
distribution. However, it has been shown in [5] that this expectation can be approximated well in nite
time by a procedure known as Contrastive Divergence (CD). The CD learning procedure approximates(1.6) by running the sampling chain for only a few steps. It is illustrated in Figure 1.7. We name CD-N
the algorithm that samples the hidden units N + 1 times.
In practice, we use CD-1 almost exclusively because it produces adequate results.

CD-1 learning

amounts to lowering the energy that the model assigns to training vectors and raising the energy of themodel's reconstructions of those training vectors. It has the potential pitfall that places in the energy
surface that are nowhere near data do not get explicitly modied by the algorithm, although they areaected by the changes in parameters that CD-1 induces.
Renaming g s to hs, the update rule for weight wij is∆wij = w (Edata [vi hj ] − Emodel [vi hj ])10

Figure 1.7: The CD-N learning procedure. To estimate Emodel [vi hj ], initialize the visible units at thedata and alternately sample the hidden and then the visible units. Use the observed value of vi hj at the(N + 1)st sample as the estimate.

Figure 1.8: The DBN architecture.

The second-layer RBM is trained on the activities of the hidden

units of the rst-layer RBM, given the data, and keeping W1 xed.

where w is the weight learning rate hyperparameter, Edata is the expectation under the model's distribution when the the visible units are clamped to the data, and Emodel is the expectation under themodel's distribution when the visible units are unclamped. As discussed above, Emodel is approximatedusing CD.
The update rules for the biases are similarly derived to be

∆bvi

=

bv (Edata [vi ] − Emodel [vi ])

∆bhj

=

bh (Edata [hj ] − Emodel [hj ]) .

1.4.2 Deep Belief Networks (DBNs)
Deep Belief Networks extend the RBM architecture to multiple hidden layers, where the weights in layer

l are trained by keeping all the weights in the lower layers constant and taking as data the activitiesof the hidden units at layer l − 1. So the DBN training algorithm trains the layers greedily and insequence. Layer l is trained after layer l − 1. If one makes the size of the second hidden layer the sameas the size of the rst hidden layer and initializes the weights of the second from the weights of the rst,
it can be proven that training the second hidden layer while keeping the rst hidden layer's weights
constant improves the log likelihood of the dataunder the model[9]. Figure 1.8 shows a two-layer DBN
architecture.

11

Looking at the DBN as a top-down generative model, Jensen's inequality tells us thatlog p(v|W1 , W2 ) ≥Xq(h1 |v) log

h1p(v, h1 |W1 , W2 )q(h1 |v)

for any distribution q(h1 |v). In particular, we may set q(h1 |v) = p(h1 |v, W1 ) and get

log p(v|W1 , W2 ) ≥

X

=

X

=

X

p(h1 |v, W1 ) log

p(v, h1 |W1 , W2 )p(h1 |v, W1 )p(h1 |v, W1 ) log

p(v|h1 , W1 )p(h1 |W2 )p(h1 |v, W1 )h1

h1p(h1 |v, W1 ) log p(h1 |W2 ) +

X

h1

h1

=

X

p(h1 |v, W1 ) log p(h1 |W2 ) +

X

=

X

p(h1 |v, W1 ) log

p(v|h1 , W1 )p(h1 |v, W1 )p(h1 |v, W1 ) log

p(v|W1 )p(h1 |W1 )h1h1p(h1 |v, W1 ) log p(h1 |W2 )

h1

−

X

p(h1 |v, W1 ) log p(h1 |W1 ) + log p(v|W1 ).

(1.7)

h1
If we initialize W2 at W1 , then the rst two terms cancel out and so the bound is tight. Training thesecond layer of the DBN while keeping W1 xed amounts to maximizingXp(h1 |v, W1 ) log p(h1 |W2 )h1which is the rst term in equation (1.7). Since the other terms stay constant, when we train the second
hideen layer we are increasing the bound on the log probability of the data. Since the bound is initiallytight due to our initialization of W2 , we must also be increasing the log probability of the data. We can
extend this reasoning to more layers with the caveat that the bound is no longer tight as we initialize W3
after learning W2 and W1 , and so we may increase the bound while lowering the actual log probabilityof the data. The bound is also not tight in the case of Gaussian-Bernoulli RBMs, which we discuss next,
and which we use to model tiny images.
RBMs and DBNs have been shown to be capable of extracting meaningful features when trained onother vision datasets, such as hand-written digits and faces ([6, 12]).

1.4.3 Gaussian-Bernoulli RBMs
An RBM in which the visible units can only take on binary values is, at best, very inconvenient formodeling real-valued data such as pixel intensities. To model real-valued data, we replace the model'senergy function withE(v, h) =VX(vi − bv )2
i

i=1

2σi2

−

H
X

bhj hj −

j=1

V X
H
X
vi
i=1 j=1

σi

hj wij .

(1.8)

This type of model is explored in [6, 2]. Here, vi denotes the now real-valued activity of visible unit vi .
Notice that here each visible unit adds a parabolic (quadratic) oset to the energy function, where σicontrols the width of the parabola. This is in contrast to the binary-to-binary RBM energy function(1.1), to which each visible unit adds only a linear oset. The signicance of this is that in the binaryto-binary case, a visible unit cannot precisely express its preference for a particular value.

This isthe reason why adapting a binary-to-binary RBM to model real values, by treating the visible units'
activation probabilities as their activations, is a bad idea.

2

2 The model we use is also dierent from the product of uni-Gauss experts presented in [5]. In that model, a Gaussian is
associated with each hidden unit. Given a data point, each hidden unit uses its posterior to stochastically decide whether
or not to activate its Gaussian.

The product of all the activated Gaussians (also a Gaussian) is used to compute thereconstruction of the data given the hidden units' activities. The product of uni-Gauss experts model also uses the hidden
units to model the variance of the Gaussians, unlike the Gaussian RBM model which we use. However, we show in section
1.4.3.2 how to learn the variances of the Gaussians in the model we use.

12

Given the energy function (1.8), we can derive the distribution p(v|h) as follows:p(v|h)=e−E(v,h)e−E(u,h) du
u

´

−

PV

2
PH
PV PH vi
(vi −bvhi) +j=1 bj hj +i=1
j=1 σi hj wij
2σ 2
i

−

PV

PV PH uiP(ui −bv )2
h
i
+ H
i=1
j=1 σi hj wij
j=1 bj hj +
2σ 2
i

e
´

e
u

i=1

i=1

−

=

e


PH
PH
2 PH
√
1
1
h
v
QV
j=1 bj hj + σi ·bi
j=1 hj wij
j=1 hj wij ) +2 ·(· σi 2π
i=1 e
−

QV
=

du

2
PH
PV PH vi
(vi −bvhi) +j=1 bj hj +i=1
i=1
j=1 σi hj wij
2σ 2
i

PV

i=1 e

2
PH
(vi −bv
vi PH
h
i) +
j=1 bj hj + σi
j=1 hj wij
2σ 2
i



PH
PH
2 PH
√
1
1
h
v
j=1 bj hj + σi ·bi
j=1 hj wij
j=1 hj wij ) +
2 ·(
·
σ
2π
e
i
i=1

QV

=

V
Y
i=1

=

V
Y
i=1

=

V
Y
i=1

1
√

σi 2π
1
√

σi 2π
1
√

σi 2π

·e

·e

·e

−

2
(vi −bvi ) −1
2
2σ 2
i

−

1
2σ 2
i

−

PH
2
1
(vi −bvi −σi
j=1 hj wij )
2σ 2
i

“

PH

(

j=1 hj wij

2) + σ1i (vi −bvi )(PH

j=1 hj wij

)

”
PH
2
2
2 PH
v
(vi −bvi ) +σi (j=1 hj wij ) −2σi (vi −bi )(j=1 hj wij ),which we recognize as the V -dimensional Gaussian distribution with diagonal covariance given by

σ12
 0


 0
0


0
σ22
0
0

0
0
..

0

.


0
0 


0 
σV2

and mean in dimension i given by

bvi + σi

H
X
j=1

13

hj wij .

As before, we can compute p(hk = 1|v) as follows:Pp(hk = 1|v)

hj6=k p(v, hk = 1, hj6=k , )=p(v)−E(v,hk =1,hj6=k )P

hj6=k e=−E(v,g)
ge
«
“P
” „P
2
PV (vi −bv
PH
PH vi
vi
V
h
V
h
i) +
2
i=1 σ wik +bk +
i=1
j6=k hj bj
i=1
j6=k σ hj wij +PPi

hj6=k e

=
e

“P

vi
V
h
i=1 σi wik +bk„”
hj6=k e=viVhi=1 σi wik +bkeP

gj6=k eP

hj6=k e−E(v,gk =0,g) + e
gj6=k e1+e−E(v,g)gePV2(vi −bv
i)
2σ 2
i

i=1

P
h
+ H
j6=k hj bj«−E(v,hk =0,hj6=k )vihV
i=1 σi wik +bkP=P

gj6=k e”=evi
j6=k σi hj wij +

P

“P

“P
V

i=1

”

−E(v,gk =0,g) +eie−E(v,g)

g
PH

PV

P

=
“P

2σ

i

P

vi
h
i=1 σi wik +bk−E(v,gk =1,g)P

hj6=k e−E(v,hk =0,hj6=k )

“P

vi
V
h
i=1 σi wik +bk”P

gj6=k e−E(v,gk =0,g)

”

“P
V

vi
h
i=1 σi wik +bk

”

1

=
1+e

“P
”
vi
V
h
−
i=1 σ wik +bkiwhich is the same as in the binary-visibles case except here the real-valued visible activity vi is scaledby the reciprocal of its standard deviation σi .

1.4.3.1 Training Gaussian-Bernoulli RBMs
The training procedure for a Gaussian-Bernoulli RBM is identical to that of an ordinary RBM. As inthat case, we take the derivative shown in equation (1.5). We nd that

C
X
c
∂ X
log
e−E(v ,g)∂wij c=1
g

= −

C
X

c

−E(vc ,g) ∂E(v ,g)∂w
P −E(vc ,g) ij
e
g

P

ge

c=1
C

1 X
= −
σi c=1−E(vc ,g) c cvi hj
P −E(vc ,g) .
ge

P

ge

And similarly,

C
C
XX
∂ X
1 X
log
e−E(u,g) = −∂wij c=1
σi c=1ug−E(u,g)
ui gj
u
ge
P
P
−E(u,g)u
ge

P P

which we estimate, as before, using CD.

1.4.3.2 Learning visible variances
Recall that the energy function of a Gaussian-Bernoulli RBM is

E(v, h) =VX(vi − bv )2
i

i=1

2σi2

−

H
X

bhj hj −

V X
H
X
vi

j=1

i=1 j=1

σi

hj wij .

We attempt to maximize the log probability of the data vectors

log p(v)==P −E(v,h)elog ´ P h −E(u,g)
e
du.
g
u
ˆ X
X
−E(v,h)loge− loge−E(u,g) du.
u

h

14

g

The rst term is the negative of the free energy that the model assigns to vector v, and it can be
expanded as follows:−F (v)Xe−E(v,h)

=

log

=

PV PH vih
X − PVi=1 (vi −b2vi )2 +PH
j=1 bj hj +i=1
j=1 σi hj wij
2σ
i
log
e

h

h

=

log e

−

PV

i=1

2
(vi −bvi)
2σ 2
i

X PH bh h +PV PH vi h w
i=1
j=1 σi j ij
e j=1 j j

!

h

= −

V
X
(vi − bv )2
i

2σi2

i=1

= −

= −

X PH bh h +PV PH vi h w
i=1
j=1 σi j ij
e j=1 j jhVX(vi − bv )2
i

2σi2

i=1

+ log

X PH hj “bh +PV vi wij ”
ji=1 σi
+ log
e j=1
h

V
X

H

V
X

H 
Y

X Y hj bh +PV vi wij(vi − bvi )2j
i=1 σi
+
log
e
2
2σ
i
i=1
j=1
“

”

h

= −

= −


P
vi
(vi − bvi )2
bh + Vi=1 σi wij
+ log
1+e j
2
2σi
i=1
j=1

V
X
(vi − bv )2
i

2σi2

i=1

+

H
X



P
vi
bh + Vi=1 σi wij.
log 1 + e j

j=1

The second-last step is justied by the fact that each hj is either 0 or 1.
The derivative of −F (v) with respect to σi is∂ (−F (v))
∂σi

=

H


PV vi
∂ X
(vi − bvi )2bhj+
i=1 σi wij
+
log
1
+
e
σi3
∂σi j=1=

H
b + i=1 σi wij
i(vi − bvi )2 X e jwij vi
PV vi
·
−
h+
3
b
w
ij
σi
σi2
i=1 σijj=1 1 + e=H1
wij vi(vi − bvi )2 X
PV vi
−
·
h−
3
w
−b
σi
σi2
i=1 σi ij
j
j=1 1 + e=H(vi − bvi )2 X
wij vi
−
aj ·
.
3
σi
σi2
j=1

h

PV

v

where aj is the real-valued, deterministic activation probability of hidden unit j given the visible vectorv.
Likewise, the derivative with respect to log

∂
log
∂σi

ˆ X
u

´ P
u

´ P
e−E(u,g) du =

u

ge

ge

−E(u,g)−E(u,g)



du is

2
PH
(ui −bvw ui)− j=1 gj · σij2 i
σi3
i

´ P
u

g

ge



du

−E(u,g) du

which is just the expected value ofH(vi − bvi )2 X
wij vi
−
hj ·
σi3
σi2
j=1
under the model's distribution.
Therefore, the update rule for σi is








H
H
v 2
v 2
X
X
(v
−
b
)
(v
−
b
)
w
v
w
v
i
ij i 
i
ij i 
ii∆σi = σ Edata −hj ·− Emodel 
−
hj ·
2
3
2
σi3
σ
σ
σ
i
i
i
j=1
j=1
15

where σ is the learning rate hyperparameter. As for weights, we use CD-1 to approximate the expectation under the model.

1.4.3.3 Visualizing lters
There is an intuitive way to interpret the weights of a Gaussian-Bernoulli RBM trained on images, andthat is to look at the lters that the hidden units apply to the image. Each hidden unit is connectedwith some weight to each pixel. If we arrange these weights on a 32 × 32 grid, we obtain a visualizationof the lter applied by the hidden unit.

Figure 2.13 shows this type of visualization of 64 dierent

hidden units. In creating these visualizations, we use intensity to indicate the strength of the weight.
So a green region in the lter denotes a set of weights that have strong positive connections to the green
channel of the pixels. But a purple region indicates strong negative connections to the green channelof the pixels, since this is the colour produced by setting the red and blue channels to high values andthe green channel to a low value. In this sense, purple is negative green, yellow is negative blue, andturquoise is negative red.

1.4.4 Measuring performance
Ideally, we would like to be able to evaluate p(v) for data vector v. But this is intractable for models
with large numbers of hidden units due to the denominator in (1.3). Instead we use the reconstruction

0 2

error. The reconstruction error is the squared dierence (v − v )between the data vector v, and thevector produced by sampling the hidden units given v to obtain a hidden conguration h, and then0sampling the visible units given h to obtain a visible conguration v . This is not a very good measureof how well the model's probability distribution matches that of the data, because the reconstruction
error depends heavily on how fast the Markov chain mixes.

1.5

Feed-forward neural networks

In our experiments we use the weights learned by an RBM to initialize feed-forward neural networks
which we train with the standard backpropagation algorithm. In Appendix B we give a brief overview
of the algorithm.

16

Chapter 2

Learning a generative model of images
2.1

Motivation

The major, recurrent theme throughout this work is our search for a good generative model of natural
images. In addition, we seek a model that is capable of extracting useful high-level features from images,
such as the locations and orientations of contours. The hope is that such features would be much more
useful to a classier than the raw pixels.

Finally, such a model would have some connection to thephysical realities of human vision, as the visual cortex contains neurons that detect high-level features
such as edges.

2.2

Previous work

One of the authors of the 80 million tiny images dataset unsuccessfully attempted to train the type ofmodel that we are interested in here[3].

He was unsuccessful in the sense that the model he trained

did not learn interesting lters. The model learned noisy global lters and point-like identity functions
similar to the ones of Figure 2.12. Another group also attempted to train this type of model on 16 × 16
colour patches of natural images and came out only with lters that are everywhere uniform or global
and noisy[7].

2.3Initial attempts

We started out by attempting to train an RBM with 8000 hidden units on a subset of 2 million imagesof the tiny images dataset. The subset was whitened but left otherwise unchanged. For this experiment
we set the variance of each of the visible units to

1, since that is the variance that the whitening

transformation produced. Unfortunately this model developed a lot of lters like the ones in Figure 2.1.
Nothing that could be mistaken for a feature.

2.4

Deleting directions of variance

One theory was that high-frequency noise in the images was making it hard for the model to latch on
to the real structure. It was busy modelling the noise, not the images. To mitigate this, we decided toremove some of the least signicant directions of variance from the dataset. We accomplished this bysetting to zero those entries of the diagonal matrix D of equation (A.1) that correspond to the 1000 leastsignicant principal components (these are the 1000 smallest entries of D ). This has no discernible eect
on the appearance of the images since the 2072 directions of variance that remain are far more important.
In support of this claim, Figure 2.3 compares images that have been whitened and then dewhitened withthe original lter with those using the new lter that also deletes the 1000 least signicant principal
components. Figure 2.2 plots the log-eigenspectrum of the tiny images dataset.
Unfortunately, this extra pre-processing step failed to convince the RBM to learn interesting features.
But we nonetheless considered it a sensible step so we kept it for the remainder of our experiments.

17

Figure 2.1: Meaningless lters learned by an RBM on whitened data. These lters are in the whitened
domain, meaning they are applied by the RBM to whitened images.

Figure 2.2: The log-eigenspectrum of the tiny images dataset. The variance in the directions of the 1000
least signicant principal components is seen to be several orders of magnitude smaller than that in the
direction of the 1000 most signicant.

18

(a)

(b)
Figure 2.3:(a) The result of whitening and then dewhitening an image with the original whiteninglter derived in section 1.3.

(b) The same as (a), but the dewhitening lter also deletes the 1000 least-signicant principal
components from the dataset as described in section 2.4.
Notice that the whitened image appears smoother and less noisy in (b) than in (a), but the dewhitened image in (b) is identical to that in (a).

This conrms that this modied whitening

transformation is still invertible, even if not technically so.

19

Figure 2.4: Segmenting a 32 × 32 image into 25 8x8 patches.

2.5

Training on patches of images

Frustrated by the model's inability to extract meaningful features, we decided to train on 8 × 8 patchesof the images. This greatly reduced the data dimensionality and hence the required model complexity,
measured in the number of hidden units. We divided the 32 × 32 images into 25 8 × 8 patches as shown in
Figure 2.4. In addition to the patches shown in Figure 2.4, we created a 26th patch: an 8 × 8 subsampled
version of the entire 32 × 32 image. We trained 26 independent RBMs with 300 hidden units on each ofthese patches; Figures 2.5 and 2.6 show the lters that they learned. These are the types of lters that
we were looking for  edge detectors.
One immediately noticeable pattern among the lters of Figure 2.5 is the RBM's anity for lowfrequency colour lters and high-frequency black-and-white lters.

One explanation may be that theblack-and-white lters are actually wider in the colour dimension, since they have strong connections
to all colour channels. We may also speculate that precise edge position information and rough colour
information is sucient to build a good model of natural images.

2.5.1 Merging RBMs trained on patches
Once we have trained 26 of these RBMs on the tiny image patches, we can combine them in a verystraightforward (perhaps naive) way by training a new RBM with 7800 (26 × 300) hidden units. We
initialize the rst 300 of these hidden units with the weights from the RBM trained on patch #1, thenext 300 with the weights trained on patch #2, and so forth. However, each of the hidden units in the
big RBM is connected to every pixel in the 32 × 32 image, so we initialize to 0 the weights that didn't
exist in the RBMs trained on patches (for example, the weight from a pixel in patch #2 to a hidden
unit from an RBM trained on patch #1). The weights from the hidden units that belonged to the RBM
trained on patch #26 (the subsampled global patch) are initialized as depicted in Figure 2.7. The biasof a visible unit of the big RBM is initialized to the average bias that the unit received among the small
RBMs.
Interestingly, this type of model behaves very well, in the sense that the weights don't blow up andthe lters stay roughly as they were in the RBMs trained on patches. In addition, it is able to reconstruct
images much better than the average small RBM is able to reconstruct image patches. This despite thefact that the patches that we trained on were overlapping, so the visible units in the big RBM mustessentially learn to reconcile the inputs from two or three sets of hidden units, each of which comes froma dierent small RBM.
Figures 2.8 and 2.9 show some of the lters learned by this model (although in truth, they were forthe most part learned by the small RBMs). Figure 2.10 shows the reconstruction error as a function oftraining time. The reconstruction error up to epoch 20 is the average among the independently-trained
small RBMs. The large spike at epoch 20 is the point at which the small RBMs were combined into
one big RBM. The merger initially has an adverse eect on the reconstruction error but it very quickly
descends below its previous minimum.

20Figure 2.5: Filters learned by an RBM trained on the 8x8 patch #1 (depicted in Figure 2.4) of thewhitened tiny images dataset. The RBMs trained on the other patches learned similar lters.

21

Figure 2.6: Filters learned by an RBM trained on 8 × 8 subsampled versions of the 32 × 32 whitened
tiny image dataset.

22

Figure 2.7: How to convert hidden units trained on a globally subsampled 8 × 8 patch to hidden units
to be trained on the entire 32 × 32 image. Each weight w in the small RBM is duplicated 16 times anddivided by 16 in the big RBM. The weights of the big RBM are untied and free to dierentiate.

2.6

Training RBMs on 32x32 images

After our successes training models of 8 × 8 and 16 × 16 patches, we decided to try with 32 × 32 images
once more. This time we developed an algorithm for parallelizing the training across all the CPU cores ofa machine. Later, we further parallelized across machines on a network, and this algorithm is describedin Chapter 4.
With this new, faster training algorithm we were quickly able to train an RBM with 10000 hidden
units on the 32 × 32 whitened images. A sample of the lters that it learned is shown in Figure 2.11.
They appear very similar to the lters learned by the RBMs trained on patches.
After successfully training this RBM, we decided to try training an RBM on unwhitened data. We
again preprocessed the data by deleting the 1000 least-signicant directions of variance, as described in
section 2.4. We measured the average standard deviation of the pixels in this dataset to be 69, so we
set the standard deviation of the visible units of the RBM to 69 as well. A curious thing happens whentraining on unwhitened data  all of the lters go through a point stage before they turn into edge lters.
A sample of such point lters is shown in Figure 2.12. In the point stage, the lters simply copy datafrom the visible units to the hidden units. The lters remain in this point stage for a signicant amountof time, which can create the illusion that the RBM has nished learning and that further training isfutile. However, the point lters eventually evaporate and in their place form all kinds of edge lters,

1

a sample of which is shown in Figure 2.13 .

The edge lters do not necessarily form at or near the

positions of their pointy ancestors, though this is common. Notice that these lters are generally larger
than the ones learned by the RBM trained on whitened data (Figure 2.11). This is most likely due tothe fact that a green pixel in a whitened image can indicate a whole region of green in the unwhitened
image.

1 Note that these lters are from a dierent RBM than that which produced the point lters pictured in Figure 2.12.

23

Figure 2.8: Some of the lters learned by the RBM produced by merging the 26 RBMs trained on image
patches, as described in section 2.5.1. All of the non-zero weights are in the top-left corner because thesehidden units were initialized from the RBM trained on patch #1. Compare with the lters of the RBM
in Figure 2.5.

24

Figure 2.9: Some of the lters learned by the RBM produced by merging the 26 RBMs trained on image
patches, as described in section 2.5.1. These hidden units were initialized from the RBM trained on the
globally subsampled patch, pictured in Figure 2.6. Notice that the globally noisy lters of Figure 2.6
have developed into entirely new local lters, while the local lters of Figure 2.6 have remained largely
unchanged.

25

Epoch 0-20: The average reconstruction error among the 26 RBMs trained on 8 × 8 image
Epochs 20+: The reconstruction error of the RBM produced by merging the 26 little RBMs

Figure 2.10:
patches.

as described in section 2.5.1.

The spike at epoch 20 demonstrates the initial adverse eect that themerger has on the reconstruction error. The spike between epochs 1 and 2 is the result of increasing thelearning rate.

2.7

Learning visible standard deviations

We then turned our attention to learning the standard deviations of the visible units, as describedin section 1.4.3.2.

Our hope was that the RBM would learn much smaller values for these standard

deviations than the true standard deviations of the pixels across the dataset. The trick to doing thiscorrectly is to set the learning rate of the standard deviations to a suciently low value. In our experience,
it should be about 100 to 1000 times smaller than the learning rate of the weights.

Failure to do so

produces a lot of point lters that never evolve into edge lters. Figure 2.14 shows a sample of the lters
learned by an RBM trained on unwhitened data while also learning the visible standard deviations.
The RBM did indeed learn lower values for the standard deviations than observed in the data; over thecourse of training the standard deviations came down to about 30 from an initial value of 69 (althoughthe nal value depends on how long one trains). Though the RBM had a separate parameter for the
standard deviation of each pixel, all the parameters remained very similar. The standard deviation of
the standard deviations was 0.42.
Learning the standard deviations improved the RBM's reconstruction error tremendously, but it had
a qualitatively negative eect on the appearance of the lters. They became more noisy and more ofthem remained in the point lter stage.

2.8

Second layer of features

Figure 2.15 shows the features learned by a binary-to-binary RBM with 10000 hidden units trainedon the 10000-dimensional hidden unit activation probabilities of the RBM trained on unwhitened data.
Hidden units in the second-level RBM tend to have strong positive weights to similar features in therst layer. The second-layer RBM is indeed extracting higher-level features.

26

Figure 2.11: A sample of the lters learned by an RBM with 10000 hidden units trained on 2 million

32 × 32 whitened images.

27

Figure 2.12: A random sample of lters from an RBM that only learned point lters.

28

Figure 2.13: A sample of the lters learned by an RBM with 10000 hidden units trained on 2 million

32 × 32 unwhitened images.

29

Figure 2.14: A sample of the lters learned by an RBM with 8192 hidden units on 2 million 32 × 32
unwhitened images while also learning the standard deviations of the visible units. Notice that the edge
lters learned by this RBM have a higher frequency than those learned by the RBM of Figure 2.13. Thisis due to the fact that this RBM has learned to set its visible standard deviations to values lower than69, and so its hidden units learned to be more precise.

30

Figure 2.15: A visualization of a random sample of 10000 lters learned by an RBM trained on the10000-dimensional hidden unit activation probabilities of the RBM trained on unwhitened data.
Every row represents a hidden unit

h in the second-level RBM, and in every column are the l-ters of the rst-level RBM to which h has the strongest connections. The four lters on the left are theones to which h has the strongest positive connection and the four lters on the right are the ones towhich h has the strongest negative connections.
In a few instances we see examples of the RBM favouring a certain edge lter orientation anddisfavouring the mirror orientation (see for example second-last row, columns 2 and 8).

31

Chapter 3

Object classication experiments
3.1

The labeled subset1

We paid students to label a subset of the tiny images dataset. The labeled subset we collected consistsof ten classes of objects with 6000 images in each class. The classes are airplane, automobile (but nottruck or pickup truck), bird, cat, deer, dog, frog, horse, ship, and truck (but not pickup truck). Since
each image in the dataset already comes with a noisy label (the search term used to nd the image), all
we needed the labelers to do was to lter out the mislabeled images. To that end, each labeler was givena class and asked to examine all the images which were found with that class as the search term. Since
the dataset contains only about 3000 images per search term, the labelers were also asked to examine
all the images which were found with a search term that is a hyponym (as dened by WordNet) of themain search term. As an example, some of the hyponyms of ship are cargo ship, ocean liner, and frigate.
The labelers were instructed to reject images which did not belong to their assigned class. The criteria

2

for deciding whether an image belongs to a class were as follows :• The class name should be high on the list of likely answers to the question What is in this picture?
• The image should be photo-realistic. Labelers were instructed to reject line drawings.
• The image should contain only one prominent instance of the object to which the class refers.
• The object may be partially occluded or seen from an unusual viewpoint as long as its identity is
still clear to the labeler.
The labelers were paid a xed sum per hour spent labeling, so there was no incentive to rush through thetask. Furthermore, we personally veried every label submitted by the labelers. We removed duplicate
images from the dataset by comparing images with the L2 norm and using a rejection threshold liberal
enough to capture not just perfect duplicates but also re-saved JPEGs and the like. Finally, we divided
the dataset into a training and test set, the training set receiving a randomly-selected 5000 images fromeach class.
We call this the CIFAR-10 dataset, after the Canadian Institute for Advanced Research, which funded
the project. In addition to this dataset, we have collected another set  600 images in each of 100 classes.
This we call the CIFAR-100 dataset. The methodology for collecting this dataset was identical to thatfor CIFAR-10. The CIFAR-100 classes are mutually exclusive with the CIFAR-10 classes, and so they
can be used as negative examples for CIFAR-10.

For example, CIFAR-10 has the classes automobile

and truck, but neither of these classes includes images of pickup trucks. CIFAR-100 has the class pickup

truck. Furthermore, the CIFAR-100 classes come in 20 superclasses of ve classes each. For example,
the superclass reptile consists of the ve classes crocodile, dinosaur, lizard, turtle, and snake. The idea
is that classes within the same superclass are similar and thus harder to distinguish than classes thatbelong to dierent superclasses. Appendix D lists the entire class structure of CIFAR-100.
All of our experiments were with the CIFAR-10 dataset because the CIFAR-100 was only very recently
completed.

1 We thank Vinod Nair for his substantial contribution to the labeling project.
2 The instruction sheet which was handed out to the labelers is reproduced in Appendix C.

32

3.2

Methods

We compared several methods of classifying the images in the CIFAR-10 dataset. Each of these methods
used multinomial logistic regression at its output layer, so we distinguish the methods mainly by the
input they took:
1. The raw pixels (unwhitened).
2. The raw pixels (whitened).
3. The features learned by an RBM trained on the raw pixels.
4. The features learned by an RBM trained on the features learned by the RBM of #3.
One can also use the features learned by an RBM to initialize a neural network, and this gave us
our best results (this approach was presented in [6]). The neural net had one hidden layer of logistic1
1+e−x ), whose weights to the visible units we initialized from the RBM trained on raw(unwhitened) pixels. We initialized the hidden-to-output weights from the logistic regression model
units (f (x) =trained on RBM features as input. So, initially, the output of the neural net was exactly identical to the
output of the logistic regression model. But the net learned to ne-tune the RBM weights to improvegeneralization performance slightly. In this fashion it is also possible to initialize two-hidden-layer neuralnets with the features learned by two layers of RBMs, and so forth. However, two hidden layers did notgive us any improvement over one. This result is in line with that found in [10].

3

Our results are summarized in Figure 3.1 . Each of our models produced a probability distribution
over the ten classes, so we took the most probable class as the model's prediction. We found that theRBM features were far more useful in the classication task than the raw pixels. Furthermore, featuresfrom an RBM trained on unwhitened data outperformed those from an RBM trained on whitened data.
This may be due to the fact that the whitening transformation xes the variance in every direction at
1, possibly exaggerating the signicance of some directions which correspond mainly to noise (although,as mentioned, we deleted the 1000 least-signicant directions of variance from the data). The neuralnet that was initialized with RBM features achieved the best result, just slightly improving on thelogistic regression model trained on RBM features. The gure also makes clear that, for the purposeof classication, the features learned by an RBM trained on the raw pixels are superior to the features
learned by a randomly-initialized neural net. We should also mention that the neural nets initialized
from RBM features take many fewer epochs to train than the equivalently-sized randomly-initialized
nets, because all the RBM-initialized neural net has to do is ne-tune the weights learned by the RBM

4which was trained on 2 million tiny images .
Figure 3.2 shows the confusion matrix of the logistic regression model trained on RBM features(unwhitened). The matrix summarizes which classes get mistaken for which other classes by the model.
It is interesting to note that the animal classes seem to form a distinct cluster from the non-animalclasses. Seldom is an animal mistaken for a non-animal, save for the occasional misidentication of a5bird as a plane.

3 The last model performed slightly worse than the second-last model probably because it had roughly 2×108 parameters
and thus had a strong tendency to overt. The model's size also made it slow and very cumbersome to train. We did not
run many instances of it to nd the best setting of the hyperparameters.

4 Which, admittedly, it took a long time to learn.
5 It is a pity we did not have the foresight to include Superman as the 11th class.

33

Figure 3.1: Classication performance on the test set of the various methods tested. The models were:(a,b) Logistic regression on the raw, whitened and unwhitened data.
(c,d) Logistic regression on 10000 RBM features from an RBM trained on whitened, unwhitened data.
(e) Backprop net with one hidden layer initialized from the 10000 features learned by an RBM trainedon unwhitened data. The hidden-out connections were initialized from the model of (d).
(f) Backprop net with one hidden layer of 1000 units, trained on unwhitened data and with logistic
regression at the output.

(g) Backprop net with one hidden layer of 10000 units, trained on unwhitened pixels and with logistic
regression at the output.

(h) Logistic regression on 10000 RBM features from an RBM trained on the 10000 features learned by
an RBM trained on unwhitened data.

(i) Backprop net with one hidden layer initialized from the 10000 features learned by an RBM trainedon the 10000 features from an RBM trained on unwhitened data.
initialized from the model of(h).

The hidden-out connections were(j) Backprop net with two hidden layers, the rst initialized as in (e) and the second as in (i). The
hidden-out connections were initialized as in (i) as well.

34

Figure 3.2:

Confusion matrix for logistic regression on 10000 RBM features trained on unwhitened

data. The area of square (i, j) indicates the frequency with which an image whose true label is i getsclassied as j . The values in each row sum to 1. This matrix was constructed from the CIFAR-10 test set.
Notice how frequently a cat is mistaken for a dog, and how infrequently an animal is mistaken
for a non-animal (or vice versa).

35

Chapter 4

Parallelizing the training of RBMs
4.1

Introduction

Here we describe an algorithm for parallelizing the training of RBMs. When both the hidden and visible
units are binary, the algorithm is extremely ecient, in that it requires very little communication andhence scales very well.

When the visible units are Gaussian the algorithm is less ecient but in the

problem we tested, it scales nearly as well as in the binary-to-binary case.

In either case the total

amount of communication required scales linearly with the number of machines, while the amount ofcommunication required per machine is constant. If the machines have more than one core, the work can
be further distributed among the cores. The specic algorithm we will describe is a distributed versionof CD-1, but the principle remains the same for any variant of CD, including Persistent CD (PCD)[13].

4.2

The algorithm

Recall that (undistributed) CD-1 training consists roughly of the following steps, where there are I
visible units and J hidden units:
1. Get the data V= [v0 , v1 , ..., vI ].

2. Compute hidden unit activities H = [h0 , h1 , ..., hJ ] given the data.
3. Compute visible unit activities (negative data) V0= [v00 , v10 , ..., vI0 ] given the hidden unit activitiesof the previous step.
4. Compute hidden unit activities H0= [h00 , h01 , ..., h0J ] given the visible unit activities of the previous

step.
The weight update for weight wij is∆wij =  vi hj − vi0 h0j .
If we're doing batch training, the weight update is∆wij =  < vi hj > − < vi0 h0j >where <> denotes expectation among the training cases in the batch.
The distributed algorithm parallelizes steps 2, 3, and 4 and inserts synchronization points

1 after eachof these steps so that all the machines proceed in lockstep. If there are n machines, each machine is
responsible for computing 1/n of the hidden unit activities in steps 2 and 4 and 1/n of the visible unit
activities in step 3. We assume that all machines have access to the whole dataset. It's probably easiest
to describe this with a picture. Figure 4.1 shows which weights each machine cares about (i.e. whichweights it has to know) when there are four machines in total.
For K machines, the algorithm proceeds as follows:

1 A synchronization point is a section of code that all machines must execute before any machine can proceed beyond
it.

36

(a)

(b)
Figure 4.1: In four-way parallelization, this shows which weights machines (a) 1 and (b) 2 have to know.
We have divided the visible layer and the hidden layer into four equal chunks arbitrarily. Note that thevisible layer does not necessarily have to be equal in size to the hidden layer  it's just convenient todraw them this way. The weights have dierent colours because it's convenient to refer to them by theircolour in the text.

1. Each machine has access to the whole dataset so it knows Vk= [v0 , v1 , ..., vI ].
kk

2. Each machine k computes its hidden unit activities Hk = [h0 , h1 , ..., hJ/K ] given the data V . Notethat each machine computes the hidden unit activities of only J/K hidden units. It does this using
the green weights in Figure 4.1.
3. All the machines send the result of their computation in step 2 to each other.
4. Now knowing all the hidden unit activities, each machine computes its visible unit activities

0

k0

k0

k0

(negative data) Vk = [v0 , v1 , ..., vI/K ] using the purple weights in Figure 4.1.
5. All the machines send the result of their computation in step 4 to each other.
6. Now knowing all the negative data, each machine computes its hidden unit activities

k0
k0
[hk0
0 , h1 , ..., hJ/K ] using the green weights in Figure 4.1.

Hk0 =7. All the machines send the result of their computation in step 6 to each other.
Notice that since each hj is only 1 bit, the cost of communicating the hidden unit activities is verysmall. If the visible units are also binary, the cost of communicating the vi s is also small. This is why
the algorithm scales particularly well for binary-to-binary RBMs.
After step 3, each machine has enough data to compute < vi hj > for all the weights that it cares

0 0

about. After step 7, each machine has enough data to compute < vi hj > for all the weights that it cares
about. This is essentially all there is to it.
You'll notice that most weights are updated twice (but on dierent machines), because most weights
are known to two machines (in Figure 4.1 notice, for example, that some green weights on machine 1
are purple weights on machine 2). This is the price of parallelization. In fact, in our implementation,
we updated every weight twice, even the ones that are known to only one machine. This is a relatively
small amount of extra computation, and avoiding it would result in having to do two small matrix
multiplications instead of one large one.

37

Wary of oating point nastiness, you might also wonder: if each weight update is computed twice,can we be sure that the two computations arrive at exactly the same answer? When the visible units arebinary, we can. This is because the oating point operations constitute taking the product of the data
matrix with the matrix of hidden activities, both of which are binary (although they are likely to be storedas oating point). When the visible units are Gaussian, however, this really does present a problem.
Because we have no control over the matrix multiplication algorithm that our numerical package uses
to compute matrix products, and further because each weight may be stored in a dierent location of
the weight matrix on each machine (and the weight matrices may even have slightly dierent shapes
on dierent machines!), we cannot be sure that the sequence of oating point operations that computeweight update ∆wij on one machine will be exactly the same as that which compute it on a dierent
machine. This causes the values stored for these weights to diverge on the two machines and requiresthat we introduce a weight synchronization step to our algorithm. In practice, the divergence is verysmall even if all our calculations are done in single-precision oating point, so the weight synchronization
step need not execute very frequently. The weight synchronization step proceeds as follows:
1. Designate the purple weights (Figure 4.1) as the weights of the RBM and forget about the green
weights.
2. Each machine k sends to machine k0 the slice of its purple weights that machine k0 needs to know
in order to ll in its green weights.

1
K 2 th of the weight matrix to K −1 machines. Since K machines are
K−1
sending stu around, the total amount of communication does not exceed
K · (size of weight matrix).
Notice that each machine must sendThus the amount of communication required for weight synchronization is constant in the number ofmachines, which means that oating point does not manage to spoil the algorithm  the algorithm does
not require an inordinate amount of correction as the number of machines increases.
We've omitted biases from our discussion thus far; that is because they are only a minor nuisance.
The biases are divided into K chunks just like the weights. Each machine is responsible for updating
the visible biases corresponding to the visible units on the purple weights in Figure 4.1 and the hidden
biases corresponding to the hidden units on the green weights in Figure 4.1. Each bias is known to only
one machine, so its update only has to be computed once. Recall that the bias updates in CD-1 are

∆bvi
∆bhj
v

=  (< vi > − < vi0 >) ,=  < hj > − < h0j >hwhere bi denotes the bias of visible unit i and bj denotes the bias of hidden unit j . Clearly after step
1, each machine can compute < vi >. After step 2 it can compute < hj >. After step 4 it can compute< vi0 >. And after step 6 it can compute < h0j >.

4.3

Implementation

We implemented this algorithm as a C extension to a Python program.

The Python code initializes

the matrices, communication channels, and so forth. The C code does the actual computation. We use
whatever implementation of BLAS (Basic Linear Algebra Subprograms) is available to perform matrix
and vector operations.
We use TCP sockets to communicate between machines.

Our implementation is also capable of

distributing the work across multiple cores of the same machine, in the same manner as described above.
The only dierence is that communication between cores is done via shared memory instead of sockets.
We used the pthreads library to parallelize across cores.
We execute the weight synchronization step after training on each batch of 8000 images. This provedsucient to keep the weights synchronized to within 10−9

at single precision. Our implementation also

computes momentum and weight decay for all the weights.
When parallelizing across K machines, our implementation spawns K − 1 writer threads and K − 1
reader threads on each machine, in addition to the threads that do the actual computation (the worker
threads). The number of worker threads is a run-time variable, but it is most sensible to set it to thenumber of available cores on the machine.

38

4.3.1 Writer threads
Each writer thread is responsible for sending data to a particular other machine. Associated with eachwriter thread is a queue. The worker threads add items to these queues when they have nished their
computation. The writer threads dequeue these items and send them to their target machine. We haveseparated communication from computation in this way so that a machine that has everything it needs
to continue its computation does not need to delay performing it just because it still has to send somedata to another machine.

4.3.2 Reader threads
Each reader thread is responsible for receiving data from a particular other machine. The reader thread
reads data from its target machine as soon as it arrives. This setup ensures that no attempt to senddata ever blocks because the receiver is still computing. There is always a thread on the other side that's
ready to receive. Similarly, since the data is received as soon as it becomes available, no machine everhas to delay receiving data merely because it is still computing.

4.4

Results

We have tested our implementation of the algorithm on a relatively large problem  8000 visible units
and 20000 hidden units. The training data consisted of 8000 examples of random binary data (hopefully
no confusion arises from the fact that we have two dierent quantities whose value is 8000). We ran
these tests on machines with two dual-core Intel Xeon 3GHz CPUs. We used Intel's MKL (Math Kernel
Library) for matrix operations. These machines are memory bandwidth-limited so returns diminishedwhen we started running the fourth thread.
1 MB = 1000000 bytes.

We measured our network speed at 105 MB/s, where

We measured our network latency at 0.091ms.

Our network is such thatmultiple machines can communicate at the peak speed without slowing each other down.

In all our

experiments, the weight synchronization step took no more than four seconds to perform (two seconds
at single precision), and these times are included in all our gures.

The RBM we study here takes,

at best, several minutes per batch to train (see Figure 4.4), so the four-second synchronization step isimperceptible.
Figures 4.2 and 4.3 show the speedup factor when parallelizing across dierent numbers of machines
and threads.

2 Note that these gures do not show absolute speeds so no comparison between them (norbetween the subgures) is possible.

Figures 4.4 and 4.5 show the actual computation times of these

RBMs on 8000 training examples. Not surprisingly, double precision is slower than single precision andsmaller minibatch sizes are slower than larger ones. Single precision is much faster initially (nearly 3x)
but winds up about 2x faster after much parallelization.
There are a couple of other things worth noting.

For binary-to-binary RBMs, it is in some cases

better to parallelize across machines than across cores. This eect is impossible to nd with Gaussianto-binary RBMs, the cost of communication between machines making itself shown. The eect is also
harder to nd for binary-to-binary RBMs when the minibatch size is 100, following the intuition thatthe eciency of the algorithm will depend on how frequently the machines have to talk to each other.
The gures also make clear that the algorithm scales better when using double-precision oating point
as opposed to single-precision, although single-precision is still faster in all cases.
With binary visible units, the algorithm appears to scale rather linearly with the number of machines.
Figure 4.6 illustrates this vividly.It shows that doubling the number of machines very nearly doubles the3 This suggests that the cost of communication is negligible, even in the cases

performance in all cases.

when the minibatch size is 100 and the communication is hence rather fragmented. When the visible
units are Gaussian, the algorithm scales just slightly worse. Notice that when the minibatch size is 1000,

2 The numbers for one thread running on one machine were computed using a dierent version of the code  one that
did not incur all the overhead of parallelization. The numbers for multiple threads running on one machine were computed
using yet a third version of the code  one that did not incur the penalty of parallelizing across machines (i.e. having tocompute each weight update twice). When parallelizing merely across cores and not machines, there is a variant of thisalgorithm in which each weight only has to be updated once and only by one core, and all the other cores immediatelysee the new weight after it has been updated. This variant also reduces the number of sync points from three to two periteration.

3 The reason we didn't show the speedup factor when using two machines versus one machine on these graphs is thatthe one-machine numbers were computed using dierent code (explained in the previous footnote) and so they wouldn'toer a fair comparison.

39

(a)

(b)

(c)

(d)

Figure 4.2: Speedup due to parallelization for a binary-to-binary RBM (versus one thread running on
one machine). (a) Minibatch size 100, double precision oats, (b) minibatch size 1000, double precision
oats, (c) minibatch size 100, single precision oats, (d) minibatch size 1000, single precision oats.

40

(a)

(b)

(c)

(d)

Figure 4.3: Speedup due to parallelization for a Gaussian-to-binary RBM (versus one thread running on
one machine). (a) Minibatch size 100, double precision oats, (b) minibatch size 1000, double precision
oats, (c) minibatch size 100, single precision oats, (d) minibatch size 1000, single precision oats.

41

(a)

(b)

(c)

(d)

Figure 4.4: Time to train on 8000 examples of random binary data (binary-to-binary RBM). (a) Minibatch size 100, double precision oats, (b) minibatch size 1000, double precision oats, (c) minibatch
size 100, single precision oats, (d) minibatch size 1000, single precision oats.

42

(a)

(b)

(c)

(d)

Figure 4.5: Time to train on 8000 examples of random real-valued data (Gaussian-to-binary RBM). (a)Minibatch size 100, double precision oats, (b) minibatch size 1000, double precision oats, (c) minibatch
size 100, single precision oats, (d) minibatch size 1000, single precision oats.

43

(a)

(b)

(c)

(d)

Figure 4.6: This gure shows the speedup factor when parallelizing a binary-to-binary RBM across fourmachines versus two (blue squares) and eight machines versus four (red diamonds). Notice that doubling
the number of machines very nearly doubles the performance.

the algorithm scales almost as well in the Gaussian-to-binary case as in the binary-to-binary case. Whenthe minibatch size is 100, the binary-to-binary version scales better than the Gaussian-to-binary one.
Figure 4.7 shows that in the Gaussian-to-binary case doubling the number machines almost, but notquite, doubles performance.

4.4.1 Communication cost analysis
We can analyze the communication cost more formally. Given K machines, we can compute the amountof data transmitted per training batch of 8000 examples like this: in steps 3 and 7, each machine has tosend its hidden unit activities to all the other machines. Thus it has to send

2 · (K − 1) · 8000 ·

20000
bits.
K

In step 5 each machine has to send its visible unit activities to all the other machines. If the visible
units are binary, this is another(K − 1) · 8000 ·

8000
bits.
K

These sum to(K − 1) 3.84 × 108
K(K − 1)= 48 ·
MB .
K


bits

Thus the total amount of data sent (equivalently, received) by all machines is 48 · (K − 1) MB. In theGaussian-to-binary case, this number is appropriately larger depending on whether we're using single

44

(a)

(b)

(c)

(d)

Figure 4.7: This gure shows the speedup factor when parallelizing a Gaussian-to-binary RBM acrossfour machines versus two (blue squares) and eight machines versus four (red diamonds). Notice that
doubling the number of machines very nearly doubles the performance.

45

Number of machines:
Data sent (MB) (binary visibles):Data sent (MB) (Gaussian visibles, single precision):
Data sent (MB) (Gaussian visibles, double precision):

1

2

4

8

0

48

144

336

0

296

888

2072

0

552

1656

3864

Table 4.1: Total amount of data sent (equivalently, received) by the RBMs discussed in the text.

or double precision oats. In either case, the cost of communication rises linearly with the number ofmachines. Table 4.1 shows how much data was transferred by the RBMs that we trained (not including
weight synchronization, which is very quick).

Note that the cost of communication per machine isbounded from above by a constant (48MB in this case).

So if machines can communicate with eachother without slowing down the communication of other machines, the communication cost essentiallydoes not increase with the number of machines.
It looks as though we have not yet reached the point at which the benet of parallelization is
outweighed by the cost of communication for this large problem.

But when we used this algorithm

to train an RBM on binarized MNIST digits (784 visible units, 392 hidden units), the benets ofparallelization disappeared after we added the second machine. But at that point it was already taking
only a few seconds per batch.

4.5

Other algorithms

We'll briey discuss a few other algorithms that could be used to parallelize RBM training.

All ofthese algorithms require a substantial amount of inter-machine communication, so they are not ideal forbinary-to-binary RBMs. But for some problems, some of these algorithms require less communicationin the Gaussian-to-binary case than does the algorithm we have presented.
There is a variant of the algorithm that we have presented that performs the weight synchronization
step after each weight update.

Due to the frequent weight synchronization, it has the benet of nothaving to compute each weight update twice, thereby saving itself some computation. It has a second
benet of not having to communicate the hidden unit activities twice. Still, it will perform poorly inmost cases due to the large amount of communication required for the weight synchronization step. But
if the minibatch size is suciently large it will outperform the algorithm presented here.

Assuming

single-precision oats, this variant requires less communication than the algorithm presented here when
the following holds:

mhK+ 4mvK ≥ 4vh
8
where m is the minibatch size, v is the number of visible units, h is the number of hidden units, and K
is the number of machines. Notice that the right-hand side is just a multiple of the size of the weightmatrix. So, broadly speaking, the variant requires less communication when the weight matrix is small
compared to the left-hand side. Just to get an idea for what this means, in the problem that we have been
considering (v = 8000, h = 20000), with K = 8 machines the variant would require less communication
than the algorithm we presented when the minibatch size is greater than 1538. Notice, however, thatmerely adding machines pushes the inequality in a direction favourable to the variant, so it may start
to look more attractive depending on the problem and number of machines.
Another variant of the algorithm presented here is suitable for training RBMs in which there arefewer hidden units than visible units.

In this variant, each machine only knows 1/K th of the data(the data is partitioned by dimensions, as before), where K is the number of machines. The algorithm
proceeds as follows:
1. Knowing only some of the data, no machine can compute the hidden unit activity of any hidden
unit. So instead each machine computes the hidden unit inputs to all the hidden units due to its

1/K th of the data. It does this with the purple weights of Figure 4.1.
2. Each machine sends to each other machine the 1/K th of the inputs that the receiver cares about.
3. Once all the machines have all the inputs they need to compute their respective hidden unit
activities, they all send these activities to each other. These are binary values so this step is cheap.

46

4. Each machine computes 1/K th of the negative data given all the hidden unit activities, again using
the purple weights.
5. The machines cooperate to compute the hidden unit activities due to the negative data, as in steps
1-4.
This algorithm trades communicating data for communicating hidden unit inputs. Roughly speaking, if
the number of hidden units is less than half of the number of visible units, this is a win. Notice that inthis variant, each machine only needs to know the purple weights (Figure 4.1). This means that eachweight is only stored on one machine, so its update needs to be computed only once. This algorithm also
avoids the weight divergence problem due to oating point imprecision that we have discussed above.
One can also imagine a similar algorithm for the case when there are more hidden units than visible
units. In this algorithm, each machine will know all the data but it will only know the green weights
of Figure 4.1. Thus no machine alone will be able to compute the data reconstruction, but they will
cooperate by sending each other visible unit inputs.

4

A third, naive algorithm for distributing RBM training would simply have the dierent machines
train on dierent (mini-)minibatches, and then send their weight updates to some designated main
machine. This machine would then average the weight updates and send out the new weight matrix to
all the other machines. It does not take much calculation to see that this algorithm would be incredibly
slow. The weight matrix would have to be sent 2(K − 1) times for every minibatch.

4 We have actually tested this algorithm on the 8000 visible / 20000 hidden problem, and it turned out to be about 30%
faster than the algorithm presented here, even though in this problem there are more hidden units than visible units. It
appears that the cost of communication is not that great in our situation. This is the version of the algorithm that weused for training our RBMs.

47

Appendix A

The ZCA whitening transformation
We can store n d-dimensional data points in the columns of a d × n matrix X . Assuming the data points
have zero mean, their covariance matrix is given by

1
XX T .
n−1
We wish to decorrelate the data dimensions from one another. We can do this with a linear transformation W , which will transform the data matrix X as follows:

Y = W X.
In order for W to be a decorrelating matrix, Y Y

Tmust be diagonal. However, we can restrict our search

only to W s that satisfy

Y Y T = (n − 1)I.
In other words, W s that make the covariance matrix of the transformed data matrix equal to the identity.
There are multiple W s that t this description, so we can restrict our search further by requiring

W = WT.
Given these restrictions, we can nd W :YYT=(n − 1)IT

T=(n − 1)IW T W XX T W T=(n − 1)W T

W 2 XX T W T=(n − 1)W T

W 2 XX T=(n − 1)I

2=

W XX WW(n − 1)(XX T )−1√1
n − 1(XX T )− 2 .
=W(XX T )

− 12

is easily found because XXTis symmetric and hence orthogonally diagonalizable. That is,

XX T = P DP T
for some orthogonal matrix P and diagonal matrix D . So
1

(XX T )− 2

−1  12

=



XX T

=



P DP T=P D−1 P T

−1  12
 12

1

= P D− 2 P T
where D

− 12

(A.1)

1
2

is just D with all the elements taken to the power − .

48

1= (XX T )− 2 transforms X in such a way that the resultant data dimensions are uncorrelatedwith one another and the variance in each dimension is exactly 1. W may also be thought of as rotating
X to the space of its principal components, dividing each principal component by the square root of thevariance in that direction, and then rotating back to pixel space. W is called a whitening matrix, and isSo, Wreferred to as the Zero Components Analysis (ZCA) solution to the equation

Y Y T = diagonal.
The dewhitening matrix, W−1, is given by1

W −1 = P D 2 P T .

49

Appendix B

Feed-forward neural networks
A feed-forward neural network with one hidden layer is shown in Figure B.1. Neuron k in layer l receives
as input the value

Nl−1

xlk = blk +X

l−1 l−1
wik
yi

i=1
where

• blk is the bias into neuron k in layer l,• Nl−1 is the number of neurons in layer l − 1,
l−1
• wik
is the weight between unit i in layer l − 1 and unit k in layer l, and• yil−1 is the output of unit i in layer l − 1.
The neuron then computes its output

ykl = f (xlk )where f is any dierentiable function of the neuron's total input. The neurons in the data layer justoutput the data. Finally, we come up with some function

L
E(y1L , . . . , yN)
Lof the output that we would like the neural net to maximize (this can be seen as just another layer on topof the output layer), where L is the number of layers in the neural network.
so

E should be dierentiable∂E
L is readily computable.
∂yk

Figure B.1: A feed-forward neural network with one hidden layer.

50

Training the network consists of clamping the data neurons at the data and updating the parameters(the weights and biases) in the direction of the gradient. The derivatives can be computed as follows:

∂E
l−1
∂wik
∂E
∂blk
∂E
∂xlk
∂E
∂ykl

=
=

∂E l−1y∂xlk i∂E∂xlk∂E ∂ykl∂y l ∂xl
k k
 ∂EL
∂y
Pk l+1
=
 N
i=1

=

if l = L

∂E
l
wki
∂xl+1
i

otherwise.

∂E
L is assumed to be readily computable and from this all the other derivatives can be computed,∂yk
working down from the top layer. This is called the backpropagation algorithm.

51

Appendix C

Labeler instruction sheet
Criteria for deciding whether to include an image
1. The main test is: Would you be quite likely to say the category name if asked to give a single basic
category to describe the main object in the image?
2. It's worse to include one that shouldn't be included than to exclude one. False positives are worse
than false negatives.
3. If there is more than one object that is roughly equally prominent, reject even if they are all of
the right class.
INCLUDEEXCLUDE

4. If it is a line drawing or cartoon, reject. You can accept fairly photorealistic drawings that haveinternal texture.
INCLUDEEXCLUDE

5. Do not reject just because the viewpoint is unusual or the object is partially occluded (provided
you think you might have assigned the right label without priming). We want ones with unusual
viewpoints.
INCLUDEEXCLUDE

6. Do not reject just because the background is cluttered. We want some cluttered backgrounds. But
also, do not reject just because the background is uniform.

52

7. Do not worry too much about accepting duplicates or near duplicates. If you are pretty sure it's aduplicate, reject it. But we will eliminate any remaining duplicates later, so including duplicatesis not a bad error.
8. If a category has two meanings (like mouse), only include the main meaning.
about what this is, then ask.

53

If there is doubtAppendix D

CIFAR-100 class structure
Following is the class and superclass structure of the CIFAR-100 dataset. Each superclass contains veclasses. Where the name of the class is plural, the labelers were instructed not to reject images in which
multiple instances of the object appear.
1. aquatic mammals• beaver• dolphin• otter• seal• whale2. sh• atsh• ordinary sh (excluding trout and atsh and salmon)• ray• shark• trout
3. owers• orchids• poppies• rose• sunowers• tulips
4. food containers• bottles• bowls• cans• cups, mugs, glasses• plates
5. fruit and vegetables• apples• mushrooms54• oranges• pears• sweet peppers
6. household electrical devices• clock• computer keyboard• lamp• telephone• television
7. household furniture• bed• chair• couch• table• wardrobe
8. insects• bee• beetle• buttery• caterpillar• cockroach
9. large carnivores• bear• leopard• lion• tiger• wolf
10. large man-made outdoor things• bridge• castle• house• road• skyscraper
11. large natural outdoor scenes• cloud• forest• mountain• plain• sea
12. large omnivores/herbivores55• camel• cattle• chimpanzee• elephant• kangaroo
13. mid-size mammals• fox• porcupine• possum• raccoon• skunk
14. non-insect invertebrates• crab• lobster• snail• spider• worm
15. people• baby• boy• girl• man• woman
16. reptiles• crocodile• dinosaur• lizard• snake• turtle
17. small mammals• hamster• mouse• rabbit• shrew• squirrel
18. trees• maple• oak• palm• pine56

• willow
19. vehicles 1• bicycle• bus• motorcycle• pickup truck• train20. vehicles 2• lawn-mower• rocket• streetcar• tank• tractor

57

Bibliography[1] Bell, A. J., Sejnowski, T. J., 1997, The independent components of natural scenes are edge lters[2] Bengio, Y., Lamblin, P., Popovici, D., Larochelle, H., 2006, Greedy Layer-Wise Training of Deep

Networks[3] Fergus, R., personal communication[4]

Freund, Y., Haussler, D., 1992, Unsupervised learning of distributions on binary vectors using twolayer networks[5] Hinton, G. E., 2002, Training Products of Experts by Minimizing Contrastive Divergence[6] Hinton, G. E., Salakhutdinov, R. R., 2006, Reducing the dimensionality of data with neural networks[7] Le Roux, N., 2009, personal communication[8] Miller, G. A., 1995, WordNet: a lexical database for English[9] Salakhutdinov, R., Murray, I., 2008, On the Quantitative Analysis of Deep Belief Networks[10] Serre, T., Wolf, L., Bileschi, S., Riesenhuber, M., Poggio, T., 2007, Robust Object Recognition with

Cortex-Like Mechanisms[11] Smolensky, P., 1986, Information processing in dynamical systems: Foundations of harmony theory[12] Teh, Y., Hinton, G. E., 2001, Rate-coded Restricted Boltzmann Machines for Face Recognition[13] Tieleman, T., 2008, Training Restricted Boltzmann Machines using Approximations to the Likeli-

hood Gradient[14] Torralba, A., Fergus, R., Freeman, W. T., 2008, 80 million tiny images: a large dataset for non-parametric object and scene recognition[15] WordNet can be found at http://wordnet.princeton.edu/

58