Présentation à l’Université Laval, février 2013

Modélisation de la variété (manifold)supportant les données

avec auto-encodeurset densités non-normalisées
Pascal Vincent
Laboratoire d’Informatique des Systèmes d’Apprentissage

Département d'informatique et de recherche
opérationnelle

L’intelligence artificielle?
Historiquement deux approches en IA:

I.A. «Classique» : capacitéde raisonnement logique• Symbolique• Ex: systèmes experts• Ex: jeu d’échec

L’intelligence artificielle?
Historiquement deux approches en IA:

I.A. «Classique» : capacitéde raisonnement logique• Symbolique• Ex: systèmes experts• Ex: jeu d’échec

Apprentissage: capacitéd’apprendre, de s’adapter à
son environnement• Sub-symbolique• «Connexionniste»• S’inspire du cerveau:

réseaux de neurones• Algorithmes
d’apprentissage
automatiqueEx: succès de l’IA classique

Aux échecs
1770: «Le Turc mécanique»automate joueur d’échec

A gagné contre Napoléon Bonaparteet Benjamin Franklin

Un canular!

1997: Garry Kasparov contre «Deep Blue» d’IBM

Apprentissage automatique

Inspiration:cerveau qui apprend• 1011 neurones,
1014 synapses• Complexe réseau deneurones interconnectés• Apprentissage:
modifiersynapsesRéseau de neurones
artificiel

