Machine learning ENSAK

IID 2 Automne 2023-2024

TP ◦ 3

Le but de ce TP est de vous initier aux techniques de classification. De plus, mené une comparaison des algorithmes traditionnels.
Rappel
Comme la régression, la classification en apprentissage supervisé consiste à minimiser le risque empirique. Contrairement à
la regrssion, dans la classification l’espace de sortie Y est sous ensemble de N. Il existe de nombreuses fonctions de perte pour le
problème de classification. Dans ce TP nous allons voir certains exemples célèbres.
1−yf (x)
1. Perte 0/1: ℓ(y, f (x)) = 2
, y ∈ {−1, 1}.
2. fonction de perte Hinge: ℓ(y, f (x)) = max(0, 1 − yf (x)), y ∈ {−1, 1}.
3. Perte quadratique : ℓ(y, f (x)) = (1 − yf (x))2 , y ∈ {−1, 1}.
4. Perte logistique, ou logistic loss : ℓ(y, f (x)) = log(1 + exp(−yf (x)), y ∈ {−1, 1}.
Étant donné que la perte de charnière n’est pas lisse, elle est généralement remplacée par une fonction lisse. L’une d’entre elles est
la perte de charnière au carré
l(ν) = max(0, 1 − ν)2 (1)
où ν = 1 − yf (x). C’est convexe, quadratique par morceaux et différentiable.
Une autre méthode consiste à remplacer la perte de charnière au carré par son approximation lisse

l(ν) = (1 − ν) + η ln(1 + e−1−ν ). (2)

Une troisième approche consiste à remplacer la Perte de charnière par:


0
 si ν ≥ 1
l(ν) = 1 − ν si ν < 1− (3)

(1 − ν)2 sinon
1
2

Une quatrième technique de lissage est présenté par

 
1−ν
Kh (ν) = (1 − ν)H (4)
h

où h est une largeur de bande et H(·) est la fonction lisse définie par :

0
 si ν ≤ −1
H(ν) = 21 + 15 ν − 32 ν 3 + 51 ν 5


16
si − 1 < ν < 1

1 sinon


Une 5eme technique consiste à remplacer hinge loss par

p
Λγ,ξ (y, f x) = 1 − yf (x) + ξγ 2 + (1 − yf (x))2 (5)

Jeux de données synthétique :

%% data generation
NN1 = 120; NN2 = 50; % Class sizes
N1 = 100; N2 = 30; % trianing Class sizes
c1=randn(NN1,2);
c2=randn(NN2,2)+3;
x0=[c1;c2];
x = [c1(1:N1,:);c2(1:N2,:)];
t = [repmat(0,N1,1);repmat(1,N2,1)];
N = size(x,1);

1 Problème de classification avec le méthode du gradient

1. En utilisant la méthode de noyaux reproduisant (nouyau Gaussien ) implèmenter la méthode de classification.
2. Comparer les différentes fonction de perte. en particulier pour le fonction Hinge qui n’est pas lisse comparer les différentes
techniques de lissage proposés.
 3. Implémenter et comparer les algorthmes suivants en utilisant la fonction de perte lisse (5) appliqués sur les données d’assurance
ci-joint.
Algorithm 1: Accelerated SGD algorithm
input : n, ε, α0 , v0 = α0
output: α∗
For k ≥ 0 do
(i) Compute
√
1 √ 1 λ
ν= , βk = 1 − λν, δk = √ , b1+k = √ 1+k
µ λν (1 − λν) 2
1
a1+k = √ 1+k
,
(1 − λν) 2
Set
δk βk b2k+1 ν
σk = ,
δk βk b2k+1 ν + a2k+1
ωk = σk vk + (1 − σk )αk ,
(ii) Select randomly ik ∈ {1, . . . , n} and then update
i
αk+1 = ωk − ν∇Jγ,ξ
k
(ωk )
i
vk+1 = βk vk + (1 − βk )ωk − δk ν∇Jγ,ξ
k
(ωk ).
Set k = k + 1
While no convergence

Algorithm 2: Batch-DG algorithm with optimal learning rate

input : n, ε, h0 > 0, α0 , ξ, γ > 0,
output: α∗
For k ≥ 0 do
(i) Compute dk = ∇Jγ,ξ (αk ),
(ii) update
αk+1 = αk − hk ∇Jγ,ξ (ωk )
Γk = ([KKT + λIn )dk ]T dk
n dTk dk
hk = .
2 Γk
Set k = k + 1
While (∥dk ∥ ≥ ε)

While the mini-batch Adam algorithm is summarized as follows.

Algorithm 3: Mini-batch-Adam algorithm
input : n, ε, υ > 0, Batch Size h0 > 0, α0 , ξ, γ > 0, β1 = 0.9, β2 = 0.999, m0 = α0 , v0 = α0 ,
output: α∗
num batch = [ Batchn Size ], For k ≥ 1 do Define Ip a random permutation of the list {1, . . . , n}
(i) For j ∈ {0, . . . , num batch}
Si = j ∗ batch Size + 1 Sl = Si + batch Size − 1 Ij = Ip (Si : Sl )
Ip
Compute Gk := ∇Jγ,ξ (αk )
(ii) update
mk = β1 mk−1 + (1 − β1 )Gk
vk = β2 vk−1 + (1 − β2 )G2k
mk
m̂k =
1 − β1k
vk
v̂ =
1 − β2k
m̂
αk+1 = αk − h √ .
v+υ
Set k = k + 1
While no convergence

2 Principe de k-plus proche voisin

C’est une approche simple et directe. Elle ne nécessite pas d’apprentissage mais simplement le stockage des données d’apprentissage.
Son principe est le suivant:
Une donnée de classe inconnue est comparée à toutes les données stockées. On choisit pour la nouvelle donnée la classe
majoritaire parmi ses K plus proches voisins (Elle peut donc être lourde pour des grandes bases de données) au sens d’une distance
choisie.

3 Besoin d’une distance

Afin de trouver les K plus proches d’une donnée à classer, on peut choisir la distance euclidienne. Soient deux données représentées
par deux vecteurs xi et xj , la distance entre ces deux données est donnée par

d
! 21
X
d(xi , xj ) = (xil − xjl )2 .
l=1

4 Questions
1. Implémenter en Matlab, l’algorithme des K-plus proches voisins pour prédire les classes de nouvelles données à partir de
données étiquetées (données d’apprentissage). On commencera par le 1-ppv. L’algorithme 1nn est donné par le pseudo-code
1 ci-après.

2. Modifier votre code pour tester et comparer la classification sur différentes valeures de K = [1, 2, 5, 10, 20, 50, 59];
3. Donner la visualisation des résultats de comparaison pour chaque K.
4. Valider les résultats sur la base ”iris dataset” déjà dans matlab.
5. Modifier la distance comme suit
d
X
d(xi , xj ) = |xil − xjl |,
l=1

Puis commenter les résultats.

6. Même question que précidente avec
d
! p1
X
d(xi , xj ) = (xil − xjl )p .
l=1

avec p ̸= 1, 2