Learning Deep Architectures for AI

Yoshua Bengio

November 16th, 2007

Thanks to: James Bergstra, Aaron Courville,
Olivier Delalleau, Dumitru Erhan, Pascal Lamblin,
Hugo Larochelle, Jerome Louradour, Nicolas Le Roux,
Dan Popovici, Clarence Simard, Joseph Turian, Pascal
Vincent
DRAFT OF THIS PAPER AVAILABLE ON MY PAGE

Yoshua Bengio
Summary

Motivation: understanding intelligence, building AI, scaling

to large scale learning of complex functions
Decomposing problems into multiple levels
Insufficient Depth ⇒ poor generalization
Local estimators and curse of dimensionality
Training deep architectures
Greedy layerwise learning of multiple levels of abstractions
Restricted Boltzmann Machines and Contrastive Divergence
Deep Belief Networks
Continuation methods for optimizing deep architectures

Yoshua Bengio
Grand Goals: Understanding Intelligence, Building AI

Ambitious goal: using statistical learning to understand

intelligence, reach AI
Tasks involving intelligence: visual and auditory perception,
language understanding, intelligent control, long-term
prediction, discovering and understanding of high-level
abstractions...
Remain elusive!
Intelligence requires a lot of knowledge, implicit or explicit,
machine usable in new contexts.
Learning algorithms are meant to capture much of that
knowledge.

Yoshua Bengio
Machine Vision Example

• MAN abstraction corre-

sponds to convoluted set
of images (some very far
in pixel distance)
• multiple levels of repre-
sentation
• multiple levels of compu-
tation
• not clear which low &
intermediate-level abstrac-
tions are good
• want to learn represen-
tations at all levels
• low & intermediate rep-
resentations can be shared
across many tasks
Yoshua Bengio
Desiderata for Learning AI

Need learning algorithms with ability to

learn complex functions.

learn multiple levels of abstractions/features/representation.
learn in time ≈ linear in data set size
learn from mostly unlabeled data.
exploiting synergies across many tasks.
strong unsupervised learning.

Others not covered here: learning to represent context, actions →

delayed effects/reward, active learning.

Yoshua Bengio
Computation Graph and Depth

output
output
*
element neuron
element set
set sin
neuron neuron neuron
*
+
neuron
sin
... neuron neuron neuron
+ *
neuron
−
x a b
inputs inputs

Each node ∈ computations element set. Left: compute

x ∗ sin(a ∗ x + b), depth 4. Right: elements = artificial neurons
f (x) = tanh(b + w 0 x). Computes a multi-layer neural network of
depth 3.

Yoshua Bengio
Current Learning Algorithms: Depth

Depth = number of levels of composition of adaptable elements:

... ...
kernel machines: shallow
multi-layer neural networks:
usually shallow, can be deep?
decision trees: shallow
boosting: adds one level, but
generally shallow

Yoshua Bengio
Gist of Results on Depth of Architecture

When a function can be compactly represented by a deep

architecture, it may need a very large architecture to be
represented by an insufficiently deep one

Yoshua Bengio
Fast Fourier Transform = Deep Architecture

The Discrete Fourier Transform over a sequence of length n

can be computed in time O(n 2 ) with a depth 1 architecture
(complex matrix multiplication).
But it can be computed in time O(n log n) with a depth log n
architecture.
This is the FFT!
The trick: computations get re-used.

Yoshua Bengio
Theoretical Results on Depth of Architecture
Kinds of element sets discussed here:

Element set = gates {AND, OR} with optional input negation

Element set = linear threshold neuron {f : f (x) = w 0 x+b≥0 }

Very Well Known Result

A two-layer circuit of logic gates can represent any Boolean
function.

Well Known Result

With depth-two logical circuits, the majority of functions require
an exponential number of logic gates.

For example,
Example Result
Depth 2 logic gates circuits for d-bit parity have exponential size.
Yoshua Bengio
Theoretical Results on Depth of Architecture
Less Known Result
∃ functions computable with a polynomial-size logic gates circuit
of depth k that require exponential size when restricted to depth
k − 1.

Ok for logic gates circuit. Very different from architectures in