Modèle de neurone simplifié{fθ (x) = fw,b (x) = sigmoid( �w, x� + b)
non-linéarité, fonction d’activation1
logistic sigmoid(x) =1 + e−x

neurone de type sigmoide

w5

w2

b

w3 w4

x1 x2 x3 x4 x5
entrée (observation) x

1
couche de neuronesd’entréeI.A. apprenante:de la science-fiction...
• 1983: dans WarGames, unordinateur apprend en
jouant contre lui-même à
tic-tac-toe et “global
thermonuclear war”.

7à la réalité...
Au Backgammon• 1995: TD-gammon, un réseau deneurones artificiel entraîné enjouant 200 000 parties debackgammon contre lui-même,joue à un niveau équivalent aux
meilleurs joueurs mondiaux(Tesauro 1995).

8À Geopardy• Février 2011:
Watson, systèmed’IBM, bat leschampions
humains deGeopardy.
Fondé sur l’apprentissage
automatique à partir dedonnées textuelles.

9

Vision de l’Intelligence Artificielle
en 1957 (Rosenblatt, “Perceptron”)

Vision de l’Intelligence Artificielle
en 1957 (Rosenblatt, “Perceptron”)
InformatiqueIntelligence Artificielle
SymboliqueVision de l’Intelligence Artificielle
en 1957 (Rosenblatt, “Perceptron”)
InformatiqueIntelligence Artificielle
SymboliqueVision de l’Intelligence Artificielle
en 1957 (Rosenblatt, “Perceptron”)
InformatiqueIntelligence Artificielle
Symbolique

Neurosciences

Vision de l’Intelligence Artificielle
en 1957 (Rosenblatt, “Perceptron”)
InformatiqueIntelligence Artificielle
Symbolique

Neurosciences

Vision de l’Intelligence Artificielle
en 1957 (Rosenblatt, “Perceptron”)
InformatiqueIntelligence Artificielle
Symbolique

e
m
is es

n
on
r
o
xi eu

e de n ls)
nn x ieCo seauartific(ré

Neurosciences

Vision actuelle des disciplines
fondatrices
InformatiqueIntelligence Artificielle

Neurosciences

Vision actuelle des disciplines
fondatrices
InformatiqueIntelligence Artificielle
ls

cie
fi
i
t
r
a

es
n
o
r
s
eu
e
l
n
l
e
e
d
ion
x
t
&
u
a
t
a
pu
m
rése
o
sc
e
c
n
cie
s
o
r
neu

Neurosciences

Vision actuelle des disciplines
fondatrices
InformatiqueIntelligence Artificielle
ls

cie
fi
i
t
r
a

Statistiques

es
n
o
r
s
eu
e
l
n
l
e
e
d
ion
x
t
&
u
a
t
a
pu
m
rése
o
sc
e
c
n
cie
s
o
r
neu

Neurosciences

Vision actuelle des disciplines
fondatrices
InformatiqueIntelligence Artificielle
ls

cie
fi
i
t
r
a

es
n
o
r
s
eu
e
l
n
l
e
e
d
ion
x
t
&
u
a
t
a
pu
m
rése
o
sc
e
c
n
cie
s
o
r
neu

Statistiques

Neurosciences

PhysiqueVision actuelle des disciplines
fondatrices
InformatiqueIntelligence Artificielle
ls

cie
fi
i
t
r
a

es
n
o
r
s
eu
e
l
n
l
e
e
d
ion
x
t
&
u
a
t
a
pu
m
rése
o
sc
e
c
n
cie
s
o
r
neu

Statistiques

e
u
q
i
t
s
i
t
a
t
S
e
u
q
i
s
Phy

Physique

Neurosciences

Vision actuelle des disciplines
fondatrices
InformatiqueThéorie del’information

Intelligence Artificielle
ls

cie
fi
i
t
r
a

es
n
o
r
s
eu
e
l
n
l
e
e
d
ion
x
t
&
u
a
t
a
pu
m
rése
o
sc
e
c
n
cie
s
o
r
neu

Statistiques

e
u
q
i
t
s
i
t
a
t
S
e
u
q
i
s
Phy

Physique

Neurosciences

Vision actuelle des disciplines
fondatrices
InformatiqueThéorie del’information

Intelligence Artificielle

Opimisation+
Automatique

ls

cie
fi
i
t
r
a

es
n
o
r
s
eu
e
l
n
l
e
e
d
ion
x
t
&
u
a
t
a
pu
m
rése
o
sc
e
c
n
cie
s
o
r
neu

Statistiques

e
u
q
i
t
s
i
t
a
t
S
e
u
q
i
s
Phy

Physique

Neurosciences

Vision actuelle des disciplines
fondatrices
InformatiqueThéorie del’information

Intelligence Artificielle
Machine Learningurones

Statistiques

Opimisation+
Automatique

ls

cie
fi
i
t
r
a

s

le
ne
l
e
e
n
d
apprentissage
x
tio
&
u
a
t
a
u
e
mp
rés
o
c
automatique iences
sc
o
r
u
unee

iq
t
s
i
t
a
t
S
e
u
q
i
s
y
h
P

Physique

Neurosciences

Exemple d’apprentissage(supervisé)
Entrée X

Sortie f(X)Cible Y

sixdeux!

Ex: régression (1D)
Étiquette
10

EntréeEx: régression (1D)
Étiquette1

1. Collecter des données

0

EntréeEx: régression (1D)
Étiquette1

1. Collecter des données
0.7

0EntréeEx: régression (1D)
Étiquette1

1. Collecter des données
0.7

0.5

0

EntréeEx: régression (1D)
Étiquette
1
0.9

1. Collecter des données

0.7

0.5
0.4
0.25

0

EntréeEx: régression (1D)
Étiquette
1
0.9

1. Collecter des données

0.7

2. Estimer la fonction
Entrée ⟼ Étiquette

0.5
0.4
0.25

0

EntréeEx: régression (1D)
Étiquette
1
0.9

1. Collecter des données

0.7

2. Estimer la fonction
Entrée ⟼ Étiquette

0.5
0.4
0.25

0

EntréeEx: régression (1D)
Étiquette1

1. Collecter des données
2. Estimer la fonction
Entrée ⟼ Étiquette

0

EntréeEx: régression (1D)
Étiquette1

1. Collecter des données
2. Estimer la fonction
Entrée ⟼ Étiquette
3. Utiliser cette fonction
sur de nouvelles données

0

EntréeEx: régression (1D)
Étiquette1

1. Collecter des données
0.75

0.55

2. Estimer la fonction
Entrée ⟼ Étiquette
3. Utiliser cette fonction
sur de nouvelles données

0.25

0

EntréeContrôle de capacité
Model
Selection
Selectionet généralisation

capacité trop faible➩sous-apprentissage

capacité trop élevée➩sur-apprentissage

capacité optimale➩bonne généralisation

la performance sur l’ensemble d’entraînementn’est pas un bon estimé de la généralisation!
14

Données d’apprentissage:
Ensemble de n exemples

2

3

Ex: reconnaissanced’écriture: classificationde chiffres manuscrits

Données d’apprentissage:
Ensemble de n exemples

2

3

Ex: reconnaissanced’écriture: classificationde chiffres manuscrits
Point de test xDonnées d’apprentissage:
Ensemble de n exemples

2

3

Ex: reconnaissanced’écriture: classificationde chiffres manuscrits
Point de test xDonnées d’apprentissage:
Ensemble de n exemples

2

3

Ex: reconnaissanced’écriture: classificationde chiffres manuscrits
Point de test x

2 ou 3 ?

Données d’apprentissage:
Ensemble de n exemples

2

3

Ex: reconnaissanced’écriture: classificationde chiffres manuscrits
Point de test x

2 ou 3 ?

Apprendre n’est pas
simplement
mémoriser...

Données d’apprentissage:
Ensemble de n exemples

2

3

Ex: reconnaissanced’écriture: classificationde chiffres manuscrits
Point de test x

2 ou 3 ?

Apprendre n’est pas
simplement
mémoriser...
C’est être capablede généraliser!

Représentation des données
une image = un point dans un espace de haute dimension
x2?
ensemble de données= nuage de points
x1

Niveau de représentation
Aire V4

abstractions visuelles
de plus haut niveau

Aire V2

détecteurs de formes
primitives

Aire V1

détecteurs de bords

RétinepixelsPart I
Manifoldmodeling18

high-dimensional data

The curse ofdimensionality
There are 1096329 possible
200x200 RGB images.

are we doomed?
19

The manifold
hypothesis

Data density
contentrates near alower dimensional
manifold

The manifold
hypothesis

Data density
contentrates near alower dimensional
manifold

The manifold
hypothesis

Data density
contentrates near alower dimensional
manifold

Can shift the cursefrom high d to dM<< dManifold follows naturally fromcontinuous underlying factors(≈ intrinsic manifold coordinates)

Ex: pose parameters of a face

Ex: rotation, size of digits (+ line thickness, ...)dImage borrowed from University of Dayton Vision Lab website.

Such continuous factors are(part of) a meaningful represetation!
21

Modeling local tangent spaces
A non-linear manifold✤

Can be represented bypatchwork of tangent spaces✤

Yields local linear coordinate
systems (chart -> atlas)

22

Manifold
Parzenwindows(Vincent and Bengio, NIPS 2003)

23

Manifold
Parzenwindows(Vincent and Bengio, NIPS 2003)
p̂(x) =
x1

x2

n
�
1

n i=1

N (x; xi , Ci )Classical Parzen Windows
density estimator

23

Manifold
Parzenwindows(Vincent and Bengio, NIPS 2003)
p̂(x) =
x1

x2

n
�
1

n i=1

N (x; xi , Ci )Classical Parzen Windows
density estimator- Archetypal «non-parametric»
kernel density estimator- Isotropic Gaussian centered oneach training point- No sense of manifold direction- Probability mass allocated awayfrom manifold
23

Manifold
Parzenwindows(Vincent and Bengio, NIPS 2003)
p̂(x) =
x1

x2

n
�
1

n i=1

N (x; xi , Ci )Classical Parzen Windows

Manifold Parzen Windows

density estimator

density estimator- Archetypal «non-parametric»
kernel density estimator- Oriented Gaussian «pancake» centeredon each training point- Isotropic Gaussian centered oneach training point- Uses low-rank parametrization of Ci,
learned from nearest neighbors (local PCA)

- No sense of manifold direction- «Parametric» cousins:- Probability mass allocated awayfrom manifold

Mixtures of Gaussian pancakes (Hinton et al. 95)
Mixtures of Factor Analysers (Gharamani + Hinton 96)
Mixtures of Probabilistic PCA (Tipping + Bishop 99)
23

Non-local manifold Parzen windows(Bengio, Larochelle, Vincent, NIPS 2006)p̂(x) =n i=1

N (x; xi , σ 2 I){

Isotropic Parzen:n�
1

isotropic

24

Non-local manifold Parzen windows(Bengio, Larochelle, Vincent, NIPS 2006)

Manifold Parzen:(Vincent and Bengio, NIPS 2003)

p̂(x) =n i=1

N (x; xi , σ 2 I)

n
�
1

n i=1

{

p̂(x) =

isotropic

N (x; xi , Ci ){Isotropic Parzen:n�1dM high variance directions from PCA on k nearest neighbors

24Non-local manifold Parzen windows(Bengio, Larochelle, Vincent, NIPS 2006)

Manifold Parzen:p̂(x) =

(Vincent and Bengio, NIPS 2003)

n i=1

N (x; xi , σ 2 I){p̂(x) =

isotropicn�
1

N (x; xi , Ci )n�1

N (x; µ(xi ), C(xi ))

n i=1

{

Isotropic Parzen:n�
1Non-local manifold Parzen: p̂(x) =(Bengio, Larochelle, Vincent, NIPS 2006)

n i=1

{

dM high variance directions from PCA on k nearest neighborsdM high variance directions output by neural network
trained to maximize likelihood of k nearest neighbors24the others.
In this experiment, to make sure that NLMP focusses on the tangent
plane of the rotation
Non-local
manifold, we fixed the number of principal directions d = 1 and thenumber of nearest
MixtureofkParzenManifoldneighbors k = 1, and also imposed µ(·) = 0. The same was done for Manifold
Manifold Parzen.

ole
training
set.
leoletraining
trainingset.
set.
Gaussians

Windows

Parzenacross the whole training set.

Experiments on Classification by Density Estimation. The USPSParzen
data set was used
to perform a classification experiment. The original training set (7291) was split into a
training (first 6291) and validation set (last 1000), used to tune hyper-parameters. One
density estimator for each of the 10 digit classes is estimated. For comparison we also
show the results obtained with a Gaussian kernel Support Vector Machine (already usedin (Vincent and Bengio, 2003)). Non-local MP* refers to the variation described in (Bengio
and Larochelle, 2005), which attemps to train faster the components with larger variance.
The t-test statistic for the null hypothesis of no difference in the average classification
error on the test set of 2007 examples between Non-local MP and the strongest competitor(Manifold Parzen) is shown in parenthesis. Figure 4 also shows some of the invariant
transformations learned by Non-local MP for this task.

Note that better SVM results (about 3% error) can be obtained using prior knowledge about
image invariances, e.g. with virtual support vectors (Decoste and Scholkopf, 2002). However,aslearnedfar
as densities
weknow(sinus
the NLMP
performanceis thebest
onthe
original
USPS dataset
trationthelearneddensities(sinuson
top,
spiralonbottom)forfourcomstration
ration
ofof
ofthe
the
learneddensities(sinus
on
on
top,
top,
spiralspiralononbottom)bottom)
for
for
four
four
comcomFigure2:
Illustrationof the learned d
Use
in
Bayes
classifier
on
USPS
among
algorithms
that donot useParzen,
prior
knowledge
about
images.
From
leftright:
Non-Local
Manifold
Parzen,Gaussian
mixture,Parzen
.From
From
left
lefttoto
toright:right:Non-Local
Non-Local
Manifold
Manifold
Parzen,Gaussian
Gaussianmixture,
mixture,ParzenParzenpared models. From left to right: No
Algorithm
Valid.
Testmass
Hyper-Parameters
nifoldParzen.
ParzenWindows
wastesprobability
massthe
spheresaroundnifoldfold Parzen.
Parzen.Parzen
ParzenWindows
Windowswastes
wastesprobability
probability
massinininthe
thespheres
spheresaroundaroundWindows, Manifold Parzen. Parzen W
hileleavingmanyholes.
Gaussian
mixturestendchoosetoo
few
compoile
hileleaving
leavingmany
manyholes.
holes.Gaussian
Gaussian1.2%
mixturesmixturestend
tendtototochoose
choosetoo
toofew
few
compocompoeach
SVM
4.68%
C
= 100,σ point,= 8 while leaving many holeoverfitting.
The
Non-Local
Manifold
Parzenexploits
globalstructureyield
verfitting.
overfitting.The
TheNon-Local
Non-Local
Manifold
Manifold
ParzenParzenexploits
exploits
globalstructure
structure
yield
yield
ParzenWindows
1.8%
5.08%global
σtototo=0.8nents to avoid overfitting. The Non-Lo
ator.
tor.
ator.
the best estimator.
Manifold Parzen 0.9%
4.08%
d = 11, k = 11, σ02 = 0.1
Non-local
MP
0.6%isisismeant
3.64%(-1.5218)d = 7, kExperiments= 10, kµ =on
10,rotated digits. The
onrotateddigits.
The
nextexperiment
meant
show
both
qualitatively
nonrotatedrotateddigits.
digits.
The
Thenext
next
experimentexperiment
meant
tototoshow
showbothbothqualitatively
qualitatively2
σ= 0.05,nhid = 70 the power of non-lo
vely
the
power
of
non-local
learning,
by
using
9
classesofrotated
digit
ely
vely
the
thepower
powerofofnon-local
non-locallearning,learning,bybyusing
using9 9classes
classesofofrotatedrotateddigit
digitimages
imagesand quantitatively
0imagesNon-local
MP* set)0.6%
3.54%(-1.9771)
d =and7,k(from= 10,= examples
4,
the
USPS
training
set)
learn
about
the
rotation
manifoldandexamplestexamplesexamplesofof
ofthe
theUSPS
USPStraining
training
set)
tototolearn
learnabout
aboutthetherotationrotationmanifold
manifoldand729kµfirstof the USPS
2rotatedleft-outclass(digit
1),
not
used
for
training.
Eachtraining
digitwas25 1),
eft-out
left-outclassclass(digit(digit1),1),notnotusedusedforfortraining.
training.Each
Eachtraining
trainingdigit
digitwaswasrotatedtesting on the left-out class (digit
σrotated0 = 0.05, nhid = 30

What do most «manifold learning»approaches have in common ?
Purely non-parametric:•Manifold Parzen, LLE, Isomap, Laplacian eigenmaps, t-SNE, ...
Learn parametrized function:•Parametric t-SNE, semi-supervised embedding, non-local manifold Parzen, ...

?

26

Neighborhood-based training!
✤

Most explicitly use
neighborhoods.

✤

Training with k-nearest
neighbors, or pairs of points.

✤

Typically Euclidean neighbors✤

But in high d, your nearest
Euclidean neighbor can bevery different from you...
27

bl

e

!

Neighborhood-based training!
Most explicitly use
neighborhoods.

✤

Training with k-nearest
neighbors, or pairs of points.

✤

Typically Euclidean neighbors

U

✤

nr
el

ia

✤

But in high d, your nearest
Euclidean neighbor can bevery different from you...
27

PART II
On Auto-Encoders
their regularization,and their link with manifolds.

28

Auto-Encoders (AE)hidden representation h = h(x)∈R

Decoder:g

Encoder:hinput x ∈ Rd
reconstruction errordhreconstruction r = g(h(x))

L(x, r)
Minimize

JAE =

�

x∈D

L(x, g(h(x))
29Auto-Encoders (AE)
Typical form
hidden representation h = h(x)∈R

Decoder:g

Encoder:hinput x ∈ Rd
reconstruction errordhreconstruction r = g(h(x))

L(x, r)
Minimize

JAE =

�

x∈D

L(x, g(h(x))
29Auto-Encoders (AE)
Typical form
hidden representation h = h(x) = s(W x + b)

∈R

Decoder:g

Encoder:hinput x ∈ Rd
reconstruction errordhreconstruction r = g(h(x))

L(x, r)
Minimize

JAE =

�

x∈D

L(x, g(h(x))
29Auto-Encoders (AE)
Typical form
hidden representation h = h(x) = s(W x + b)

∈R

Decoder:g

Encoder:hinput x ∈ Rd
reconstruction errordhreconstruction r = g(h(x))

L(x, r)�= sd (W h + bd )Minimize

JAE =

�

x∈D

L(x, g(h(x))
29Auto-Encoders (AE)
Typical form
hidden representation h = h(x) = s(W x + b)

∈R

Decoder:g

Encoder:hinput x ∈ Rd
reconstruction errordhreconstruction r = g(h(x))
�= sd (W h + bd )L(x, r)2

squared error: �x − r�or Bernoulli cross-entropy

Minimize

JAE =

�

x∈D

L(x, g(h(x))
29Regularized robust auto-encoders
Principle: reconstruction and representation
should be robust to input perturbations✤

Denoising Auto-Encoder (DAE)(Vincent, Larochelle, Bengio, Manzagol, ICML 2008)

uses stochastic input perturbations✤

Contractive Auto-Encoder (CAE)(Rifai, Vincent, Muller, Glorot, Bengio, ICML 2011)
uses analytic penalty (penalizes input sensitivity)✤

Both can learn over-complete representations (dh>d)✤Related to training Gaussian RBM via regularized score matching30

Denoising auto-encoder (DAE)features:(hidden representation)h = h(x)Decoder:g

Encoder:hcorrupted input~

reconstruction
error

~ ~
x̃

noise

q(x̃|x)L(x, r)reconstruction

input

r = g(h(x))

x
31

S

Learned filters

Figure 5 displays filters learnt by a regularof 50 hidden units, as well as those learnt by an
Filters obtained in the under-complete case loo
apparent in the filters learnt in the over-comple

V INCENT, L AROCHELLE, L AJOIEa fixed learning rateVofINCENT
0.05. All , L AROCHELLE , L AJOIE, B ENGIOAND M ANZAGOL
weights
similarresults. patchesa) yielded
Naturalimagee.g.:
oencoder that used a bottleneck
encoder using 200 hidden units.
b detectors. No clear structure isAE

Left: some of the 12 × 12 image
lar under-complete autoencodern error. Right: filters learnt by ahe under-complete autoencoders. Filters obtained in the overtirely random.

AE with weight decay

DAE

Figure 5: Regular autoencoder trained on natu
patches used for training. Middle: fi(50 hidden units) using tied weights
regular over-complete autoencoder (appears to learn rather uninteresting
complete case have no recognizable

We then trained 200 hidden units over-co32

(a) SAE

Learned filters(b) SDAE(a) SAE(b) SD(a) SAE , L AJOIE , B ENGIO AND M ANZAGOLV INCENT, L AROCHELLEb) MNIST digits

e.g.:

DAE

AE

(b) SDAE(a)Increasing
No corruption noise(b) 25%(c) DBN(a) No corruption(d) Neuron A (0%, 10%, 20%, 50% corruption)(b) 25% corruption(c) 50% corruption(c) DBN

Figure 8: Filters(c) learnt
DBN by denoising autoencode
Figure 15: Variability of the samplesshow
generatedwith
3-hidden-laye
some
of
the
filterslearnt by den(c) DBNmodels.
Each sub-figure
be readthlevels!.is toFilters
at therow-wise:same positio
Figure 15: Variability of trained
the samples
generatedwith
3-hidden-layer
SAE,
SDAE
that
the
autoencoders
werestarted pa
frois Eacha training
set
pattern.
Following
the 3-hidden-layer
samplegeneration
trainedmodels.
sub-figure
is
to
be
read
row-wise:theleftmost
Figure15:
Variabilityofthesamples
generated
withSA(d) Neuron A (0%, 10%, 20%, 50% corruption)(e) Neuron
B (0%,
50% corruption)
space.
(d)10%,
and 20%,(e) zoom
in on the filteprovided
as
input
to
the
network
andits
top-layer
represset ofpattern.
Following
the sample
generation
depicted
trainedmodels.
Each sub-figure
is
to
be
read
row-wise:theinlefFigure is15:a training
Variability
the samples
generatedwith
3-hidden-layer
SAE,with no noise, many filters remain
siSF
terministicbottomup
encoding.
Patterns
togeneration
itsAstheright
were
asamodels.
input
to Eachtheanditstorandom
top-layer
representation
wasFigure 8: Filtersprovided
learntby denoising
autoencoder
on MNIST
zero-masking
noise.
(a-c)
istraining
set network
pattern.
Followingthesampledepc
grey
patches).
weleftmo
increasetrainedsub-figure
isdigits,
beusingreadrow-wise:
given
that
top tolevel
representation.
SDAE
trainedshow terministic
someisofathe
filterslearntbydenoisingtrainedwithvariouscorruption
to
more,
and
capturemobottomup
encoding.
Patterns
todifferentiate
its
right
were
then
generate
providedas
input
theautoencoders
network
anditsClearly,
top-layer
representat
training
set
pattern.
Followingthesamplegeneration
depictedlevelsgiven!. Filtersat thesame
positionhighin thethree
imagesarefrom
relatedonly
byexpected.
thefact
inducelesslocal
filters,astoregeneratequalitysamples
their
high
level
rew
that
top
level
representation.
Clearly,
SDAE
trainednetworks,
liketerministicbottomup
encoding.
Patterns
to
its
right
were
then
provided
as
input
to
the
network
andits
top-layer
representation
33
that the autoencoders werestartedthealsosameappear
randominitializationpoint
in parameter
localtoblob
strokedetecto
SDAE
andfrom
DBNs
givedetectors,
rise toatosimilarlevel

corruption(c) 50% corruption(b) 25% corruption

to regeneratequalityfromtheirClearly,
highrepresentation,
givenhighthat
top level
representation.
SDAE
trainedterministicbottomupsamples
encoding.
Patterns
to itslevel
right
were
thennetwgenDenoising auto-encoder (DAE)(Vincent, Larochelle, Bengio, Manzagol, ICML 2008)✤

DAE learns to «project back» corrupted input onto manifold.

✤

Representation h ≈ location on the manifold
Corrupted input!"#$"%&'()*!+',&-$.-'./")/'&.')"&)&+$0'"&1#*'.,#$.)+&
2*).#3$+14&&
Corrupted input

original
input
34

Contractive Auto-Encoder (CAE)(Rifai, Vincent, Muller, Glorot, Bengio, ICML 2011)✤

Minimize

JCAE =

n
�

x∈D

�
�2
� ∂h(x) ��L(x, g(h(x)) + λ �� ∂x �

Reconstruction✤

Contraction

For training examples, encourages both:➡ small reconstruction error➡ representation insensitive to small variations around example

With a sigmoid layer, penalty is easy and cheap to compute:∂hj(x) = hj (x)(1 − hj (x))Wj∂xCAE must capture manifold directions
JCAE =

n
�

x∈D

�
�2
� ∂h(x) ��L(x, g(h(x)) + λ �� ∂x �

Reconstruction⇐ tradeoff ⇒Contraction(warning: may require tied weights) pressure to be insensitive

to all directions

CAE must capture manifold directions
JCAE =

n
�

x∈D

�
�2
� ∂h(x) ��L(x, g(h(x)) + λ �� ∂x �

Reconstruction⇐ tradeoff ⇒Contraction(warning: may require tied weights) pressure to be insensitive

to all directions

CAE must capture manifold directions
JCAE =

n
�

x∈D

�
�2
� ∂h(x) ��L(x, g(h(x)) + λ �� ∂x �

Reconstruction⇐ tradeoff ⇒Contraction(warning: may require tied weights) pressure to be insensitive

to all directions

CAE must capture manifold directions
JCAE =

n
�

x∈D

�
�2
� ∂h(x) ��L(x, g(h(x)) + λ �� ∂x �

Reconstruction⇐ tradeoff ⇒Contraction(warning: may require tied weights) pressure to be insensitive

to all directions

CAE must capture manifold directions
JCAE =

n
�

x∈D

�
�2
� ∂h(x) ��L(x, g(h(x)) + λ �� ∂x �

Reconstruction⇐ tradeoff ⇒Contraction(warning: may require tied weights) pressure to be insensitive

to all directions

CAE must capture manifold directions
JCAE =

n
�

x∈D

�
�2
� ∂h(x) ��L(x, g(h(x)) + λ �� ∂x �

Reconstruction⇐ tradeoff ⇒Contraction(warning: may require tied weights) pressure to be insensitive

to all directions

Learned tangent space✤∂h
Jacobian Jh (x) =(x) measures∂x
sensitivity of h locally around x✤

CAE captures the structure of
the manifold by defining anatlas of charts.

SVD:

Top singular vectors are tangent
directions to which h is most sensitive.

37

SVD of∂hJh (x) =(x)∂x
CIFAR!10Jacobian singular values

1.5

AE
CAE

1

0.5

0

100

200

300 400 500# singular values

600

700

800
38

Learned tangents CIFAR-10
Tangents}

Input Point

Local PCA (as e.g. in Manifold Parzen)

Contractive Auto-Encoder (singular vectors of Jh(x) )Not based on explicit neighbors or pairs of points!

Learned tangents CIFAR-10
Tangents}

Input Point

Local PCA (as e.g. in Manifold Parzen)

Contractive Auto-Encoder (singular vectors of Jh(x) )Not based on explicit neighbors or pairs of points!

How to exploit the learned tangents✤

Simard et al, 1993 exploited tangents derived from prior-knowledge ofimage deformations we can use our learned tangents instead.

✤

Use them to define tangent distance to use
in your favorite distance (k-NN) or kernel-based classifier...

✤

Use them with tangent propagation when fine-tuning a deep-net
classifier to make class prediction insensitive to tangent directions.

(Manifold Tangent Classifier, Rifai et al. NIPS 2011) 0.81% on MNIST✤Moving preferably along tangents
allows efficient quality sampling(Rifai et al. ICML 2012)

33
40

How to exploit the learned tangents✤

Simard et al, 1993 exploited tangents derived from prior-knowledge ofimage deformations we can use our learned tangents instead.

✤

Use them to define tangent distance to use
in your favorite distance (k-NN) or kernel-based classifier...

✤

Use them with tangent propagation when fine-tuning a deep-net
classifier to make class prediction insensitive to tangent directions.

(Manifold Tangent Classifier, Rifai et al. NIPS 2011) 0.81% on MNIST✤Moving preferably along tangents
allows efficient quality sampling(Rifai et al. ICML 2012)33
40

Results: MNIST(standard split)

Models invariant to random feature permutation
i.e. no domain knowledge, except LeNet
LeNet

K-NN NNSVM DBN CAE DBM CNN MTC

3,09% 1,60% 1,40% 1,17% 1,04% 0,95% 0,95% 0,81%41

PART III

Ongoing work,
thoughts and speculation
42

Probability density modelingof data that follows the manifold hypothesis

Example:

x2

x1
43

What do these inductive principles yield✤

Maximum likelihood✤

Contrastive Divergence✤

Score Matchinge-E(x)

when applied to a modelof very high capacity

?

x2

x1

44

They tend to a Dirac comb!
Common fitting procedures increaseprobability at training points
e-E(x)
lower it everywhere else...

➪ Dirac comb

x2

x1

45

They tend to a Dirac comb!
Common fitting procedures increaseprobability at training points
e-E(x)
lower it everywhere else...

➪ Dirac comb

x2

The Porcupine effect!

x1

45

Ex: score matching(Hyvärinen 2005)

Learn energy function by minimizing:

��
�
�
d
2
2
� � ∂E
�
�
∂
E
�
� −
JSM (θ) =
(x)
(x)
2
� ∂x
�
∂x
i
i=1
x∈D

46

Ex: score matching(Hyvärinen 2005)

Learn energy function by minimizing:

��
�
�
d
2
2
� � ∂E
�
�
∂
E
�
� −
JSM (θ) =
(x)
(x)
2
� ∂x
�
∂x
i
i=1
x∈D

�JE (x)�2

46

Ex: score matching(Hyvärinen 2005)

Learn energy function by minimizing:

��
�
�
d
2
2
� � ∂E
�
�
∂
E
�
� −
JSM (θ) =
(x)
(x)
2
� ∂x
�
∂x
i
i=1
x∈D

�JE (x)�2

First derivative encouraged to be small: ensures
training points stay close to local minima of E

46

Ex: score matching(Hyvärinen 2005)

Learn energy function by minimizing:

��
�
�
d
2
2
� � ∂E
�
�
∂
E
�
� −
JSM (θ) =
(x)
(x)
2
� ∂x
�
∂x
i
i=1
x∈D

�JE (x)�2

Laplacian

Tr(HE (x))

First derivative encouraged to be small: ensures
training points stay close to local minima of E

46

Ex: score matching(Hyvärinen 2005)

Learn energy function by minimizing:

��
�
�
d
2
2
� � ∂E
�
�
∂
E
�
� −
JSM (θ) =
(x)
(x)
2
� ∂x
�
∂x
i
i=1
x∈D

�JE (x)�2

First derivative encouraged to be small: ensures
training points stay close to local minima of E

Laplacian

Tr(HE (x))

Encourage large positive
curvature in all directions

46

Ex: score matching(Hyvärinen 2005)

Learn energy function by minimizing:

��
�
�
d
2
2
� � ∂E
�
�
∂
E
�
� −
JSM (θ) =
(x)
(x)
2
� ∂x
�
∂x
i
i=1
x∈D

�JE (x)�2

First derivative encouraged to be small: ensures
training points stay close to local minima of E

Laplacian

Tr(HE (x))

Encourage large positive
curvature in all directions

E(x)

x

46

Ex: score matching(Hyvärinen 2005)

Learn energy function by minimizing:

��
�
�
d
2
2
� � ∂E
�
�
∂
E
�
� −
JSM (θ) =
(x)
(x)
2
� ∂x
�
∂x
i
i=1
x∈D

Laplacian

Tr(HE (x))

�JE (x)�2

First derivative encouraged to be small: ensures
training points stay close to local minima of E
E(x)e-E(x)

Encourage large positive
curvature in all directions

x2

sharply peaked
densityxx1

46

Unseen porcupine ?
✤Porcupine corresponds tomany 0d manifolds.

✤

We don’t usually see him
because parametrized models
are very constrained.

✤

He may be lurking for when we
increase capacity...

Could we define a non-parametric priorpreference towards >0-dimensional
manifolds ?
47

A manifold inductive bias
for learning an Energy function E

Can we bias the training criteria towards modeling a manifold structure?
Score matching

Manifold bias

48

A manifold inductive bias
for learning an Energy function E

Can we bias the training criteria towards modeling a manifold structure?
Score matching

Manifold bias✤

Encourages large «curvature»of E in all directions:✤

By maximizing Laplacian

Tr(HE (x)) =

d
�

λi

i=1

∂2E
HE (x) =
(x)
2
∂x
48

A manifold inductive bias
for learning an Energy function E

Can we bias the training criteria towards modeling a manifold structure?
Score matching

Manifold bias✤

Encourages large «curvature»of E in all directions:✤

By maximizing Laplacian

Tr(HE (x)) =

d
�

λi

i=1

eigenspectrumof HE (x)∂2E
HE (x) =
(x)
2
∂x
48

A manifold inductive bias
for learning an Energy function E

Can we bias the training criteria towards modeling a manifold structure?
Score matching

Manifold bias✤

Encourages large «curvature»of E in all directions:✤

By maximizing Laplacian

Tr(HE (x)) =
o
s
I

o
r
t

c
i
p

d
�

λi

i=1

eigenspectrumof HE (x)∂2E
HE (x) =
(x)
2
∂x
48

A manifold inductive bias
for learning an Energy function E

Can we bias the training criteria towards modeling a manifold structure?
Score matching

Manifold bias✤

Encourages large «curvature»of E in all directions:✤

By maximizing Laplacian

Tr(HE (x)) =
o
s
I

o
r
t

c
i
p

d
�

λi

i=1

eigenspectrumof HE (x)

E(x)

0c
ur
v

at

ur
e

di
re
ct
io

n

∂2E
HE (x) =
(x)
2
∂x
48

A manifold inductive bias
for learning an Energy function E

Can we bias the training criteria towards modeling a manifold structure?
Score matching✤✤

Manifold bias

Encourages large «curvature»of E in all directions:✤

Tr(HE (x)) =
o
s
I

o
r
t

c
i
p

λi

i=1

eigenspectrumof HE (x)∂2E
HE (x) =(x)
2∂x

Instead encourage- near zero curvaturein ≈dM directions
0cur- target positivevaturecurvature C indirectremaining d-dM directionsio

By maximizing Laplacian
d
�

E(x)

✤

n

by encouraging
λ ≈ (C, . . . , C , 0, . . . , 0)
� �� � � �� �
d−dM

dM

48

A manifold inductive bias
for learning a representation h

Can we bias the training criteria towards modeling a manifold structure?

Contractive autoencoder penalty Manifold bias

49

A manifold inductive bias
for learning a representation h

Can we bias the training criteria towards modeling a manifold structure?

Contractive autoencoder penalty Manifold bias✤

Encourages insensitivity ofrepresentation in all directions:

By penalizing Jacobian normd��Jh (x)�2F = Tr(Jh JhT ) =
λi

✤

i=1

∂h
Jh (x) =
(x)
∂x

49

A manifold inductive bias
for learning a representation h

Can we bias the training criteria towards modeling a manifold structure?

Contractive autoencoder penalty Manifold bias✤

Encourages insensitivity ofrepresentation in all directions:

By penalizing Jacobian normd��Jh (x)�2F = Tr(Jh JhT ) =
λi

✤

i=1

∂h
Jh (x) =(x) squared singular value∂xspectrum of Jh (x)49A manifold inductive bias
for learning a representation h

Can we bias the training criteria towards modeling a manifold structure?

Contractive autoencoder penalty Manifold bias✤

Encourages insensitivity ofrepresentation in all directions:

By penalizing Jacobian normd��Jh (x)�2F = Tr(Jh JhT ) =
λi

✤

i=1

∂h
Jh (x) =(x) squared singular value∂xspectrum of Jh (x)

o
s
I

o
r
t

c
i
p
49

A manifold inductive bias
for learning a representation h

Can we bias the training criteria towards modeling a manifold structure?

Contractive autoencoder penalty Manifold bias✤

Encourages insensitivity ofrepresentation in all directions:

By penalizing Jacobian normd��Jh (x)�2F = Tr(Jh JhT ) =
λi

✤

i=1

∂h
Jh (x) =(x) squared singular value∂xspectrum of Jh (x)

o
s
I

o
r
t

c
i
p

Encourages 0 dim.
«manifolds»

49

A manifold inductive bias
for learning a representation h

Can we bias the training criteria towards modeling a manifold structure?

Contractive autoencoder penalty Manifold bias✤

✤ Instead encourage
Encourages insensitivity ofrepresentation in all directions: - representation sensitive to

By penalizing Jacobian normd��Jh (x)�2F = Tr(Jh JhT ) =λi✤≈dM input directions- insensitive to remaining d-dM
directions

i=1✤ by encouraging∂hJh (x) =(x) squared singular value∂xspectrum of Jh (x)

o
s
I

o
r
t

c
i
p

Encourages 0 dim.
«manifolds»λ ≈ (1, . . . , 1, 0, . . . , 0)
� �� � � �� �
dM

d−dM

49

How to encourage this kind of spectrumλ ≈ (1, . . . , 1, 0, . . . , 0)in practice� �� � � �� �
dM

d−dM

Manifold Autoencoder:T✤ Encourage J to be a partial isometry: Jh J
h Jh ≈ Jh
will ensure that singular values are close to either 1 or 0.
✤

Encourage sum of squared singular values to be close to target dMd�λi = Tr(Jh JhT ) = �Jh (x)�2F ≈ dM
i=150

How to encourage this kind of spectrumλ ≈ (1, . . . , 1, 0, . . . , 0)in practice� �� � � �� �
dM

d−dM

Manifold Autoencoder:T✤ Encourage J to be a partial isometry: Jh J
h Jh ≈ Jh
will ensure that singular values are close to either 1 or 0.
✤

Encourage sum of squared singular values to be close to target dMd�λi = Tr(Jh JhT ) = �Jh (x)�2F ≈ dM
i=1

Penalty, added to reconstruction error:

Contractive Autoencoder: Manifold Autoencoder:50How to encourage this kind of spectrumλ ≈ (1, . . . , 1, 0, . . . , 0)in practice� �� � � �� �
dM

d−dM

Manifold Autoencoder:T✤ Encourage J to be a partial isometry: Jh J
h Jh ≈ Jh
will ensure that singular values are close to either 1 or 0.
✤

Encourage sum of squared singular values to be close to target dMd�λi = Tr(Jh JhT ) = �Jh (x)�2F ≈ dM
i=1

Penalty, added to reconstruction error:

Contractive Autoencoder: Manifold Autoencoder:γ�Jh (x)�2F
o
s
I

o
r
t

c
i
p
50

How to encourage this kind of spectrumλ ≈ (1, . . . , 1, 0, . . . , 0)in practice� �� � � �� �
dM

d−dM

Manifold Autoencoder:T✤ Encourage J to be a partial isometry: Jh J
h Jh ≈ Jh
will ensure that singular values are close to either 1 or 0.
✤

Encourage sum of squared singular values to be close to target dMd�λi = Tr(Jh JhT ) = �Jh (x)�2F ≈ dM
i=1

Penalty, added to reconstruction error:

Contractive Autoencoder: Manifold Autoencoder:γ�Jh (x)�2F
o
s
I

o
r
t

c
i
p

�

γ1 �Jh (x)�2F − dM

�2

+ γ2 �Jh JhT Jh − Jh �2F

50How to encourage this kind of spectrumλ ≈ (1, . . . , 1, 0, . . . , 0)in practice� �� � � �� �
dM

d−dM

Manifold Autoencoder:T✤ Encourage J to be a partial isometry: Jh J
h Jh ≈ Jh
will ensure that singular values are close to either 1 or 0.
✤

Encourage sum of squared singular values to be close to target dMd�λi = Tr(Jh JhT ) = �Jh (x)�2F ≈ dM
i=1

Penalty, added to reconstruction error:

Contractive Autoencoder: Manifold Autoencoder:

o
s
I

o
r
t

c
i
p

�

γ1 �Jh (x)�2F − dM

�2

+ γ2 �Jh JhT Jh − Jh �2F{γ�Jh (x)�2F

or computationally more�Jh JhT Jh � − Jh ��2F
efficient stochastic probe:� random vector (or matrix)
50

Preliminary proof of concept result
target dM=100
sharp drop-off

student:
Hani Almousli51

Is this enough?
✤Now instead of a Porcupine (dimension 0 peaks)
we can get a Pangolin (dM dimensional scales) !!!
e-E(x)

x2
Ex: dM=1

x1✤

Not guaranteed to be oriented along manifold!

✤

How can this be fixed?
52

Is this enough?
✤Now instead of a Porcupine (dimension 0 peaks)
we can get a Pangolin (dM dimensional scales) !!!
e-E(x)

x2
Ex: dM=1

x1✤

Not guaranteed to be oriented along manifold!

✤

How can this be fixed?
52Additional requirement: smoothness✤

Additional requirement: smoothness of Jh(x) or HE(x)✤may be (partially?) induced by model parametrization✤

can be added to criterion as in e.g.
Higher Order Contractive Autoencoders (CAE+H)(Rifai, Mesnil, Vincent, Muller, Bengio, Dauphin, Glorot; ECML 2011)

�

E�∼N (0,σ2 ) �Jh (x) − Jh (�)�Additional smoothness penalty

2

�

53

Efficient parametrization of hugetangent spaces patchwork✤

Modeling tangent spaces of real world data
may require a huge patchwork✤

Ex: Combinatorial explosion of tangent spaces
due to combinatorial possibilities of
movements of objects in a scene✤

Rather than a big mixture of PPCA or FA(like manifold Parzen) with indep. params.
E(x)Use a product of mixtures!

✤

These yield gigantic combinatorial mixture
with shared parameters.

✤=> RBMs with low-rank Gaussian covariancex
parametrizations.

ex: billiard

54

And then what?

Stitching together the patchwork✤

Large representations =distributed representations oflocal tangent spaces.

✤

Having a good model oftangent spaces...

✤

How can we go beyond local
coordinate systems?

✤

To synthesize more global
continuous coordinates?
55

Thank you to past and current students
who did most of the hard work

Hugo Larochelle Isabelle Lajoie

Salah Rifai

Xavier Muller Grégoire Mesnil Yann Dauphin Hani Almousli

and to my colleague and mentor

Questions?

Yoshua Bengio

56