Apprentissage supervisé:

Algorithmes
de « résolution »

Mourad NACHAOUI

ENSA de Khouribga
Sommaire

1. Introduction

2. Optimisation
Gradient descente
Fonctions convexes

1/45
Apprentissage
supervisé et
optimisation

2/45
Composantes d’apprentissage
automatique
• programme A :
algorithme A
• expérience En :
données {xi , yi }
• performance ℓ :
coût : ℓ
• tâche - hypothèses H :
modèle f ∈ H

Optimisation

min ℓ(f , {xi , yi }, i = 1, . . . , n) f̂ = arg min ℓ = A(H, {xi , yi }i=1,...,n , ℓ)

f ∈H f ∈H

3/45
Minimisation du risque empirique
• On cherche : prédicteur minimisant le risque empirique

f̂n ∈ arg min R̂n (f )

f ∈S

sur une classe S de fonctions (S ∈ H )

• pas trop petite pour pouvoir contenir une bonne approximation du
prédicteur de Bayes
• pas trop grande pour éviter le sur-apprentissage (coller trop aux
données, mal généraliser)
• et pour laquelle on sait "résoudre" le problème d’optimisation

4/45
L’apprentissage supervisé : cas général

Données d’apprentissage : (Xi , yi )i=1,...,n ∈ (X × Y)n .

Modèle : y = f (x), pour un certain f ∈ S.
Problème à résoudre pour l’apprentissage :

Trouver un modèle qui permet d’accomplir la généralisation,contrôler la

complexité, réduire l’erreur, et avec un temps raisonnable. 5/45
Exemples de différentes pénalités utilisées
en apprentissage

6/45
regression ridge

7/45
8/45
9/45
10/45
11/45
12/45
13/45
14/45
15/45
Gradient descente
Pour une fonction F : Rd → R, considérons le problème d’optimisation

min F(θ)
θ∈Rd

On suppose que l’on nous donne accès à certains «oracles»: l’oracle d’ordre
k correspond à l’accès à : (F(x), F ′ (x), . . . , F (k) )

Algorithm 1: (Gradient descent (GD))

Choisir θ0 ∈ Rd et pour t > 1, soit

θt = θt−1 − γt F ′ (θt−1 ),

pour une séquence de taille de pas choisie (potentiellement adaptative)

(γt )t>1 .
16/45
Analyse la plus simple: les moindres carrés
ordinaires
Soit Φ ∈ Rn×d une matrice de conception et y ∈ Rn le vecteur des réponses.
L’estimation moindres carrés consiste à trouver un minimiseur θ∗ de
1
F(θ) = ∥Φθ − y∥22
2n
Le gradient de F est F ′ (θ) := ∇θ F(θ) = n1 ΦT Φθ − 1n ΦT y. Notons par
H = ΦT Φ ∈ Rd×d , alors le minimiseur θ∗ est caractérisé par
1
Hθ∗ = ΦT y
n
Utilisant le formule de Taylor et le fait que F ′ (θ) = 0
1 1
F(θ) − F(θ∗ ) = F ′ (θ)T (θ − θ∗ ) + (θ − θ∗ )T H(θ − θ∗ ) = (θ − θ∗ )T H(θ − θ∗ ).
2 2 17/45
Mesures de performance
L’itération de gradient avec pas fixe γt = γ est
γ T
θt = θt−1 − γF ′ (θt−1 ) = θt−1 − Φ (Φθt−1 − y) = θt−1 − γH(θt−1 − θ∗ ),
n
donc
θt − θ∗ = θt−1 − θ∗ − γH(θt−1 − θ∗ ) = (I − γH)(θt−1 − θ∗ ),
par récursivité θt − θ∗ = (I − γH)(θ0 − θ∗ ),

Deux mesures de performance d’optimisation

∥θt − θ∗ ∥22 = (θ0 − θ∗ )T (I − γH)2t (θ0 − θ∗ )

F(θt ) − F(θ∗ ) = (θ0 − θ∗ )T (I − γH)2t H(θ0 − θ∗ ).
18/45
convergence de ∥θt − θ∗∥2
Tenant compte la forme ∥θt − θ∗ ∥2 , il suffit de contrôler les valeurs propres de
(I − γH)2t .
Les valeurs propres de (I − γH)2t sont (1 − γλ)2t pour λ ∈ [λ, λ] une valeur
propre de H.
Donc les valeurs propres de (I − γH)2t ont une magnitude inférieure à

max |1 − γλ|
λ∈[λ,λ]

Choix optimal
on peut vérifier que minimiser maxλ∈[λ,λ] |1 − γλ| se fait en mettant

γ = 2/(λ + λ),

avec une valeur optimale de 1−κ

