Apprentissage Supervisé

Stephan Clémençon,
[Link]@[Link]

Telecom ParisTech, Paris, France

 Introduction

Sommaire

2/1
 Introduction

Intervenants

Stephan Clémençon (Telecom ParisTech - STA)

Contact : [Link]@[Link]
Profil : Enseignement/Recherche/Conseil/Industrie
Web : http ://[Link]/∼clemenco/
Mots-clés : processus stochastiques (markoviens, empiriques,
etc.), apprentissage statistique, applications : finance, high
tech, biosciences

3/1
 Introduction

Session 2 - Apprentissage Supervisé

Algorithmes de Classification
Moyennes locales, arbres de classification
Perceptron, SVM et réseaux de neurones
Méthodes ensemblistes : bagging, boosting et forêts
aléatoires
Classification multi-classe
Algorithmes de Régression
Adapter les algorithmes de classification à la régression
(arbres de régression, etc.)
Autres Problèmes Supervisés
Régression ordinale, ranking

4/1
 Introduction

Cadre générique - apprentissage supervisé

Couple de v.a. = (X , Y ) ∼ P inconnue

X = vecteur d’entrée à valeurs dans X (Rd ), ici d  1

Y = label/étiquette dans Y ⊂ R

A priori, X modélise une information utile pour prédire Y

Règle prédictive : g : X → Y choisie dans une classe G
(e.g. prédicteur linéaire g (x) =t βx + α)

Fonction de perte : ` : Y × Y → R+

Risque (inconnu !) = Erreur de généralisation

L(g ) = E (`(Y , g (X )))
à minimiser sur g ∈ G.
i.i.d.
Données = Dn = {(X1 , Y1 ), . . . , (Xn , Yn )} ∼ P
5/1
 Classification binaire

Sommaire

6/1
 Classification binaire

Classification binaire

Exemples : Prédiction de l’état d’un système (normal vs

anormal), ciblage commercial, diagnostic médical, etc.
Y = {−1, +1}
Fonction de perte :

