Travaux Pratiques Joseph Salmon

Apprentissage supervisé
Les sources et liens utiles sont sur le site du cours et/ou de l'auteur. Commencez par télécharger des
chiers utiles pour ce TP :
 le chier source tp_ML_supervise_source.py
 un exemple de scripte d'utilisation tp_ML_supervise_scripte.py

- Découverte de Python -

Consulter les pages suivantes pour démarrer ou bien trouver quelques rappels
??? http://perso.telecom-paristech.fr/~gramfort/liesse_python/1-Intro-Python.html
??? http://perso.telecom-paristech.fr/~gramfort/liesse_python/2-Numpy.html
??? http://perso.telecom-paristech.fr/~gramfort/liesse_python/3-Scipy.html
??? http://scikit-learn.org/stable/index.html
?? http://www.loria.fr/~rougier/teaching/matplotlib/matplotlib.html
?? http://jrjohansson.github.io/

- Classification binaire -

Introduction

Dénitions et notations
On rappelle que dans la cadre de la classication binaire supervisée on utilise les notations :
 Y l'ensemble des étiquettes (ou labels en anglais), communément Y = {−1, 1} dans le cas de la
classication binaire,
 x = (x1 , . . . , xp ) ∈ X ⊂ Rp est un attribut (ou un feature en anglais),
 Dn = {(xi , yi ), i = 1, . . . n} un ensemble d'apprentissage contenant n exemples et leurs étiquettes,
 Il existe un modèle probabiliste qui gouverne la génération de nos observations selon des variables
i.i.d
aléatoires X et Y : ∀i ∈ {1, . . . , n}, (xi , yi ) ∼ (X, Y ).
 On cherche à construire à partir de l'ensemble d'apprentissage Dn une fonction fˆ : X 7→ {−1, 1}
qui pour un point inconnu ( i.e., qui n'est pas présent dans l'ensemble d'apprentissage) prédit son
étiquette : fˆ(x).

Génération articielle de données

Dans un but d'expérimentation, il est plus aisé de travailler sur des données engendrées articiellement.
On considère dans cette partie que les observations sont décrites en deux dimensions (an de pouvoir les
visualiser facilement).

1. Étudiez la fonction rand_gauss(n,mu,sigma) qui engendre n observations selon la loi normale

multidimensionnelle de moyenne le vecteur mu et de matrice de covariance considérée diagonale de
diagonale sigma. Étudiez ensuite les fonctions rand_bi_gauss, rand_clown et rand_checkers.
Que renvoient ces fonctions ? À quoi correspond la dernière colonne ?

2. Sauvegardez quelques jeux de données an de les utiliser dans la suite : pour chacun, il faudra
sauver dans une variable les données sous forme d'un tableau à deux colonnes, et dans une autre
les labels correspondants à chaque exemple.

3. Utilisez la fonction plot_2d an d'acher quelques jeux de données.

page 1
Travaux Pratiques Joseph Salmon

Extensions aux cas multi-classe

Dans le cas où la variable de sortie Y compte plus de deux modalités, il existe plusieurs façon d'étendre
directement les méthodes du cas binaire.

"Un contre un". Dans le cas où l'on cherche à prédire un label pouvant prendre K ≥ 3 modalités, on
2
peut considérer toutes les paires de labels (k, l) possibles, 1≤k<l≤K (il y en a CK ) et ajuster un
classieur Ck,l (X) pour chacune d'entre elles. La prédiction correspond alors au label qui a gagné le plus
de "duels".

"Un contre tous". Pour chaque modalité k, on apprend un classieur permettant de discriminer entre
les populations Y =k et Y 6= k . À partir des estimations des probabilités a posteriori, on aecte le label
estimé le plus probable.

Analyse Discriminante Linéaire

Le nom anglais est Linear Discirmiant Analysis (LDA) et il est utile pour trouver de l'aide pour la
partie numérique.

Aspect théorique
On considère deux populations gaussiennes dans Rp ayant la même structure de covariance. On
observe des points dans le mélange de ces deux populations.
Les lois conditionnelles de X sachant Y = +1 (respectivement Y = −1) sont des gaussiennes multiva-
riéesNp (µ+ , Σ) (respectivement Np (µ− , Σ)). On notera leur densités respectives f+ et f− . Les vecteurs µ+
p
et µ− sont dans R et la matrice Σ est (symétrique) de taille p × p. On note également π+ = P{Y = +1}.
On rappelle que la densité p-dimensionnelle de la loi Np (µ, Σ) est donnée par :

 
1 1 > −1
f (x) = p exp − (x − µ) Σ (x − µ) .
(2π)p/2 det(Σ) 2

Σ = E (X −E(X))(X −E(X))> ) .
 