1+κ ∈ (0, 1), telle que κ = λλ . 19/45
Convergence de F(θt ) − F(θ∗)
• Afin d’obtenir un taux de convergence, nous devrons limiter les valeurs
propres de (I − γH)2t H au lieu de (I − γH)2t .
• La principale différence est que pour les valeurs propres λ de H qui sont
proches de zéro (1 − γλ)2t ne fait pas un fort effet de contraction, mais ils
comptent moins car ils sont multipliés par λ dans la borne.
• Nous pouvons maintenant préciser ce compromis, pour γ ≤ 1/λ, comme

|λ(1 − γλ)2t | ≤ λ exp(−γλ)2t = λ exp(−2γλt)

1 1 1 1
= 2tγλ exp(−γλ) ≤ sup α exp(−α) = ≤
2tγ 2tγ α≥0 2teγ 4tγ

Ceci mène à
1
F(θt ) − F(θ∗ ) ≤ ∥θ0 − θ∗ ∥22 .
4tγ
20/45
(fonction Convexe)

∀η, θ ∈ Rd et α ∈ [0, 1], F(αη + (1 − α)θ) ≤ αF(η) + (1 − α)F(θ).

et si F est différentielle alors

F(η) ≥ F(θ) + F ′ (θ)T (η − θ), ∀η, θ ∈ Rd

Ceci correspond à la fonction F étant au-dessus de sa tangente en θ,

21/45
S
upposons que F : Rd → R est convexe et différentiable. Alors θ∗ ∈ Rd est un
minimiseur global de F si et seulement si

F ′ (θ∗ ) = 0.

Ceci implique que pour la fonction convexe, nous devons seulement

rechercher des points stationnaires. Ce n’est pas le cas pour les fonctions
non convexes.

22/45
 (Forte convexité)
Une fonction différentiable F est dite µ-fortement convexe, avec µ > 0, si et
seulement si
µ
F(η) ≥ F(θ) + F ′ (θ)T (η − θ) + ∥η − θ∥22 , ∀η, θ ∈ Rd .
2
Pour des fonctions deux fois différentiables, cela équivaut à F ′′ < µI
(Lissage)
Une fonction différentiable F est dite L-lisse si et seulement si
L
|F ′ (η) − F(θ) − F ′ (θ)T (η − θ)| ≤ ∥η − θ∥22 , ∀ θ, η ∈ Rd
2
Ceci est équivalent à F ayant un gradient L-Lipschitz, c’est-à-dire

∥F ′ (η) − F ′ (θ)∥22 ≤ L∥η − θ∥22 , ∀ θ, η ∈ Rd .

Pour les fonctions deux fois différentiables, cela équivaut à

−LI ≤ F ′′ (θ) ≤ LI
23/45
Lorsqu’une fonction est à la fois lisse et fortement convexe, on note
τ = L/µ > 1 son nombre de condition. La performance de la descente de
gradient dépendra de ce nombre de condition (voir la descente la plus raide
ci-dessous, c’est-à-dire la descente de gradient avec recherche de ligne
exacte): avec un petit nombre de condition (à gauche), nous obtenons une
convergence rapide, tandis que pour un grand nombre de condition (à droite)
, nous obtenons des oscillations.

24/45
Pour les problèmes d’apprentissage automatique, pour les prédictions
linéaires et les pertes lisses (carrées ou logistiques), alors nous avons des
problèmes lisses. Si nous utilisons un régulariseur carré ℓ2 -régulariseur
µ
2 , nous obtenons un problème µ-fortement convexe. Notez que lors de
l’utilisation de la régularisation, la valeur de µ décroît avec la taille de échantil-
√
lon n, typiquement entre 1/n et 1/ n, conduisant à des nombres de condition
√
entre n et n. Dans ce contexte, la descente de gradient sur le risque em-
pirique, est souvent appelée technique «batch».

Théorème: (Convergence de GD pour les fonctions fortement

convexes)
Supposons que F est L-lisse et µ-fortement convexe. En choisissant γt = 1/L,
les itérations (θt )t≥0 de GD sur F satisfont

F(θt ) − F(θ∗ ) ≤ exp(−tµ/L)(F(θ0 ) − F(θ∗ )).