`(y , z) = I{y 6= z}

Risque d’erreur :

L(g ) = P{Y 6= g (X )}

= P{Y · g (X ) < 0} = E (I{−Y · g (X ) > 0})

7/1
Approches Paramétriques
-
Rappels
 Régression logistique
Modélisation explicite de
η(x) = P(Y = +1 | X = x) ∈]0, 1[
η(x)
Transformée logistique : f (x) = logit η(x) = log( 1−η(x) )
e f (x)
Transformée inverse : η(x) = 1+e f (x)

Supposons f ∈ F = {fθ (x); θ ∈ Θ} avec Θ ⊂ Rd

e fθ (x)
ηθ (x) =
1 + e fθ (x)

Ex : régression logistique linéaire

f (x) = α +t β · x, θ = (α, β)
Maximiser la log-vraisemblance
n  
X 1 + yi 1 − yi
ln (θ) = log(ηθ (xi )) + log(1 − ηθ (xi ))
i=1
2 2
 Régression logistique
Même dans la cas linéaire, l’équation de score
∇θ ln (θ) = 0
ne peut être résolue explicitement !
Implementer une méthode de Newton-Raphson

Alternative : modèle probit Φ−1 (η(X )) = α +t βX

Z x
1 t2
with Φ(x) = √ exp(− )dt.
2π −∞ 2
 Régression logistique linéaire

Classifieur linéaire :ηθ (x) ≥ 1/2 ⇔ fθ (x) ≥ 0

 
’Plug-in’ g (x) = sgn α b +t βb · x ,
 Analyse Discriminante Linéaire
Hypothèse : les lois conditionnelles de X sachant Y = +1,
sachant Y = −1 sont Gaussiennes de même matrice de
covariance Γ mais des moyennes distinctes µ+ et µ− . Soit
p = P{Y = +1}.
Estimer les moments d’ordre 1 et 2, puis le rapport de
vraisemblance : le label prédit est le label le plus probable
sachant X .
 Analyse Discriminante Linéaire

Au point X = (X (1) , . . . , X (d) ), on prédit Y = +1 si

 
P{Y = +1 | X }
log >0⇔
P{Y = −1 | X }

p 1
log( ) − (µ+ − µ− )t Γ−1 (µ+ − µ− ) + x t Γ−1 (µ+ − µ− ) > 0
1−p 2

On remplace µ+ , µ− et Γ par leurs versions statistiques

Un classifieur ’plug-in’ linéaire

6= régression logistique linéaire sauf si p = 1/2

 Analyse Discriminante Linéaire - Extensions
Naive Bayes : on suppose que, sachant Y , les variables
prédicitves X (1) , . . . , X (d) sont indépendantes
Extensions non linéaires : analyse discriminante quadratique
(QDA), mélange de Gaussiennes
L’extension au cadre multiclasse est immédiate
 Le Perceptron Monocouche

L’espace d’entrée est divisé en deux regions par un hyperplan

affine
g (x) = sgn(t w · X + θ)

L’algorithme de Rosenblatt (1962) pour minimiser

X
− yi (t w · xi + θ)
i

1 Choisir au hasard un point mal classé par la règle courante

(xi , yi )
2 Effectuer une descente de gradient à la vitesse ρ

w w yx
( )←( ) + ρ( i i )
θ θ yi

Convergence ssi les données sont linéairement separables

Le Perceptron Monocouche
 Moyennes Locales

Sommaire

17/1
 Approches Non
Paramétriques
-
Moyennes Locales et
Arbres de Classification
 Une méthode nonparamétrique simple :
les K -plus proches voisins

Soit K ≥ 1. On considère une distance d sur RD , (ex :

distance euclidienne)

En tout point x, soit σ = σx la permutation de {1, . . . , n}

telle que
d(x, xσ(1) ) ≤ . . . ≤ d(x, xσ(n) )

Extraire les K -plus proches voisins de x

{xσ(1) , . . . , xσ(K ) }

Vote à la majorité : Ny = Card{k ∈ {1, ..., K }; yσ(k) = y },

y ∈ {−1, 1}
C (x) = arg max Ny ,
y ∈{−1,+1}
Une méthode nonparamétrique simple :
les K -plus proches voisins
 Les K -plus proches voisins

Consistance universelle (Stone ’77)

Si k = kn → ∞ et kn = o(n), la classifieur des K –plus proches
voisins est consistant

L(CK −NN ) − L∗ → 0, as n → ∞
Mais...
La vitesse est arbitrairement lente

Fléau de la dimension : ordonner les données est coûteux en

calcul

Instabilité : choix de K ? de la métrique D ?

Metric learning (e.g. distance Mahalanobis distance)

Variantes avec des poids

Les K -plus proches voisins
Une méthode trop flexible ?
 Histogrammes - Moyennes Locales
Les limites des K -plus proches voisins : le voisin le plus proche
peut être très loin de X !
Considérer une partition de l’espace d’entrée :
[ [
C1 · · · CK = X

Appliquer la règle majoritaire : si X tombe dans Ck ,

1 Compter le nombre d’exemples d’apprentissage avec label
positif
P dans Ck P
2 Si i: Xi ∈Ck I{Yi = +1} > i: Xi ∈Ck I{Yi = −1}, prédire
Y = +1. Prédire Y = −1 sinon.
Cette règle correspond au classifieur ”plug-in” 2I{b η (x)} − 1,
où
K Pn
X I{Yi = +1, Xi ∈ Ck }
ηb(x) = I{x ∈ Ck } i=1Pn
k=1 i=1 I{Xi ∈ Ck }

est l’estimateur de Nadaraya-Watson estimator de la

probabilité a posteriori.
 Histogrammes - Moyennes Locales
Lisser l’estimateur, la région de décision !
Remplacer la fonction indicatrice par un noyau de
convolution :
Z
d
K : R → R+ , K ≥ 0, symétrique et K (x)dx = 1

Fenêtre h > 0 et mise à l’échelle

1
Kh (x) = K (x/h)
h
Exemples : noyau Gaussian, de Novikov, de Haar, etc.
 Méthodes à noyaux - Moyennes Locales

Si
Pn
= +1}Kh (x − Xi ) > ni=1 I{Yi = −1}Kh (x − Xi ),
P
i=1 I{Yi
prédire Y = +1. Prédire Y = −1 sinon.

η (x)} − 1,
Cette règle correspond au classifieur ”plug-in” 2I{e
où Pn
I{Yi = +1}Kh (x − Xi )
ηe(x) = i=1 Pn
i=1 Kh (x − Xi )
est l’estimateur de Nadaraya-Watson estimator de la
probabilité a posteriori.
Argument statistique : Si η est une fonction ”régulière”, ηe
peut être un meilleur estimateur que ηb (de plus faible variance
mais... biaisé)
 Arbres de classification : l’algorithme CART

Si la partition est donnée à l’avance (avant d’observer les

données)...
 Arbres de classification : l’algorithme CART

Si la partition est donnée à l’avance (avant d’observer les

données)...
de nombreuses cellules peuvent être vides !
 Arbres de classification : l’algorithme CART

Si la partition est donnée à l’avance (avant d’observer les

données)...
de nombreuses cellules peuvent être vides !

Choisir la partition en fonction des données

d’apprentissage !
 Arbres de classification : l’algorithme CART

Si la partition est donnée à l’avance (avant d’observer les

données)...
de nombreuses cellules peuvent être vides !

Choisir la partition en fonction des données

d’apprentissage !

The CART Book - Breiman, Friedman, Olshen & Stone

(1986)

Un algorithme de partitionnement récursif glouton :

X = (X (1) , . . . , X (d) ) ∈ Rd
 Arbres de classification : l’algorithme CART
Données d’apprentissage (X1 , Y1 ), . . . , ; (Xn , Yn )
Pour toute région R ⊂ X , considérer le label majoritaire :
ȲR , où
n n
X 1X
ȲR = +1 if I{Yi = +1, Xi ∈ R} > I{Xi ∈ R}
2
i=1 i=1

et ȲR = −1 sinon

On part du noeud racine R = X = C0,0 et du classifieur

constant ȲC0,0 . Le but est de scinder la cellule C0,0
[
C0,0 = C1,0 C1,1
de façon à raffiner le classifieur courant et obtenir
g1 (x) = ȲC1,0 I{x ∈ C1,0 } + ȲC1,1 I{x ∈ C1,1 }.
 ”Faire pousser l’arbre”

La scission de C0,0 = X est effectuée de manière à minimiser

LbN (g1 ), ou de façon équivalent la mesure d’impureté
N
X
I{Xi ∈ C1,0 , Yi 6= ȲC1,0 } + I{Xi ∈ C1,1 , Yi 6= ȲC1,1 }
i=1

On considère des régions de la forme

C1,0 = C0,0 ∩ {X (j) ≤ s},

C1,1 = C0,0 ∩ {X (j) > s}.

Il est suffisant de choisir les meileurs seuils de scission parmi

(j)
les valeurs Xi !
”Faire pousser l’arbre”

C0,0

C2,2 C1,0 C1,1

X2 C1,0

C2,3 C2,2 C2,3

X1
 ”Faire pousser l’arbre”

Afin de scinder la cellule Cj,k , si elle n’est pas pure et contient

au moins nmin données d’apprentissage, itére rla double
boucle :
1 De j = 1 à d, trouver s (meilleur seuil de scission pour X (j) )
de manière à minimiser l’impureté des régions

Cj,k ∩ {Xj > s} and Cj,k ∩ {Xj ≤ s}

2 Trouver la meilleur variable de scission X (j)

Mesures d’impureté :
erreur de classification
indice de Gini
entropie
Arbres de classification : l’algorithme CART
 Arbres de classification : l’algorithme CART
Interprétabilité, visualisation

Variables qualitatives

Données incomplètes

Quantification de l’importance relative des variables prédictives

Randomisation

Scissions diagonales

Asymétrisation de l’erreur/impureté

Extension au cadre multiclasse, à la régression

Sélection de modèle : ”meilleur sous-arbre, ”élagage” rapide

Algorithme alternatif : C4.5 (Ross Quinlan)

 Arbres de classification : l’algorithme CART
Interprétabilité, visualisation

Variables qualitatives

Données incomplètes

Quantification de l’importance relative des variables prédictives

Randomisation

Scissions diagonales

Asymétrisation de l’erreur/impureté

Extension au cadre multiclasse, à la régression

Sélection de modèle : ”meilleur sous-arbre, ”élagage” rapide

Algorithme alternatif : C4.5 (Ross Quinlan)

Mais... performance prédictive moyenne et grande instabilité

 Ensemble Learning

Sommaire

33/1
 Ensemble Learning
–
Bagging, Boosting et
Forêts Aléatoires
 En bref

Ensemble Learning - Méthodes de Consensus

Bagging - accroı̂tre la stabilité

Boosting - ”La meilleure technique sur l’étagère”

”Le hasard fait bien les choses !” - les Forêts Aléatoires

 Méthodes de Consensus
Au lieu d’ajuster un unique classifieur, combiner les
prédictions d’un ensemble de classifieurs
C1 (X ), . . . , CM (X ).
Amit et Geman (1997)
Vote majoritaire :
M
!
X
sign Cm (X )
m=1
P
Variante - vote majoritaire pondéré : αi ≥ 0, i αi = 1
M
!
X
sign αm Cm (X )
m=1

Extension au cadre multiclasse, à la régression

Un vieux challenge : ”ranking” et consensus
 Bagging - Agrégation Boostrap
Bootstrap aggregating technique - Breiman (1996)
Appliquable à tout algorithme L
A partir des données d’apprentissage Dn :
∗(b)
1 Générer indépendamment B ≥ 1 échantillons bootstrap Dn
(par tirage avec remise dans Dn )
2 Pour b : 1 à B, mettre en oeuvre l’algorithme L à partir de
∗(b)
Dn , produisant le classifieur C ∗(b)
3 Agréger les prédictions bootstrap en calculant le vote
majoritaire :
B
!
X
∗(b)
Cbag (X ) = sign C (X )
b=1

Variante : si C ∗(b) (X ) = sign(f ∗(b) (X )),

B
!
X
Cebag = sign f ∗(b) (X )
b=1
 Bagging - Commentaires
Le bagging peut réduire significativement la variance
de procédures instables (ex : arbres de décision)
La réduction de variance peut conduire à une erreur test
moindre
En régression : fbag (x) = E[f ∗ (x)] (espérance prise sur
Dn )
h i h i
E (Y − f ∗ (x))2 = E (Y − fbag (x))2
h i h i
+ E (fbag (x) − f ∗ (x))2 ≥ E (Y − fbag (x))2

En classification :
L’agrégation bootstrap d’un bon classifieur l’améliore,
mais ...
celle d’un mauvais classifieur peut le détériorer encore !
 Boosting
AdaBoost - Freund & Schapire (1995)
L’ingrédient pour un ”apprentissage lent”, résistant au
surapprentissage : une méthode de classification ”faible”
L
Heuristique :
appliquer L à des versions pondérées de l’échantillon original
accroı̂tre le poids des observations mal classées par la règle
prédictive courante
agréger les classifieurs de façon non uniforme
(un bon prédicteur ne devrait pas être construit à partir de
quelques données aberrantes)

AdaBoost surpasse ses concurrents sur la plupart des

bases de données de référence
Interpétation statistique : cinq ans plus tard...
Boosting - Schéma général

Training  sample   C1(X)  

C2(X)  
Weighted  sample  

C3(X)  
Weighted  sample  

       …  

Weighted  sample   CM(X)  

Vo>ng  scheme:   Sign(a1C1(X)+…+aMCM(X))  

 L’algorithme ”Adaptive Boosting”

Initialisation : poids uniformes, ωi = 1/n affectés à chaque

exemple (Xi , Yi ), 1 ≤ i ≤ n
De m : 1 à M,
1 Au moyen de l’algorithme L, ajuster un classifieur faible Cm à
partir de l’échantillon pondéré {(Xi , Yi , ωi ) : 1 ≤ i ≤ n}
2 Calculer l’erreur de classification pondérée
n
X
errm = ωi I{Yi 6= Cm (Xi )}
i=1

et am = log((1 − errm )/errm )

3 Mettre à jour les poids :
ωi ← ωi exp
P (am I{Yi 6= C (Xi )})
ωi ← ωi / nj=1 ωj
P 
M
Sortie : CBoost (X ) = sign m=1 am Cm (X )
 AdaBoost résiste au surapprentissage !
Classifieur faible typique : stumps (arbres de profondeur 1)
Lorsque M croı̂t, l’erreur test décroı̂t et se stabilise
 Aspects pratiques

Comment mettre en oeuvre L à partir d’un échantillon

pondéré ?
modifier le critère explicitement (ex : CART, SVM, k-NN, etc.)

tirer
P un échantillon d’apprentissage avec la distribution
i ωi δ(Xi ,Yi )

Quand faut-il stopper les intérations ?

tracer l’erreur test en fonction de M
on stoppe lorsque l’erreur test se stabilise
 Une interpétation statistique du Boosting

Friedman, Hastie & Tibshirani (2000)

Stagewise forward additive modelling

Perte exponentielle : C (X ) = sign(f (X ))

Le (f ) = E[exp(−Yf (X ))]

Solution optimale :
 
∗ 1 η(X )
f (X ) = log
2 1 − η(X )
 Forward stagewise additive modelling
Heuristique : raffiner la règle prédictive courante fm−1 (x) en
ajoutant αm Cm (x), avec αm ∈ R et Cm (x) ∈ {−1, +1}
Comment choisir αm et Cm (x) de façon à minimiser le risque
empirique exponentiel ?
Xn
arg min exp (−Yi (fm−1 (Xi ) + αC (Xi ))) =?
α, C i=1

Posons ωi = exp(−Yi fm−1 (Xi )), le risque empirique s’écrit

alors :
Xn
ωi exp (−Yi αC (Xi ))
i=1

Quel que soit α > 0, le classifieur de risque minimum est celui

qui minimise le risque pondéré :
Xn
ωi I{Yi 6= C (Xi )}
i=1
 Forward stagewise additive modelling

Soit Cm (X ) la solution de ce problème de classification

pondérée :
Xn
errm = ωi I{Yi 6= Cm (Xi )}
i=1

Il reste enfin à minimiser en α :

e α errm + e −α (1 − errm ),

et obtenir αm = (1/2) · log((1 − errm )/errm )

Très nombreuses variantes : autres fonctions de perte,

seuillage des poids, etc.
L’agrégation produit des régions ”régulières”
 Forêts Aléatoires

Ingrédients : bagging + randomisation

Randomiser la collection de variables prédictives (i.e. les

composantes de X ) : avant de scinder chaque noeud d’un
arbre de décision bootstrap

Classifieur faible typique : arbre de faible profondeur, sans

élagage

L’agrégation préserve la consistance...

mais aucune explication théorique de la performance
observée !

Heuristique : la randomisation ”enrichit” la règle

Randomisation des données d’apprentissage lorsqu’elles sont

massives
 Machines à Vecteurs Supports (SVM)

Sommaire

49/1
 Machines à Vecteurs Supports (SVM)

Séparateur linéaire

Définition
Soit x ∈ Rp
f (x) = signe(wT x + b)
L’équation : wT x + b = 0 définit un hyperplan dans l’espace
euclidien Rp

Exemple : données d’apprentissage en 3D et séparateur linéaire

50/1
 Machines à Vecteurs Supports (SVM)

Cas de données linéairement séparables

Exemple en 2D : quelle droite choisir ?

51/1
 Machines à Vecteurs Supports (SVM)

Critère de marge

52/1
 Machines à Vecteurs Supports (SVM)

Critère de marge

Notion de marge géométrique

Pour séparer les données, on considère un triplet
d’hyperplans :
H : wT x + b = 0, H1 : wT x + b = 1, H−1 : wT x + b = −1
On appelle marge géométrique, ρ(w) la plus petite distance
entre les données et l’hyperplan H, ici donc la moitié de la
distance entre H1 et H−1
1
Un calcul simple donne : ρ(w) = ||w|| .

53/1
 Machines à Vecteurs Supports (SVM)

Nouvelle fonction de coût à optimiser

Comment déterminer w et b ?
Maximiser la marge ρ(w) tout en séparant les données de part
et d’autre de H1 et H−1
Séparer les données bleues (yi = 1) : wT xi + b ≥ 1
Séparer les données rouges (yi = −1) : wT xi + b ≤ −1

54/1
 Machines à Vecteurs Supports (SVM)

SVM linéaire : cas séparable

Optimisation dans l’espace primal

1
minimiser kwk2
w,b 2
sous la contrainte yi (wT xi + b) ≥ 1, i = 1, . . . , n.

Référence
Boser, B. E. ; Guyon, I. M. ; Vapnik, V. N. (1992). ”A training
algorithm for optimal margin classifiers”. Proceedings of the fifth
annual workshop on Computational learning theory - COLT ’92. p.
144.

55/1
 Machines à Vecteurs Supports (SVM)

Programmation quadratique sous contraintes

inégalités

Problème du type (attention les notations changent !)

56/1
 Machines à Vecteurs Supports (SVM)

Programmation quadratique sous contraintes

inégalités

Problème du type :
minx f (x)
s.c. g (x) ≤ 0
Ici, g (x) linéaire
f strictement convexe

1 Lagrangien : J(x, λ) = f (x) + λg (x), λ ≥ 0

57/1
 Machines à Vecteurs Supports (SVM)

Programmation quadratique sous contraintes

inégalités

Lagrangien

1 X
L(w, b, α) = ||w||2 + αi (1 − yi (wT xi + b))
2
i
∀i, αi ≥ 0

58/1
 Machines à Vecteurs Supports (SVM)

Conditions de Karush-Kunh-Tucker

En l’extremum, on a

n
X
∇w L(w) = w − αi yi xi = 0
i=1
Xn
∇b L(b) = − αi yi = 0
i=1
∀i, αi ≥ 0
T
∀i, αi [1 − yi (w xi + b)] = 0

59/1
 Machines à Vecteurs Supports (SVM)

Obtention des αi : résolution dans l’espace

dual

X 1X
L(α) = αi − αi αj yi yj (xT
i xj )
2
i i,j

Maximiser
P L sous les contraintes αi ≥ 0 et
i αi yi = 0, ∀i = 1, . . . , n
Faire appel à un solveur quadratique

60/1
 Machines à Vecteurs Supports (SVM)

SVM linéaires ou Optimal Margin Hyperplan

Supposons que les multiplicateurs de Lagrange αi soient

déterminés :
Equation d’un SVM linéaire
Xn
f (x) = signe( αi y i xT
i x + b)
i=1

Pour classer une donnée x, ce classifier combine linéairement les

valeurs de classe yi des données support avec des poids du type
αi xT
i x dépendant de la ressemblance entre x et les données
support au sens du produit scalaire.

61/1
 Machines à Vecteurs Supports (SVM)

Vecteurs ”supports”

Les données d’apprentissage

xi telles que αi 6= 0 sont sur l’un ou l’autre des hyperplans H1 ou
H−1 . Seules ces données dites vecteur de support comptent dans la
définition de w = ni=1 αi yi xi
P
NB : b est obtenu en choisissant une donnée support (αi 6= 0)

62/1
 Machines à Vecteurs Supports (SVM)

Cas réaliste : SVM linéaire dans le cas

données non séparables

Introduire une variable d’écart ξi pour chaque donnée :

Problème dans le primal
n
1 X
min kwk2 + C ξi
w,b,ξ 2
i=1
sous les contraintes yi (wT xi + b) ≥ 1 − ξi i = 1, . . . , n.
ξi ≥ 0 i = 1, . . . , n.

63/1
 Machines à Vecteurs Supports (SVM)

Cas réaliste : SVM linéaire dans le cas

données non séparables

64/1
 Machines à Vecteurs Supports (SVM)

Cas réaliste : SVM linéaire dans le cas

données non séparables

Problème dans le dual

X 1X
max αi − αi αj yi yj xT
i xj
α 2
i i,j

sous les contraintes 0 ≤ αi ≤ C i = 1, . . . , n.

X
αi yi i = 1, . . . , n.
i

65/1
 Machines à Vecteurs Supports (SVM)

Conditions de Karush-Kuhn-Tucker (KKT)

Soit α∗ la solution du problème dual :

∀i, [yi fw ∗ ,b∗ (xi ) − 1 + ξi∗ ] ≤ 0 (1)
∀i, α∗i ≥ 0 (2)
∀i, α∗i [yi fw ∗ ,b∗ (xi ) − 1 + ξi∗ ] = 0 (3)
∀i, µ∗i ≥ 0 (4)
∀i, µ∗i ξi∗ = 0 (5)
∀i, α∗i + µ∗i = C (6)
∀i, ξi∗ ≥0 (7)
X
w∗ = α∗i yi xi (8)
i
X
α∗i yi = 0 (9)
i
(10)

66/1
 Machines à Vecteurs Supports (SVM)

Différents cas de figure

Soit α∗ la solution du problème dual :

si αi∗ = 0, alors µ∗i = C > 0 et donc, ξi∗ = 0 : xi est bien classé
si 0 < αi∗ < C alors µ∗i > 0 et donc, ξi∗ = 0 : xi est tel que :
yi f (xi ) = 1
si αi∗ = C , alors µ∗i = 0, ξi∗ = 1 − yi fw ∗ ,b∗ (xi )
NB : on calcule b ∗ en utilisant un i tel que 0 < αi∗ < C

67/1
 Machines à Vecteurs Supports (SVM)

Cas réaliste : SVM linéaire dans le cas

données non séparables

Quelques remarques
certaines données support peuvent donc être de l’autre côté
des hyperplans H1 ou H−1
C est un hyperparamètre qui contrôle le compromis entre la
complexité du modèle et le nombre d’erreurs de classification
du modèle.

68/1
 Machines à Vecteurs Supports (SVM)

SVM : approche par régularisation

Optimisation dans l’espace primal

n
X 1
min (1 − yi (wT xi + b))+ + λ kwk2
w,b 2
i=1

Avec : (z)+ = max(0, z)

f (x) = signe(h(x))
Fonction de coût : L(x, y , h(x)) = (1 − yh(x))+
yh(x) est appelée marge du classifieur

69/1
 Machines à Vecteurs Supports (SVM)

Support Vector Machine : le cas non linéaire

70/1
 Machines à Vecteurs Supports (SVM)

Remarque

Le problème de l’hyperplan de marge optimale ne fait intervenir les

données d’apprentissage qu’à travers de produits scalaires.
X 1X
max αi − αi αj yi yj xT
i xj
α 2
i i,j

sous les contraintes 0 ≤ αi ≤ C i = 1, . . . , n.

X
αi yi i = 1, . . . , n.
i

71/1
 Machines à Vecteurs Supports (SVM)

Remarque 1 : apprentissage

Si je transforme les données à l’aide d’une fonction ϕ (non linéaire)

et si je sais calculer les produits scalaires ϕ(xi )T ϕ(xj ), je peux
apprendre une fonction de séparation non linéaire.
X 1X
max αi − αi αj yi yj ϕ(xi )T ϕ(xj )
α 2
i i,j

sous les contraintes 0 ≤ αi ≤ C i = 1, . . . , n.

X
αi yi i = 1, . . . , n.
i

Pour classer une nouvelle donné x, je n’ai besoin que de savoir

calculer ϕ(x)T ϕ(xi ).

72/1
 Machines à Vecteurs Supports (SVM)

Astuce du noyau

Si on remplace xT i xj par l’image par une fonction k : k(xi , xj ) telle

qu’il existe un espace de caractérisques F et une fonction de
caractéristique (feature map) ϕ : X → F et
∀(x, x0 ) ∈ X , k(x, x0 ) = ϕ(x)T ϕ(x0 ), alors on peut appliquer le
même algorithme d’optimisation (résolution dans le dual) et
obtenir :
f (x) = signe( ni=1 αi yi k(xi , x) + b)
P
Des telles fonctions existent et sont appelées noyaux.

73/1
 Machines à Vecteurs Supports (SVM)

Astuce du noyau et feature map 1/2

74/1
 Machines à Vecteurs Supports (SVM)

Astuce du noyau et feature map 2/2

75/1
 Machines à Vecteurs Supports (SVM)

Astuce du noyau et feature map 2/2

Pn FonctionT
h du type
P:n
h(x) = i=1 βi ϕ(x) ϕ(xi ) = i=1 βi k(x, xi ),
avec k : X × X → R un noyau positif défini.

75/1
 Machines à Vecteurs Supports (SVM)

Noyaux

Définition
Soit X un ensemble. Soit k :X × X → R, une fonction symétrique.
La fonction k est appelée noyau positif défini si et seulement si
quel que soit le sous-ensemble fini {x1 , . . . , xm } de X et le vecteur
colonne cP de Rm ,
c Kc = m
T
i,j=1 ci cj k(xi , xj ) ≥ 0

76/1
 Machines à Vecteurs Supports (SVM)

Théorème de Moore-Aronzajn

Théorème de Moore-Aronzajn
Soit K un noyau positif défini. Alors, il existe un unique espace de
Hilbert F pour lequel k est un noyau reproduisant :
∀x ∈ X , hf (·), k(·, x)iF = f (x)
On a en particulier : hk(·, x), k(·, x 0 )iF = k(x, x 0 )

77/1
 Machines à Vecteurs Supports (SVM)

Théorème de Moore-Aronzajn

Théorème de Moore-Aronzajn
Soit K un noyau positif défini. Alors, il existe un unique espace de
Hilbert F pour lequel k est un noyau reproduisant :
∀x ∈ X , hf (·), k(·, x)iF = f (x)
On a en particulier : hk(·, x), k(·, x 0 )iF = k(x, x 0 )
NB :Cela veut dire qu’on peut toujours choisir ϕ(x) = k(·, x)
Important : un noyau peut admettre plusieurs fonctions de
caractérisques et espaces correspondants mais un seul est RKHS
(espace de Hilbert à noyau reproduisant).

77/1
 Machines à Vecteurs Supports (SVM)

Noyaux

Noyaux entre vecteurs

∀x, x0 ∈ Rp
Noyau linéaire : k(x, x0 ) = xT x0
Noyau polynomial : k(x, x0 ) = (xT x0 + c)d
Noyau gaussien : k(x, x0 ) = exp(−γ||x − x0 ||2 )

78/1
 Machines à Vecteurs Supports (SVM)

Support Vector Machine : séparateur non

linéaire par noyau gaussien

79/1
 Machines à Vecteurs Supports (SVM)

Exemple : noyau polynomial

80/1
 Machines à Vecteurs Supports (SVM)

Exemple : noyau polynomial

Astuce du noyau
On remarque que ϕ(x1 )T ϕ(x0 ) peut se calculer sans travailler dans
R3
Je peux définir k(x, x0 ) = ϕ(x)T ϕ(x0 ) = (xT x0 )2

81/1
 Machines à Vecteurs Supports (SVM)

Construction d’un noyau

Combiner des noyaux connus

Des noyaux spécifiques à certains types de données :
Objets structurés : ensembles, graphes, arbres, séquences, . . .
Données non structurées avec une structure sous-jacente :
textes, images, documents, signaux, objets biologiques
Sélection d’un noyau :
Hyperparameter learning : Chapelle et al. 2002
Multiple Kernel Learning :P
étant donnés k1 , . . . , km , apprendre
une combinaison convexe i βi ki (see SimpleMKL
Rakotomamonjy et al. 2008, unifying view in Kloft et al. 2010)

82/1
 Machines à Vecteurs Supports (SVM)

Régression

Cadre probabiliste et statistique

Soit X un vecteur aléatoire de X = Rp
Y une variable aléatoire continue Y = R
Soit P la loi de probabilité jointe de (X,Y), loi fixée mais inconnue
Supposons que Sapp = {(xi , yi ), i = 1, . . . , n} soit un échantillon
i.i.d. tiré de la loi P

83/1
 Machines à Vecteurs Supports (SVM)

Régression

Cadre probabiliste et statistique

A partir de Sapp , déterminer la fonction f ∈ F qui minimise
R(f ) = EP [`(X , Y , f (X )]
` étant une fonction de coût local qui mesure à quel point la
vraie cible et la prédiction par le classifieur sont différentes
Pb : la loi jointe n’est pas connue : on ne peut pas calculer R(f )

84/1
 Machines à Vecteurs Supports (SVM)

Support Vector Regression

Etendre l’idée de la marge maximal soft à la régression

Imposer un ε-tube : perte ε-insensible
|y 0 − y |ε = max(0, |y 0 − y | − ε)

85/1
 Machines à Vecteurs Supports (SVM)

Support Vector Regression

SVR dans l’espace primal

Etant donnés C and P ε
minw ,b,ξ 2 kwk + C i (ξi + ξi∗ )
1 2

s.c.
∀i = 1, . . . n, yi − f (xi ) ≤ ε + ξi
∀i = 1, . . . n, f (xi ) − yi ≤ ε + ξi∗
∀i = 1, ξi ≥ 0, ξi∗ ≥ 0
avec f (x) = w T ϕ(x) + b
Cas général : ϕ feature map associée à un noyau défini positif k.

86/1
 Machines à Vecteurs Supports (SVM)

Solution dans le dual

∗ ∗ ∗
P P
min
P α,α
∗
i,j (αi − αi )(αj − αj )k(xi , xj ) + ε i (αi + αi ) −
∗
i (αi − αi )
i yP
s.c. Pi (αi − αi∗ ) = 0 et 0 ≤ αi ≤ C et 0 ≤ αi∗ ≤ C
w = ni=1 (αi − αi∗ )ϕ(xi )
Solution
n
X
f (x) = (αi − αi∗ )k(xi , x) + b
i=1

87/1
 Machines à Vecteurs Supports (SVM)

Support Vector Regression : example in 1D

88/1
 Réseaux de neurones

Sommaire

89/1
 Réseaux de neurones

Neuron network growth over 24 hours

In 2014, the group of Gabriel Popescu at Illinois U. visualized a

growing net of baby neurons using spatial light interference
microscopy (SLIM). Ref : [Link]
wp-content/uploads/2014/03/Mir_SRep_2014.pdf
Video : [Link]
90/1
 Réseaux de neurones

Développement des réseaux de neurones chez

l’enfant

91/1 Re : Museum de Toulouse [Link]

 Réseaux de neurones

Neurone

92/1
 Réseaux de neurones

Réseau de neurones formels (perceptron

multi-couches)

93/1
 Réseaux de neurones

Du neurone formel aux réseaux de neurones

formels 1/2

Neurone formel : Mc Cullogh et Pitts, 1943

Règle d’apprentissage du perceptron, Rosenblatt, 1957
Minsky et Papert : capacité limitée du perceptron, 1959
Apprentissage d’un perceptron multi-couches par
rétropropagation du gradient, Y. Le Cun, 1985, Hinton et
Sejnowski, 1986.
Perceptron multi-couches = approximateur universel, Hornik
et al. 1991
Convolutional networks, 1995, Y. Le Cun et Y. Bengio
Entre 1995 et 2008, peu d’expansion du domaine (pbs
fonctions non convexes, temps d’apprentissage, pas de théorie)

94/1
 Réseaux de neurones

Du neurone formel aux réseaux de neurones

formels 1/2

Généralisation des GPU (processeurs graphiques) 2005

Très large ensemble d’images : Imagenet, Fei-Fei et al. 2008
(maintenant 11 millions d’images)
Réseaux de neurones de plus en plus profonds appris avec de
gigantesques bases de données
Apprentissage initial non supervisé (avec auto encodeur)
Word2vec (Mikolov et al. 2013)
Dropout (Srivastava et al. 2014)

95/1
 Réseaux de neurones

Agenda

Données non structurées

Rappel : neurone formel ou perceptron
Perceptron multi-couches
Autoencodeurs
Un mot sur les réseaux convolutionnels

96/1
 Réseaux de neurones

Définition du neurone formel

une fonction d’activation

un vecteur de poids et un biais (intercept)
f (x) = g (w T x + b) (11)
On choisit g différentiable

97/1
 Réseaux de neurones

Fonctions d’activation du neurone formel

par exemple :

Mais aussi tanh (sortie entre -1 et 1).

98/1
 Réseaux de neurones

Limitation du neurone formel

Limité aux données linéairement séparables :

99/1
 Réseaux de neurones

Ajouter une couche de traitement

intermédiaire

Φ(x)1 = AND(x¯1 , x2 )
Φ(x)2 = AND(x1 , x¯2 )

Maintenant, calculer :

f (x) = g (Φ(x)T w + b)

On parle de fonction de redescription (feature map) ou de

repésentation interne.
Grand avantage des réseaux de neurones à plus d’une
couche : apprentissage de la fonction Φ.

100/1
 Réseaux de neurones

Approximateur universel

En 1991, Hornik et al. démontrent que la famille des perceptrons à

une couche cachée et à p + 1 entrées est dense dans l’ensemble des
fonctions continues de Rp dans R. Un MLP à une couche cachée
est un approximateur universel.

101/1
 Réseaux de neurones

Approximateur universel

En 1991, Hornik et al. démontrent que la famille des perceptrons à

une couche cachée et à p + 1 entrées est dense dans l’ensemble des
fonctions continues de Rp dans R. Un MLP à une couche cachée
est un approximateur universel.
D’autres exemples d’approximateurs universels que vous
connaissez :
Régresseur linéaire : NON
SVM avec noyau universel tel que le noyau Gaussien : OUI
Forêts aléatoires : OUI
Boosting de stumps : OUI

101/1
 Réseaux de neurones

Exemple d’un réseau de neurones

multi-couches ”feedforward”

Prenons comme exemple un MLP à une couche de sortie de taille

K=1, une couche cachée de taille M + 1, un vecteur d’entrée de
taille p + 1 pour la régression

Famille de fonctions Hmlp = {hmlp : Rp+1 → Y}

M
(2)
X
hMLP (x) = wj zj (12)
j=0
zj = tanh(aj ) (13)
p
(1)
X
aj = wji xi (14)
i=0

102/1
 Réseaux de neurones

Remarque sur la fonction de saturation

La tangente hyperbolique est choisie comme fonction de

saturation, dérivable.

e a − e −a
h(a) = tanh(a) = (15)
e a + e −a
h0 (a) = 1 − h(a)2 (16)

En termes de calculs, cette fonction est très avantageuse car la

dérivée se définit directement en terme de h(a). Nous avons une
1
propriété similaire pour la fonction sigmoide :g (a) = 1+exp(− 1
a)
.
2

103/1
 Réseaux de neurones

Architecture d’un réseau de neurones

multi-couches ”feedforward”

Nous avons choisi : la sortie unique du régresseur MLP fournit

une valeur réelle
Pour un problème de classification à K classes, nous aurions
choisi K sorties avec la fonction sigmoide ou mieux softmax
Pour un problème de régression à K sorties, nous aurions
plutôt choisi, K sorties linéaires (ici K = 1)

104/1
 Réseaux de neurones

Exemple d’un réseau de neurones

multi-couches ”feedforward”
Prenons comme exemple un MLP à une couche de sortie de taille
K=1, une couche cachée de taille M + 1, un vecteur d’entrée de
taille p + 1 pour la régression
Famille de fonctions Hmlp = {hmlp : Rp+1 → Y}

M
(2)
X
hc (x) = g ( wjc zj ) (17)
j=0
zj = g (aj ) (18)
p
(1)
X
aj = wji xi (19)
i=0

1
avec g (t) = 1+exp(−1/2t) .

105/1
 Réseaux de neurones

Apprentissage à partir de données

N
X
L(W ; S) = `(h(xn ), yn ))
n=1
Régression :
`(h(xn ), yn ) = (h(xn ) − yn )2
Classification (maximiser la vraisemblance) : On interprète
fc (x) = p(y = c|x) (plusieurs sorties : on peut utiliser la fonction
softmax )
`(h(x), y ) = − log fy (x)
Importante remarque : L est non convexe et possède de nombreux
minima locaux
Le mieux que nous puissions faire, c’est trouver un bon
minimum local
C’est principalement pour cette raison que les MLP ont été
pendant longtemps abandonés en faveur des SVM/SVR plus
106/1 faciles à optimiser
 Réseaux de neurones

