Knowledge Matters: Importance of Prior Information for Optimization
Authors: Çağlar Gülçehre, Yoshua Bengio
ICLR 2013

Abstract: We explore the effect of introducing prior information into the intermediate level of neural networks for a learning task on which all the state-of-the-art machine learning algorithms tested failed to learn. We motivate our work from the hypothesis that humans learn such intermediate concepts from other individuals via a form of supervision or guidance using a curriculum. The experiments we have conducted provide positive evidence in favor of this hypothesis. In our experiments, a two-tiered MLP architecture is trained on a dataset with 64x64 binary inputs images, each image with three sprites. The final task is to decide whether all the sprites are the same or one of them is different. Sprites are pentomino tetris shapes and they are placed in an image with different locations using scaling and rotation transformations. The first part of the two-tiered MLP is pre-trained with intermediate-level targets being the presence of sprites at each location, while the second part takes the output of the first part as input and predicts the final task's target binary event. The two-tiered MLP architecture, with a few tens of thousand examples, was able to learn the task perfectly, whereas all other algorithms (include unsupervised pre-training, but also traditional algorithms like SVMs, decision trees and boosting) all perform no better than chance. We hypothesize that the optimization difficulty involved when the intermediate pre-training is not performed is due to the {em composition} of two highly non-linear tasks. Our findings are also consistent with hypotheses on cultural learning inspired by the observations of optimization problems with deep learning, presumably because of effective local minima.

Knowledge Matters: Importance of Prior Information for
Optimization
C ¸ a˘ glar G¨ ul¸ cehre gulcehrc@iro.umontreal.ca
D´ epartement d’informatique et de recherche op´ erationnelle
Universit´ e de Montr´ eal, Montr´ eal, QC, Canada
Yoshua Bengio bengioy@iro.umontreal.ca
D´ epartement d’informatique et de recherche op´ erationnelle
Universit´ e de Montr´ eal, Montr´ eal, QC, Canada
Editor: Not Assigned
Abstract
We explore the eﬀect of introducing prior information into the intermediate level of deep
supervised neural networks for a learning task on which all the black-box state-of-the-art ma-
chine learning algorithms tested have failed to learn. We motivate our work from the hypothesis
that there is an optimization obstacle involved in the nature of such tasks, and that humans
learn useful intermediate concepts from other individuals via a form of supervision or guidance
using a curriculum. The experiments we have conducted provide positive evidence in favor of
this hypothesis. In our experiments, a two-tiered MLP architecture is trained on a dataset for
which each image input contains three sprites, and the binary target class is 1 if all three have
the same shape. Black-box machine learning algorithms only got chance on this task. Standard
deep supervised neural networks also failed. However, using a particular structure and guiding
the learner by providing intermediate targets in the form of intermediate concepts (the pres-
ence of each object) allows to nail the task. Much better than chance but imperfect results are
also obtained by exploring architecture and optimization variants, pointing towards a diﬃcult
optimization task. We hypothesize that the learning diﬃculty is due to the composition of two
highly non-linear tasks. Our ﬁndings are also consistent with hypotheses on cultural learning
inspired by the observations of eﬀective local minima (possibly due to ill-conditioning and the
training procedure not being able to escape what appears like a local minimum).
Keywords: Deep Learning, Neural Networks, Optimization, Evolution of Culture, Curricu-
lum Learning, Training with Hints
1. Introduction
There is a recent emerging interest in diﬀerent ﬁelds of science for cultural learning (Henrich
and McElreath, 2003) and how groups of individuals exchanging information can learn in ways
superior to individual learning. This is also witnessed by the emergence of new research ﬁelds
such as ”Social Neuroscience”. Learning from other agents in an environment by the means
of cultural transmission of knowledge with a peer-to-peer communication is an eﬃcient and
natural way of acquiring or propagating common knowledge. The most popular belief on how
the information is transmitted between individuals is that bits of information are transmitted
by small units, called memes, which share some characteristics of genes, such as self-replication,
mutation and response to selective pressures (Dawkins, 1976).
1
arXiv:1301.4083v6  [cs.LG]  13 Jul 2013
This paper is based on the hypothesis (which is further elaborated in Bengio (2013a)) that
human culture and the evolution of ideas have been crucial to counter an optimization issue:
this diﬃculty would otherwise make it diﬃcult for human brains to capture high level knowl-
edge of the world without the help of other educated humans. In this paper machine learning
experiments are used to investigate some elements of this hypothesis by seeking answers for
the following questions: are there machine learning tasks which are intrinsically hard for a
lone learning agent but that may become very easy when intermediate concepts are provided
by another agent as additional intermediate learning cues, in the spirit of Curriculum Learn-
ing (Bengio et al., 2009b)? What makes such learning tasks more diﬃcult? Can speciﬁc initial
values of the neural network parameters yield success when random initialization yield com-
plete failure? Is it possible to verify that the problem being faced is an optimization problem or
with a regularization problem? These are the questions discussed (if not completely addressed)
here, which relate to the following broader question: how can humans (and potentially one day,
machines) learn complex concepts?
In this paper, results of diﬀerent machine learning algorithms on an artiﬁcial learning task
involving binary 64×64 images are presented. In that task, each image in the dataset contains
3 Pentomino tetris sprites (simple shapes). The task is to ﬁgure out if all the sprites in the
image are the same or if there are diﬀerent sprite shapes in the image. Several state-of-the-art
machine learning algorithms have been tested and none of them could perform better than
a random predictor on the test set. Nevertheless by providing hints about the intermediate
concepts (the presence and location of particular sprite classes), the problem can easily be solved
where the same-architecture neural network without the intermediate concepts guidance fails.
Surprisingly, our attempts at solving this problem with unsupervised pre-training algorithms
failed solve this problem. However, with speciﬁc variations in the network architecture or
training procedure, it is found that one can make a big dent in the problem. For showing the
impact of intermediate level guidance, we experimented with a two-tiered neural network, with
supervised pre-training of the ﬁrst part to recognize the category of sprites independently of
their orientation and scale, at diﬀerent locations, while the second part learns from the output
of the ﬁrst part and predicts the binary task of interest.
The objective of this paper is not to propose a novel learning algorithm or architecture,
but rather to reﬁne our understanding of the learning diﬃculties involved with composed tasks
(here a logical formula composed with the detection of object classes), in particular the training
diﬃculties involved for deep neural networks. The results also bring empirical evidence in favor
of some of the hypotheses from Bengio (2013a), discussed below, as well as introducing a
particular form of curriculum learning (Bengio et al., 2009b).
Building diﬃcult AI problems has a long history in computer science. Speciﬁcally hard
AI problems have been studied to create CAPTCHA’s that are easy to solve for humans, but
hard to solve for machines (Von Ahn et al., 2003). In this paper we are investigating a diﬃcult
problem for the oﬀ-the-shelf black-box machine learning algorithms. 1
1.1 Curriculum Learning and Cultural Evolution Against Eﬀective Local Minima
What Bengio (2013a) calls an eﬀective local minimum is a point where iterative training
stalls, either because of an actual local minimum or because the optimization algorithm is
1. You can access the source code of some experiments presented in that paper and their hyperparameters from
here: https://github.com/caglar/kmatters
2
unable (in reasonable time) to ﬁnd a descent path (e.g., because of serious ill-conditioning). In
this paper, it is hypothesized that some more abstract learning tasks such as those obtained
by composing simpler tasks are more likely to yield eﬀective local minima for neural networks,
and are generally hard for general-purpose machine learning algorithms.
The idea that learning can be enhanced by guiding the learner through intermediate easier
tasks is old, starting with animal training by shaping (Skinner, 1958; Peterson, 2004; Krueger
and Dayan, 2009). Bengio et al. (2009b) introduce a computational hypothesis related to a
presumed issue with eﬀective local minima when directly learning the target task: the good
solutions correspond to hard-to-ﬁnd-by-chance eﬀective local minima, and intermediate tasks
prepare the learner’s internal conﬁguration (parameters) in a way similar to continuation meth-
ods in global optimization (which go through a sequence of intermediate optimization problems,
starting with a convex one where local minima are no issue, and gradually morphing into the
target task of interest).
In a related vein, Bengio (2013a) makes the following inferences based on experimental
observations of deep learning and neural network learning:
Point 1: Training deep architectures is easier when some hints are given about the function
that the intermediate levels should compute (Hinton et al., 2006; Weston et al., 2008;
Salakhutdinov and Hinton, 2009; Bengio, 2009). The experiments performed here expand
in particular on this point.
Point 2: It is much easier to train a neural network with supervision (where examples ar
provided to it of when a concept is present and when it is not present in a variety of
examples) than to expect unsupervised learning to discover the concept (which may also
happen but usually leads to poorer renditions of the concept). The poor results obtained
with unsupervised pre-training reinforce that hypothesis.
Point 3: Directly training all the layers of a deep network together not only makes it diﬃcult to
exploit all the extra modeling power of a deeper architecture but in many cases it actually
yields worse results as the number of required layers is increased (Larochelle et al., 2009;
Erhan et al., 2010). The experiments performed here also reinforce that hypothesis.
Point 4: Erhan et al. (2010) observed that no two training trajectories ended up in the
same eﬀective local minimum, out of hundreds of runs, even when comparing solutions as
functions from input to output, rather than in parameter space (thus eliminating from the
picture the presence of symmetries and multiple local minima due to relabeling and other
reparametrizations). This suggests that the number of diﬀerent eﬀective local minima
(even when considering them only in function space) must be huge.
Point 5: Unsupervised pre-training, which changes the initial conditions of the descent pro-
cedure, sometimes allows to reach substantially better eﬀective local minima (in terms
of generalization error!), and these better local minima do not appear to be reachable
by chance alone (Erhan et al., 2010). The experiments performed here provide another
piece of evidence in favor of the hypothesis that where random initialization can yield
rather poor results, speciﬁcally targeted initialization can have a drastic impact, i.e., that
3
eﬀective local minima are not just numerous but that some small subset of them are much
better and hard to reach by chance. 2
Based on the above points, Bengio (2013a) then proposed the following hypotheses regarding
learning of high-level abstractions.
•Optimization Hypothesis: When it learns, a biological agent performs an approximate
optimization with respect to some implicit objective function.
•Deep Abstractions Hypothesis: Higher level abstractions represented in brains re-
quire deeper computations (involving the composition of more non-linearities).
•Local Descent Hypothesis: The brain of a biological agent relies on approximate local
descent and gradually improves itself while learning.
•Eﬀective Local Minima Hypothesis: The learning process of a single human learner
(not helped by others) is limited by eﬀective local minima.
•Deeper Harder Hypothesis: Eﬀective local minima are more likely to hamper learning
as the required depth of the architecture increases.
•Abstractions Harder Hypothesis: High-level abstractions are unlikely to be discov-
ered by a single human learner by chance, because these abstractions are represented by
a deep subnetwork of the brain, which learns by local descent.
•Guided Learning Hypothesis: A human brain can learn high level abstractions if
guided by the signals produced by other agents that act as hints or indirect supervision
for these high-level abstractions.
•Memes Divide-and-Conquer Hypothesis: Linguistic exchange, individual learning
and the recombination of memes constitute an eﬃcient evolutionary recombination oper-
ator in the meme-space. This helps human learners to collectively build better internal
representations of their environment, including fairly high-level abstractions.
This paper is focused on “ Point 1 ” and testing the “ Guided Learning Hypothesis ”, using
machine learning algorithms to provide experimental evidence. The experiments performed
also provide evidence in favor of the “Deeper Harder Hypothesis” and associated “Abstractions
Harder Hypothesis”. Machine Learning is still far beyond the current capabilities of humans,
and it is important to tackle the remaining obstacles to approach AI. For this purpose, the
question to be answered is why tasks that humans learn eﬀortlessly from very few examples,
while machine learning algorithms fail miserably?
2. Recent work showed that rather deep feedforward networks can be very successfully trained when large
quantities of labeled data are available (Ciresan et al., 2010; Glorot et al., 2011a; Krizhevsky et al., 2012).
Nonetheless, the experiments reported here suggest that it all depends on the task being considered, since
even with very large quantities of labeled examples, the deep networks trained here were unsuccessful.
4
2. Culture and Optimization Diﬃculty
As hypothesized in the “ Local Descent Hypothesis ”, human brains would rely on a local ap-
proximate descent, just like a Multi-Layer Perceptron trained by a gradient-based iterative op-
timization. The main argument in favor of this hypothesis relies on the biologically-grounded
assumption that although ﬁring patterns in the brain change rapidly, synaptic strengths un-
derlying these neural activities change only gradually, making sure that behaviors are generally
consistent across time. If a learning algorithm is based on a form of local (e.g. gradient-based)
descent, it can be sensitive to eﬀective local minima (Bengio, 2013a).
When one trains a neural network, at some point in the training phase the evaluation of
error seems to saturate, even if new examples are introduced. In particular Erhan et al. (2010)
ﬁnd that early examples have a much larger weight in the ﬁnal solution. It looks like the learner
is stuck in or near a local minimum. But since it is diﬃcult to verify if this is near a true local
minimum or simply an eﬀect of strong ill-conditioning, we call such a “stuck” conﬁguration an
eﬀective local minimum , whose deﬁnition depends not just on the optimization objective but
also on the limitations of the optimization algorithm.
Erhan et al. (2010) highlighted both the issue of eﬀective local minima and a regulariza-
tion eﬀect when initializing a deep network with unsupervised pre-training. Interestingly, as
the network gets deeper the diﬃculty due to eﬀective local minima seems to be get more pro-
nounced. That might be because of the number of eﬀective local minima increases (more like
an actual local minima issue), or maybe because the good ones are harder to reach (more like
an ill-conditioning issue) and more work will be needed to clarify this question.
As a result of Point 4 we hypothesize that it is very diﬃcult for an individual’s brain to
discover some higher level abstractions by chance only. As mentioned in the “ Guided Learning
Hypothesis” humans get hints from other humans and learn high-level concepts with the guid-
ance of other humans 3. Curriculum learning (Bengio et al., 2009a) and incremental learning
(Solomonoﬀ, 1989), are examples of this. This is done by properly choosing the sequence of
examples seen by the learner, where simpler examples are introduced ﬁrst and more complex
examples shown when the learner is ready for them. One of the hypothesis on why curriculum
works states that curriculum learning acts as a continuation method that allows one to discover
a good minimum, by ﬁrst ﬁnding a good minimum of a smoother error function. Recent ex-
periments on human subjects also indicates that humans teach by using a curriculum strategy
(Khan et al., 2011).
Some parts of the human brain are known to have a hierarchical organization (i.e. visual
cortex) consistent with the deep architecture studied in machine learning papers. As we go from
the sensory level to higher levels of the visual cortex, we ﬁnd higher level areas corresponding
to more abstract concepts. This is consistent with the Deep Abstractions Hypothesis.
Training neural networks and machine learning algorithms by decomposing the learning
task into sub-tasks and exploiting prior information about the task is well-established and
in fact constitutes the main approach to solving industrial problems with machine learning.
The contribution of this paper is rather on rendering explicit the eﬀective local minima issue
and providing evidence on the type of problems for which this diﬃculty arises. This prior
information and hints given to the learner can be viewed as inductive bias for a particular task,
an important ingredient to obtain a good generalization error (Mitchell, 1980). An interesting
3. But some high-level concepts may also be hardwired in the brain, as assumed in the universal grammar
hypothesis (Montague, 1970), or in nature vs nurture discussions in cognitive science.
5
earlier ﬁnding in that line of research was done with Explanation Based Neural Networks
(EBNN) in which a neural network transfers knowledge across multiple learning tasks. An
EBNN uses previously learned domain knowledge as an initialization or search bias (i.e. to
constrain the learner in the parameter space) (O’Sullivan, 1996; Mitchell and Thrun, 1993).
Another related work in machine learning is mainly focused on reinforcement learning al-
gorithms, based on incorporating prior knowledge in terms of logical rules to the learning
algorithm as a prior knowledge to speed up and bias learning (Kunapuli et al., 2010; Towell
and Shavlik, 1994).
As discussed in “ Memes Divide and Conquer Hypothesis “ societies can be viewed as a
distributed computational processing systems. In civilized societies knowledge is distributed
across diﬀerent individuals, this yields a space eﬃciency. Moreover computation, i.e. each
individual can specialize on a particular task/topic, is also divided across the individuals in the
society and hence this will yield a computational eﬃciency. Considering the limitations of the
human brain, the whole processing can not be done just by a single agent in an eﬃcient manner.
A recent study in paleoantropology states that there is a substantial decline in endocranial
volume of the brain in the last 30000 years Henneberg (1988). The volume of the brain shrunk
to 1241 ml from 1502 ml (Henneberg and Steyn, 1993). One of the hypothesis on the reduction
of the volume of skull claims that, decline in the volume of the brain might be related to the
functional changes in brain that arose as a result of cultural development and emergence of
societies given that this time period overlaps with the transition from hunter-gatherer lifestyle
to agricultural societies.
3. Experimental Setup
Some tasks, which seem reasonably easy for humans to learn4, are nonetheless appearing almost
impossible to learn for current generic state-of-art machine learning algorithms.
Here we study more closely such a task, which becomes learnable if one provides hints to
the learner about appropriate intermediate concepts. Interestingly, the task we used in our
experiments is not only hard for deep neural networks but also for non-parametric machine
learning algorithms such as SVM’s, boosting and decision trees.
The result of the experiments for varying size of dataset with several oﬀ-the-shelf black box
machine learning algorithms and some popular deep learning algorithms are provided in Table
1. The detailed explanations about the algorithms and the hyperparameters used for those
algorithms are given in the Appendix Section 5.2. We also provide some explanations about
the methodologies conducted for the experiments at Section 3.2.
3.1 Pentomino Dataset
In order to test our hypothesis, an artiﬁcial dataset for object recognition using 64 ×64 binary
images is designed 5. If the task is two tiered (i.e., with guidance provided), the task in the
ﬁrst part is to recognize and locate each Pentomino object class 6 in the image. The second
4. keeping in mind that humans can exploit prior knowledge, either from previous learning or innate knowledge.
5. The source code for the script that generates the artiﬁcial Pentomino datasets (Arcade-Universe) is available
at: https://github.com/caglar/Arcade-Universe. This implementation is based on Olivier Breuleux’s
bugland dataset generator.
6. A human learner does not seem to need to be taught the shape categories of each Pentomino sprite in order
to solve the task. On the other hand, humans have lots of previously learned knowledge about the notion of
shape and how central it is in deﬁning categories.
6
(a) sprites, not all same type
 (b) sprites, all of same type
