Machine learning ENSA de Khouribga

IID 2 2023-2024

TP ◦ 2

Le but de ce TP est de revisiter certaines notions vues dans le chapitre 4 qui introduit l’apprentissage automatique et
l’optimisation du point de vue pratique.

Rappel
Notions : Différentiabilité, différentes variantes d’algorithmes de descente de gradient, Matlab/Scilab ou n’importe quel outil
de programmation et de visualisation.

1 Préliminaire sur les espaces de Hilbert à noyau reproduisant

Nous commençons par présenter quelques rappels sur les espaces de Hilbert, les noyaux et les noyaux reproduisants. Ensuite, les
caractéristiques de tels noyaux sont données. Puis nous définissons la notion des espaces de Hilbert à noyau reproduisant. Ensuite,
nous introduisons un des éléments fondamentaux des méthodes à noyaux qui est le théorème de Représentation.

Définition 1 (Espace Hilbert) L’espace de Hilbert est un espace complet muni d’un produit scalaire, c’est-à-dire qu’il s’agit d’un
espace de Banach muni d’un produit scalaire.

Définition 2 (noyau défini positif ) Un noyau défini positif (n.d.p.) sur l’ensemble Ω est une fonction K : Ω × Ω → R symétrique:

∀(x, y) ∈ Ω2 , K(x, y) = K(y, x),

et qui satisfait, pour tout N ∈ N, (x1 , ..., xN ) ∈ ΩN et (a1 , ..., aN ) ∈ RN :

N X
X N
ai aj K(xi , xj ) ≥ 0
i=1 j=1

Théorème 1 Si K est un n.d.p. sur un espace Ω quelconque, alors il existe un espace de Hilbert H muni du produit scalaire ⟨., .⟩H
et une application ϕ : Ω 7→ H tels que :
∀(x, y) ∈ Ω2 , K(x, y) = ⟨ϕ(x), ϕ(y)⟩H .

1.0.1 Espace de Hilbert à noyau reproduisant (RKHS)

Soit Ω un espace quelconque, et (H, ⟨., .⟩H ) un espace de Hilbert de fonction.

Définition 3 Une fonction K : Ω 7→ R est appelée un noyau reproduisant (noté n.r.) si et seulement si :
ˆ H contient toutes les fonctions de la forme
∀x ∈ Ω, Kx : y 7→ K(x, y)
ˆ Pour tout x ∈ Ω et f ∈ H, on a:
f (x) = ⟨f, Kx ⟩H
Si un n.r. existe, H est appelé un espace de Hilbert à noyau reproduisant (RKHS).

1.0.2 Propriétés des n.r. et RKHS

Théorème 2 (Aronszajn, 1950)
ˆ Si un n.r. existe, il est unique.
ˆ Un n.r. existe si et seulement si ∀x ∈ Ω, la fonctionnelle f 7→ f (x) (de H dans R) est continue.
ˆ Un n.r. est un noyau d.p.
ˆ Réciproquement, si K est d.p., alors il existe un RKHS ayant K pour n.r.
ˆ Si K est un n.r., il vérifie la propriété reproduisante:

∀(x, y) ∈ Ω2 , ⟨Kx , Ky ⟩H = K(x, y)

.
1.0.3 Théorème de Représentation
Nous pouvons constater que sous certaines conditions, la solution optimale d’un problème d’optimisation dans H peut s’écrire sous
la forme d’une combinaison de noyaux, indépendamment de la dimension de H. Cette constatation est formulée par le théorème
suivant :