Algorithme d’optimisation

La rétropropagation du gradient
L’idée est d’appliquer un algorithme de descente du gradient :
on rétropropage une erreur à travers chacune des couches, en
débutant par la dernière couche,
On utilise la règle de dérivation en chaı̂ne :
∂L(W ) ∂L(W ) ∂aj
(1) = ∂aj (1) pour pouvoir corriger les poids de la
∂wji ∂wji
couche cachée.
Une fois toutes les corrections calculées, on met à jour les
poids du réseau.
L’algorithme peut s’appliquer globalement ou localement
(nous allons voir ce que cela signifie)

107/1
 Réseaux de neurones

La rétropropagation du gradient

Références :
Y. LeCun : Une procédure d’apprentissage pour réseau à seuil
asymmétrique (a Learning Scheme for Asymmetric Threshold
Networks), Proceedings of Cognitiva 85, 599-604, Paris, France,
1985.
Rumelhart, D. E., Hinton, G. E., and Williams, R. J. (1986)
Learning representations by back-propagating errors. Nature, 323,
533–536.

108/1
 Réseaux de neurones

Rappelons la descente de gradient ordinaire

Soit une fonction C(θ) dépendant de θ :

Les valeurs θ telles que ∂C∂θ(θ) = 0 correspondent à des minima
ou des maxima de cette fonction.
Lorsque C est strictement convexe en θ, l’algorithme que nous
allons présenter s’approche de la solution aussi prèsque
possible.
Cependant, même quand C n’est pas s. convexe, nous
pouvons toujours essayer de trouver un ”bon” minimum local.
Idée : corriger θ itérativement par : θt+1 ← θt − ηt ∂C(θ)
∂θ
Après chaque mise à jour, le gradient est ré-évalué pour le nouveau
vecteur de paramètre et la correction est à nouveau calculée