learning algorithms?
Monotone weighted threshold = neuron with positive weights.
Theorem
A monotone weighted threshold circuit of depth k − 1 computing a
function fk ∈ Fk,N has size at least 2cN for some constant c > 0
and N > N0 .

where Fk,N is a particular class of functions representable by a

depth k logic gate circuit (Hastad and Goldmann, 1991).
Yoshua Bengio
Local vs Non-Local Generalization

Local generalization: core of many learning algorithms

To infer f at x, look for training examples x i near x
Simple example: nearest neighbor classifier
Fails when target function varies a lot compared to how much
the training examples “fill the space”

training
examples
xi
Variations are not arbitrary: they
are caused by the structure of the
world and the laws of physics.
?
test example
x

(Bengio and Monperrus, 2005;

Bengio, Delalleau and Le Roux, 2006)
Yoshua Bengio
Smoothness Prior is Not Enough

Smoothness prior: assume target f more likely to be smooth,

i.e.,
if x ≈ y then f (x) ≈ f (y ).
Useful but unsufficient prior!
unfit to learn functions that vary a lot, e.g. needed for
complex AI tasks, e.g. natural language, machine translation,
general-purpose vision, robotics...
A problem with many learning algorithms, such as SVMs with
local kernel, manifold learning algorithms (LLE, ISOMAP,
kernel PCA), graph-based semi-supervised learning, decision
trees...

Yoshua Bengio
Local Learning Algorithms

Soft or hard partition of the space, where each learned parameter

associated to only one region of the partition.

With local kernel machine

X
f (x) = αi K (x, xi ),
i

and K (x, xi ) → 0 for x far from xi :

(αi , xi ) only influences f (x) for x near xi .

Yoshua Bengio
Mathematical Problem with Local Learning
Theorem
With K the Gaussian kernel and target f (·) changing sign at least
2k times along some straight line (i.e. that line crosses the decision
surface at least 2k times), then at least k examples are required.

Class −1

With local kernels, learn-

ing a function that has
decision surface many “bumps” requires as
Class 1
many examples as bumps.
(Bengio, Delalleau and Le Roux, 2006;
Bengio and Le Cun, 2007)

Yoshua Bengio
Mathematical Problem with Local Kernels

Theorem
With K the Gaussian kernel, and the goal
to learn a maximally changing binary
function (f (x) 6= f (x 0 ) when |x − x 0 | = 1)
with d inputs, then at least 2d−1 examples
are required.

⇒ need to cover the space of possibilities with examples

⇒ may require nb examples exponential in nb inputs
Other similar results in (Bengio, Delalleau and Le Roux, 2006), for
manifold learning and semi-supervised learning based on the
neighborhood graph.

Yoshua Bengio
Locally Linear Approximation of Manifolds

Set of images associated

with translating or
shrinking digit 4 image
forms smooth manifold
in space of image pixels
intensities.

Can be approximated
locally by linear patches.

But if highly curved

manifold, many patches
needed, exponentially
wrt dimension.

Yoshua Bengio
Decision Trees Partition the Space
x1<2

R1
x2<1
• A decision tree recur-
sively partitions the input
x2
x1<0.5 x1<1.25
space.

R3 R4 R5
R2
• In a binary tree, the
root node splits it in two.

R5
• Each node is associated
R4
with a region.
R1
1
1.25 • Separate parameters for
R2
each node.
R3

.5 2
x1

Yoshua Bengio
Decision Trees do not Generalize to New Variations!
If piece-wise constant approximation of f requires N pieces to
achieve error , then decision tree requires at least N examples to
obtain generalization error .
Corollary
Nb exemples required to train a constant-leaves decision tree can
grow exponentially with d (input dim.)

Theorem
On d-bits parity task, constant-leaves decision tree with
axis-aligned decision nodes requires at least 2 d (1 − 2)
examples to reach gen. error ≤ .

Proposition
A sum of n trees can represent a nb of piece-wise constant regions
exponential in n, whereas a single tree can only represent a number
of regions = nb of leaves.
Yoshua Bengio
Local vs Distributed Representation

Input x mapped to representation of x as intermediate step