et que la matrice de covariance d'un vecteur aléatoire X est dénie par

1. En utilisant la formule de Bayes donner la formule des probabilités a posteriori : P{Y = +1 | X = x},
P{Y = −1 | X = x}, comme fonctions de f+ , f− et π+ .
2. Exprimer le log-ratio des deux classes :

 
P{Y = +1 | X = x}
log
P{Y = −1 | X = x}

en fonction de π+ , µ+ , µ− et Σ.
3. On dispose à présent d'un échantillon de ce mélange et on suppose que π+ , µ+ , µ− et Σ sont
des paramètres inconnus. On suppose que l'échantillon considéré contient
Pn n observations notées
(x1 , y1 ), . . . , (xn , yn ) et que i=1 1{yi = +1} = m. En utilisant la méthode des moments utilisée

en estimation paramétrique, proposer des estimateurs π

b+ , µ
b+ , µ
b− et Σ
b des paramètres.

4. Justier le choix du classieur suivant :

(
1 si x> Σ
b −1 (b
µ+ − µ b>
b− ) > 12 µ+Σ
b −1 µ b>
b+ − 12 µ−Σ
b −1 µ
b− + log(1 − m/n) − log(m/n) ,
−1 sinon

5. Que se passe-t-il lorsque les matrices de covariance ne sont pas égales ? Quelle forme prend la
frontière ?

6. Comment généraliser l'analyse discriminante linéaire au cas multi-classes ?

page 2
Travaux Pratiques Joseph Salmon

Mise en oeuvre
Il s'agit ici d'appliquer concrètement la méthode ci-dessus sur des observations simulées puis à une
base de données réelles. Dans ce dernier cas, on scindera aléatoirement les données en deux échantillons :
un échantillon d'apprentissage (70% des données environ) à partir duquel les paramètres régissant le score
seront estimés et un échantillon test (les 30% restant) sur lequel on évaluera la performance de la règle
de score précédemment apprise.
Le paquet sklearn met à disposition un grand nombre d'algorithmes usuels de l'apprentissage sta-
tistique. Pour commencer, importez le paquet sklearn.lda qui contient en particulier la classe LDA qui
nous servira d'exemple dans la suite.

from sklearn.lda import LDA

Pour utiliser ces algorithmes, il est nécessaire de procéder par étape en Python. Nous allons voir en
détail le processus pour l'analyse discriminante linéaire tout d'abord.

7. Créer un modèle LDA :

my_lda = LDA()

Vous pouvez paramétrer le modèle lors de sa création (en passant des arguments) ou bien par la
suite directement par l'intermédiaire de la variable.

8. An d'apprendre le modèle sur une matrice de données dataX et de labels dataY, on utilise fit.
my_lda.fit(dataX,dataY)

9. Appliquer l'analyse discriminante linéaire sur les données du mélange de gaussiennes générées par
rand_bi_gauss. Estimer son erreur de prédiction au moyen de l'échantillon test (comparer l'esti-
mation à l'"erreur d'apprentissage"). Tracer la frontière.

10. Appliquer la classication par régression logistique sur les données non gaussiennes rand_clown et
rand_checkers.

Régression logistique

Importer le paquet sklearn.linear_model qui contient en particulier la classe LogisticRegression

qui nous servira d'exemple dans la suite.

from sklearn import linear_model

Pour utiliser ces algorithmes, il est nécessaire de procéder par étape en Python. Nous allons voir en
détail le processus pour la régression logistique.

1. Créer un modèle LogisticRegression :

my_log = linear_model.LogisticRegression()

Vous pouvez paramétrer le modèle lors de sa création (en passant des arguments) ou bien par la
suite directement par l'intermédiaire de la variable

2. An d'apprendre le modèle sur une matrice de données dataX et de labels dataY, on utilise fit
my_log.fit(dataX,dataY)

On pourra s'inspirer de l'exemple suivant pour utiliser des variantes de régression :

http://scikit-learn.org/stable/auto_examples/linear_model/plot_ols.html#example-
linear-model-plot-ols-py
http://scikit-learn.org/stable/auto_examples/linear_model/plot_iris_logistic.html
3. À quoi correspond la variable coef_ du modèle ? intercep_ ?

4. Que vous retourne la fonction predict ? Et la fonction score ?

5. Utiliser la fonction frontiere pour visualiser la frontière de décision.

. s données issues de la base zipcode (modalités

6. Appliquer la classication par régression logistique e
2 et 3) disponibles sur le site http://www-stat.stanford.edu/ElemStatLearn.

page 3
Travaux Pratiques Joseph Salmon

Le perceptron

Un perceptron est un classieur linéaire binaire qui projette chaque observation x dans R. L'ensemble
des frontières de décision considérées est alors l'ensemble des hyperplans (ane) de Rp dénis pour un
certain vecteur w = (w0 , w1 , · · · , wp ) ∈ Rp+1 par
p
( )
X
Hw = x : fˆw (x) = w0 + wi xi = 0 .
i=1

Pour classer une observation x, il s'agit simplement de considérer la position de

 x par rapport à

l'hyperplan Hw . Cela revient à prédire comme étiquette de x la valeur de sign fˆw (x) , où la fonction

sign est dénie par


1
 si x > 0,
sign(x) = −1 si x < 0,

0 sinon.


L'objectif est de trouver l'hyperplan qui sépare au mieux les données selon leur étiquette. Le vecteur w
est appelé vecteur de poids (et w0 l'ordonnée à l'origine, ou intercept en anglais).

Perceptron simple
Nous supposerons dans cette partie introductive que nos données sont en deux dimensions (p = 2).
Utilisez les données articielles pour illustrer les questions suivantes.

1. A quoi correspond la frontière de décision du perceptron ? Trouvez (à la main) une bonne séparatrice.
Quand est-ce que fˆw (x) est grand ? négatif ? positif ? Quelle signication géométrique ?

2. Codez une fonction predict(x,w) qui à partir d'une matrice x et d'un vecteur poids w renvoie
le vecteur de prédiction fˆw (x). Codez de même une fonction predict_class(x,w) qui renvoie le
 
vecteur d'étiquettes prédites sign fˆw (x) .

Fonction de coût
An de mesurer l'erreur sur l'ensemble d'un jeu de données Dn il est nécessaire de se xer une fonction
+
`
de perte
h : Y × R →
7 i R qui mesure le coût d'une erreur lors de la prédiction d'un exemple. Le coût

Cw = E `(fˆw (x), y) est l'espérance de la fonction de perte sur l'ensemble des données.

Trois fonctions de perte sont utilisées habituellement :

 le pourcentage d'erreur : ZeroOneloss(y, fˆw (x)) = |y − sign(fˆw (x))|/2

quadratique : MSEloss(y, fˆw (x)) = (y − fˆw (x)) =
2
 l'erreur
 l'erreur hinge (i.e., charnière en français) : HingeLoss(y, fˆw (x)) = max(0, 1 − y · fˆw (x))
Cette partie à pour but d'étudier ces diérentes fonction de pertes.

3. Codez ces trois fonctions (en bloc de préférence, de manière à ce que x soit la matrice de données,
et y le vecteur des labels et qu'elles renvoient le vecteur des pertes).

4. Pour un w xé, sur un exemple 2D, comment varient ces fonctions en fonction de fˆw (x) ? Et de x?
Quelle est l'interprétation géométrique ?

5. Comment observer graphiquement l'évolution de ces fonctions selon w pour une base d'exemples
xée en 2D (pensez à l'utilité de w0 ) ? Tracer en 2D (grâce à la fonction fonction frontiere par
exemple) le coût sur une base d'exemple en fonction de w. Où se situe le vecteur

n
!
∗ 1X ˆ
w ∈ arg min `(fw (xi ), yi )
w∈Rp+1 n i=1

minimisant l'erreur empirique (correspondant à la séparatrice minimisant l'erreur) ? Quelle(s) pro-

priété(s) remarquable(s) possèdent (ou non) ces fonctions ?

page 4
Travaux Pratiques Joseph Salmon

Apprentissage du perceptron - Algorithme de descente du gradient

Dans le cas général, il est bien sûr impossible de faire une recherche exhaustive de l'espace Rp+1 où
évolue w an de trouver le minimum. On utilise pour cela l'algorithme de descente du gradient, une
méthode usuelle et générale d'optimisation de fonction diérentiable. La méthode est itérative : à chaque
pas, le point courant est corrigé dans la direction du gradient, mais en sens opposé. L'algorithme converge
dans le cas général vers un minimum local. Le minimum atteint est global en particulier pour les fonctions
convexes.

L'algorithme est le suivant :

Algorithme 1 : Perceptron
Data : les observations et leurs étiquettes Dn = {(xi , yi ) : 1 ≤ i ≤ n} ; le pas de gradient :  ;
le nombre maximal d'itérations : niter ;
Result : w
initialiser (aléatoirement) w; initialiser j=0
while j ≤ niter do
wold ← w
for i = 1 to n do
w ← wold − ∇w `(fˆwold (xi ), yi )
j ←j+1

6. Expérimentez sur diérents jeux de données : utiliser soit les fonctions fournies, soit le paquet
sklearn. On peut aussi utiliser à cet eet la fonction SGD (pour Stochastique Gradient Descent )
dont une description est donnée sur la page : http://scikit-learn.org/stable/modules/sgd.
html
from sklearn.linear_model import SGDClassifier

Étudiez les performances au moins selon les points suivants : nombre d'itérations, le choix de la
fonction de coût, la diculté du problème. Observez vous des comportements étranges ? Quelles
raisons ?

7. Une variante de l'algorithme, dite stochastique (le précédent est communément appelé batch, i.e., lot
ou stock en français), consiste à ne prendre en compte la correction que sur un exemple tiré aléa-
toirement à chaque itération. Modiez le code en conséquence. Étudiez comme précédemment le
comportement de l'algorithme. Quelles conclusions en tirez-vous ? Dans quel cas doit-on utiliser
quelle variante ?

8. Question optionnelle : Étudier numériquement la vitesse de convergence dans le cas suivant : les Xi
sont des points uniformément repartis sur les segments {0} × [0, M ] (alors les yi valent −1) ou bien
sur le segment {δ} × [0, M ] (alors les yi valent −1). De plus la proportion de de 1 est égal à 1/2.
On regardera l'impact de δ, M et n sur le temps de convergence du perceptron.
9. Proposez des variantes sur les conditions d'arrêt de l'algorithme.

10. Quel est le principal problème du perceptron ?

11. Trouver un fonction de perte telle que l'algorithme du perceptron soit équivalent à la version suivante
(qui est la version initiale de l'algorithme) :

Pour en savoir plus sur le point de vue classique : hagan.okstate.edu/4_Perceptron.pdf

Enn, pour un point de vue plus moderne sur la technique du gradient stochastique on peut consulter
[3].

Perceptron : linéaire... vraiment ?

1. Quelle est la formule analytique d'une ellipse, d'une hyperbole et d'une parabole en 2D ?

2. Proposez une méthode pour réussir à classier le jeu de données clown. Peut-on généraliser au
delà ? On pourra utiliser la fonction poly2 du chier source associé au TP, qui plonge les données
bi-dimensionnel dans l'espace des fonction polynomiale de degré 2 en les données. Comment l'utiliser
pour apprendre un perceptron ?

page 5
Travaux Pratiques Joseph Salmon

Algorithme 2 : Perceptron classique

Data : les observations et leurs étiquettes Dn = {(xi , yi ) : 1 ≤ i ≤ n} ; le pas de gradient :  ;
le nombre maximal d'itérations : niter ;
Result : w
initialiser (aléatoirement) w; initialiser j=0
while j ≤ niter do
wold ← w
i=0
while j ≤ niter and fˆwold (xi ) · yi ≤ 0 do
w ← wold + (1, xi ) · yi
j ←j+1

3. Sur le jeu de données clown, faites quelques expériences en transformant vos données et tracez les
frontières de décision.

page 6
Travaux Pratiques Joseph Salmon

La méthode des k -plus proches voisins

L'algorithme des k-plus proches voisins (k -nn : pour k-neighrest neighbors en anglais) est un algorithme
intuitif, aisément paramétrable et souvent performant pour traiter un problème de classication.
Le principe de l'algorithme est le suivant : pour chaque point x on commence par déterminer les k
plus proches voisins Vk (x) = {x1 , . . . , xk }. La classe associée à x est la classe majoritaire dans Vk (x).
De manière formelle, soit une distance d : Rp × R p 7 → R et une fonction poids α : R+ 7→ R+
décroissante, la décision pour un point x est

 
X
fˆk (x) ∈ arg max  α(d(x, v)) .
y∈{−1,1}
v∈Vk (x) : (v,y)∈Dn

Si α est constant cela revient au vote majoritaire parmi les voisins.

Nous utiliserons le paquet sklearn.neighbors. En suivant les mêmes étapes que précédemment,
faites tourner sur un exemple cet algorithme de classication.

y = −1 y = −1

x x
fˆk (x) = −1 fˆk (x) = −1

y=1 y=1

(a) k=3 (b) k=5

Figure 1  Exemple des plus proches voisins pour deux valeurs du paramètres

4. Faites varier le nombre de voisins pris en compte. Quels sont les nombres remarquables ?

5. Expérimenter en comparant les frontières de décisions apprises : dans quelles cas la frontière est
complexe ? simple ?

6. Un autre poids très utilisée est un poids gaussien, qui renvoie une valeur proportionelle à e−d . À
quel type de problème répond l'utilisation de poids variable en fonction de la distance ?

7. Quel est le taux d'erreur sur vos données d'apprentissage ? est-ce normal ? Que dire des prédictions
sur de nouveaux exemples ? Quels points sont les plus sujet à erreurs ? Comment évaluer empiri-
quement mais de manière précise l'erreur sur les données articielles ? Qu'en concluez vous pour
des données réelles ?

8. Sur plusieurs jeux de données, sous plusieurs conditions de bruits, tracez les diérentes courbes
d'erreurs. Quel est la meilleure valeur de k? Est-ce toujours la même ?

9. A votre avis, quels sont les avantages et les inconvénients des k -nn : optimalité ? temps de calcul ?
expressivité ? passage à l'échelle ? interprétabilité ?

10. Appliquer la méthode k -nn (version multi-classe) aux données issues de la base zipcode de
scikitlearn avec diérents choix de K ≥ 1. On pourra se référer à http://scikit-learn.org/
stable/_downloads/plot_digits_classification.py pour le chargement et la manipulation de
la base de donnée.

Estimer la matrice de confusion (P{Y = i, CK (X) = j})i, j associée au classieur CK ainsi obtenu.
Proposer une méthode pour choisir K et la mettre en oeuvre.

page 7
Travaux Pratiques Joseph Salmon

Arbres de régression - Algorithme CART

On pourra se référer à [2], chapitre 9.2 pour plus de détails sur les arbres. La source la plus détaillée
sur le sujet étant le livre fondateur [1].
Avec scikitlearn on peut construire et élaguer des arbres de régression grâce au package tree.
from sklearn import tree

et créer un classieur avec la fonction tree.DecisionTreeClassifier.

On considérera dans CART les mesures d'impureté suivantes :

• l'indice de Gini : pk (R)(1 − pbk (R))

2b
• l'entropie : −b pk (R)) − (1 − pbk (R)) log(1 − pbk (R)).
pk (R) log(b
1. Reprendre les exemples simulés précédemment, et jouer sur le paramètre de profondeur de l'arbre.

2. Tester les diérents classieurs obtenus sur de nouvelles données, et estimer leur risque.

3. Mettre en évidence le phénomène d' overtting (ou sur-apprentissage en français) et l'équilibre biais-
variance à trouver.

4. Eectuer le même genre de comparaison sur les données issues de la base zipcode.

page 8
Travaux Pratiques Joseph Salmon

Méthodes de choix de paramètres - Sélection de modèles

Il est rare de disposer en pratique d'un ensemble de test (on préfère inclure le plus grand nombre de
données dans l'ensemble d'apprentissage). Pour sélectionner un modèle tout en considérant le plus grand
nombre d'exemples possible pour l'apprentissage, on utilise généralement une procédure dite de sélection
par validation croisée. Pour chaque paramétrisation du problème, une estimation de l'erreur empirique
du classieur appris est faîte selon la procédure suivante :
 l'ensemble d'apprentissage est partitionné en N ensembles
 pour les N combinaisons possibles, un classieur est appris sur N −1 sous-ensembles et testé sur
le dernier sous-ensemble
 l'erreur estimée est la moyenne de l'erreur des classieurs appris.
Utiliser par exemple la fonction sklearn.cross_validation.cross_val_score et testez la en faisant
varier le nombre de divisions envisagées. On pourra se servir de cette fonction avec pour choisir le nombre
de voisins à considérer dans les méthodes des k plus proches voisins.

Références
[1] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classication and regression trees.
Wadsworth Statistics/Probability Series. Wadsworth Advanced Books and Software, Belmont, CA,
1984. 8

[2] T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer Series in
Statistics. Springer, New York, second edition, 2009. 8

[3] S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in
Machine Learning, 4(2) :107194, 2011. http://www.cs.huji.ac.il/~shais/papers/OLsurvey.
pdf. 5

page 9