109/1
 Réseaux de neurones

Rappelons la descente de gradient globale

PN
C(θ) = n=1 cn (θ)
1 E = 1000 ;
2 ε= petite valeur
3 θ0 valeur initiale ; t = 0 ;
4 Tant que (E > ε)
PN ∂cn (θ t )
θt+1 ← θt − ηt n=1 ∂θ t
calculer E = L(θt+1 )
5 Fournir θ courant

110/1
 Réseaux de neurones

Choix de ηk

Théorème P :
Si la série ( k ηk ) diverge et si ( k ηk2 ) converge alors
P
l’algorithme de gradient converge vers un minimum local.

111/1
 Réseaux de neurones

Descente de gradient stochastique et locale

PN
C(θ) = n=1 cn (θ)
1 E = 1000 ;
2 ε= petite valeur
3 θ0 valeur initiale ; t = 0 ;
4 nbcycle = 0
5 Tant que (E ≥ ε) et (nbcycle < 500)
nbcycle = nbcycle + 1
pour ` = 1 à N
Tirer uniformément un indice n ∈ {1, . . . , N}
t
θt+1 ← θt − ηt ∂c∂θ
n (θ )
t

calculer E = L(θt+1 )

112/1
 Réseaux de neurones

Descente de gradient stochastique avec

minibatch de taille constante

PN
C(θ) = n=1 cn (θ)
1 E = 1000 ;
2 ε= petite valeur
3 θ0 valeur initiale ; t = 0 ;
4 nbcycle = 0
5 Tant que (E ≥ ε) et (nbcycle < 500)
nbcycle = nbcycle + 1
Tirer uniformément M fois un indice n ∈ {1, . . . , N}
t
θt+1 ← θt − ηt ∂c∂θ
M (θ )
t

calculer E = L(θt+1 )

113/1
 Réseaux de neurones

Rétropropagation du gradient (1/4)

On souhaite appliquer la règle de descente de gradient aux poids

de la couche 1 et de la couche 2 (ici réduite à une unité de sortie).
Soit ` = 21 (h(x) − y )2
Calcul pour une donnée, algorithme local
Gradient par rapport aux poids de sortie :