before taking decision.
Consider representation a binary vector and two extremes:
1 With h independent binary features (distributed
representation) one can represent 2 h different input patterns
2 With h maximally dependent binary hidden units (e.g., all 0’s,
single 1), one can represent only h different input patterns

⇒ distributed representations can be exponentially more

efficient than local ones. (Bengio and Le Cun, 2007)

Yoshua Bengio
Clustering vs Multi-Clustering
• Clustering maps input x to category c learned by algorithm.
• Loss of information.
• Partitions input space, with separate parameters for each region
(prototype = center of region).
• Better: multi-clustering = map x to (c 1 , c2 , . . . , ck ) where ci a
category among i-th category set. k overlapping partitions.
• Can represent exponential number of configurations of x:
distributed representation. Partition 3
Partition 2
C1=1
C2=0
C3=0

C1=0
C2=0
C3=0
C1=0
C2=1 C1=0 Partition 1
C3=0 C2=1
C3=1

Yoshua Bengio
Optimizing Deep Architectures

Until 2006, we knew no way to train a deep neural net to

obtain better results than a shallow one (1 or 2 hidden
layer) (Tesauro, 1992), except for convolutional neural
nets (Bengio and Le Cun, 2007).
Training seemed to get stuck in sub-optimal solutions, local
minima or plateaus or just a too convoluted error surface.
We still do not know why deeper is ok for convolutional nets.
We still do not fully understand why it is so difficult to
optimize deep architectures by gradient-based techniques.
But DEPTH seems a necessary condition for statistical
efficiency!

Yoshua Bengio
Greedy Learning of Multiple Levels of Abstractions

Learning AI ⇒ learning abstractions

General principle: Greedily learning simple things first,
higher-level abstractions on top of lower-level ones.
Implicit prior (Bengio et al., 2007): restrict to functions that
1 can be represented as a composition of simpler ones such that
2 the simpler ones can be learned first (i.e., are also good models
of the data).
Coherent with psychological literature (Piaget, 1952).
We learn baby math before arithmetic before algebra before
differential equations . . .
Also some evidence from neurobiology: (Guillery, 2005) “Is
postnatal neocortical maturation hierarchical?”.

Yoshua Bengio
What happened in 2006?

Geoff Hinton, Simon Osindero and Yee-Wye Teh published a

Neural Computation paper on “A fast learning algorithm for Deep
Belief Nets” (2006), that introduces these ideas:

A deep unsupervised network could be trained greedily, layer

by layer.
Each layer tries to model its inputs.
Each layer outputs a representation of its input.
This unsupervised net is a good initialization for a supervised
net.

Presumably easier to learn “locally” (within each layer) than

having to coordinate all the layers in a deep network.

Yoshua Bengio
Restricted Boltzmann Machines

RBM = building block initializing each layer of Deep Belief Net

Undirected graphical model with hidden variables = learned
probabilistic representation of input of the layer.
With x and h binary vectors
X X e b0 x+c 0 h+h0 Wx
P(x) = P(x, h) =
Z
h h

where Z = normalization, parameters are θ = (b, c, W ). The

numerator can be computed tractably but not the denominator.
P(h|x) and P(x|h) easy to compute, not P(x).
Can use Gibbs sampling x1 ⇒ h1 ⇒ x2 ⇒ h2 ⇒ . . . to obtain
approximate sample from P(x) or P(x, h).
P(h|x) a distributed representation of x = multi-clustering.

Yoshua Bengio
RBMs are Universal Approximators
With enough hidden units any distribution can be represented
exactly: (paper to appear by Le Roux & Bengio)
Theorem
Any distribution over {0, 1}n can be approximated arbitrary well
with a RBM with k + 1 hidden units where k is the number of
input vectors whose probability is not 0.

Adding one hidden unit (with proper parameters) increases

log-likelihood:
Theorem
Let u be an arbitrary distribution over {0, 1} n and let P be a RBM
with marginal distribution p over the visible units such that
KL(u||p) > 0. Then there exists a RBM Q composed of P and an
additional hidden unit, with marginal distribution q over the visible
units such that KL(u||q) < KL(u||p).
Yoshua Bengio
Many Variants of RBMs Already

