Introduction au Machine Learning

Gilles Gasso

INSA Rouen -Département ASI

Laboratoire LITIS

4 septembre 2018

Gilles Gasso Introduction au Machine Learning 1 / 30

Machine Learning : introduction

Machine Learning ≡ apprentissage automatique

Capacité des des ordinateurs à apprendre à accomplir des tâches
(reconnaissance, traduction. . .) sans être explicitement programmés
Regroupe un ensemble de techniques et d’outils de la Statistique,
l’Informatique et la Science de l’information

Gilles Gasso Introduction au Machine Learning 2 / 30

Les raisons du développement

Données
Big Data : augmentation sans cesse de données générées
Twitter : 50M de tweets /jour (=7 téraoctets)
Facebook : 10 téraoctets /jour
Youtube : 50h de vidéos uploadées /minute
2.9 million de mail /seconde

Puissance de calcul Création de valeur ajoutée

Loi de Moore Intérêt : du produit aux clients.
Calcul massivement Extraction de connaissances des big
distribué data

Gilles Gasso Introduction au Machine Learning 3 / 30

Perspective historique

IA aujourd’hui : c’est du Deep Learning (une technique de Machine Learning)

[Link] learning- and- artificial- intelligence/

Gilles Gasso Introduction au Machine Learning 4 / 30

Exemples d’applications : E-commerce
Targeting
Stocker les séquences de clicks des visiteurs, analyser les
caractéristiques des acheteurs
Faire du ”targeting” lors de la visite d’un client potentiel

Recommandation, ranking
Y

1 1

1 1 1

1? 1 1

1 1

1 1

Gilles Gasso Introduction au Machine Learning 5 / 30

Exemples d’applications : Commerce

Opinion mining
Exemple : analyser l’opinion des usagers sur les produits d’une
entreprise à travers les commentaires sur les réseaux sociaux et les
blogs

Gilles Gasso Introduction au Machine Learning 6 / 30

Exemples d’applications : aide au diagnostic médical

détection de mélanome de la peau

130 000 images dont 2000 cas de cancers
taux d’erreur 28 % (humain 34 %)

the Digital Mammography DREAM Challenge

640 000 mammographies (1209 participants)
5 % de faux positif en moins

analyse du rythme cardiaque

500 000 ECG
précision 92.6 % (humain 80.0 %) sensibilité de 97 %

Gilles Gasso Introduction au Machine Learning 7 / 30

Mise en oeuvre d’un projet de Machine Learning

Collecte Ingénierie
Monde Réel Consolidation Business
Données données

Industries Capteurs Nettoyage Exploration Interpretation

Assurances Transactions Organisation Représentation Pattern of
Internet Web-clicks, logs Aggrégation Visualisation interests
Réseaux sociaux Mobilité
Gestion Machine Learning Dec. stratégique
Medical Open data
erreurs . . . Data Mining . . . Valorisation . . .
... Docs . . .

Gilles Gasso Introduction au Machine Learning 8 / 30

Chaîne d’ingénierie des données

Pré- Apprendre
Données Evaluation Modèle
traitement le modèle

1 Comprendre et analyser les objectifs

du projet Y
2 Pré-traitement/analyse des données
1 1
3 Identifier le type de problème 1 1 1

1? 1 1
4 Élaborer un algorithme de 1 1

résolution 1
1

5 Évaluer ses performances

6 Retour à 2) si nécessaire

Objectifs du cours : étude des méthodes des étapes 2 à 5

Gilles Gasso Introduction au Machine Learning 9 / 30
Ensemble de données

Données d’un problème de DM

Les informations sont des exemples avec des attributs
On dispose généralement d’un ensemble de N données

Attributs
Un attribut est un descripteur d’une entité. On l’appelle également
variable, ou caractéristique

Exemple
C’est une entité caractérisant un objet ; il est constitué d’attributs.
Synonymes : point, vecteur (souvent dans Rd )

Gilles Gasso Introduction au Machine Learning 10 / 30

Données : illustration
hhhh Variables
hh citric acid residual sugar chlorides sulfur dioxide
Points x hh h
1 0 1.9 0.076 11
2 0 2.6 0.098 25
3 0.04 2.3 0.092 15
Point x ∈ R4 0.56 1.9 0.075 17
5 0 1.9 0.076 11
6 0 1.8 0.075 13
7 0.06 1.6 0.069 15
8 0.02 2 0.073 9
9 0.36 2.8 0.071 17
10 0.08 1.8 0.097 15

0.1
25

0.095
Variable 3 : Chlorides

Variable 4 : Sulfur
20
0.09
Points
0.085 Moyenne des points 15

0.08
10

0.075
0.1
2.8
0.09 2.6
0.07 Va
ria 0.08
2.4
bl 2.2
e 0.07 2 r
3 ga
:C 1.8 l Su
0.065 hl
or 0.06 1.6 esid
ua
1.5 2 2.5 3 id 2:R
es a ble
Variable 2 : Residual Sugar Vari