∂` ∂` ∂h(x)
(2)
= (20)
∂wj ∂h(x) ∂w (2)
j

Gradient par rapport aux poids de la couche cachée :

∂` ∂` ∂h(x)
(1)
= (21)
∂wji ∂h(x) ∂w (1)
ji

114/1
 Réseaux de neurones

Rétropropagation du gradient local (2/4) : les

calculs

Calcul pour une donnée, algorithme local

Gradient pour les poids de sortie :

∂` ∂` ∂h(x)
(2)
= (22)
∂wj ∂h(x) ∂w (2)
j
∂`
= h(x) − y (23)
∂h(x)
(2) P (2)
∂h(x) ∂g (wj zj + k6=j wk zk )
(2)
= (2)
(24)
∂wj ∂wj
(25)

115/1
 Réseaux de neurones

Rétropropagation du gradient local (3/4) : les

calculs

Calcul pour une donnée, algorithme local

Gradient pour les poids de la couche cachée :

∂` ∂` ∂h(x)
(1)
= (26)
∂wji ∂h(x) ∂w (1)
ji
P
∂h(x) (2) ∂g ( k wjk xk )
(1)
= wj (1)
(27)
∂wji ∂wji
∂h(x) X (2)
(1)
= (1 − g ( wjk xk )2 )wj xi (28)
∂wji k

116/1
 Réseaux de neurones

Rétropropagation du gradient (4/4) :

l’algorithme

Pour une descente locale pour un exemple xn tiré uniformément :

1 Calculer pour xn , h(xn )
∂`n ∂`n
2 Calculer les gradients : (2),t puis (1),t
∂wj ∂wji
3 Corriger tous les poids avec les gradients préalablement
calculés :
Corriger la couche (1) :
Pour tout j=0 à M :
(1),t+1 (1),t ∂`n
wj ← wj − ηt (1),t
∂wj