Conditional RBMs:
P represent
P(x|context) = h P(x, h|context) by making parameters of
RBM functions of context.
RBMs with 3-way interactions: used to capture flow in video.
RBMs with interactions between x’s: efficiently capture 2nd
order dependencies (image whitening)
Temporal RBMs: conditional RBMs where context = past h,
similar to HMMs but distributed hidden state.
Factored RBMs: factor parameter W to reduce
parametrization and learn a distributed representation for each
word in a language model.
Regularize to discrete encoding, used for learning a hash code
for documents in super-fast information retrieval system.

Yoshua Bengio
Training RBMs: Contrastive Divergence
Although exact computation of gradient ∂ log∂θP(x) in RBMs in
intractable, a stochastic and biased approximation works well:
Contrastive Divergence, requiring running t steps of Gibbs chain.
We proved that it corresponds to truncation of a converging series:
Theorem
Consider converging Gibbs chain x1 ⇒ h1 ⇒ x2 ⇒ h2 . . . The
log-likelihood gradient can be expanded in a converging series
t−1   
∂ log P(x1 ) X ∂ log P(xs |hs ) ∂ log P(hs |xs+1 )
= E + | x1
∂θ ∂θ ∂θ
s=1
 
∂ log P(xt )
+ E | x1
∂θ

with the terms in s converging to 0 as s → ∞, and the final term

(in t) also converges to 0, as t → ∞.
Yoshua Bengio
Deep Belief Net Model