Théorème 3 (Théorème de Représentation) Soient un espace non vide Ω, un noyau défini positif K sur Ω×Ω, soient (x1 , y1 ), ..., (xd , yd ) ∈
Ω × R, une fonction réelle g strictement monotone croissante sur [0, ∞[, et une fonction coût arbitraire c. Soit H l’espace de Hilbert
associé au noyau K, avec Kxi = K(xi , .). Toute fonction f ∈ H minimisant la fonctionnelle régularisée
c ((x1 , y1 , f (x1 )), ..., (xd , yd , f (xd ))) + g (∥f ∥) ,
admet une représentation de la forme
d
X
f= αi Kxi .
i=1

1.0.4 Exemples de RKHS

Des exemples très courants de noyaux RKHS symétriques sont
ˆ linéaire :
K(x, x′ ) = xT x′ + c, x, x′ ∈ Rd , c∈R
ˆ polynômial :
K(x, x′ ) = (αxT x′ + c)d , x, x′ ∈ Rd , c∈R
ˆ Gaussien :
∥x − x′ ∥2
K(x, x′ ) = exp(− ), x, x′ ∈ Rd
2σ 2
ˆ exponentiel :
∥x − x′ ∥
K(x, x′ ) = exp(− ), x, x′ ∈ Rd
2σ 2
ˆ Laplacien :
∥x − x′ ∥
K(x, x′ ) = exp(− ), x, x′ ∈ Rd
σ
ˆ Sinc noyau :
n
Y sin(σ(xi − x′i )
K(x, x′ ) = ), x, x′ ∈ Rd
i=1
xi − x′i

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.
Nous allons étudier du point de vue pratique l’impact des trois ingrédients cités dans le schéma. A savoir,
l’optimisation, la fonction de perte (mesure d’erreur) et la régularisation.
On considère le couple de variables aléatoires (X, Y ), tel que X suit une loi uniforme sur [0, 1] et Y =
f (X) + ε où f ∗ (x) = cos(2x) et ε est un bruit Gaussien indépendant de X de variance unité et de moyenne
∗

nulle.
2 Impact du choix de l’espace d’hypothèse
Exemple 1
On se place dans le cadre où la fonction de perte est quadratique ∥ · ∥2 , et α = 0. Nous choisirons comme
outil d’optimisation le gradient descente. Notre objectif est d’étudier l’influence du choix d’un sous espace
d’hypothèse S. Nous considérons que
n
( )
X
S = f : Rd 7→ R, | f (x) = ωi K(x, xi ), x ∈ R et ω ∈ Rn .
i=1

Le problème d’apprentissage supervisé revient à chercher fˆ ∈ S qui réalise le minimum du risque empirique
n
1X
J (ω1 , . . . , ωn ) := ∥f (xi ) − yi ∥2 .
n
i=1

1. Calculer le gradient

∇Jω (ω1 , . . . , ωn ) = (∂ω1 J (ω1 , . . . , ωn ), . . . , ∂ωn J (ω1 , . . . , ωn ))T .

2. On considère que K(x, x′ ) = xT x′ + c noyau linéaire. En utilisant l’algorithme 1 de gradient descente,

estimer fˆ en se basant sur les points des données d’entraı̂nement. Afficher le résultat obtenu sur le même
graphique que les données. Puis essayer l’estimateur fˆ sur les données de test.

3. Afficher les résultats si on cherche à estimer les modèles suivants :

(a) f ∗ (x) = |x|, x ∈ [−1, 1]

(b) f ∗ (x) = 3∥x∥32 − 2∥x∥22 + 3∥x∥2 + 3, x ∈ [−1, 1]3
(c) f ∗ (x) = sin(x1 + x2 ) x ∈ [−2, 2]2
(d) f ∗ (x) = 3∥x∥32 − 2∥x∥22 + 3∥x∥2 + 3, x ∈ [−1, 1]3
(e) f ∗ (x) = 1
3 (x1 + x2 )3 − 14 (x1 + x2 ) , x ∈ [−1, 1]2

4. Afficher le risque empirique en fonction des itérations.

∥f ∗ −y∥2
5. Calculer l’erreur relative ∥y∥2 pour chaque case, puis regrouper les résultats dans un tableau.

6. On répète le même travail en considérant le noyau polynômial.

7. On répète le même travail en considérant le noyau Gaussien. Vérifier l’influence du paramètre σ sur les
résultats de prédiction.

8. Comparer les résultats de prédiction obtenus en utilisant les différents noyaux (Gaussien, exponentiel,
Laplacien, Sinc).

9. En utilisant le noyau qui donne le meilleur résultat d’après le tableau de la question précédente, appliquer
l’approche pour la prédiction d’un modèle issu de données réelles.

3 Impact du choix de la régularisation

Notre objectif ici est d’étudier l’influence du terme de régularisation Ω(f ), ainsi que le coefficient α.

Exercice 2:
1. Cas de régularisation de Tikhonov (Regression ridge). Reprendre l’approche étudiée dans l’exercice 1 en
considérant cette fois-ci que α ̸= 0. Calculer le gradient de J dans ce cas. Étudier l’influence du choix de
α sur la convergence de l’algorithme et sur la qualité de prédiction.
 2. Cas de régularisation L1 (Regression LASSO Ω(f ) = ∥f ∥1 ). Dans ce cadre on ne peut pas utiliser
l’algorithme de gradient car Ω(f ) n’est pas différentiel. Nous avons donc deux façons pour résoudre ce
problème d’apprentissage. On utilise soit un algorithme qui n’a pas besoin de calcul du gradient, soit un
algorithme basé sur le calcul du proximal. Puisque nous nous intéressons à l’influence de la régularisation,
nous allons opter pour une méthode de lissage. Cela consiste à pénaliser le module de la façon suivante :

for γ > 0 ∥f ∥γ1 = (f + γ)2 .

p

Comme ∥f ∥γ1 est différentiable, on peut appliquer l’algorithme de gradient descente. Reprendre l’approche
étudiée dans la question précédente. Calculer le gradient de J γ dans ce cas. Étudier l’influence du choix
de α sur la convergence de l’algorithme et sur la qualité de prédiction. Enfin, tester le rôle de γ.

3. Elastic net regularization : il consiste à utiliser une combinaison de régularisation Ridge et LASSO de la
façon suivante
Ω(f ) = λ1 ∥f ∥22 + λ2 ∥f ∥1 .
En utilisant la même pénalisation, reprendre l’approche étudiée dans la question précédente. Calculer le
gradient de J γ dans ce cas. Étudier l’influence du choix de λ1 et λ2 sur la convergence de l’algorithme et
sur la qualité de prédiction.

4 Impact du choix de l’algorithme d’optimisation

Notre objectif ici est d’étudier l’intérêt de l’algorithme d’optimisation sur la qualité de prédiction des modèles.
Nous allons tester 5 algorithmes d’optimisation. A savoir, l’algorithme de gradient descente classique, sa variante
stochastique, son accélération Nestrov et l’algorithme de Newton, puis la méthode proximale pour les fonctions
coût non-différentielles.

5 Impact du choix de la fonction de perte

Notre objectif ici est d’étudier l’influence du choix de la fonction de perte ℓ. Nous allons nous restreindre à
quatre fonctions de perte. A savoir, quadratique ℓ(f ) = ∥f ∥2 , perte absolue (ℓ(f ) = |f |), ϵ-insensitive loss
ℓ(f ) = max(0, |f | − ϵ), Huber loss (
1 2
f si |f | ≤ δ
ℓ(f ) = 2 1
δ(|f | − 2 δ) sinon