Corriger la couche (2) : ici unique neurone de sortie

w (2),t+1 ← w (2),t − ηt ∂w∂`(2),t
n

117/1
 Réseaux de neurones

Régularisation et early stopping

Early Stopping
Une première méthode de régularisation a été proposée dans
les années 90 : il s’agit d’arrêter a priori l’apprentissage
prématurément avant le sur-apprentissage : on évite de se
rapprocher trop près d’un minimum !
Régularisation
On peut plus P rigoureusement définir :
L(W , Sapp = n `(h(xn ), yn ) + λ2 ||w (2),∗ ||2 + λ1 ||w (1),∗ ||2
(2) (1) (2)
On évitera de régulariser w0 , wj0 et w0i . Le ∗ signifie qu’on
ne considère pas ces coordonnées-là.
(1) 2
En pratique, on note que : ||w (1),∗ ||2 =
P
ji,j6=0,i6=0 (wji ) .

118/1
 Réseaux de neurones

Sélection de modèles

Le MLP a plusieurs hyperparamètres :

Nb de couches cachées
Tailles des couches cachées
paramètre λ
nbcycle , ε
γ
ηt = 1+t
La plupart sont trouvés par VALIDATION CROISEE.

119/1
 Réseaux de neurones

Pour
Flexibilité au niveau des sorties : plusieurs classes, etc..
Technique éprouvé depuis 1985
Algorithme de gradient stochastique se plie bien aux besoins
du BIG DATA
Bénéficie des architectures GPU
PLUG and PLAY : on peut enchaı̂ner différents traitements
dans un même paradigme
Contre
Fonction de perte non convexe : pas de minimum global
Descente de gradient nécessite souvent de nombreux ajustements
Pas de cadre théorique
Beaucoup de développements ad hoc