25/45
• On a forcément µ ≤ L. Le rapport τ := L/µ est appelé nombre de
condition.
• Si nous supposons seulement que la fonction est lisse et convexe (pas
fortement convexe), alors GD avec un pas constant γ = 1/L converge
également quand un minimiseur existe, mais à un rythme plus lent en
O(1/t).
• Le choix de la taille de pas ne nécessite qu’une borne supérieure L sur
la constante de lissage (en cas de surestimation, le taux de convergence
ne se dégrade que légèrement).
• Notez que la descente de gradient est adaptative à une forte convexité:
le même algorithme s’applique aux cas fortement convexes et convexes,
et les deux limites s’appliquent. Cette adaptivité est importante en
pratique, car souvent, localement autour de l’optimum global, la
constante de forte convexité converge vers la valeur propre minimale de
la Hessien à θ∗ , qui peut être très significativement supérieure à µ (la
constante globale).
26/45
Quelques variantes de gradient descente
Pour l’algorithme de gradient descente classique à chaque itération,
nécessite de calculer un gradient «complet» F ′ (θt ) qui pourrait être coûteux.
Une alternative consiste à ne calculer que des estimations stochastiques non
biaisées du gradient gt (θt ), c’est-à-dire telles que E[gt (θt )|θt ] = F ′ (θt ), ce qui
pourrait être beaucoup plus rapide à calculer. Cela conduit à l’algorithme
suivant.
Algorithme (Descente de gradient stochastique (SDG))
Choisir la séquence de taille de pas (γt )t≥0 , choisir θ0 ∈ Rd et pour t ≥ 0, soit

θt+1 = θt − γt gt (θt ).

SGD dans l’apprentissage automatique. Où l’itération t on peut choisir unifor-

mément au hasard it ∈ {1, . . . , n} et définissez gt (θ) = F ′ [ℓ(yit , fθ (xit ))]. Il existe
un «mini-bash» variantes où à chaque itération, le gradient est moyenné sur
un sous-ensemble aléatoire d’indices. 27/45
Accélération Nesterov:
Pour les fonctions convexes, une simple modification de la descente de gra-
dient permet de obtenir de meilleurs taux de convergence. L’algorithme est le
suivant et est basé sur la mise à jour des itérations:
1 ′
θt = ηt−1 − F (ηt−1 )
L
t−1
ηt = θt + (θt − θt−1 ).
t+2
Cette simple modification remonte à Nesterov en 1983, et conduit au taux de
convergence suivant
2L
F(θt ) − F(θ∗ ) ≤ ∥θ0 − θ∗ ∥2
(t + 1)2
.

28/45
Pour les fonctions fortement convexes, l’algorithme a une forme similaire à
celle des fonctions convexes, mais avec tous les coefficients indépendants de
t:
1 ′
θt = ηt−1 − F (ηt−1 )
Lp
1 − µ/L
ηt = θt + p (θt − θt−1 ).
1 + µ/L

et le taux de convergence est

F(θt ) − F(θ∗ ) ≤ L(1 − µ/L)t ∥θ0 − θ∗ ∥2 ,

p

c’est-à-dire que le temps caractéristique de convergence va de τ à τ . Si τ

√
est grand (typiquement d’ordre n ou n pour l’apprentissage automatique),
les gains sont substantiels. En pratique, cela conduit à des améliorations
significatives.
29/45
Méthodes de Newton:
Étant donné θt−1 , la méthode de Newton minimise l’expansion de Taylor du
second ordre autour de θt−1 ,

1
F(θt−1 ) + F ′ (θt−1 )T (θ − θt−1 ) + (θ − θt−1 )T F ′′ (θt−1 )T (θ − θt−1 ),
2
ce qui conduit à
θt = θt−1 − F ′′ (θt−1 )−1 F ′ (θt−1 ),
qui est une itération expansive, car la complexité en temps d’exécution est
O(d3 ) en général pour résoudre le système linéaire . Cela conduit à une con-
vergence quadratique locale: Si ∥θt−1 − θ∗ ∥ assez petit, pour une certaine
constante C, on a (C∥θt − θ∗ ∥) = (C∥θt−1 − θ∗ ∥)2 .

30/45
Descente de proximal gradient:
De nombreux problèmes d’optimisation sont dits «composites», c’est-à-dire
que la fonction objectif F est la somme d’une fonction lisse G et d’une fonction
non lisse H (telle qu’une norme). Il s’avère qu’une simple modification de la
descente de gradient permet de bénéficier des taux de convergence rapides
de l’optimisation en douceur.
Pour cela, nous devons d’abord voir la descente de gradient comme une méth-
ode proximale. En effet, on peut voir l’itération θt = θt−1 − L1 G′ (θt−1 ), comme

L
θt = arg min G(θt−1 ) + (θ − θt−1 )T G′ (θt−1 ) + ∥θ − θt−1 ∥2 ,
θ∈Rd 2

où, pour une fonction L−lisse G, la fonction objectif ci-dessus est une borne
supérieure de G(θ) qui est serrée à θt−1 .
L
θt = arg min G(θt−1 ) + (θ − θt−1 )T G′ (θt−1 ) + ∥θ − θt−1 ∥2 + H(θ),
θ∈Rd 2