Gilles Gasso Introduction au Machine Learning 11 / 30

Type de données

Capteurs → variables quantitatives,

qualitatives, ordinales
Texte → Chaîne de caractères
Parole → Séries temporelles
Images → données 2D
Vidéos → données 2D + temps
Réseaux → Graphes
Flux → Logs, coupons. . .
Étiquettes → information d’évaluation

Gilles Gasso Introduction au Machine Learning 12 / 30

Données et Métriques

Les algorithmes nécessitent une notion de similarité dans l’espace X des

données. La similarité est traduite par la notion de distance.

1
distance euclidienne : x, z ∈ Rd , on a
qPz) = kx − zk2 =p
d(x,
d 2
j=1 (xj − zj ) = (x − z)> (x − z)
Euclidien
0 Manhattan
Mahalanobis

distance de manhattanP
d(x, z) = kx − zk1 = dj=1 |(xj − zj )|
−1
distance depmahalanobis −1 0 1

d(x, z) = (x − z)> Σ−1 (x − z)

Σ ∈ Rd×d : matrice carrée définie positive

Gilles Gasso Introduction au Machine Learning 13 / 30

Caractérisation des techniques de Machine Learning
Types d’apprentissage
Apprentissage supervisé
Apprentissage non-supervisé
Apprentissage semi-supervisé

Gilles Gasso Introduction au Machine Learning 14 / 30

Caractérisation des méthodes : apprentissage supervisé
Objectif
A partir des données {(xi , yi ) ∈ X × Y, i = · · · , N}, estimer les
dépendances entre X et Y.
On parle d’apprentissage supervisé car les yi permettent de guider le
processus d’estimation.

Exemples
Estimer les liens entre habitudes alimentaires et risque d’infarctus. xi :
d attributs concernant le régime d’un patient, yi sa catégorie (risque,
pas risque).
Applications : détection de fraude, diagnostic médical ...

Techniques
k-plus proches voisins, SVM, régression logistique, arbre de décision ...
Gilles Gasso Introduction au Machine Learning 15 / 30
Caractérisation des méthodes : Apprentissage non-supervisé
Objectifs
Seules les données {xi ∈ X , i = · · · , N} sont disponibles. On cherche
à décrire comment les données sont organisées et en extraire des
sous-ensemble homogènes.

Exemples
Catégoriser les clients d’un supermarché. xi représente un individu
(adresse, âge, habitudes de courses ...)
Applications : identification de segments de marchés, catégorisation de
documents similaires, segmentation d’images biomédicales ...

Techniques
Classification hiérarchique, Carte de Kohonen, K-means, extractions de
règles ...
Gilles Gasso Introduction au Machine Learning 16 / 30
Caractérisation des méthodes : apprentissage semi-supervisé

Objectifs
Objectifs : parmi les données, seulement un petit nombre ont un label
i.e {(x1 , y1 ), · · · , (xn , yn ), xn+1 , · · · , N}. L’objectif est le même que
pour l’apprentissage supervisé mais on aimerait tirer profit des données
sans étiquette.

Exemples
Exemple : pour la discrimination de pages Web, le nombre ’exemples
peut être très grand mais leur associer un label (ou étiquette) est
coûteux.

Techniques
Méthodes bayésiennes, SVM ...

Gilles Gasso Introduction au Machine Learning 17 / 30

Apprentissage supervisé : les concepts

Soit deux ensembles X et Y munis d’une loi de probabilité jointe

p(X , Y ).

Objectifs : On cherche une fonction f : X → Y qui à X associe f (X )

qui permet d’estimer la valeur y associée à x. f appartient à un espace
H appelé espace d’hypothèses.
Exemple de H : ensemble des fonctions polynomiales

Gilles Gasso Introduction au Machine Learning 18 / 30

Apprentissage supervisé : les concepts

On introduit une notion de coût L(Y , f (X )) qui permet d’évaluer la

pertinence de la prédiction de f , et de pénaliser les erreurs.

L’objectif est donc de choisir la fonction f qui minimise

R(f ) = EX ,Y [L(Y , f (X ))]

où R est appelé le risque moyen ou erreur de généralisation. Il est

également noté EPE (f ) pour expected prediction error

Gilles Gasso Introduction au Machine Learning 19 / 30

Apprentissage supervisé : les concepts

Exemples de fonction coût et de risque moyen associé.

Coût quadratique (moindres carrés)

L(Y , f (X )) = (Y − f (X ))2
Z
R(f ) = E [(Y − f (X ))2 ] = (y − f (x))2 p(x, y )dxdy

Coût `1 (moindres valeurs absolues)

L(Y , f (X )) = |Y − f (X )|
Z
R(f ) = E [|Y − f (X ))|] = |y − f (x)|p(x, y )dxdy

Gilles Gasso Introduction au Machine Learning 20 / 30

Apprentissage supervisé : les concepts

Régression 1
Support Vector Machine Regression

On parle de régression quand Y 0.5

est un sous-espace de Rd .
0

y
−0.5

Fonction de coût typique :

quadratique (y − f (x))2
−1

−1.5
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
x

Gilles Gasso Introduction au Machine Learning 21 / 30

Apprentissage supervisé : les concepts

Discrimination 2

si Y est un ensemble discret 1

1

0
1

non-ordonné, (par exemple 0

−1
0
−1

−1
{−1, 1}), on parle de −1
−1 1
0

0
discrimination ou classification. 1

−1
−2

−1

1
−3 0
−3 −2 −1 0 1 2 3

La fonction de coût la plus usitée

est : Θ(−yf (x)) où Θ est la
fonction échelon.

Gilles Gasso Introduction au Machine Learning 22 / 30

Apprentissage supervisé : les concepts

En pratique, on a un ensemble de données {(xi , yi ) ∈ X × Y}N

i=1
appelé ensemble d’apprentissage obtenu par échantillonnage
indépendant de p(X , Y ) que l’on ne connaît pas.
On cherche une fonction f , appartenant à H qui minimise le risque
empirique :
N
1 X
Remp (f ) = L(yi , f (xi ))
N
i=1

Le risque empirique ne permet pas d’évaluer la pertinence d’un modèle

car il est possible de choisir f de sorte que le risque empirique soit nul
mais que l’erreur en généralisation soit élevée. On parle alors de
sur-apprentissage

Gilles Gasso Introduction au Machine Learning 23 / 30

Illustration du sur-apprentissage
Erreur de prediction

Ensemble de Test

Ensemble d’apprentissage
Faible Elevé
Complexité du modèle

Gilles Gasso Introduction au Machine Learning 24 / 30

Sélection de modèles

Problématique
On cherche une fonction f qui minimise un risque empirique donné.
On suppose que f appartient à une classe de fonctions paramétrées
par α. Comment choisir α pour que f minimise le risque empirique et
généralise bien ?
Exemple : OnPcherche un polynôme de degré α qui minimise un risque
Remp (fα ) = N
i=1 (yi − f α (xi ))2.

Objectifs :
1 proposer une méthode d’estimation d’un modèle afin de choisir
(approximativement) le meilleur modèle appartenant à l’espace
hypothèses.
2 une fois le modèle choisi, calculer son erreur de généralisation.

Gilles Gasso Introduction au Machine Learning 25 / 30

Sélection de modèles : approche classique
Cas idéal : les données DN abondent (N est très grand)
Données disponibles

Apprentissage {X app ,Y app } Validation {X val ,Y val } Test {X test , Y test }

1 Découper aléatoirement DN = Dapp ∪ Dval ∪ Dtest

2 Apprendre chaque modèle possible sur Dapp
3 Evaluer sa performance en généralisation sur Dval
Rval = N1val i∈Dval L(yi , f (xi ))
P

4 Sélectionner le modèle qui donne la meilleure performance sur Dval

5 Tester le modèle retenu sur Dtest

Remarque
Dtest n’est utilisé qu’une seule fois !
Gilles Gasso Introduction au Machine Learning 26 / 30
Sélection de modèles : Validation Croisée

Cas moins favorable : les données DN sont modestes (N est petit)

Estimation de l’erreur de généralisation par rééchantillonnage.

Principe
1 Séparer les N données en K ensembles de part égales.
2 Pour chaque k = 1, · · · , K , apprendre un modèle en utilisant les K − 1
autres ensemble de données et évaluer le modèle sur la k-ième partie.
3 Moyenner les K estimations de l’erreur obtenues pour avoir l’erreur de
validation croisée.

K=1 K=2 K=3 K=4 K=5

APP APP TEST APP APP

Gilles Gasso Introduction au Machine Learning 27 / 30

Sélection de modèles : Validation Croisée (2)

Détails :
K Nk
1 X 1 X
RCV = L(yik , f −k (xik ))
K Nk
k=1 i=1

où f −k est le modèle f appris sur l’ensemble des données sauf la

k-ième partie.
Propriétés : Si K = N, CV est approximativement un estimateur sans
biais de l’erreur en généralisation. L’inconvénient est qu’il faut
apprendre N − 1 modèles.
typiquement, on choisit K = 5 ou K = 10 pour un bon compromis
entre le biais et la variance de l’estimateur.

Gilles Gasso Introduction au Machine Learning 28 / 30

Conclusions

Pour bien mener un projet de traitement automatique des données

Identifier et énoncer clairement les besoins.
Créer ou obtenir des données représentatives du problème
Identifier le contexte de l’apprentissage
Analyser et réduire la dimension des données
Choisir un algorithme et/ou un espace d’hypothèses.
Choisir un modèle en appliquant l’algorithme aux données prétraitées.
Valider les performances de la méthode.

Gilles Gasso Introduction au Machine Learning 29 / 30

Au final ...
Les voies du Machine Learning et du traitement des données c’est ...

Gilles Gasso Introduction au Machine Learning 30 / 30