120/1
 Réseaux de neurones

Réseaux dits profonds - Deep Learning

Image Y. Bengio

121/1
 Réseaux de neurones

Apprentissage des réseaux dits profonds

A partir de 3 couches cachées, on parle de ”deep learning”, ce type

de réseau est a priori intéréssant pour traiter des données
complexes comme des images ou du texte.
Pourquoi utiliser plusieurs couches cachées ?
Même si un réseau à une couche cachée est en principe un
approximateur universel, cela ne veut pas dire qu’un réseau à une
couche cachée fournit la meilleure représentation et les meilleures
performances.

122/1
 Réseaux de neurones

Apprentissage des réseaux dits profonds

Malgré le risque de surapprentissage,

deux bonnes raisons de s’intéresser aux réseaux profonds
l’amélioration des capacités de calcul et de mémoire (GPU)
la disponibilité de gigantesques bases de données (Imagenet,
Fei-Fei, 2008)
Apprendre un réseau profond par simple rétropropagation du
gradient ne fonctionne pas si bien que cela (Bengio et al. 2007 ;
Erhan et al. 2009).
Le réseau tombe dans des minima locaux très mauvais sans une
bonne initialisation.

123/1
 Réseaux de neurones

Apprentissage des réseaux dits profonds

124/1
 Réseaux de neurones