DBN models joint distribution between observed x and ` hidden

layers hk :
`−2
!
Y
P(x, h1 , . . . , h` ) = P(hk |hk+1 ) P(h`−1 , h` )
k=1

where P(hk−1 |hk ) is parametrized like conditional in an RBM and

P(h`−1 , h` ) is an RBM.

Generative model: sample h`−1 from top-level RBM, then h`−2

from P(h`−2 |h`−1 ) . . . until x = h0 from P(h0 |h1 ).

Yoshua Bengio
Greedy Procedure Increases Likelihood

Form of DBN greedy layerwise procedure guaranteed to improved

likelihood at each step.

Condition: equal layer sizes on odd (even) layers, initialize each

new RBM with transpose W of previous layer.

Q = lower-level RBM probabilities (obtained w/ greedy procedure).

P = DBN probabilities.

log P(x) =
X
KL(Q(h|x)||P(h|x)) + HQ(h|x) + Q(h|x) (log P(h) + log P(x|h))
h

Yoshua Bengio
Experiments on Greedy Layer-Wise Initialization

(Bengio et al., 2007)

train. test.
Deep Belief Net, unsupervised pre-training 0% 1.2%
Deep net, auto-associator pre-training 0% 1.4%
Deep net, supervised pre-training 0% 2.0%
Deep net, no pre-training .004% 2.4%
Shallow net, no pre-training .004% 1.9%

Classification error on MNIST digits benchmark training,

validation, and test sets, with the best hyper-parameters according
to validation error.

Deep nets with 3 to 5 hidden layers.

Selects around 500 hidden units per layer.
Supervised greedy is too greedy.
Greedy unsupervised initialization works great.
Yoshua Bengio
Deep Networks vs SVMs

From top to bottom,

samples from rectangles
and rectangles-image
(Larochelle et al., 2007)

Gradually more complex tasks:

Dataset SVMrbf SVMpoly NNet DBN-1 SAA-3 DBN-3
mnist-basic 2.2% 2.9% 3.2% 3.0% 2.45% 2.4 %
mnist-rot 10.5% 12.7% 16.5% 12.7% 11.6% 12.9%
mnist-back-rand 14.1% 16.5% 19.4% 9.2% 11.4% 5.9%
mnist-back-img 22.5% 23.6% 29.2% 16.4% 23.3% 17.5%
mnist-rot-back-img 31.0% 36.0% 40.8% 31.4% 23.1% 26.9%
rectangles 2.43% 3.2% 7.9% 6.0% 2.1% 2.6%
rectangles-img 23.5% 24.2% 31.1% 23.4% 23.9% 22.0%
convex 19.1% 19.0% 27.7% 20.3% 18.9% 17.6%

Yoshua Bengio
A Curriculum for Training AIs?

Learning high-level abstractions is fundamentally difficult

(NP-hard in the worst case).
Experiments suggest that while trying to optimize directly a
deep architecture is difficult, one can first teach it the
lower-level concepts and once they are mastered show it
more advanced concepts based on previously learned ones.
Humans do not learn very abstract concepts early on! It takes
20 years of guided learning to obtain a math major!
Why should we expect computers to need less help?
Future AI research may require help from educators to design
an appropriate sequence of learning tasks for AIs.

Yoshua Bengio
Global Optimization though Continuation Methods

Continuation Methods: optimize a sequence of gradually less

smooth cost functions leading to target cost function.

Can prove that the greedy layer-wise approach to training

RBMs is a discrete continuation method. Adding each layer
removes a constraint.
A curriculum can be framed as a continuation method
(changing a sampling probability on examples according to
how difficult they currently are to learn).
Stochastic gradient descent from small parameters is nearly a
continuation method (with parameter norm as the smoothness
control).

Yoshua Bengio
Critical Mass Hypotheses

Two forms:

As we train with more and richer data, using models with

more and more capacity (but maybe not much more
sophisticated than current DBN technology), abstractions
that were apparently difficult to learn will be learned more
easily (because of the reinforcing signals from many sources
about the usefulness of these abstractions).
As we build better models, there will come a time when the
learning systems can take much better advantage of the
massive amount of image/video/text data available from
human culture (e.g. through the web).

Yoshua Bengio
Nailing the Semantics

What is missing from today’s AI and ML research? Nailing the

semantics.
What would be more impressive in terms of AI?

1 Beating all other language models by  in perplexity? or

2 Demonstrating a learning algorithm that can nail the
semantics of a “baby” virtual world (where current
state-of-the-art still fails miserably).

I vote for the 2nd: work with a small vocabulary, language data
associated with meaning (e.g., images).

Yoshua Bengio
The Baby AI Project
Learning multiple levels of representation / abstraction from
multiple modalities: language + video
Huge amounts of data → online learning
Deep architectures = multiple levels of abstractions (both
context and input)
necessary to avoid curse of dimensionality
Learn more abstract concepts on top of / after simpler ones
e.g. first simple static shapes, then video + naming actions &
movement
Teach the Baby AI with a sequence of tasks = curriculum
Use mostly unlabeled data, exploit the little labeled data as
hints
AI should understand semantics of language + images:
multi-modal architectures
We already have a data generator for a simple “block world” (at
different degrees of complexity) with images and natural language.
Yoshua Bengio
Baby AI Datasets

We created programs that gener-

ate artificial images and accompa-
nying text.
Images contain 1, 2, 3 or 4 objects
(2-D shapes).
Factors of variation: size, posi-
tion, rotation, shape, color, com-
binatorics over multiple objects.
As many examples as wanted can be generated.
Tasks are already very challenging for current learning algorithms.

Yoshua Bengio
Baby AI Datasets
Text is “natural language”-like. One or few sentences about the
image. Statement or question + answer pair.
Statement + image pairs can be used to set up match/nomatch
classification tests.
Question/answer pairs can be used to set up more standard
classification problems (question + image ⇒ answer) for
comparisons with state-of-the-art classifiers.
Topic Question given to the computer Answer
Color There is a small triangle. What color is it? Green
Shape What is the shape of the green object? Triangle
Location Is the blue square at the top or at the bottom? At the top
Size There is a triangle on the right.
Is it rather small or bigger? Small
Size (relative) Is the square smaller or bigger than the triangle? Bigger
Datasets and python scripts will soon be released on our web page.
Yoshua Bengio
Culture and Language as Optimization Techniques
Since optimizing brains is NP-hard and frought with local minima,
nature may well have used culture and language to make the whole
human species a large optimization machine for the space of
abstractions (= ideas) helpful to humans:

Abstractions that have worked in the past are taught to us

through language.
Human society (over generations) performs a random search
in the space of neurally implementable abstractions.
Language is a low-capacity discrete channel to hint at the
good abstractions previously discovered. Only high-level and
discrete abstractions can be verbalized.
We propagate what we believe are good ideas as well as our
new ideas (even more important).
We can only verify the utility of some of them...

Previous work in this direction: (Hutchins and Hazlehurst, 1995)

Yoshua Bengio
Conclusions

AI ⇒ learn high level abstractions efficiently

⇒ deep architectures (statistical efficiency)
Limitations of local or shallow learning algorithms
Optimizing deep architectures?
RBMs as building blocks of DBNs.
Contrastive Divergence approximation ok.
greedy layer-wise unsupervised, more generally continuation
methods.
Human analogies? curriculum + parallel search.

Yoshua Bengio
To Know More

Machine learning: Bishop’s book Pattern Recognition and

Machine Learning,
machine learning graduate classes in McGill and Montreal.
Review paper on deep architectures: Learning Deep
Architectures for AI available on my web page.
Just google Bengio or Geoff Hinton.

Yoshua Bengio
Bengio, Y., Delalleau, O., and Le Roux, N. (2006).
The curse of highly variable functions for local kernel machines.
In Weiss, Y., Schölkopf, B., and Platt, J., editors, Advances in Neural Information Processing Systems 18,
pages 107–114. MIT Press, Cambridge, MA.

Bengio, Y., Lamblin, P., Popovici, D., and Larochelle, H. (2007).

Greedy layer-wise training of deep networks.
In Schölkopf, B., Platt, J., and Hoffman, T., editors, Advances in Neural Information Processing Systems
19, pages 153–160. MIT Press.

Bengio, Y. and Le Cun, Y. (2007).

Scaling learning algorithms towards AI.
In Bottou, L., Chapelle, O., DeCoste, D., and Weston, J., editors, Large Scale Kernel Machines. MIT Press.

Bengio, Y. and Monperrus, M. (2005).

Non-local manifold tangent learning.
In Saul, L., Weiss, Y., and Bottou, L., editors, Advances in Neural Information Processing Systems 17.
MIT Press.

Guillery, R. (2005).
Is postnatal neocortical maturation hierarchical?
Trends in Neuroscience, 28(10):512–517.

Hastad, J. (1986).
Almost optimal lower bounds for small depth circuits.
In Proceedings of the 18th annual ACM Symposium on Theory of Computing, pages 6–20, Berkeley,
California. ACM Press.

Hastad, J. and Goldmann, M. (1991).

On the power of small-depth threshold circuits.
Computational Complexity, 1:113–129.

Hinton, G. (2002).
Training products of experts by minimizing contrastive divergence.
Neural Computation, 14:1771–1800.
Yoshua Bengio
Hinton, G. and Ghahramani, Z. (1997).
Generative models for discovering sparse distributed representations.
Philosophical Transactions of the Royal Society of London, B(352):1177–1190.

Hinton, G. E., Osindero, S., and Teh, Y. (2006).

A fast learning algorithm for deep belief nets.
Neural Computation, 18:1527–1554.

Hinton, G. E., Osindero, S., Welling, M., and Teh, Y.-W. (2006).
Unsupervised discovery of non-linear structure using contrastive backpropagation.
Cognitive Science, 30(4).

Hutchins, E. and Hazlehurst, B. (1995).

How to invent a lexicon: the development of shared symbols in interaction.
In Gilbert, N. and Conte, R., editors, Artificial Societies: the computer simulation of social life, pages
157–189. London: UCL Press.

Larochelle, H., Erhan, D., Courville, A., Bergstra, J., and Bengio, Y. (2007).
An empirical evaluation of deep architectures on problems with many factors of variation.
In Twenty-fourth International Conference on Machine Learning (ICML’2007).

Paccanaro, A. and Hinton, G. (2000).

Extracting distributed representations of concepts and relations from positive and negative propositions.
In Proceedings of the International Joint Conference on Neural Network, IJCNN’2000, Como, Italy. IEEE,
New York.

Piaget, J.-P. (1952).

The origins of intelligence in children.
International Universities Press, New York.

Tesauro, G. (1992).
Practical issues in temporal difference learning.
Machine Learning, 8:257–277.

Wegener, I. (1987).
The Complexity of Boolean Functions.
John Wiley & Sons.
Yoshua Bengio
Yao, A. (1985).
Separating the polynomial-time hierarchy by oracles.
In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pages 1–10.

Yoshua Bengio