Figure 1: Left (a): An example image from the dataset which has a diﬀerent sprite type in it.
Right (b): An example image from the dataset that has only one type of Pentomino
object in it, but with diﬀerent orientations and scales.
part/ﬁnal binary classiﬁcation task is to ﬁgure out if all the Pentominos in the image are of
the same shape class or not. If a neural network learned to detect the categories of each object
at each location in an image, the remaining task becomes an XOR-like operation between the
detected object categories. The types of Pentomino objects that is used for generating the
dataset are as follows:
Pentomino sprites N, P, F, Y, J, and Q, along with the Pentomino N2 sprite (mirror of
“Pentomino N” sprite), the Pentomino F2 sprite (mirror of “Pentomino F” sprite), and the
Pentomino Y2 sprite (mirror of “Pentomino Y” sprite).
Figure 2: Diﬀerent classes of Pentomino shapes used in our dataset.
As shown in Figures 1(a) and 1(b), the synthesized images are fairly simple and do not
have any texture. Foreground pixels are “1” and background pixels are “0”. Images of the
training and test sets are generated iid. For notational convenience, assume that the domain
of raw input images is X, the set of sprites is S, the set of intermediate object categories is Y
for each possible location in the image and the set of ﬁnal binary task outcomes is Z = {0,1}.
Two diﬀerent types of rigid body transformation is performed: sprite rotation rot(X,γ) where
Γ = {γ: (γ = 90 ×φ) ∧[(φ∈N),(0 ≤φ≤3)]}and scaling scale(X,α) where α∈{1,2}is the
scaling factor. The data generating procedure is summarized below.
Sprite transformations: Before placing the sprites in an empty image, for each image x∈X,
a value for z ∈Z is randomly sampled which is to have (or not) the same three sprite
shapes in the image. Conditioned on the constraint given by z, three sprites are randomly
7
selected sij from S without replacement. Using a uniform probability distribution over
all possible scales, a scale is chosen and accordingly each sprite image is scaled. Then
rotate each sprite is randomly rotated by a multiple of 90 degrees.
Sprite placement: Upon completion of sprite transformations, a 64 ×64 uniform grid is gener-
ated which is divided into 8×8 blocks, each block being of size 8 ×8 pixels, and randomly
select three diﬀerent blocks from the 64=8 ×8 on the grid and place the transformed
objects into diﬀerent blocks (so they cannot overlap, by construction).
Each sprite is centered in the block in which it is located. Thus there is no object translation
inside the blocks. The only translation invariance is due to the location of the block inside the
image.
A Pentomino sprite is guaranteed to not overﬂow the block in which it is located, and there
are no collisions or overlaps between sprites, making the task simpler. The largest possible
Pentomino sprite can be ﬁt into an 8 ×4 mask.
3.2 Learning Algorithms Evaluated
Initially the models are cross-validated by using 5-fold cross-validation. With 40,000 examples,
this gives 32,000 examples for training and 8,000 examples for testing. For neural network
algorithms, stochastic gradient descent (SGD) is used for training. The following standard
learning algorithms were ﬁrst evaluated: decision trees, SVMs with Gaussian kernel, ordinary
fully-connected Multi-Layer Perceptrons, Random Forests, k-Nearest Neighbors, Convolutional
Neural Networks, and Stacked Denoising Auto-Encoders with supervised ﬁne-tuning. More
details of the conﬁgurations and hyper-parameters for each of them are given in Appendix
Section 5.2. The only better than chance results were obtained with variations of the Structured
Multi-Layer Perceptron described below.
3.2.1 Structured Multi-Layer Perceptron (SMLP)
The neural network architecture that is used to solve this task is called the SMLP (Structured
Multi-Layer Perceptron), a deep neural network with two parts as illustrated in Figure 5 and
7:
The lower part, P1NN ( Part 1 Neural Network , as it is called in the rest of the paper),
has shared weights and local connectivity, with one identical MLP instance of the P1NN for
each patch of the image, and typically an 11-element output vector per patch (unless otherwise
noted). The idea is that these 11 outputs per patch could represent the detection of the sprite
shape category (or the absence of sprite in the patch). The upper part, P2NN ( Part 2 Neural
Network) is a fully connected one hidden layer MLP that takes the concatenation of the outputs
of all patch-wise P1NNs as input. Note that the ﬁrst layer of P1NN is similar to a convolutional
layer but where the stride equals the kernel size, so that windows do not overlap, i.e., P1NN can
be decomposed into separate networks sharing the same parameters but applied on diﬀerent
patches of the input image, so that each network can actually be trained patch-wise in the case
where a target is provided for the P1NN outputs. The P1NN output for patch pi which is
extracted from the image x is computed as follows:
fθ(pi) = g2(Vg1(Upi + b) + c) (1)
8
where pi ∈Rd is the input patch/receptive ﬁeld extracted from location iof a single image.
U ∈Rdh×d is the weight matrix for the ﬁrst layer of P1NN and b ∈Rd
h is the vector of biases
for the ﬁrst layer of P1NN. g1(·) is the activation function of the ﬁrst layer and g2(·) is the
activation function of the second layer. In many of the experiments, best results were obtained
with g1(·) a rectifying non-linearity (a.k.a. as RELU), which is max(0, X) (Jarrett et al.,
2009b; Nair and Hinton, 2010; Glorot et al., 2011a; Krizhevsky et al., 2012). V ∈Rdh×do is the
second layer’s weights matrix, such that and c ∈Rdo are the biases of the second layer of the
P1NN, with do expected to be smaller than dh.
In this way, g1(Upi + b) is an overcomplete representation of the input patch that can
potentially represent all the possible Pentomino shapes for all factors of variations in the patch
(rotation, scaling and Pentomino shape type). On the other hand, when trained with hints,
fθ(pi) is expected to be the lower dimensional representation of a Pentomino shape category
invariant to scaling and rotation in the given patch.
In the experiments with SMLP trained with hints (targets at the output of P1NN), the
P1NN is expected to perform classiﬁcation of each 8 ×8 non-overlapping patches of the original
64×64 input image without having any prior knowledge of whether that speciﬁc patch contains
a Pentomino shape or not. P1NN in SMLP without hints just outputs the local activations for
each patch, and gradients on fθ(pi) are backpropagated from the upper layers. In both cases
P1NN produces the input representation for the Part 2 Neural Net (P2NN). Thus the input
representation of P2NN is the concatenated output of P1NN across all the 64 patch locations:
ho = [fθ(p0),...,f θ(pi),...,f θ(pN))] where N is the number of patches and theho ∈Rdi ,di =
do ×N. ho is the concatenated output of the P1NN at each patch.
There is a standardization layer on top of the output of P1NN that centers the activations
and performs divisive normalization by dividing by the standard deviation over a minibatch
of the activations of that layer. We denote the standardization function z(·). Standardization
makes use of the mean and standard deviation computed for each hidden unit such that each
hidden unit of ho will have 0 activation and unit standard deviation on average over the
minibatch. X is the set of pentomino images in the minibatch, where X ∈Rdin×N is a matrix
with N images. h(i)
o (xj) is the vector of activations of the i-th hidden unit of hidden layer
ho(xj) for the j-th example, with xj ∈X.
µh(i)
o
= 1
N
∑
xj∈X
h(i)
o (xj) (2)
σh(i)
o
=
√∑N
j (h(i)
o (xj) −µh(i)
o
)2
N + ϵ (3)
z(h(i)
o (xj)) =
h(i)
o (xj) −µh(i)
o
max(σh(i)
o
,ϵ) (4)
where ϵis a very small constant, that is used to prevent numerical underﬂows in the standard
deviation. P1NN is trained on each 8 ×8 patches extracted from the image.
ho is standardized for each training and test sample separately. Diﬀerent values of ϵ were
used for SMLP-hints and SMLP-nohints.
The concatenated output of P1NN is fed as an input to the P2NN. P2NN is a feedforward
MLP with a sigmoid output layer using a single RELU hidden layer. The task of P2NN is to
perform a nonlinear logical operation on the representation provided at the output of P1NN.
9
3.2.2 Structured Multi Layer Perceptron Trained with Hints (SMLP-hints)
The SMLP-hints architecture exploits a hint about the presence and category of Pentomino
objects, specifying a semantics for the P1NN outputs. P1NN is trained with the intermediate
target Y, specifying the type of Pentomino sprite shape present (if any) at each of the 64 patches
(8×8 non-overlapping blocks) of the image. Because a possible answer at a given location can
be “none of the object types” i.e., an empty patch, yp (for patch p) can take one of the 11
possible values, 1 for rejection and the rest is for the Pentomino shape classes, illustrated in
Figure 2:
yp =
{
0 if patch p is empty
s∈S if the patch p contains a Pentomino sprite .
A similar task has been studied by Fleuret et al. (2011) (at SI appendix Problem 17), who
compared the performance of humans vs computers.
The SMLP-hints architecture takes advantage of dividing the task into two subtasks during
training with prior information about intermediate-level relevant factors. Because the sum of
the training losses decomposes into the loss on each patch, the P1NN can be pre-trained patch-
wise. Each patch-speciﬁc component of the P1NN is a fully connected MLP with 8 ×8 inputs
and 11 outputs with a softmax output layer. SMLP-hints uses the the standardization given
in Equation 3 but with ϵ= 0.
The standardization is a crucial step for training the SMLP on the Pentomino dataset, and
yields much sparser outputs, as seen on Figures 3 and 4. If the standardization is not used,
even SMLP-hints could not solve the Pentomino task. In general, the standardization step
dampens the small activations and augments larger ones(reducing the noise). Centering the
activations of each feature detector in a neural network has been studied in (Raiko et al., 2012)
and (Vatanen et al., 2013). They proposed that transforming the outputs of each hidden neuron
in a multi-layer perceptron network to have zero output and zero slope on average makes ﬁrst
order optimization methods closer to the second order techniques.
By default, the SMLP uses rectiﬁer hidden units as activation function, we found a sig-
niﬁcant boost by using rectiﬁcation compared to hyperbolic tangent and sigmoid activation
functions. The P1NN has a highly overcomplete architecture with 1024 hidden units per patch,
and L1 and L2 weight decay regularization coeﬃcients on the weights (not the biases) are re-
spectively 1e-6 and 1e-5. The learning rate for the P1NN is 0.75. 1 training epoch was enough
for the P1NN to learn the features of Pentomino shapes perfectly on the 40000 training ex-
amples. The P2NN has 2048 hidden units. L1 and L2 penalty coeﬃcients for the P2NN are
1e-6, and the learning rate is 0.1. These were selected by trial and error based on validation
set error. Both P1NN (for each patch) and P2NN are fully-connected neural networks, even
though P1NN globally is a special kind of convolutional neural network.
Filters of the ﬁrst layer of SMLP are shown in Figure 6. These are the examples of the
ﬁlters obtained with the SLMP-hints trained with 40k examples, whose results are given in
Table 1. Those ﬁlters look very noisy but they work perfectly on the Pentomino task.
3.2.3 Deep and Structured Supervised MLP without Hints (SMLP-nohints)
SMLP-nohints uses the same connectivity pattern (and deep architecture) that is also used
in the SMLP-hints architecture, but without using the intermediate targets ( Y). It directly
predicts the ﬁnal outcome of the task ( Z), using the same number of hidden units, the same
10
Figure 3: Bar chart of concatenated softmax output activations ho of P1NN (11×64=704 out-
puts) in SMLP-hints before standardization, for a selected example. There are very
large spikes at each location for one of the possible 11 outcome (1 of K representa-
tion).
11
Figure 4: Softmax output activations ho of P1NN at SMLP-hints before standardization. There
are positive spiked outputs at the locations where there is a Pentomino shape. Posi-
tive and negative spikes arise because most of the outputs are near an average value.
Activations are higher at the locations where there is a pentomino shape.
12
Structured MLP 
Architecture with 
Hints
Final Binary task 
labels
Intermediate level 
targets.
Second 
Level 
Neural 
Network
First 
Level 
Neural 
Network
Figure 5: Structured MLP architecture, used with hints (trained in two phases, ﬁrst P1NN,
bottom two layers, then P2NN, top two layers). In SMLP-hints, P1NN is trained
on each 8x8 patch extracted from the image and the softmax output probabilities of
all 64 patches are concatenated into a 64 ×11 vector that forms the input of P2NN.
Only U and V are learned in the P1NN and its output on each patch is fed into
P2NN. The ﬁrst level and the second level neural networks are trained separately,
not jointly.
Figure 6: Filters of Structured MLP architecture, trained with hints on 40k examples.
13
connectivity and the same activation function for the hidden units as SMLP-hints. 120 hy-
perparameter values have been evaluated by randomly selecting the number of hidden units
from [64,128,256,512,1024,1200,2048] and randomly sampling 20 learning rates uniformly in
the log-domain within the interval of [0 .008,0.8]. Two fully connected hidden layers with 1024
hidden units (same as P1NN) per patch is used and 2048 (same as P2NN) for the last hid-
den layer, with twenty training epochs. For this network the best results are obtained with a
learning rate of 0.05. 7
Structured MLP 
Architecture without 
Hints
Final Binary task 
labels
Second 
Level 
Neural 
Network
First 
Level 
Neural 
Network
Figure 7: Structured MLP architecture, used without hints (SMLP-nohints). It is the same
architecture as SMLP-hints (Figure 5) but with both parts (P1NN and P2NN) trained
jointly with respect to the ﬁnal binary classiﬁcation task.
We chose to experiment with various SMLP-nohint architectures and optimization proce-
dures, trying unsuccessfully to achieve as good results with SMLP-nohint as with SMLP-hints.
Rectiﬁer Non-Linearity A rectiﬁer nonlinearity is used for the activations of MLP hidden
layers. We observed that using piecewise linear nonlinearity activation function such as the
rectiﬁer can make the optimization more tractable.
7. The source code of the structured MLP is available at the github repository: https://github.com/caglar/
structured_mlp
14
Figure 8: First layer ﬁlters learned by the Structured MLP architecture, trained without us-
ing hints on 447600 examples with online SGD and a sigmoid intermediate layer
activation.
Intermediate Layer The output of the P1NN is considered as an intermediate layer of the
SMLP. For the SMLP-hints, only softmax output activations have been tried at the intermediate
layer, and that suﬃced to learn the task. Since things did not work nearly as well with
the SMLP-nohints, several diﬀerent activation functions have been tried: softmax( ·), tanh(·),
sigmoid(·) and linear activation functions.
Standardization Layer Normalization at the last layer of the convolutional neural networks
has been used occasionaly to encourage the competition between the hidden units. (Jarrett
et al., 2009a) used a local contrast normalization layer in their architecture which performs
subtractive and divisive normalization. A local contrast normalization layer enforces a local
competition between adjacent features in the feature map and between features at the same
spatial location in diﬀerent feature maps. Similarly (Krizhevsky et al., 2012) observed that
using a local response layer that enjoys the beneﬁt of using local normalization scheme aids
generalization.
Standardization has been observed to be crucial for both SMLP trained with or with-
out hints. In both SMLP-hints and SMLP-nohints experiments, the neural network was not
able to generalize or even learn the training set without using standardization in the SMLP
intermediate layer, doing just chance performance. More speciﬁcally, in the SMLP-nohints ar-
chitecture, standardization is part of the computational graph, hence the gradients are being
backpropagated through it. The mean and the standard deviation is computed for each hidden
unit separately at the intermediate layer as in Equation 4. But in order to prevent numerical
underﬂows or overﬂows during the backpropagation we have used ϵ= 1e−8 (Equation 3).
The beneﬁt of having sparse activations may be speciﬁcally important for the ill-conditioned
problems, for the following reasons. When a hidden unit is “oﬀ”, its gradient (the derivative of
the loss with respect to its output) is usually close to 0 as well, as seen here. That means that all
oﬀ-diagonal second derivatives involving that hidden unit (e.g. its input weights) are also near 0.
This is basically like removing some columns and rows from the Hessian matrix associated with
a particular example. It has been observed that the condition number of the Hessian matrix
(speciﬁcally, its largest eigenvalue) increases as the size of the network increases (Dauphin and
Bengio, 2013), making training considerably slower and ineﬃcient (Dauphin and Bengio, 2013).
Hence one would expect that as sparsity of the gradients (obtained because of sparsity of the
activations) increases, training would become more eﬃcient, as if we were training a smaller
sub-network for each example, with shared weights across examples, as in dropouts (Hinton
et al., 2012).
In Figure 9, the activation of each hidden unit in a bar chart is shown: the eﬀect of
standardization is signiﬁcant, making the activations sparser.
15
(a) Before standardization.
 (b) After standardization.
Figure 9: Activations of the intermediate-level hidden units of an SLMP-nohints for a particular
examples (x-axis: hidden unit number, y-axis: activation value). Left (a): before
standardization. Right (b): after standardization.
In Figure 10, one can see the activation histogram of the SMLP-nohints intermediate layer,
showing the distribution of activation values, before and after standardization. Again the
sparsifying eﬀect of standardization is very apparent.
(a) Before standardization.
 (b) After standardization.
Figure 10: Distribution histogram of activation values of SMLP-nohints intermediate layer.
Left (a): before standardization. Right (b): after standardization.
In Figures 10 and 9, the intermediate level activations of SMLP-nohints are shown before
and after standardization. These are for the same SMLP-nohints architecture whose results
are presented on Table 1. For that same SMLP, the Adadelta (Zeiler, 2012) adaptive learning
16
rate scheme has been used, with 512 hidden units for the hidden layer of P1NN and rectiﬁer
activation function. For the output of the P1NN, 11 sigmoidal units have been used while
P2NN had 1200 hidden units with rectiﬁer activation function. The output nonlinearity of the
P2NN is a sigmoid and the training objective is the binary crossentropy.
Adaptive Learning Rates We have experimented with several diﬀerent adaptive learning
rate algorithms. We tried rmsprop 8, Adadelta (Zeiler, 2012), Adagrad (Duchi et al., 2010) and
a linearly (1/t) decaying learning rate (Bengio, 2013b). For the SMLP-nohints with sigmoid
activation function we have found Adadelta(Zeiler, 2012) converging faster to an eﬀective local
minima and usually yielding better generalization error compared to the others.
3.2.4 Deep and Structured MLP with Unsupervised Pre-Training
Several experiments have been conducted using an architecture similar to the SMLP-nohints,
but by using unsupervised pre-training of P1NN, with Denoising Auto-Encoder (DAE) and/or
Contractive Auto-Encoders (CAE). Supervised ﬁne-tuning proceeds as in the deep and struc-
tured MLP without hints. Because an unsupervised learner may not focus the representation
just on the shapes, a larger number of intermediate-level units at the output of P1NN has been
explored: previous work on unsupervised pre-training generally found that larger hidden layers
were optimal when using unsupervised pre-training, because not all unsupervised features will
be relevant to the task at hand. Instead of limiting to 11 units per patch, we experimented
with networks with up to 20 hidden (i.e., code) units per patch in the second-layer patch-wise
auto-encoder.
In Appendix 5.1 we also provided the result of some experiments with binary-binary RBMs
trained on 8×8 patches from the 40k training dataset.
In unsupervised pretraining experiments in this paper, both contractive auto-encoder(CAE)
with sigmoid nonlinearity and binary cross entropy cost function anddenoising auto-encoder(DAE)
have been used. In the second layer, experiments were performed with a DAE with rectiﬁer
hidden units utilizing L1 sparsity and weight decay on the weights of the auto-encoder. Greedy
layerwise unsupervised training procedure is used to train the deep auto-encoder architecture
(Bengio et al., 2007). In unsupervised pretraining experiments, tied weights have been used.
Diﬀerent combinations of CAE and DAE for unsupervised pretraining have been tested, but
none of the conﬁgurations tested managed to learn the Pentomino task, as shown in Table 1.
3.3 Experiments with 1 of K representation
To explore the eﬀect of changing the complexity of the input representation on the diﬃculty
of the task, a set of experiments have been designed with symbolic representations of the
information in each patch. In all cases an empty patch is represented with a 0 vector. These
representation can be seen as an alternative input for a P2NN-like network, i.e., they were fed
as input to an MLP or another black-box classiﬁer.
The following four experiments have been conducted, each one using one using a diﬀerent
input representation for each patch:
8. This is learning rate scaling method that is discussed by G. Hinton in his Video Lecture 6.5 - rmsprop: Divide
the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine
Learning, 2012.
17
Algorithm 20k dataset 40k dataset 80k dataset
Training Test Training Test Training Test
Error Error Error Error Error Error
SVM RBF 26.2 50.2 28.2 50.2 30.2 49.6
K Nearest Neighbors 24.7 50.0 25.3 49.5 25.6 49.0
Decision Tree 5.8 48.6 6.3 49.4 6.9 49.9
Randomized Trees 3.2 49.8 3.4 50.5 3.5 49.1
MLP 26.5 49.3 33.2 49.9 27.2 50.1
Convnet/Lenet5 50.6 49.8 49.4 49.8 50.2 49.8
Maxout Convnet 14.5 49.5 0.0 50.1 0.0 44.6
2 layer sDA 49.4 50.3 50.2 50.3 49.7 50.3
Struct. Supervised MLP w/o hints 0.0 48.6 0.0 36.0 0.0 12.4
Struct. MLP+CAE Supervised Finetuning 50.5 49.7 49.8 49.7 50.3 49.7
Struct. MLP+CAE+DAE, Supervised Finetuning 49.1 49.7 49.4 49.7 50.1 49.7
Struct. MLP+DAE+DAE, Supervised Finetuning 49.5 50.3 49.7 49.8 50.3 49.7
Struct. MLP with Hints 0.21 30.7 0 3.1 0 0.01
Table 1: The error percentages with diﬀerent learning algorithms on Pentomino dataset with
diﬀerent number of training examples.
Experiment 1-Onehot representation without transformations: In this experiment sev-
eral trials have been done with a 10-input one-hot vector per patch. Each input corre-
sponds to an object category given in clear, i.e., the ideal input for P2NN if a supervised
P1NN perfectly did its job.
Experiment 2-Disentangled representations: In this experiment, we did trials with 16
binary inputs per patch, 10 one-hot bits for representing each object category, 4 for
rotations and 2 for scaling, i.e., the whole information about the input is given, but it is
perfectly disentangled. This would be the ideal input for P2NN if an unsupervised P1NN
perfectly did its job.
Experiment 3-Onehot representation with transformations: For each of the ten object
types there are 8 = 4 ×2 possible transformations. Two objects in two diﬀerent patches
are the considered “the same” (for the ﬁnal task) if their category is the same regardless
of the transformations. The one-hot representation of a patch corresponds to the cross-
product between the 10 object shape classes and the 4 ×2 transformations, i.e., one out of
80=10×4 ×2 possibilities represented in an 80-bit one-hot vector. This also contains all
the information about the input image patch, but spread out in a kind of non-parametric
and non-informative (not disentangled) way, like a perfect memory-based unsupervised
learner (like clustering) could produce. Nevertheless, the shape class would be easier to
read out from this representation than from the image representation (it would be an OR
over 8 of the bits).
Experiment 4-Onehot representation with 80 choices: This representation has the same
1 of 80 one-hot representation per patch but the target task is deﬁned diﬀerently. Two ob-
jects in two diﬀerent patches are considered the same iﬀ they have exactly the same 80-bit
onehot representation (i.e., are of the same object category with the same transformation
applied).
The ﬁrst experiment is a sanity check. It was conducted with single hidden-layered MLP’s
with rectiﬁer and tanh nonlinearity, and the task was learned perfectly (0 error on both training
and test dataset) with very few training epochs.
18
0 100 200 300 400 500 600 700 800 9000.0
0.1
0.2
0.3
0.4
0.5
0.6
Training Error Rate
Test Error Rate
(a) Training and Test Errors for Experiment 4
0 100 200 300 400 500 600 700 8000.0
0.1
0.2
0.3
0.4
0.5
0.6
Training Error Rate
Test Error Rate (b) Training and Test Errors for Experiment 3
Figure 11: Tanh MLP training curves. Left (a): The training and test errors of Experiment
3 over 800 training epochs with 100k training examples using Tanh MLP. Right
(b):The training and test errors of Experiment 4 over 700 training epochs with 100k
training examples using Tanh MLP.
The results of Experiment 2 are given in Table 2. To improve results, we experimented
with the Maxout non-linearity in a feedforward MLP (Goodfellow et al., 2013) with two hidden
layers. Unlike the typical Maxout network mentioned in the original paper, regularizers have
been deliberately avoided in order to focus on the optimization issue, i.e: no weight decay, norm
constraint on the weights, or dropout. Although learning from a disentangled representation is
more diﬃcult than learning from perfect object detectors, it is feasible with some architectures
such as the Maxout network. Note that this representation is the kind of representation that
one could hope an unsupervised learning algorithm could discover, at best, as argued in Bengio
et al. (2012).
The only results obtained on the validation set for Experiment 3 and Experiment 4 are
shown respectively in Table 3 and Table 4. In these experiments a tanh MLP with two hidden
layers have been tested with the same hyperparameters. In experiment 3 the complexity of the
problem comes from the transformations (8=4 ×2) and the number of object types.
But in experiment 4, the only source of complexity of the task comes from the number of
diﬀerent object types. These results are in between the complete failure and complete success
observed with other experiments, suggesting that the task could become solvable with better
training or more training examples. Figure 11 illustrates the progress of training a tanh MLP,
on both the training and test error, for Experiments 3 and 4. Clearly, something has been
learned, but the task is not nailed yet. On experiment 3 for both maxout and tanh the maxout
there was a long plateau where the training error and objective stays almost same. Maxout
did just chance on the experiment for about 120 iterations on the training and the test set.
But after 120th iteration the training and test error started decline and eventually it was able
to solve the task. Moreover as seen from the curves in Figure 11(a) and 11(b), the training
and test error curves are almost the same for both tasks. This implies that for onehot inputs,
whether you increase the number of possible transformations for each object or the number of
19
Learning Algorithm Training Error Test Error
SVM 0.0 35.6
Random Forests 1.29 40.475
Tanh MLP 0.0 0.0
Maxout MLP 0.0 0.0
Table 2: Performance of diﬀerent learning algorithms on disentangled representation in Exper-
iment 2.
Learning Algorithm Training Error Test Error
SVM 11.212 32.37
Random Forests 24.839 48.915
Tanh MLP 0.0 22.475
Maxout MLP 0.0 0.0
Table 3: Performance of diﬀerent learning algorithms using a dataset with onehot vector and
80 inputs as discussed for Experiment 3.
object categories, as soon as the number of possible conﬁgurations is same, the complexity of
the problem is almost the same for the MLP.
3.4 Does the Eﬀect Persist with Larger Training Set Sizes?
The results shown in this section indicate that the problem in the Pentomino task clearly
is not just a regularization problem, but rather basically hinges on an optimization problem.
Otherwise, we would expect test error to decrease as the number of training examples increases.
This is shown ﬁrst by studying the online case and then by studying the ordinary training
case with a ﬁxed size training set but considering increasing training set sizes. In the online
minibatch setting, parameter updates are performed as follows:
θt+1 = θt −∆θt (5)
∆θt = ϵ
∑N
i ∇θt L(xt,θt)
N (6)
where L(xt,θt) is the loss incurred on example xt with parameters θt , where t∈Z+ and ϵ
is the learning rate.
Ordinary batch algorithms converge linearly to the optimum θ∗, however the noisy gradient
estimates in the online SGD will cause parameterθto ﬂuctuate near the local optima. However,
online SGD directly optimizes the expected risk, because the examples are drawn iid from the
ground-truth distribution (Bottou, 2010). Thus:
L∞= E[L(x,θ)] =
∫
x
L(x,θ)p(x)dx (7)
20
Learning Algorithm Training Error Test Error
SVM 4.346 40.545
Random Forests 23.456 47.345
Tanh MLP 0 25.8
Table 4: Performance of diﬀerent algorithms using a dataset with onehot vector and 80 binary
inputs as discussed in Experiment 4.
where L∞ is the generalization error. Therefore online SGD is trying to minimize the
expected risk with noisy updates. Those noisy updates have the eﬀect of regularizer:
∆θt = ϵ
∑N
i ∇θt L(xt,θt)
N = ϵ∇θt L(x,θt) + ϵξt (8)
where ∇θt L(x,θt) is the true gradient and ξt is the zero-mean stochastic gradient “noise”
due to computing the gradient over a ﬁnite-size minibatch sample.
We would like to know if the problem with the Pentomino dataset is more a regularization
or an optimization problem. An SMLP-nohints model was trained by online SGD with the ran-
domly generated online Pentomino stream. The learning rate was adaptive, with the Adadelta
procedure (Zeiler, 2012) on minibatches of 100 examples. In the online SGD experiments, two
SMLP-nohints that is trained with and without standardization at the intermediate layer with
exactly the same hyperparameters are tested. The SMLP-nohints P1NN patch-wise submodel
has 2048 hidden units and the SMLP intermediate layer has 1152 = 64 ×18 hidden units. The
nonlinearity that is used for the intermediate layer is the sigmoid. P2NN has 2048 hidden units.
SMLP-nohints has been trained either with or without standardization on top of the output
units of the P1NN. The experiments illustrated in Figures 12 and 13 are with the same SMLP
without hints architecture for which results are given in Table 1. In those graphs only the results
for the training on the randomly generated 545400 Pentomino samples have been presented. As
shown in the plots SMLP-nohints was not able to generalize without standardization. Although
without standardization the training loss seems to decrease initially, it eventually gets stuck in
a plateau where training loss doesn’t change much.
Training of SMLP-nohints online minibatch SGD is performed using standardization in the
intermediate layer and Adadelta learning rate adaptation, on 1046000 training examples from
the randomly generated Pentomino stream. At the end of the training, test error is down to
27.5%, which is much better than chance but from from the score obtained with SMLP-hints
of near 0 error.
In another SMLP-nohints experiment without standardization the model is trained with the
1580000 Pentomino examples using online minibatch SGD. P1NN has 2048 hidden units and 16
sigmoidal outputs per patch. for the P1NN hidden layer. P2NN has 1024 hidden units for the
hidden layer. Adadelta is used to adapt the learning rate. At the end of training this SMLP,
the test error remained stuck, at 50.1%.
21
0 100 200 300 400 500 600 700 800
Batch no
0.20
0.25
0.30
0.35
0.40
0.45
0.50
0.55Test Error
SMLP with standardization
SMLP without standardization
Figure 12: Test errors of SMLP-nohints with and without standardization in the intermediate
layer. Sigmoid as an intermediate layer activation has been used. Each tick (batch
no) in the x-axis represents 400 examples.
22
0 100 200 300 400 500 600 700
Batch no
0
1
2
3
4
5
6
7Training Loss
SMLP with standardization
SMLP without standardization
Figure 13: Training errors of SMLP-nohints with and without standardization in the interme-
diate layer. Sigmoid nonlinearity has been used as an intermediate layer activation
function. The x-axis is in units of blocks of 400 examples in the training set.
23
3.4.1 Experiments with Increased Training Set Size
Here we consider the eﬀect of training diﬀerent learners with diﬀerent numbers of training
examples. For the experimental results shown in Table 1, 3 training set sizes (20k, 40k and 80k
examples) had been used. Each dataset was generated with diﬀerent random seeds (so they
do not overlap). Figure 14 also shows the error bars for an ordinary MLP with three hidden
layers, for a larger range of training set sizes, between 40k and 320k examples. The number of
training epochs is 8 (more did not help), and there are three hidden layers with 2048 feature
detectors. The learning rate we used in our experiments is 0.01. The activation function of the
MLP is a tanh nonlinearity, while the L1, L2 penalty coeﬃcients are both 1e-6.
Table 1 shows that, without guiding hints, none of the state-of-art learning algorithms could
perform noticeably better than a random predictor on the test set. This shows the importance
of intermediate hints introduced in the SMLP. The decision trees and SVMs can overﬁt the
training set but they could not generalize on the test set. Note that the numbers reported in the
table are for hyper-parameters selected based on validation set error, hence lower training errors
are possible if avoiding all regularization and taking large enough models. On the training set,
the MLP with two large hidden layers (several thousands) could reach nearly 0% training error,
but still did not manage to achieve good test error.
In the experiment results shown in Figure 14, we evaluate the impact of adding more training
data for the fully-connected MLP. As mentioned before for these experiments we have used a
MLP with three hidden layers where each layer has 2048 hidden units. The tanh( ·) activation
function is used with 0.05 learning rate and minibatches of size 200.
As can be seen from the ﬁgure, adding more training examples did not help either training
or test error (both are near 50%, with training error slightly lower and test error slightly
higher), reinforcing the hypothesis that the diﬃcult encountered is one of optimization, not of
regularization.
Figure 14: Training and test error bar charts for a regular MLP with 3 hidden layers. There
is no signiﬁcant improvement on the generalization error of the MLP as the new
training examples are introduced.
24
3.5 Experiments on Eﬀect of Initializing with Hints
Initialization of the parameters in a neural network can have a big impact on the learning
and generalization (Glorot and Bengio, 2010). Previously Erhan et al. (2010) showed that
initializing the parameters of a neural network with unsupervised pretraining guides the learn-
ing towards basins of attraction of local minima that provides better generalization from the
training dataset. In this section we analyze the eﬀect of initializing the SMLP with hints and
then continuing without hints at the rest of the training. For experimental analysis of hints
based initialization, SMLP is trained for 1 training epoch using the hints and for 60 epochs it
is trained without hints on the 40k examples training set. We also compared the same archi-
tecture with the same hyperparameters, against to SMLP-nohints trained for 61 iterations on
the same dataset. After one iteration of hint-based training SMLP obtained 9% training error
and 39% test error. Following the hint based training, SMLP is trained without hints for 60
epochs, but at epoch 18, it already got 0% training and 0% test error. The hyperparameters
for this experiment and the experiment that the results shown for the SMLP-hints in Table 1
are the same. The test results for initialization with and without hints are shown on Figure 15.
This ﬁgure suggests that initializing with hints can give the same generalization performance
but training takes longer.
Figure 15: Plots showing the test error of SMLP with random initialization vs initializing with
hint based training.
3.5.1 Further Experiments on Optimization for Pentomino Dataset
With extensive hyperparameter optimization and using standardization in the intermediate
level of the SMLP with softmax nonlinearity, SMLP-nohints was able to get 5.3% training and
25
6.7% test error on the 80k Pentomino training dataset. We used the 2050 hidden units for the
hidden layer of P1NN and 11 softmax output per patch. For the P2NN, we used 1024 hidden
units with sigmoid and learning rate 0.1 without using any adaptive learning rate method. This
SMLP uses a rectiﬁer nonlinearity for hidden layers of both P1NN and P2NN. Considering that
architecture uses softmax as the intermediate activation function of SMLP-nohints. It is very
likely that P1NN is trying to learn the presence of speciﬁc Pentomino shape in a given patch.
This architecture has a very large capacity in the P1NN, that probably provides it enough
capacity to learn the presence of Pentomino shapes at each patch eﬀortlessly.
An MLP with 2 hidden layers, each 1024 rectiﬁer units, was trained using LBFGS (the
implementation from the scipy.optimize library) on 40k training examples, with gradients com-
puted on batches of 10000 examples at each iteration. However, after convergence of training,
the MLP was still doing chance on the test dataset.
We also observed that using linear units for the intermediate layer yields better general-
ization error without standardization compared to using activation functions such as sigmoid,
tanh and RELU for the intermediate layer. SMLP-nohints was able to get 25% generaliza-
tion error with linear units without standardization whereas all the other activation functions
that has been tested failed to generalize with the same number of training iterations without
standardization and hints. This suggests that using non-linear intermediate-level activation
functions without standardization introduces an optimization diﬃculty for the SMLP-nohints,
maybe because the intermediate level acts like a bottleneck in this architecture.
4. Conclusion and Discussion
In this paper we have shown an example of task which seems almost impossible to solve by
standard black-box machine learning algorithms, but can be almost perfectly solved when
one encourages a semantics for the intermediate-level representation that is guided by prior
knowledge. The task has the particularity that it is deﬁned by the composition of two non-
linear sub-tasks (object detection on one hand, and a non-linear logical operation similar to
XOR on the other hand).
What is interesting is that in the case of the neural network, we can compare two networks
with exactly the same architecture but a diﬀerent pre-training, one of which uses the known
intermediate concepts to teach an intermediate representation to the network. With enough
capacity and training time they can overﬁt but did not not capture the essence of the task, as
seen by test set performance.
We know that a structured deep network can learn the task, if it is initialized in the right
place, and do it from very few training examples. Furthermore we have shown that if one
pre-trains SMLP with hints for only one epoch, it can nail the task. But the exactly same
architecture which started training from random initialization, failed to generalize.
Consider the fact that even SMLP-nohints with standardization after being trained using
online SGD on 1046000 generated examples and still gets 27.5% test error. This is an indication
that the problem is not a regularization problem but possibly an inability to ﬁnd agood eﬀective
local minima of generalization error .
What we hypothesize is that for most initializations and architectures (in particular the
fully-connected ones), although it is possible to ﬁnd a good eﬀective local minimum of training
error when enough capacity is provided, it is diﬃcult (without the proper initialization) to ﬁnd a
good local minimum of generalization error. On the other hand, when the network architecture
26
is constrained enough but still allows it to represent a good solution (such as the structured
MLP of our experiments), it seems that the optimization problem can still be diﬃcult and even
training error remains stuck high if the standardization isn’t used. Standardization obviously
makes the training objective of the SMLP easier to optimize and helps it to ﬁnd at least a
better eﬀective local minimum of training error . This ﬁnding suggests that by using speciﬁc
architectural constraints and sometimes domain speciﬁc knowledge about the problem, one can
alleviate the optimization diﬃculty that generic neural network architectures face.
It could be that the combination of the network architecture and training procedure pro-
duces a training dynamics that tends to yield into these minima that are poor from the point of
view of generalization error, even when they manage to nail training error by providing enough
capacity. Of course, as the number of examples increases, we would expect this discrepancy to
decrease, but then the optimization problem could still make the task unfeasible in practice.
Note however that our preliminary experiments with increasing the training set size (8-fold) for
MLPs did not reveal signs of potential improvements in test error yet, as shown in Figure 14.
Even using online training on 545400 Pentomino examples, the SMLP-nohints architecture was
still doing far from perfect in terms of generalization error (Figure 12).
These ﬁndings bring supporting evidence to the “Guided Learning Hypothesis” and “Deeper
Harder Hypothesis” from Bengio (2013a): higher level abstractions, which are expressed by
composing simpler concepts, are more diﬃcult to learn (with the learner often getting in an
eﬀective local minimum ), but that diﬃculty can be overcome if another agent provides hints
of the importance of learning other, intermediate-level abstractions which are relevant to the
task.
Many interesting questions remain open. Would a network without any guiding hint even-
tually ﬁnd the solution with a enough training time and/or with alternate parametrizations?
To what extent is ill-conditioning a core issue? The results with LBFGS were disappointing but
changes in the architectures (such as standardization of the intermediate level) seem to make
training much easier. Clearly, one can reach good solutions from an appropriate initialization,
pointing in the direction of an issue with local minima, but it may be that good solutions are
also reachable from other initializations, albeit going through a tortuous ill-conditioned path
in parameter space. Why did our attempts at learning the intermediate concepts in an unsu-
pervised way fail? Are these results speciﬁc to the task we are testing or a limitation of the
unsupervised feature learning algorithm tested? Trying with many more unsupervised vari-
ants and exploring explanatory hypotheses for the observed failures could help us answer that.
Finally, and most ambitious, can we solve these kinds of problems if we allow a community
of learners to collaborate and collectively discover and combine partial solutions in order to
obtain solutions to more abstract tasks like the one presented here? Indeed, we would like to
discover learning algorithms that can solve such tasks without the use of prior knowledge as
speciﬁc and strong as the one used in the SMLP here. These experiments could be inspired by
and inform us about potential mechanisms for collective learning through cultural evolutions
in human societies.
Acknowledgments
We would like to thank to the ICLR 2013 reviewers for their insightful comments, and NSERC,
CIFAR, Compute Canada and Canada Research Chairs for funding.
27
References
A. Ben-Hur and J. Weston. A user’s guide to support vector machines. Methods in Molecular
Biology, 609:223–239, 2010.
Y. Bengio, P. Lamblin, D. Popovici, and H. Larochelle. Greedy layer-wise training of deep
networks. In NIPS’2006, 2007.
Yoshua Bengio. Learning deep architectures for AI. Foundations and Trends in Machine
Learning, 2(1):1–127, 2009. Also published as a book. Now Publishers, 2009.
Yoshua Bengio. Evolving culture vs local minima. In Growing Adaptive Machines: Integrating
Development and Learning in Artiﬁcial Neural Networks, number also as ArXiv 1203.2990v1,
pages T. Kowaliw, N. Bredeche & R. Doursat, eds. Springer-Verlag, March 2013a. URL
http://arxiv.org/abs/1203.2990.
Yoshua Bengio. Practical recommendations for gradient-based training of deep architectures.
In K.-R. M¨ uller, G. Montavon, and G. B. Orr, editors,Neural Networks: Tricks of the Trade .
Springer, 2013b.
Yoshua Bengio, Jerome Louradour, Ronan Collobert, and Jason Weston. Curriculum learning.
In L´ eon Bottou and Michael Littman, editors,Proceedings of the Twenty-sixth International
Conference on Machine Learning (ICML’09) . ACM, 2009a.
Yoshua Bengio, Jerome Louradour, Ronan Collobert, and Jason Weston. Curriculum learning.
In ICML’09, 2009b.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Unsupervised feature learning and deep
learning: A review and new perspectives. Technical Report arXiv:1206.5538, U. Montreal,
2012. URL http://arxiv.org/abs/1206.5538.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Unsupervised feature learning and deep
learning: A review and new perspectives. IEEE Trans. Pattern Analysis and Machine Intel-
ligence (PAMI), 2013.
James Bergstra, Olivier Breuleux, Fr´ ed´ eric Bastien, Pascal Lamblin, Razvan Pascanu, Guil-
laume Desjardins, Joseph Turian, David Warde-Farley, and Yoshua Bengio. Theano: a CPU
and GPU math expression compiler. In Proceedings of the Python for Scientiﬁc Computing
Conference (SciPy), 2010.
L´ eon Bottou. Large-scale machine learning with stochastic gradient descent. InProceedings of
COMPSTAT’2010, pages 177–186. Springer, 2010.
Leo Breiman. Random forests. Machine Learning, 45(1):5–32, 2001.
D. C. Ciresan, U. Meier, L. M. Gambardella, and J. Schmidhuber. Deep big simple neural nets
for handwritten digit recognition. Neural Computation, 22:1–14, 2010.
Yann Dauphin and Yoshua Bengio. Big neural networks waste capacity. Technical Report
arXiv:1301.3583, Universite de Montreal, 2013.
Richard Dawkins. The Selﬁsh Gene . Oxford University Press, 1976.
28
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and
stochastic optimization. Journal of Machine Learning Research , 12:2121–2159, 2010.
Dumitru Erhan, Yoshua Bengio, Aaron Courville, Pierre-Antoine Manzagol, Pascal Vincent,
and Samy Bengio. Why does unsupervised pre-training help deep learning? Journal of
Machine Learning Research, 11:625–660, February 2010.
Fran¸ cois Fleuret, Ting Li, Charles Dubout, Emma K Wampler, Steven Yantis, and Donald
Geman. Comparing machines and humans on a visual categorization test. Proceedings of the
National Academy of Sciences , 108(43):17621–17625, 2011.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectiﬁer neural networks. In AISTATS,
2011a.
Xavier Glorot and Yoshua Bengio. Understanding the diﬃculty of training deep feedforward
neural networks. In JMLR W&CP: Proceedings of the Thirteenth International Conference
on Artiﬁcial Intelligence and Statistics (AISTATS 2010) , volume 9, pages 249–256, May
2010.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectiﬁer neural networks. In
JMLR W&CP: Proceedings of the Fourteenth International Conference on Artiﬁcial Intelli-
gence and Statistics (AISTATS 2011) , April 2011b.
Ian J. Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio.
Maxout networks. In ICML, 2013.
Maciej Henneberg. Decrease of human skull size in the holocene.Human biology, pages 395–405,
1988.
Maciej Henneberg and Maryna Steyn. Trends in cranial capacity and cranial index in subsa-
haran africa during the holocene. American journal of human biology , 5(4):473–479, 1993.
J. Henrich and R. McElreath. The evolution of cultural evolution. Evolutionary Anthropology:
Issues, News, and Reviews , 12(3):123–135, 2003.
Geoﬀrey E. Hinton, Simon Osindero, and Yee Whye Teh. A fast learning algorithm for deep
belief nets. Neural Computation, 18:1527–1554, 2006.
Geoﬀrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdi-
nov. Improving neural networks by preventing co-adaptation of feature detectors. Technical
report, arXiv:1207.0580, 2012.
C.W. Hsu, C.C. Chang, C.J. Lin, et al. A practical guide to support vector classiﬁcation, 2003.
Kevin Jarrett, Koray Kavukcuoglu, Marc’Aurelio Ranzato, and Yann LeCun. What is the
best multi-stage architecture for object recognition? In Proc. International Conference on
Computer Vision (ICCV’09) , pages 2146–2153. IEEE, 2009a.
Kevin Jarrett, Koray Kavukcuoglu, Marc’Aurelio Ranzato, and Yann LeCun. What is the best
multi-stage architecture for object recognition? In ICCV’09, 2009b.
29
Faisal Khan, Xiaojin Zhu, and Bilge Mutlu. How do humans teach: On curriculum learning and
teaching dimension. In Advances in Neural Information Processing Systems 24 (NIPS’11) ,
pages 1449–1457, 2011.
Alex Krizhevsky, Ilya Sutskever, and Geoﬀrey Hinton. ImageNet classiﬁcation with deep
convolutional neural networks. In Advances in Neural Information Processing Systems 25
(NIPS’2012). 2012.
Kai A. Krueger and Peter Dayan. Flexible shaping: how learning in small steps helps.Cognition,
110:380–394, 2009.
G. Kunapuli, K.P. Bennett, R. Maclin, and J.W. Shavlik. The adviceptron: Giving advice to
the perceptron. Proceedings of the Conference on Artiﬁcial Neural Networks In Engineering
(ANNIE 2010), 2010.
Hugo Larochelle, Yoshua Bengio, Jerome Louradour, and Pascal Lamblin. Exploring strategies
for training deep neural networks. Journal of Machine Learning Research , 10:1–40, 2009.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haﬀner. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
T.M. Mitchell. The need for biases in learning generalizations . Department of Computer
Science, Laboratory for Computer Science Research, Rutgers Univ., 1980.
T.M. Mitchell and S.B. Thrun. Explanation-based neural network learning for robot control.
Advances in Neural information processing systems , pages 287–287, 1993.
R. Montague. Universal grammar. Theoria, 36(3):373–398, 1970.
V. Nair and G. E Hinton. Rectiﬁed linear units improve restricted Boltzmann machines. In
ICML’10, 2010.
L.B.J.H.F.R.A. Olshen and C.J. Stone. Classiﬁcation and regression trees. Belmont, Calif.:
Wadsworth, 1984.
Joseph O’Sullivan. Integrating initialization bias and search bias in neural network learning,
1996.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,
P. Prettenhofer, R. Weiss, V. Dubourg, et al. Scikit-learn: Machine learning in python. The
Journal of Machine Learning Research , 12:2825–2830, 2011.
Gail B. Peterson. A day of great illumination: B. F. Skinner’s discovery of shaping. Journal of
the Experimental Analysis of Behavior , 82(3):317–328, 2004.
Tapani Raiko, Harri Valpola, and Yann LeCun. Deep learning made easier by linear transfor-
mations in perceptrons. In International Conference on Artiﬁcial Intelligence and Statistics ,
pages 924–932, 2012.
Salah Rifai, Pascal Vincent, Xavier Muller, Xavier Glorot, and Yoshua Bengio. Contractive
auto-encoders: Explicit invariance during feature extraction. In ICML’2011, 2011.
30
Salah Rifai, Yoshua Bengio, Yann Dauphin, and Pascal Vincent. A generative process for sam-
pling contractive auto-encoders. In Proceedings of the Twenty-nine International Conference
on Machine Learning (ICML’12) . ACM, 2012. URL http://icml.cc/discuss/2012/590.
html.
R. Salakhutdinov and G.E. Hinton. Deep Boltzmann machines. In Proceedings of the Twelfth
International Conference on Artiﬁcial Intelligence and Statistics (AISTATS 2009), volume 8,
2009.
Burrhus F. Skinner. Reinforcement today. American Psychologist, 13:94–99, 1958.
R.J. Solomonoﬀ. A system for incremental learning based on algorithmic probability. InProceed-
ings of the Sixth Israeli Conference on Artiﬁcial Intelligence, Computer Vision and Pattern
Recognition, pages 515–527. Citeseer, 1989.
G.G. Towell and J.W. Shavlik. Knowledge-based artiﬁcial neural networks. Artiﬁcial intelli-
gence, 70(1):119–165, 1994.
Tommi Vatanen, Tapani Raiko, Harri Valpola, and Yann LeCun. Pushing stochastic gradient
towards second-order methods–backpropagation learning with transformations in nonlinear-
ities. arXiv preprint arXiv:1301.3476 , 2013.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol.
Stacked denoising autoencoders: Learning useful representations in a deep network with a
local denoising criterion. Journal of Machine Learning Research , 11:3371–3408, December
2010.
Luis Von Ahn, Manuel Blum, Nicholas J Hopper, and John Langford. Captcha: Using hard
ai problems for security. In Advances in CryptologyEUROCRYPT 2003 , pages 294–311.
Springer, 2003.
Jason Weston, Fr´ ed´ eric Ratle, and Ronan Collobert. Deep learning via semi-supervised em-
bedding. In William W. Cohen, Andrew McCallum, and Sam T. Roweis, editors, Pro-
ceedings of the Twenty-ﬁfth International Conference on Machine Learning (ICML’08) ,
pages 1168–1175, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-205-4. doi:
10.1145/1390156.1390303.
Matthew D Zeiler. Adadelta: An adaptive learning rate method. arXiv preprint
arXiv:1212.5701, 2012.
5. Appendix
5.1 Binary-Binary RBMs on Pentomino Dataset
We trained binary-binary RBMs (both visible and hidden are binary) on 8×8 patches extracted
from the Pentomino Dataset using PCD (stochastic maximum likelihood), a weight decay of
.0001 and a sparsity penalty 9. We used 256 hidden units and trained by SGD with a batch
size of 32 and a annealing learning rate (Bengio, 2013b) starting from 1e-3 with annealing rate
9. implemented as TorontoSparsity in pylearn2, see the yaml ﬁle in the repository for more details
31
1.000015. The RBM is trained with momentum starting from 0.5. The biases are initialized to
-2 in order to get a sparse representation. The RBM is trained for 120 epochs (approximately
50 million updates).
After pretraining the RBM, its parameters are used to initialize the ﬁrst layer of an SMLP-
nohints network. As in the usual architecture of the SMLP-nohints on top of P1NN, there is
an intermediate layer. Both P1NN and the intermediate layer have a sigmoid nonlinearity, and
the intermediate layer has 11 units per location. This SMLP-nohints is trained with Adadelta
and standardization at the intermediate layer 10.
0 5 10 15 20 25 30 35 40 45
Epoch
0.0
0.1
0.2
0.3
0.4
0.5Error percentage
RBM Test and Training Errors
Training Error
Test Error
Figure 16: Training and test errors of an SMLP-nohints network whose ﬁrst layer is pre-trained
as an RBM. Training error reduces to 0% at epoch 42, but test error is still chance.
5.2 Experimental Setup and Hyper-parameters
5.2.1 Decision Trees
We used the decision tree implementation in the scikit-learn (Pedregosa et al., 2011) python
package which is an implementation of the CART (Regression Trees) algorithm. The CART
algorithm constructs the decision tree recursively and partitions the input space such that the
samples belonging to the same category are grouped together (Olshen and Stone, 1984). We
used The Gini index as the impurity criteria. We evaluated the hyper-parameter conﬁgura-
tions with a grid-search. We cross-validated the maximum depth ( max depth) of the tree (for
preventing the algorithm to severely overﬁt the training set) and minimum number of samples
10. In our auto-encoder experiments we directly fed features to P2NN without standardization and Adadelta.
32
Figure 17: Filters learned by the binary-binary RBM after training on the 40k examples. The
RBM did learn the edge structure of Pentomino shapes.
Figure 18: 100 samples generated from trained RBM. All the generated samples are valid Pen-
tomino shapes.
33
required to create a split (min split). 20 diﬀerent conﬁgurations of hyper-parameter values were
evaluated. We obtained the best validation error with max depth= 300 and min split= 8.
5.2.2 Support Vector Machines
We used the “Support Vector Classiﬁer (SVC)” implementation from the scikit-learn package
which in turn uses the libsvm’s Support Vector Machine (SVM) implementation. Kernel-
based SVMs are non-parametric models that map the data into a high dimensional space and
separate diﬀerent classes with hyperplane(s) such that the support vectors for each category
will be separated by a large margin. We cross-validated three hyper-parameters of the model
using grid-search: C, γ and the type of kernel( kernel type). C is the penalty term (weight
decay) for the SVM and γ is a hyper-parameter that controls the width of the Gaussian for
the RBF kernel. For the polynomial kernel, γ controls the ﬂexibility of the classiﬁer (degree
of the polynomial) as the number of parameters increases (Hsu et al., 2003; Ben-Hur and
Weston, 2010). We evaluated forty-two hyper-parameter conﬁgurations. That includes, two
kernel types: {RBF, Polynomial}; three gammas: {1e−2, 1e−3, 1e−4}for the RBF kernel,
{1,2,5}for the polynomial kernel, and seven C values among: {0.1,1,2,4,8,10,16}. As a
result of the grid search and cross-validation, we have obtained the best test error by using the
RBF kernel, with C = 2 and γ = 1.
5.2.3 Multi Layer Perceptron
We have our own implementation of Multi Layer Perceptron based on the Theano (Bergstra
et al., 2010) machine learning libraries. We have selected 2 hidden layers, the rectiﬁer activation
function, and 2048 hidden units per layer. We cross-validated three hyper-parameters of the
model using random-search, sampling the learning rates ϵ in log-domain, and selecting L1
and L2 regularization penalty coeﬃcients in sets of ﬁxed values, evaluating 64 hyperparameter
values. The range of the hyperparameter values areϵ∈[0.0001,1], L1 ∈{0.,1e−6,1e−5,1e−4}
and L2 ∈{0,1e−6,1e−5}. As a result, the following were selected: L1 = 1e−6, L2 = 1e−5
and ϵ= 0.05.
5.2.4 Random Forests
We used scikit-learn’s implementation of “Random Forests” decision tree learning. The Ran-
dom Forests algorithm creates an ensemble of decision trees by randomly selecting for each tree
a subset of features and applying bagging to combine the individual decision trees (Breiman,
2001). We have used grid-search and cross-validated the max depth, min split, and number
of trees ( n estimators). We have done the grid-search on the following hyperparameter val-
ues, n estimators ∈ {5,10,15,25,50}, max depth ∈ {100,300,600,900}, and min splits ∈
{1,4,16}. We obtained the best validation error with max depth = 300, min split = 4 and
n estimators= 10.
5.2.5 k-Nearest Neighbors
We used scikit-learn’s implementation of k-Nearest Neighbors (k-NN). k-NN is an instance-
based, lazy learning algorithm that selects the training examples closest in Euclidean distance
to the input query. It assigns a class label to the test example based on the categories of the
k closest neighbors. The hyper-parameters we have evaluated in the cross-validation are the
number of neighbors (k) and weights. The weightshyper-parameter can be either “uniform” or
34
“distance”. With “uniform”, the value assigned to the query point is computed by the majority
vote of the nearest neighbors. With “distance”, each value assigned to the query point is
computed by weighted majority votes where the weights are computed with the inverse distance
between the query point and the neighbors. We have used n neighbours ∈{1,2,4,6,8,12}and
weights ∈{”uniform”,”distance”}for hyper-parameter search. As a result of cross-validation
and grid search, we obtained the best validation error with k= 2 and weights=“uniform”.
5.2.6 Convolutional Neural Nets
We used a Theano (Bergstra et al., 2010) implementation of Convolutional Neural Networks
(CNN) from the deep learning tutorial at deeplearning.net, which is based on a vanilla
version of a CNN LeCun et al. (1998). Our CNN has two convolutional layers. Following
each convolutional layer, we have a max-pooling layer. On top of the convolution-pooling-
convolution-pooling layers there is an MLP with one hidden layer. In the cross-validation we
have sampled 36 learning rates in log-domain in the range [0 .0001,1] and the number of ﬁlters
from the range [10 ,20,30,40,50,60] uniformly. For the ﬁrst convolutional layer we used 9 ×9
receptive ﬁelds in order to guarantee that each object ﬁts inside the receptive ﬁeld. As a result
of random hyperparameter search and doing manual hyperparameter search on the validation
dataset, the following values were selected:
•The number of features used for the ﬁrst layer is 30 and the second layer is 60.
•For the second convolutional layer, 7×7 receptive ﬁelds. The stride for both convolutional
layers is 1.
•Convolved images are downsampled by a factor of 2 ×2 at each pooling operation.
•The learning rate for CNN is 0.01 and it was trained for 8 epochs.
5.2.7 Maxout Convolutional Neural Nets
We used the pylearn2 (https://github.com/lisa-lab/pylearn2) implementation of maxout
convolutional networks (Goodfellow et al., 2013). There are two convolutional layers in the
selected architecture, without any pooling. In the last convolutional layer, there is a maxout
non-linearity. The following were selected by cross-validation: learning rate, number of channels
for the both convolution layers, number of kernels for the second layer and number of units and
pieces per maxout unit in the last layer, a linearly decaying learning rate, momentum starting
from 0.5 and saturating to 0.8 at the 200’th epoch. Random search for the hyperparameters
was used to evaluate 48 diﬀerent hyperparameter conﬁgurations on the validation dataset. For
the ﬁrst convolutional layer, 8×8 kernels were selected to make sure that each Pentomino shape
ﬁts into the kernel. Early stopping was used and test error on the model that has the best
validation error is reported. Using norm constraint on the fan-in of the ﬁnal softmax units
yields slightly better result on the validation dataset.
As a result of cross-validation and manually tuning the hyperparameters we used the fol-
lowing hyperparameters:
•16 channels per convolutional layer. 600 hidden units for the maxout layer.
•6x6 kernels for the second convolutional layer.
35
•5 pieces for the convolution layers and 4 pieces for the maxout layer per maxout units.
•We decayed the learning rate by the factor of 0.001 and the initial learning rate is 0.026367.
But we scaled the learning rate of the second convolutional layer by a constant factor of
0.6.
•The norm constraint (on the incoming weights of each unit) is 1.9365.
Figure 19 shows the ﬁrst layer ﬁlters of the maxout convolutional net, after being trained
on the 80k training set for 85 epochs.
Figure 19: Maxout convolutional net ﬁrst layer ﬁlters. Most of the ﬁlters were able to learn
the basic edge structure of the Pentomino shapes.
5.2.8 Stacked Denoising Auto-Encoders
Denoising Auto-Encoders (DAE) are a form of regularized auto-encoder (Bengio et al., 2013).
The DAE forces the hidden layer to discover more robust features and prevents it from simply
learning the identity by reconstructing the input from a corrupted version of it (Vincent et al.,
2010). Two DAEs were stacked, resulting in an unsupervised transformation with two hidden
layers of 1024 units each. Parameters of all layers are then ﬁne-tuned with supervised ﬁne-
tuning using logistic regression as the classiﬁer and SGD as the gradient-based optimization
algorithm. The stochastic corruption process is binomial (0 or 1 replacing each input value,
with probability 0.2). The selected learning rate is ϵ0 = 0 .01 for the DAe and ϵ1 = 0 .1 for
supervised ﬁne-tuning. Both L1 and L2 penalty for the DAEs and for the logistic regression
layer are set to 1e-6.
CAE+MLP with Supervised Finetuning: A regularized auto-encoder which sometimes
outperforms the DAE is the Contractive Auto-Encoder (CAE), (Rifai et al., 2012), which
penalizes the Frobenius norm of the Jacobian matrix of derivatives of the hidden units with
respect to the CAE’s inputs. The CAE serves as pre-training for an MLP, and in the supervised
ﬁne-tuning state, the Adagrad method was used to automatically tune the learning rate (Duchi
et al., 2010).
After training a CAE with 100 sigmoidal units patch-wise, the features extracted on each
patch are concatenated and fed as input to an MLP. The selected Jacobian penalty coeﬃcient
is 2, the learning rate for pre-training is 0.082 with batch size of 200 and 200 epochs of un-
supervised learning are performed on the training set. For supervised ﬁnetuning, the learning
rate is 0.12 over 100 epochs, L1 and L2 regularization penalty terms respectively are 1e-4 and
1e-6, and the top-level MLP has 6400 hidden units.
36
Greedy Layerwise CAE+DAE Supervised Finetuning: For this experiment we stack a
CAE with sigmoid non-linearities and then a DAE with rectiﬁer non-linearities during the pre-
training phase. As recommended by Glorot et al. (2011b) we have used a softplus nonlinearity
for reconstruction, softplus(x) = log(1 + ex). We used an L1 penalty on the rectiﬁer outputs
to obtain a sparser representation with rectiﬁer non-linearity and L2 regularization to keep the
non-zero weights small.
The main diﬀerence between the DAE and CAE is that the DAE yields more robust recon-
struction whereas the CAE obtains more robust features (Rifai et al., 2011).
As seen on Figure 7 the weights U and V are shared on each patch and we concatenate the
outputs of the last auto-encoder on each patch to feed it as an input to an MLP with a large
hidden layer.
We used 400 hidden units for the CAE and 100 hidden units for DAE. The learning rate
used for the CAE is 0.82 and for DAE it is 9*1e-3. The corruption level for the DAE (binomial
noise) is 0.25 and the contraction level for the CAE is 2.0. The L1 regularization penalty for
the DAE is 2.25*1e-4 and the L2 penalty is 9.5*1e-5. For the supervised ﬁnetuning phase the
learning rate used is 4*1e-4 with L1 and L2 penalties respectively 1e-5 and 1e-6. The top-level
MLP has 6400 hidden units. The auto-encoders are each trained for 150 epochs while the whole
MLP is ﬁne-tuned for 50 epochs.
Greedy Layerwise DAE+DAE Supervised Finetuning: For this architecture, we have
trained two layers of denoising auto-encoders greedily and performed supervised ﬁnetuning
after unsupervised pre-training. The motivation for using two denoising auto-encoders is the
fact that rectiﬁer nonlinearities work well with the deep networks but it is diﬃcult to train
CAEs with the rectiﬁer non-linearity. We have used the same type of denoising auto-encoder
that is used for the greedy layerwise CAE+DAE supervised ﬁnetuning experiment.
In this experiment we have used 400 hidden units for the ﬁrst layer DAE and 100 hidden
units for the second layer DAE. The other hyperparameters for DAE and supervised ﬁnetuning
are the same as with the CAE+DAE MLP Supervised Finetuning experiment.
37


Peer review:
[Review]:
We have uploaded the revision of the paper to arxiv. The revision will be announced by Arxiv soon.