Apprentissage des réseaux dits profonds

Deux améliorations notables

Dropout

Auto-encodeurs

125/1
 Réseaux de neurones

Eviter l’overfitting des réseaux profonds par

dropout 1/3
Pour les réseaux profonds (>>2 couches) :

Durant l’apprentissage, à chaque étape de gradient : chaque

unité(neurone) est présente avec une probabilité p, ce qui veut dire
que certains neurones ne sont pas présents et donc ne sont pas
corrigés systématiquement.
Pendant la prédiction (en test), chaque unité est présente et un
facteur p est appliqué à ses poids.

126/1
 Réseaux de neurones

Eviter l’overtfitting des réseaux profonds par

dropout 2/3

Une interprétation :
Si on dispose de m neurones au total, c’est comme si on apprenait
avec 2m réseaux clairsemés et au moment du test, on superpose
tous ces réseaux en un seul avec lequel on prédit.
Les neurones ne peuvent s’adapter les uns aux autres

127/1
 Réseaux de neurones

Eviter l’overfitting des réseaux profonds par

dropout 3/3

128/1
 Réseaux de neurones

Apprentissage des réseaux dits profonds

Les réseaux à plusieurs couches sont aujourd’hui appris en étant

initialisés par un apprentissage non supervisé souvent à l’aide
d’autoencodeurs ou de Machines de Boltzman restreintes (RBM).
Nous allons voir comment...

129/1
 Réseaux de neurones

Autoencodeurs
Autoencodeurs
Un autoencodeur (aussi appelé réseau diabolo) est un réseau à une
couche d’entrée, une ou plusieurs couches cachées et une couche
de sortie. Ce type de réseau cherche à construire une
représentation interne (la couche du milieu) en apprenant à prédire
l’entrée à partir de celle-ci : x ≈ g (x).

130/1
 Réseaux de neurones

Apprentissage d’autoencodeurs

Un auto-encodeur s’apprend par rétropropagation du gradient.

Dans le cas des autoencodeurs parcimonieux, la fonction de perte
utilisée est en général le critère quadratique pénalisé par un terme
de régularisation qui contraint l’activité (moyenne) de chaque unité
de la couche cachée à rester limitée.

L’autoencodeur n’a d’autre intérêt que d’apprendre des

représentations internes dans le cas de données complexs

131/1
 Réseaux de neurones

Autoencodeur et apprentissage d’un réseau

”feed-forward” profond (Erhan et al.)
Pour chaque couche cachée en démarrant par la plus proche de
l’entrée x, on définit ses poids en les extrayant de la première
couche d’un autoencodeur appris sur :
Poids de la couche 2 : on apprend un autoencodeur x ≈ h(x). On
initialise les poids de la couche 2 par ceux de la couche 2 de
l’autoencodeur

Poids de la couche 3 : on apprend un autoencodeur

f1 (x) ≈ h(f1 (x)). On initialise les poids de la couche 3 par ceux de
la couche 2 de ce nouvel autoencodeur

etc...

Ensuite, on apprend de manière supervisée à partir de cette

initialisation
132/1
 Réseaux de neurones

Réseaux convolutionnels pour les images

Y. Le Cun.

133/1
 Réseaux de neurones

Cortex visuel

134/1
 Réseaux de neurones

Skip-gram modele pour codage de mots

Mikolov et al. 2013.

NB : représentations continues des mots déjà proposées en

2002/2003.

135/1
 Références

Sommaire

136/1
 Références

Références Ensemble Learning

Y. Amit, D. Geman, and K. Wilder, Joint induction of shape features and
tree classifiers, IEEE Trans. Pattern Anal. Mach. Intell., 19, 1300-1305,
1997.
Breiman, L., Bagging predictors. Mach Learn (1996) 24 : 123.
Y. Freund, R. Schapire, A decision-theoretic generalization of on-line
learning and an application to boosting. In Computational Learning
Theory, 1995.
J. Friedman, T. Hastie and R. Tibshirani, Additive logistic regression : a
statistical view of boosting. Ann. Statist. Vol. 28, No. 2 (2000), 337-407.
Breiman, L., Random Forests. Mach. Learn. (2001), Vol. 45, No. 1, pp
5–32
Tutorial : Ensemble Methods in Machine Learning. T.G. Dietterich,
available at :
http ://[Link]/ tgd/publications/[Link]

137/1
 Références

Références - Réseaux de Neurones

Le cours de Hugo Larochelle (youtube)

Notes de cours IT6266, Université de Montréal, Equipe de Yoshua

Bengio.

Learning Deep Architectures for AI, Yoshua Bengio, Foundations Trends

in Machine Learning, 2009

Dropout : A simple way to prevent overfitting, Srivastava et al. JMLR

2014

Pattern Recognition and Machine Learning, C. Bishop, Springer, 2006.

[Link] : pour tout document y

compris implémentations...

138/1
 Références

Sommaire

139/1
 Références

Références SVM

BOSER, Bernhard E., Isabelle M. GUYON, and Vladimir N.

VAPNIK, 1992. A training algorithm for optimal margin classifiers.
In : COLT ’92 : Proceedings of the Fifth Annual Workshop on
Computational Learning Theory. New York, NY, USA : ACM
Press, pp. 144-152.

CORTES, Corinna, and Vladimir VAPNIK, 1995. Support-vector

networks. Machine Learning, 20(3), 273–297.

A tutorial review of RKHS methods in Machine Learning, Hoffman,

Schölkopf, Smola, 2005 (https:
//[Link]/publication/228827159_A_
Tutorial_Review_of_RKHS_Methods_in_Machine_Learning)

140/1
 Références

Références - Réseaux de Neurones

Le cours de Hugo Larochelle (youtube)

Notes de cours IT6266, Université de Montréal, Equipe de Yoshua

Bengio.

Learning Deep Architectures for AI, Yoshua Bengio, Foundations Trends

in Machine Learning, 2009

Dropout : A simple way to prevent overfitting, Srivastava et al. JMLR

2014

Pattern Recognition and Machine Learning, C. Bishop, Springer, 2006.

[Link] : pour tout document y

compris implémentations...

141/1
 Références

Questions ?

Merci !

142/1