où H est laissé tel quel. Il s’avère que les taux de convergence pour G + H
sont les mêmes que l’optimisation douce, avec une accélération potentielle. 31/45
Autres algorithmes
• Stochastic gradient descent
• Coordinate gradient descent
• Accelerated gradient descent
• Averaged gradient descent
• Subgradient descent
• Proximal gradient descent
• Conjugate gradient descent
• Conditional gradient descent
• Quasi Newton methods
• Alternative direction method of multipliers
• Douglas-Rachford
• ... 32/45
Quel algorithme choisir lorsque n et p sont grands

1
L’erreur statistique est de l’ordre de n ∝ ε2
Principe : l’erreur statistique ≈ l’erreur algorithmique

L’algorithme le plus rapide est

le gradient stochastique
33/45
Les différents types de modèles universels
• modèles basées sur les variables
◦ la notion de dictionnaire (base, polynômes, ondelettes. . . )
n
X
f̂ (x) = αk ϕk (x)
k=1

• modèles basées sur les exemples

◦ plus proches voisins
◦ noyaux (SVM)
• combinaison d’éléments simples (partitions)
◦ les forêts aléatoires
◦ le boosting
• modèles profonds (deep learning)
◦ linéaires vs non linéaires : → C’est un problème de représentation
(extraction de caractéristiques) 34/45
La régression logistique

Définition (Modèle probabiliste )

Soit θ ⊂ Rp un ensemble de paramètres. On appelle modèle P un ensemble
de lois de probabilités à valeur dans Y, possédant un densité par rapport à la
mesure de référence sur Y et indexés par Θ : P = {pθ dµ|θ ∈ Θ}
Exemple. Modèles Binomial, Multiomial, Gaussien univarié et multivarié.

Définition. (Vraisemblance)
Soit une donnée y ∈ Y. On appelle vraisemblance la fonction θ → pθ (x)
On considère un ensemble d’entraînement i.i.d. y1 , . . . , yn (dans ce contexte
aussi échantillon). La vraisemblance de l’ensemble d’entraînement est
n
Y
L(θ) := pθ (yi )
i=1
35/45
Principe du maximum de vraisemblance
Principe : un bon choix de paramètre est un choix de paramètre qui maximise
la probabilité des données observées, i.e. qui maximise la vraisemblance.
• principe du à Sir Ronald Fisher
• validé a posteriori par les bonnes propriétés du maximum de
vraisemblance

Reformulation en terme de risque

On définit comme fonction de perte la log-vraisemblance ℓ(θ, y) = − log(pθ (y)).
Le risque associé est
R(θ) = −E[log(pθ (Y))]
En particulier si Y ∼ pθ0 dµ pour θ0 ∈ Θ alors le paramètre cible est θ∗ = θ0 . Le
risque empirique est alors par définition
n
1X
R̂n (θ) = − log(pθ (yi ))
n
i=1 36/45
La régression logistique (Cox, 1958)
Le modèle logistique : yi réalisation d’une variable aléatoire Y ∼ Bernouilli de
paramètre
exp(φ(xi ))T w
p(xi ) =
1 + exp((φ(xi ))T w

Le cout logistique : le max de vraisemblance

n
X
−yi ϕ(xi )T w + log 1 + exp(φ(xi ))T w



R̂n (w) = − log L(w) =
i=1
Cette fonction cout est non linéaire mais
• différentiable
• convexe
• consistante
37/45
38/45
Définition formelle
Soit d une distance sur X. Pour chaque x, on peut ordonner les points de la
base d’apprentissage par leur distance à x :

d(x, Xπ(n) (x) ) ≤ d(x, Xπ(n) (x) ) ≤ . . . d(x, Xπ(n) (x) ).

1 2 n

(n)
πi (x): indice du i-ème point de En le plus proche de x

Prédicteur des k-plus proches voisins

Pour k ∈ {1, . . . , n}, le prédicteur k-ppv est tel que
n o
f̂nk−ppv (x) = "moyenne" des Yπ(n) (x) , 1 ≤ i ≤ n
i

39/45
Définition formelle

Régression :
k
1X
f̂nk−ppv (x) = Yπ(n) (x)
k i
i=1

(moyenne arithmétique)

Classification :
k
X
f̂nk−ppv (x) = arg max 1Y (n)
y∈Y πi (x)
i=1

(classe majoritaire)
40/45
Visualisation (classification binaire)

Classifieur du plus-proche voisin 41/45

Comment choisir k ?
Evaluons le risque d’apprentissage et le risque de test pour différentes
valeurs de k.

• petites valeurs de k: forte variance (sur-apprentissage) overfitting

• grandes valeurs de k: fort biais (le classifieur appris est trop simple) 42/45
Comment choisir k ?
Peut on sélectionner la valeur k̂ ci-dessous ?
(t)
k̂ = k̂(En , Em )
ajusté pour minimiser le risque sur cette base de test particulière...

( ! sur-apprentissage) 43/45
Comment choisir k ?
La méthode la plus courante pour choisir K est la validation croisée.

44/45