0% ont trouvé ce document utile (0 vote)

47 vues72 pages

Méthodes en Apprentissage Supervisé

Ce document introduit le sujet de l'apprentissage automatique. Il définit l'apprentissage automatique et ses domaines connexes comme les statistiques, l'intelligence artificielle et le traitement du langage naturel. Il décrit également les différents types d'apprentissage comme l'apprentissage supervisé, non supervisé et par renforcement.

Transféré par

Cheujeu chaldou

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

47 vues72 pages

Méthodes en Apprentissage Supervisé

Transféré par

Cheujeu chaldou

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Introduction : Apprentissage Automatique (AA)

Rappel du Sommaire

Méthodes avancées en apprentissage supervisé et

non-supervisé 1 Introduction : Apprentissage Automatique (AA)

2 Apprentissage supervisé
Julien Ah-Pine ([Link]-pine@[Link])
3 Apprentissage non-supervisé
Université Lyon 2

M2 SISE 2020/2021

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 1 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 2 / 285

Introduction : Apprentissage Automatique (AA) Introduction : Apprentissage Automatique (AA)

En quoi consiste l’apprentissage automatique ? Un domaine pluri-disciplinaire

De manière générale, un programme informatique tente de résoudre
L’apprentissage automatique (AA) (“Machine Learning”) est à la
un problème pour lequel nous avons la solution. Par exemple : calculer
croisée de plusieurs disciplines :
la moyenne générale des étudiants, classer les étudiants selon leur I Les statistiques : pour l’inférence de modèles à partir de données.
moyenne. . . I Les probabilités : pour modéliser l’aspect aléatoire inhérent aux
Pour certains problèmes, nous ne connaissons pas de solution exacte données et au problème d’apprentissage.
et donc nous ne pouvons pas écrire de programme informatique. Par I L’intelligence artificielle : pour étudier les tâches simples de
exemple : reconnaı̂tre automatiquement des chiffres écrits à la main à reconnaissance de formes que font les humains (comme la
partir d’une image scannée, déterminer automatiquement une reconnaissance de chiffres par exemple), et parce qu’elle fonde une
typologie des clients d’une banque, jouer automatiquement aux branche de l’AA dite symbolique qui repose sur la logique et la
représentation des connaissances.
échecs contre un humain ou un autre programme. . . I L’optimisation : pour optimiser un critère de performance afin, soit
En revanche, pour ces problèmes il est facile d’avoir une base de d’estimer des paramètres d’un modèle, soit de déterminer la meilleure
données regroupant de nombreuses instances du problème considéré. décision à prendre étant donné une instance d’un problème.
L’apprentissage automatique consiste alors à programmer des I L’informatique : puisqu’il s’agit de programmer des algorithmes et
algorithmes permettant d’apprendre automatiquement de données et qu’en AA ceux-ci peuvent être de grande complexité et gourmands en
d’expériences passées, un algorithme cherchant à résoudre au mieux termes de ressources de calcul et de mémoire.
un problème considéré.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 3 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 4 / 285
Introduction : Apprentissage Automatique (AA) Introduction : Apprentissage Automatique (AA)

AA et matières connexes AA et matières connexes (suite)

Quelques références et domaines d’application faisant intervenir l’AA :

I Les statistiques (“Statistical Machine Learning”) : modèles d’AA
traités sous l’angle des statistiques [Hastie et al., 2011, Dreyfus, 2008]. Plus récemment :
I L’intelligence artificielle (“Artifical Intelligence”) : modèles d’AA I La science des données (“Data science”) : approche(s)
mettant l’accent sur le raisonnement, l’inférence et la représentation pluri-disciplinaire pour l’extraction de connaissances à partir de données
des connaissances hétérogènes [Cleveland, 2001, Abiteboul et al., 2014].
[Cornuéjols and Miclet, 2003, Mitchell, 1997, Alpaydin, 2010]. I Les données massives (“Big data”) : mettant l’accent sur les
I La fouille de données (“Data Mining”) : lorsque les objets étudiés problématiques “4V” (volume, variété, vélocité, véracité) et des
sont stockées dans des bases de données volumineuses éléments de solutions issus du stockage/calcul distribué
[Han and Kamber, 2006]. [Leskovec et al., 2014].
I La reconnaissance de formes (“Pattern Recognition”) : lorsque les I Pour plus de ressources, consultez le site
objets concernés sont de type “signal” comme les images, les vidéos ou [Link]
le son [Bishop, 2006a].
I Le traitement automatique du langage - TAL (“Natural Langage
Processing” - NLP) : lorsque les problèmes concernent l’analyse
linguistique de textes [Manning and Schütze, 1999, Clark et al., 2010].

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 5 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 6 / 285

Introduction : Apprentissage Automatique (AA) Introduction : Apprentissage Automatique (AA)

Plusieurs types de problèmes en AA Plusieurs types de problèmes (suite)

Apprentissage automatique :
I Supervisé : on dispose d’un ensemble d’objets et pour chaque objet
une valeur cible associée ; il faut apprendre un modèle capable de Apprentissage automatique (suite) :
prédire la bonne valeur cible d’un objet nouveau. I Semi-supervisé : on dispose d’un petit ensemble d’objets avec pour
I Non-supervisé : on dispose d’un ensemble d’objets sans aucune valeur chacun une valeur cible associée et d’un plus grand ensemble d’objets
cible associée ; il faut apprendre un modèle capable d’extraire les sans valeur cible ; il faut tirer profit à la fois des données avec et sans
régularités présentes au sein des objets pour mieux visualiser ou valeurs cibles pour résoudre des tâches d’apprentissage supervisé ou
appréhender la structure de l’ensemble des données. non-supervisé.
I Par renforcement : on dispose d’un ensemble de séquences de I Actif : on dispose d’un petit ensemble d’objets avec pour chacun une
décisions (politiques ou stratégiques) dans un environnement valeur cible associée ; il faut intéragir avec l’utilisateur et lui demander
dynamique, et pour chaque action de chaque séquence une valeur de de donner la valeur cible d’un nouvel objet afin de mieux apprendre le
récompense (la valeur de récompense de la séquence est alors la modèle de prédiction.
somme des valeurs des récompenses des actions qu’elle met en
oeuvre) ; il faut apprendre un modèle capable de prédire la meilleure
décision à prendre étant donné un état de l’environnement.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 7 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 8 / 285
Introduction : Apprentissage Automatique (AA) Introduction : Apprentissage Automatique (AA)

Motivations de ce cours Organisation de ce cours

Dans le cadre de ce cours, nous étudierons des problèmes supervisés

dans un premier temps puis (plus brièvement) des problèmes 6 séances de CM/TP de 3h
non-supervisés. (2/3 à 3/4 de CM et 1/4 à 1/3 de TP - TP à terminer à la maison).
Nous commencerons par étudier quelques concepts importants en Une feuille d’exercices
apprentissage supervisé (classes d’hypothèses, sous et (à faire à la maison - correction rapide en début ou fin de séance).
sur-apprentissage, arbitrage biais-variance, principe de généralisation, Evaluation :
données de grande dimension) avant de traiter quelques méthodes I 1 projet (rapport + code R ou Python - coef. ∼0.4).
classiques (modèles linéaires pénalisés, réseaux de neuronnes, SVM). I 1 examen sur table individuel (2h - coef. ∼0.6).
Nous verrons ensuite le problème des données non-linéairement Supports de cours sur ma page : [Link]/~jahpine.
séparables en apprentissage non-supervisé et en particulier des
méthodes à noyaux et l’approche spectral clustering.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 9 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 10 / 285

Apprentissage supervisé Apprentissage supervisé Définitions, notations et concepts importants

Rappel du Sommaire Rappel du Sommaire

2 Apprentissage supervisé
1 Introduction : Apprentissage Automatique (AA) Définitions, notations et concepts importants
Quelques méthodes simples en guise d’illustration
Différentes caractéristiques des méthodes d’apprentissage supervisé
2 Apprentissage supervisé
Concepts importants en apprentissage supervisé
Evaluation et comparaison de modèles en apprentissage supervisé
3 Apprentissage non-supervisé (Quelques) Aspects théoriques en apprentissage automatique
Les méthodes linéaires et leurs pénalisations (elasticnet ...)
Les réseaux de neurones artificiels (“Artificial Neural Networks”)
Les machines à vecteurs supports (“Support Vector Machines”)

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 11 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 12 / 285
Apprentissage supervisé Définitions, notations et concepts importants Apprentissage supervisé Définitions, notations et concepts importants

Apprentissage supervisé symbolique et numérique Apprentissage supervisé numérique

Deux familles en apprentissage supervisé Il existe deux types de sous-problèmes en apprentissage supervisé
[Cornuéjols and Miclet, 2003] : numérique :
I Apprentissage supervisé symbolique : méthodes inspirées de I Régression (“Regression”) : lorsque la valeur cible à prédire est
l’intelligence artificielle et dont les fondements reposent beaucoup sur continue.
des modèles de logique, une représentation binaire des données I Classement, classification ou catégorisation (“Classification”) : lorsque
(vrai/faux), et sur les méthodes de représentation des connaissances. la valeur cible à prédire est discrète.
I Apprentissage supervisé numérique : méthodes inspirées de la Par ailleurs nous supposerons également que les objets étudiés qui
statistique, les données sont en général des vecteurs de réels, et les peuvent être complexe à l’origine (comme des données mutimédia)
méthodes font intervenir des outils provenant des probabilités, de sont représentés dans un format numérique structuré. En d’autres
l’algèbre linéaire et de l’optimisation. termes :
Dans le cadre de ce cours, nous étudierons principalement les I On représente un objet Xi par un vecteur noté xi défini dans un espace
problèmes d’apprentissage supervisé numérique : le cours nécessite de description composé de plusieurs variables.
donc des prérequis de base dans les domaines sus-mentionnés. I A chaque xi on lui associe une valeur cible notée yi .

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 13 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 14 / 285

Apprentissage supervisé Définitions, notations et concepts importants Apprentissage supervisé Définitions, notations et concepts importants

Quelques exemples d’application Notations

Comme données à notre disposition nous supposerons que nous avons
Exemples de problèmes de régression : une table X avec n lignes et p colonnes et un vecteur colonne
I Prédiction du montant des ventes d’une entreprise compte tenu du (variable cible) y de n éléments.
contexte économique.    
x11 x12 . . . x1p y1
I Prédiction du prix de vente d’une maison en fonction de plusieurs x21 x22 . . . x1p  y2 
critères. X= . .  et y =  .. 
   
I Prédiction de la consommation électrique dans une ville étant donné  .. . . . . . . ..  .
des conditions météorologiques. . . xn1 xn2 . . . xnp yn
Exemples de problèmes de catégorisation :
I Prédiction de l’état sain/malade d’un patient par rapport à une La ligne i de X est associée à l’objet Xi et l’ensemble des objets
maladie et compte tenu de différents facteurs. {X1 , . . . , Xn } sera noté O.
I Prédiction de l’accord ou du refus d’un crédit à un client d’une banque La colonne j de X est associée à la variable ou attribut X j et
en fonction de ses caractéristiques. l’ensemble des variables {X 1 , . . . , X p } sera noté A.
I Prédiction du chiffre correct à partir d’une image scannée d’un chiffre
xij terme général de X est la valeur de la variable X j pour l’objet Xi .
écrit à la main. . .
A chaque objet Xi est associé une valeur yi de la variable Y ∈ Y où Y
est l’ensemble des valeurs que peut prendre Y .
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 15 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 16 / 285
Apprentissage supervisé Définitions, notations et concepts importants Apprentissage supervisé Définitions, notations et concepts importants

Notations (suite) Formalisation du problème

Chaque objet Xi est associé à un vecteur numérique xi appartenant à Etant donné un ensemble d’entraı̂nement E, on cherche à déterminer
un espace de description X. f : X → Y une fonction modélisant la relation entre les X décrits
Sauf mention contraire, on supposera que X est un espace vectoriel dans l’espace de représentation X et la variable cible Y :
engendré par les variables {X 1 , . . . , X p }.
Ainsi on notera par xi = (xi1 , . . . , xip ) le vecteur colonne de taille f (X ) = Y
(p × 1) des valeurs observées représentant Xi dans X. En revanche, ne connaissant pas la vraie nature de la relation entre X
On notera par xj = (x1j , . . . , xnj ) le vecteur colonne de taille (n × 1) et Y et les données observées en {X 1 , . . . , X p } étant soit bruitées,
des valeurs observées sur O pour la variable X j . soit incomplètes ; il n’est pas raisonnable de supposer une relation
y = (y1 , . . . , yn ) est le vecteur colonne de taille (n × 1) des valeurs déterministe. Aussi, on posera le problème en les termes suivants :
observées sur O pour la variable cible Y .
L’ensemble des couples observés f (X ) = Y +
E = {(x1 , y1 ), . . . , (xi , yi ), . . . , (xn , yn )} est appelé ensemble où est l’erreur ou le résidu.
d’entraı̂nement ou d’apprentissage (ou ensemble des données
Autrement dit, il s’agit d’approximer f en commettant le moins
annotées ou étiquetées).
d’erreurs possibles sur E tout en faisant de bonnes prédictions
Nous dénoterons par X un objet quelconque, x son vecteur
pour des valeurs de X non encore observées.
représentant dans X et y la valeur cible associée à x.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 17 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 18 / 285

Apprentissage supervisé Définitions, notations et concepts importants Apprentissage supervisé Définitions, notations et concepts importants

Schéma général Schéma général (suite)

Comme précisé précédemment, nous ne traitons pas dans ce cours du
procédé permettant de représenter numériquement les données
complexes telles que les images, vidéos, textes. . .
FEATURE
MATRIX Partant d’objets complexes comme une image par exemple, il s’agit
d’extraire des variables de l’ensemble des objets permettant de
DATABASE
(numerical
data, texts,
NUMERICAL
REPRESENTA
CLASSIFI-
-CATION
CLASSIFI-
-CATION
représenter ceux-ci au travers d’un vecteur de nombres. On parle
images, TION ALGORITHM OUTPUT d’extraction d’attributs (“features extraction”).
networks, …)
Ces procédés sont les champs d’expertises d’autres domaines que sont
PROXIMITY
MATRIX l’analyse d’images et le traitement automatique du langage naturel. . .
Néanmoins, des outils sont disponibles et peuvent être utilisés même
par des non experts.
CLASSIFI-
-CATION Notre point de départ sera nécessairement soit une matrice de
ASSESSMENT
données de type table comme présenté précédemment soit une
matrice carrée de dissimilarités ou de similarités entre objets (que
nous étudierons ultérieurement comme pour le cas des svm).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 19 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 20 / 285
Apprentissage supervisé Définitions, notations et concepts importants Apprentissage supervisé Définitions, notations et concepts importants

Schéma général (suite) Schéma général (suite)

FEATURE
MATRIX

Dans ce qui suit nous présentons des exemples simples de régression

DATABASE
(numerical NUMERICAL CLASSIFI- CLASSIFI- et de catégorisation qui sont à vocation pédagogique.
data, texts, REPRESENTA -CATION -CATION
images, TION ALGORITHM OUTPUT
networks, …) Nous présentons également quelques méthodes relativement simples
qui nous permettront de mettre en lumière certains concepts et
PROXIMITY
MATRIX sous-problèmes traités en apprentissage supervisé.

CLASSIFI-
-CATION
ASSESSMENT

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 21 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 22 / 285

Apprentissage supervisé Définitions, notations et concepts importants Apprentissage supervisé Quelques méthodes simples en guise d’illustration

Schéma général (suite) Rappel du Sommaire

2 Apprentissage supervisé
FEATURE
MATRIX Définitions, notations et concepts importants
Quelques méthodes simples en guise d’illustration
DATABASE
(numerical NUMERICAL CLASSIFI- CLASSIFI- Différentes caractéristiques des méthodes d’apprentissage supervisé
data, texts, REPRESENTA -CATION -CATION
images, TION ALGORITHM OUTPUT Concepts importants en apprentissage supervisé
networks, …)
Evaluation et comparaison de modèles en apprentissage supervisé
PROXIMITY (Quelques) Aspects théoriques en apprentissage automatique
MATRIX
Les méthodes linéaires et leurs pénalisations (elasticnet ...)
Les réseaux de neurones artificiels (“Artificial Neural Networks”)
CLASSIFI-
-CATION
Les machines à vecteurs supports (“Support Vector Machines”)
ASSESSMENT

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 23 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 24 / 285
Apprentissage supervisé Quelques méthodes simples en guise d’illustration Apprentissage supervisé Quelques méthodes simples en guise d’illustration

Exemple de problème de régression Régression linéaire simple

L’objectif est de déterminer une fonction f qui étant donné un Nous observons 12 couples de données avec en abscisse la variable X
nouveau x ∈ R prédise correctement y ∈ R et en ordonnées la variable cible Y dont les éléments sont des réels.
L’objectif est d’estimer une fonction Y = f (X ) + qui représente la
relation entre Y et X afin de prédire la valeur ŷ = fˆ(x) pour une
1.0

valeur de x quelconque.
Pour un problème de régression on parlera également de prédicteur
0.5

pour la fonction fˆ.

En statistique une méthode très classique est donnée par les
Moindres Carrés Ordinaires (MCO) que l’on notera par scr (f )
0.0
y

(somme des carrés des résidus ou “Residual Sum of Squares”) :

n
−0.5

X
scr (f ) = (yi − f (xi ))2
i=1
n
−1.0

X
−2 −1 0 1 2 3 = (i )2
x i=1
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 25 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 26 / 285

Apprentissage supervisé Quelques méthodes simples en guise d’illustration Apprentissage supervisé Quelques méthodes simples en guise d’illustration

Régression linéaire simple (suite) Régression linéaire simple (suite)

La régression linéaire simple consiste à prendre pour hypothèse que la Régression linéaire simple
relation f est un polynôme de degré 1 de X : f (X ) = a + bX
Ce qui nous donne :

1.0
scr (f ) = scr (a, b) = ni=1 (yi − (a + bxi ))2
P

P = {a, b} est l’ensemble des paramètres du modèle et on cherche les

0.5
estimations â et b̂ qui minimisent scr .
Il faut déterminer les points critiques (ou stationnaires), solutions des
équations normales (dérivées premières nulles). On obtient une

0.0
y
solution analytique :
Pn
(x − x)(yi − y)
â = y − b̂x et b̂ = i=1 Pn i 2 −0.5
i=1 (xi − x)
où y = n1 ni=1 yi est la moyenne empirique de Y .
P
−1.0

Le modèle de prédiction est alors donné par : −2 −1 0 1 2 3

x
fˆ(x) = â + b̂x
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 27 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 28 / 285
Apprentissage supervisé Quelques méthodes simples en guise d’illustration Apprentissage supervisé Quelques méthodes simples en guise d’illustration

Régression linéaire multiple (polynôme de degré > 1) Régression linéaire multiple

Régression linéaire multiple utilisant des fonctions de base
La régression linéaire simple fait l’hypothèse que la fonction f est un polynômiales (jusqu’au degré 2).
polynôme de degré 1 et clairement ceci n’est pas une hypothèse
raisonnable pour l’exemple traité.

1.0
Autre type d’hypothèse : f est un polynôme de degré 2 de X ,
f (X ) = a + bX + cX 2

0.5
Dans ce cas P = {a, b, c} et on cherche à minimiser :
n

0.0
X

y
scr (f ) = scr (a, b, c) = (yi − (a + bxi + cxi2 ))2
i=1

−0.5
Remarque : on parle de modèle linéaire car f est une fonction linéaire
des paramètres P ! Les variables peuvent être tout type de fonction

−1.0
des variables initiales.
−2 −1 0 1 2 3
x

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 29 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 30 / 285

Apprentissage supervisé Quelques méthodes simples en guise d’illustration Apprentissage supervisé Quelques méthodes simples en guise d’illustration

Exemple de problème de catégorisation Régression linéaire multiple avec variables artificielles

L’objectif est de déterminer une fonction fˆ qui étant donné un On attribue des valeurs numériques à chacune des deux classes
nouveau x ∈ R2 prédit correctement sa classe y ∈ {C1 , C2 } comme par exemple C1 ↔ 1 et C2 ↔ −1.
On remplace Y variable discrète par Z une variable numérique
remplie de −1 et 1.
1.0

On traite le problème comme une régression linéaire multiple :

0.8

Z = g (X ).
●
●
● ●
●
● Pour un nouveau x on applique la règle de décision suivante :
0.6

●
● ●● ● ●
●●● ●●
● ●
X^2

● ● ●

● ●
●●●
● ●●
●●●
●●
●
●
ˆ C1 si ĝ (x) ≥ 0
● ● ● ● f (x) =
0.4

● ●● ●●
● ●●
●
● ●
● ●
●
C2 si ĝ (x) < 0
● ●● ● ●
● ● ●● ●
● ● ●●● ●
● ●
● ● ● ●
0.2

● ● ●
● ●
●
● ●
●
●●
●
● ● ●
●
●

●
La ligne de niveau {x ∈ R2 : ĝ (x) = 0} est la frontière de décision.
● ●
0.0

●
Pour un problème de catégorisation on parlera également de
0.0 0.2 0.4
X^1
0.6 0.8 1.0
classifieur pour la fonction fˆ.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 31 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 32 / 285
Apprentissage supervisé Quelques méthodes simples en guise d’illustration Apprentissage supervisé Quelques méthodes simples en guise d’illustration

Régression linéaire multiple (suite) Régression linéaire multiple (suite)

Hypothèse : Z = g (X ) = a + bX 1 + cX 2 (polynôme de degré 1 des Hypothèse : Z = g (X ) = a + bX 1 + cX 2 + dX 1 X 2 (polynôme de
{X j }2j=1 ) degré 2 des {X j }2j=1 ).
En vert on a tracé la frontière de décision.
1.0 En bleu on a tracé la frontière de décision.

1.0
0.8

0.8
● ●
● ●
● ● ● ●
● ●
● ●
0.6

0.6
● ●
● ●● ● ● ●● ● ● ●
●●● ●● ●●● ●●
● ● ● ●
X^2

X^2
● ● ● ● ● ● ● ●
● ● ● ● ●● ● ● ● ● ● ● ●● ● ●
● ● ●●● ● ● ●●●
● ●
● ● ● ● ● ● ● ●
0.4

0.4
● ●● ●● ● ●● ●●
● ● ● ● ● ●
● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ●
● ● ● ● ● ●
● ● ●● ● ● ● ●● ●
● ● ●●● ● ● ● ●●● ●
● ● ● ●
● ● ● ● ● ● ● ●
0.2

0.2
● ● ● ● ● ●
● ●
● ● ●
●
●● ● ●● ●
● ● ● ● ● ●
● ● ● ● ● ● ● ●
● ● ● ●
● ● ● ●
0.0

0.0
● ●

0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
X^1 X^1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 33 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 34 / 285

Apprentissage supervisé Quelques méthodes simples en guise d’illustration Apprentissage supervisé Quelques méthodes simples en guise d’illustration

Méthode des k plus proches voisins (k-ppv) Méthode des k-ppv (suite)

Nous avons utilisé la régression linéaire associée à des variables k=1

artificielles pour un problème de catégorisation.
Nous voyons une autre approche simple qui est un modèle non

1.0
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

paramétrique : les k plus proches voisins. ●

●
●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

Etant donné un nouvel objet x, la méthode consiste à déterminer les ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

0.8
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
k plus proches objets (annotés) et d’effectuer un vote à la majorité ●

●
●

● ●
●

●
●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
● ● ● ● ● ● ● ● ● ● ● ●

●
relative afin de déterminer la classe de x.

0.6
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
●
●● ●
● ● ● ● ● ● ●

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●●●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ●

X^2
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ●
Formellement nous avons la fonction de prédiction suivante : ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ●● ●●
●●●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ●

0.4
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ●●
● ● ● ●
●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ● ● ● ●

●
● ●

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ●●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

|{xi ∈ Vk (x) : yi = Cl }| ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●● ●
●● ●
● ● ● ● ●

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

fˆ(x) = arg max

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ●
● ● ● ● ● ● ●

●● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ●●● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
● ● ● ●
●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

Cl ∈Y k 0.2
●

●
●

●
●
●

●
●

● ●
●

●
● ● ●
●

●
●

●
●
●

●
●

●
●●
●

●
●

●
● ●

●
●

●
●
●

●
●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
● ● ●
● ● ● ● ● ● ●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●● ● ● ●
● ●
● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
|{xi ∈Vk (x):yi =Cl }| ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

où Vk (x) est l’ensemble des k plus proches xi de x et

0.0

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

k
est la proportion d’objets appartenant à la classe Cl parmi les k plus 0.0 0.2 0.4 0.6 0.8 1.0
X^1
proches voisins.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 35 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 36 / 285
Apprentissage supervisé Quelques méthodes simples en guise d’illustration Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Méthode des k-ppv (suite) Rappel du Sommaire

k=9

2 Apprentissage supervisé
1.0

Définitions, notations et concepts importants

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

Quelques méthodes simples en guise d’illustration

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
0.8

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
●

●
●
●

●
●

●
Différentes caractéristiques des méthodes d’apprentissage supervisé
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
●

●
●
●

●
●

●
Concepts importants en apprentissage supervisé
0.6

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●● ●
● ● ●

●
● ● ● ●

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
●

●●●
●

●
●●
●
●

●
●

●
Evaluation et comparaison de modèles en apprentissage supervisé
X^2

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ●●
●
● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
● ● ● ● ● ●
● ●
● ●
●
●●
● ● ● ●
●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ●
●

●
●

● ●
●

● ●●●
●

●
●

●
●
●

●
●

●
(Quelques) Aspects théoriques en apprentissage automatique
0.4

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ●●
● ● ●
●●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●● ● ● ●

●
● ● ●

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
●

●
● ●
●
●
●

●
●

●
●●
●

● ●
●
●
●

●
●

●
●
●

●
●

●
Les méthodes linéaires et leurs pénalisations (elasticnet ...)
●● ●
● ● ●●● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
●

● ● ●
●

●
●

●
●
●

●
●

Les réseaux de neurones artificiels (“Artificial Neural Networks”)

0.2

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●● ●
Les machines à vecteurs supports (“Support Vector Machines”)
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
● ● ● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
● ● ● ● ● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
● ● ● ●
● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
0.0

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

0.0 0.2 0.4 0.6 0.8 1.0

X^1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 37 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 38 / 285

Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Choix de la méthode d’apprentissage Approches inductives et classes d’hypothèses

Les méthodes que nous voyons sont de type inductif : à partir

d’observations on instancie une fonction appartenant à un ensemble
Il existe plusieurs méthodes en apprentissage supervisé que ce soit défini appelé espace (ou classe) d’hypothèses. Cette famille
pour la régression ou la catégorisation. paramétrique de fonctions sera notée H et les paramètres par P.
Pour choisir une méthode, il y a deux approches complémentaires : Les valeurs des paramètres choisies sont celles qui optimisent un
I l’une relève de la bonne compréhension des fondements des critère de performance (souvent associé à une fonction de perte).
méthodes et de ce qui permet de les distinguer afin de déterminer les La fonction estimée permet alors de généraliser la relation apprise
modèles qui traiteraient au mieux un cas d’étude donné,
sur les données d’entraı̂nement E à tout couple X × Y.
I l’autre, résolument empirique, relève de l’application de méthodes et
critères d’évaluation et de sélection permettant de sélectionner les Par exemple pour la régression linéaire multiple :
Pp
algorithmes de catégorisation les plus performants étant donné un cas I H = {f : X → Y : f (X ) = a0 + j=1 aj X j },
d’étude. I P = {a0 , . . . , ap } ∈ Rp+1 ,
I Le critère d’optimisation est les MCO ou la scr ,
I A partir de E, on détermine {â0 , . . . , âp } et on définit
Pp
fˆ(x) = a0 + j=1 âj x j , ∀x ∈ X.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 39 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 40 / 285
Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Biais inductif Plusieurs types de fonction de performance

Le modèle linéaire dans sa forme générale peut s’écrire : Etant donné un espace d’hypothèses H, pour déterminer la fonction
M
X de prédiction (une instance de H), il faut estimer les paramètres P en
f (X ) = a0 + am gm (X ) optimisant un critère de performance sur les données E.
m=1 Pour la régression linéaire nous avons déjà évoqué les MCO ou la scr :
où gm : X → R sont des fonctions quelconques appelées expansions n
de base (par exemple : f (X ) = a0 + a1X 1 + a2 X 2 + a3 X 1 X 2 ). scr (f ) =
X
(yi − f (xi ))2
Il peut donc exister plusieurs familles d’hypothèses donnant autant de i=1
résultats de prédictions différents. Le choix d’un espace d’hypothèses
H implique un biais inductif dans le processus d’apprentissage. Il peut également exister plusieurs critères de performances
Par exemple, il existe une infinité de façon de séparer les classes C1 et pouvant donner également autant d’instances différentes de H.
C2 dans l’exemple de catégorisation. Si on choisit la régression linéaire Dans le cas des MCO, on suppose que pour chaque (xi , yi ) ∈ E :
multiple, la frontière de décision est nécessairement un hyperplan. I la mesure de l’erreur est l’écart quadratique,
Le biais inductif c’est donc l’ensemble des hypothèses implicites que
I le poids dans le critère de performance est identique.
l’on fait lorsque l’on utilise une méthode d’apprentissage supervisé On peut généraliser le concept de critère de performance en utilisation
pour résoudre un problème de régression ou de catégorisation. les outils de la décision statistique.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 41 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 42 / 285

Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Notations Notations (suite)

Nous nous plaçons dans un cadre probabiliste et dans ce cas :
Les variables X 1 , . . . , X p sont des variables aléatoires (v.a.) réelles.
La variable Y est une v.a. prenant ses valeurs dans Y.
Les objets X1 , . . . , Xn et X sont des vecteurs aléatoires de dimension X est un vecteur aléatoire de taille (p × 1) prenant ses valeurs dans X.
(p × 1), chaque dimension j étant associée à la variable X j . Y est une variable aléatoire prenant ses valeurs dans Y.
On notera par P(X ) la fonction de densité de probabilité Soient P(X ), P(Y ), les fonctions de probabilité de X et Y .
(multidimensionnelle) du vecteur aléatoire X .
Soit P(X , Y ) la fonction de probabilité jointe du couple (X , Y ).
On notera par P(Y |X ) la probabilité conditionnelle de Y sachant X .
Soit `(f (X ), Y ) une fonction de perte (“loss”) mesurant le coût de
On notera par EX (f (X )) l’espérance de f (X ) par rapport à X . la différence entre la prédiction du modèle et l’observation.
On notera par EY |X (f (Y )|X ) l’espérance conditionnelle de f (Y ) par
rapport à Y sachant X .
{Xij }ni=1 et {Yi }ni=1 sont n variables aléatoires que l’on supposera
i.i.d. (indépendantes et identiquement distribuées) selon les lois mères
P(X j ) et P(Y ) respectivement.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 43 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 44 / 285
Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Fonction de performance et décision statistique Fonction de perte quadratique et fonction de régression

Etudions EX ,Y (`) dans le cas d’une fonction de perte quadratique :
Définition. (Espérance de la fonction de perte) Z Z
On définit l’espérance sous (X , Y ) de la fonction de perte ` associée à f : min EX ,Y (`2 ) = (f (x) − y )2 P(x, y )dxdy
f X Y
Z Z
EX ,Y (`(f (X ), Y )) = EX ,Y (`) = `(f (x), y )P(x, y )dxdy On montre que la solution du problème est de la forme :
X Y
f ∗ (x) = EY |X (Y |X = x)

En théorie, on cherche donc f qui minimise l’espérance de la La fonction qui minimise au point x, EX ,Y (`2 ), est l’espérance de Y
fonction de perte `. sous la probabilité conditionnelle P(Y |X = x). Cette solution
scr (f ) est le cas particulier donné par : s’appelle fonction de régression. Celle-ci est un outil théorique
puisque nous ne connaissons pas P(X , Y ) ni P(Y |X ). Au contraire,
I `(f (X ), Y ) est la fonction de perte quadratique
`2 (f (X ), Y ) = (Y − f (X ))2 ; en pratique, si nous supposons la fonction de perte quadratique, nous
I P(X , Y ) est la loi uniforme sur X × Y. cherchons en fait f qui approxime la fonction de regression.
On peut donc généraliser et utiliser d’autres types de fonction de Le cas de `2 est souvent utilisé car elle conduit à la solution simple
perte ` et/ou en donnant différents poids selon P(X , Y ). ci-dessus mais le principe d’espérance de fonction de perte permet
d’avoir plusieurs types de fonction de performance (cf svm par ex.).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 45 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 46 / 285

Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Fonction de perte quadratique et fonction de régression Fonction de performance pour la catégorisation

(suite)
Que se passe t-il dans le cas où Y est discret ?
Cas de la fonction quadratique et illustration de la fonction de Le principe de minimisation de l’espérance de la fonction de perte est
régression. valide mais il faut adapter la fonction de perte au cas discret.
Y Un coût de la fonction de perte intervient lorsqu’on attribue à un x
une classe qui n’est pas la bonne.
Supposons que la classe de x est Cl et qu’on lui attribue par erreur la
classe Cl 0 . Pour chaque couple (Cl , Cl 0 ) on a le coût L(Cl , Cl 0 ) associé
à une mauvaise catégorisation.
fˆ(x) P(Y |X = x)
On a la donnée d’une matrice de perte L de taille (q × q) (q étant le
cardinal de Y càd le nombre de classes) dont le terme général est :

L(Cl , Cl 0 ) = Lll 0 = Coût associée à une mauvaise affectation

d’un objet de classe Cl à une classe Cl 0
X
0 x L est d’éléments positifs ou nuls et la diagonale est remplie de 0.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 47 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 48 / 285
Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Fonction de performance pour la catégorisation (suite) Fonction de perte binaire et classifieur bayésien
La fonction de perte la plus simple est associée à la matrice de perte
L’espérance de perte s’écrit alors : suivante :
1 si l 6= l 0

Lll 0 =
Z X
EX ,Y (L) = L(Cl , f (x))P(x, Cl )dx 0 si l = l 0
X C ∈Y
l
Dans ce cas, nous avons :
La solution est alors :
X
∀x ∈ X : f ∗ (x) = arg min Lll 0 P(Cl |X = x)
X Cl 0 ∈Y C ∈Y
l
∀x ∈ X : f ∗ (x) = arg min L(Cl , Cl 0 )P(Cl |X = x)
Cl 0 ∈Y C ∈Y = arg min(1 − P(Cl 0 |X = x))
l Cl 0 ∈Y

Comme précédemment, il existe plusieurs façons de définir la matrice = arg max P(Cl 0 |X = x)
Cl 0 ∈Y
de perte L. La fonction de perte la plus simple consiste à attribuer un
coût uniforme pour chaque type d’erreur. Autrement dit, la fonction de prédiction est telle que : f ∗ (x) = Cl ssi
P(Cl |X = x) = maxCl 0 ∈Y P(Cl 0 |X = x). Cette approche est appelée
classifieur bayésien.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 49 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 50 / 285

Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Classifieur bayésien Classifieur bayésien naı̈f

Si on suppose une matrice de perte uniforme et qu’on minimise Si l’on suppose de plus que les v.a. sont mutuellement indépendantes
l’espérance de la perte sous P(X , Y ) alors on obtient le classifieur (P(A|B) = P(A)) on a :
bayésien qui repose sur la probabilité conditionnelle P(Y |X ).
Si on applique le théorème de Bayes on a : P(X |Y ) = P(X 1 |Y )P(X 2 |Y ) . . . P(X p−1 |Y )P(X p |Y )
prior likelihood
z }| { z }| { Il s’agit dans ce cas du classifieur bayésien naı̈f dans ce cas il suffit
P(Y ) P(X |Y ) d’estimer à partir de E les probabilités suivantes pour chaque Cl ∈ Y :
P(Y |X ) =
| {z } P(X ) I La probabilité a priori : P(Cl ).
posterior
Les probabilités conditionnelles : P(X 1 |Y = Cl ), . . . , P(X p |Y = Cl ).
| {z } I
evidence

Rappelons que X = (X 1 , . . . , X p )
est un vecteur aléatoire de L’estimation de P(X = x) n’est pas nécessaire car c’est un
dimension p. En utilisant successivement les probabilités dénominateur commun aux probabilités a posteriori de chaque classe.
conditionnelles (P(A, B) = P(A|B)P(B)) on a : La fonction de décision pour x = (x1 , . . . , xp ) est f ∗ (x) = Cl ssi
P(X |Y ) = P(X 1 , . . . , X p |Y ) P(Cl |X = x) = maxCl 0 ∈Y P(Cl 0 |X = x) où :
= P(X 1 |Y , X 2 , . . . , X p )P(X 2 , . . . , X p |Y ) P(Cl 0 |X = x) ∝ P(Cl 0 )P(X 1 = x1 |Cl 0 ) . . . P(X p = xp |Cl 0 )
= P(X 1 |Y , X 2 , . . . , X p ) . . . P(X p−1 |Y , X p )P(X p |Y )
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 51 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 52 / 285
Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé Apprentissage supervisé Dif. caractéristiques des méthodes d’apprentissage supervisé

Classifieur bayésien naı̈f (suite) Estimation, décision, zone de rejet

Pour les méhodes de type inductif, il y a deux phases :
1 une étape d’inférence ou d’estimation des paramètres du modèle P,
2 une étape de décision qui permet d’aboutir à la prédiction fˆ(X ).
Il existe plusieurs façons de définir théoriquement f (X ) (espaces
Il est “naı̈f” de supposer l’indépendance entre les variables mais ce d’hypothèses H).
modèle probabiliste est simple à estimer. Certains modèles sont simples et conduisent à des solutions
On peut supposer d’autres modèles de dépendance pour analytiques comme la régression linéaire multiple.
P(X 1 , . . . , X p |Y ). Une approche consiste à modéliser les relations de Pour des classes d’hypothèses plus complexes on a recours à des
dépendance par le biais de graphes. On parle alors de modèles algorithmes d’optimisation numérique. Il existe également plusieurs
graphiques (ou de réseaux bayésiens). façon d’estimer les paramètres de f (X ) étant donné E.
Certains modèles permettent d’appréhender une incertitude de la
prédiction donnée par fˆ(X ). Dans ce cas, on peut définir une zone de
rejet dans la prise de décision et faire intervernir l’humain. Par
exemple, dans le cas des k-ppv et d’une catégorisation binaire, si la
classe majoritaire ne dépasse pas 60% on peut avoir une zone de rejet.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 53 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 54 / 285

Apprentissage supervisé Concepts importants en apprentissage supervisé Apprentissage supervisé Concepts importants en apprentissage supervisé

Rappel du Sommaire Généralisation, sous et sur-apprentissage

Le choix d’une méthode revient à choisir un espace d’hypothèses, une

2 Apprentissage supervisé fonction de perte et une technique d’inférence.
Définitions, notations et concepts importants Ce qu’on attend d’une bonne méthode n’est pas tant sa capacité à
Quelques méthodes simples en guise d’illustration reproduire à l’identique le résultat des données d’entraı̂nement mais
Différentes caractéristiques des méthodes d’apprentissage supervisé de produire les résultats corrects sur des données de test càd non
Concepts importants en apprentissage supervisé observées : c’est le principe de généralisation.
Evaluation et comparaison de modèles en apprentissage supervisé Dans cette perspective il faut une bonne adéquation entre la
(Quelques) Aspects théoriques en apprentissage automatique complexité de la classe d’hypothèse choisie H et la véritable relation
Les méthodes linéaires et leurs pénalisations (elasticnet ...) entre X et Y . Si la complexité de H n’est pas assez suffisante on
Les réseaux de neurones artificiels (“Artificial Neural Networks”) parle de sous-apprentissage.
Les machines à vecteurs supports (“Support Vector Machines”) Quand au contraire, la complexité de H est trop grande, il arrive que
l’erreur sur E est proche de zéro mais l’erreur sur les données de test
est grande. Dans ce cas on parle de sur-apprentissage.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 55 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 56 / 285
Apprentissage supervisé Concepts importants en apprentissage supervisé Apprentissage supervisé Concepts importants en apprentissage supervisé

Généralisation, sous et sur-apprentissage (suite) Généralisation, sous et sur-apprentissage (suite)

Exemple de sous-apprentissage (H=Ensemble des polynômes de degré Exemple de sur-apprentissage (H=Ensemble des polynôme de degré
1 de X ). 12 de X ).
1.0

1.0
0.5

0.5
0.0

0.0
y

y
−0.5

−0.5
−1.0

−1.0
−2 −1 0 1 2 3 −2 −1 0 1 2 3
x x

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 57 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 58 / 285

Apprentissage supervisé Concepts importants en apprentissage supervisé Apprentissage supervisé Concepts importants en apprentissage supervisé

Compléxité des modèles de régression linéaire Arbitrage biais-variance

Dans l’exemple de régression, la complexité d’un modèle ou d’une Définition. (Décomposition Erreur quadratique - Bruit)
classe d’hypothèses H est l’ordre du polynôme. EY |X ((f (X ) − Y )2 |X )
| {z }
Si l’ordre est trop petit, il y a sous-apprentissage et s’il est trop grand EY |X (`2 |X )
il y a sur-apprentissage. =
Pour le polynôme de degré 1 : 2 2
EY |X ( f (X ) − EY |X (Y |X ) |X ) + EY |X ( EY |X (Y |X ) − Y |X )
I la complexité des données et celle du modèle ne coı̈ncident pas, | {z } | {z }
I l’erreur mesurée sur les données E est très grande, Erreur quadratique Bruit irréductible
I mais la fonction de prédiction étant une droite la variance du modèle
est faible (si on change E la “droite changera peu”). Le bruit irréductible est intrinsèque aux données (les erreurs de
Pour le polynôme de degré 12 : mesure par exemple) et le terme associé représente l’erreur minimale
I la complexité des données et celle du modèle ne coı̈ncident pas, que l’on peut commettre en moyenne.
I l’erreur mesurée sur les données E est très faible, L’erreur quadratique est l’espérance de l’erreur entre f et la
I mais la fonction de prédiction est instable et donc la variance du modèle
fonction de regression (que l’on a vue être la fonction optimale pour
est très grande (si on change E la “courbe changera beaucoup”).
la minimisation de EX ,Y (`2 )).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 59 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 60 / 285
Apprentissage supervisé Concepts importants en apprentissage supervisé Apprentissage supervisé Concepts importants en apprentissage supervisé

Arbitrage biais-variance (suite) Arbitrage biais-variance (suite)

Dans ce contexte, les méthodes d’apprentissage consistent donc à Définition. (Décomposition Biais - Variance)
approximer EY |X (Y |X ). Etant donné les données d’apprentissage à h i2
disposition, E, on infère une fonction de prédiction fˆE (X ). ˆ
EE fE (X ) − EY |X (Y |X )
Si l’on change de données d’apprentissage on obtient une autre | {z }
fonction de prédiction. Ainsi, on peut voir les données d’entraı̂nement Erreur quadratique

comme la réalisation d’un processus aléatoire et on définit ainsi : h =

i2 h i2
EE (fÊ (X )) qui est l’espérance de la fonction de prédiction dépendant EE fÊ (X ) − EE (fÊ (X )) + EE (fÊ (X )) − EY |X (Y |X )
du processus aléatoire générant les données E. | {z } | {z }
2
Etant donné un ensemble E et une fonction de prédiction induite Variance Biais

fˆE (X ), on peut alors décomposer l’erreur quadratique comme suit :

Le biais indique, l’écart entre la fonction de prédiction moyenne
apprise sur plusieurs jeux de données et la fonction de régression.
h i2
ˆ
EE fE (X ) − EY |X (Y |X )
h La variance représente en moyenne, l’écart quadratique entre une
i2 h i2
ˆ ˆ
= EE fE (X ) − EE (fE (X )) ˆ
+ EE EE (fE (X )) − EY |X (Y |X ) fonction de prédiction apprise sur un jeux de données et la fonction de
prédiction moyenne apprise sur plusieurs jeux de données.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 61 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 62 / 285

Apprentissage supervisé Concepts importants en apprentissage supervisé Apprentissage supervisé Concepts importants en apprentissage supervisé

Arbitrage biais-variance (suite) Arbitrage biais-variance (suite)

Illustration du problème de l’arbitrage biais-variance

A erreur quadratique constante, on voit qu’il y a un arbitrage entre
biais et variance.
Exemple de fort biais et faible variance : régression linéaire avec

Erreur de prédiction
polynôme de degré 1.
Exemple de faible biais et forte variance : régression linéaire avec
polynôme de degré 12.
Données de test
L’idéal est d’avoir un faible biais et une faible variance pour une ou de validation
meilleure généralisation mais plus facile à dire qu’à faire !
Plus la complexité d’un modèle augmente plus le biais mesuré sur des
données E diminue. Mais la variance augmentant également, le bon Données d’entraı̂nement
comportement du modèle estimé sur des données non observées n’est
alors plus garanti.
Complexité du modèle

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 63 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 64 / 285
Apprentissage supervisé Concepts importants en apprentissage supervisé Apprentissage supervisé Concepts importants en apprentissage supervisé

Impact de la taille de l’échantillon d’entraı̂nement E Arbitrage triple Complexité - Données d’entraı̂nement -

Erreur en généralisation
Même tâche que précedemment : les données sont générées par la
fonction cos sur [−π, π] à laquelle on ajoute un bruit ∼ N (0, 0.08). En apprentissage automatique à partir d’exemples d’entraı̂nement, il y
H =Ensemble des polynômes de X de degré 12. a un arbitrage entre ces trois facteurs :
Estimation sur deux échantillons de tailles n = 12 et n = 50. I La complexité de l’espace des hypothèses choisis H.
I La quantité de données d’entraı̂nement n.
I La qualité de généralisation de la fonction de prédiction sur des
1.0

données de tests.

1.0
Une grande complexité de H permet une meilleure flexibilité du
0.5

0.5
modèle et implique une meilleure généralisation.
0.0

Mais une trop grande complexité donne parfois trop de flexibilité : sur

0.0
y

y
E l’erreur diminue mais la variance du modèle sera plus forte. Ainsi, si
−0.5

−0.5
−1.0 les données de test sortent de la région des données E, le
comportement de la fonction de prédiction risque d’être chaotique.
−1.0

−2 −1 0 1 2 3 −3 −2 −1 0 1 2 3
x x
Ce problème est moins fort lorsque n est grand comme on vient de le
Bien sûr plus on a de données meilleure est l’estimation ! voir mais jusqu’à un certain point.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 65 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 66 / 285

Apprentissage supervisé Concepts importants en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Arbitrage triple Complexité - Données d’entraı̂nement - Rappel du Sommaire

Erreur en généralisation (suite)
Extrapolation du modèle appris précédemment jusqu’à 2π.
2 Apprentissage supervisé
Définitions, notations et concepts importants
Quelques méthodes simples en guise d’illustration
1.0

Différentes caractéristiques des méthodes d’apprentissage supervisé

Concepts importants en apprentissage supervisé
0.5

Evaluation et comparaison de modèles en apprentissage supervisé

(Quelques) Aspects théoriques en apprentissage automatique
0.0
y

Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Les réseaux de neurones artificiels (“Artificial Neural Networks”)
−0.5

Les machines à vecteurs supports (“Support Vector Machines”)

−1.0

−2 0 2 4 6
x
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 67 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 68 / 285
Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Schéma général Protocol expérimental en apprentissage supervisée

Etant donné une tâche d’apprentissage supervisé, le but est donc
d’estimer plusieurs modèles afin de prédire au mieux la variable
cible pour des données futures. Pour sélectionner le modèle, il faut
FEATURE
MATRIX
procéder en distinguant au moins deux ensembles de données.
1 Un ensemble des données d’apprentissage ou d’entraı̂nement E à
DATABASE
(numerical NUMERICAL CLASSIFI- CLASSIFI- partir duquel on estime une ou plusieurs fonctions de prédiction
data, texts, REPRESENTA -CATION -CATION
images, TION ALGORITHM OUTPUT appartenant à un ou plusieurs espaces d’hypothèses.
networks, …)
2 Un ensemble de données de validation noté V qui n’est pas utilisé
PROXIMITY
MATRIX
lors de l’estimation des modèles et qui sert à mesurer l’erreur de
prédiction des différents modèles appris.
C’est l’erreur de prédiction mesurée sur V qui permet en pratique de
CLASSIFI- sélectionner le meilleur modèle fˆ∗ .
-CATION
ASSESSMENT 3 En revanche, si l’on souhaite avoir une estimation de l’erreur en
généralisation de fˆ∗ alors on ne peut pas utiliser celle mesurée à l’aide
de V. On a recourt à un troisième jeu de données appelé ensemble de
données de test et noté T.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 69 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 70 / 285

Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Protocol expérimental en apprentissage supervisée (suite) Validation croisée

En général on prend 50% des données annotées pour E, 25% pour V Précédemment on a supposé les données annotées séparées en E et T.
et 25% pour T. Mais il n’y a pas en théorie de découpage optimal. Mais l’estimation de l’erreur de prédiction est plus précise si on avait
Dans certaines situations, on utilisera uniquement un ensemble de à disposition plusieurs ensembles E et T.
données d’entraı̂nement E et un ensemble de données de test T : La validation croisée consiste à :
I Séparer aléatoirement l’ensemble des données annotées en k
I Lorsque nous voulons tester un seul modèle et non plusieurs. Dans ce
sous-ensembles.
cas, l’ensemble de données de validation n’est pas nécessaire. I Utiliser un sous-ensemble comme ensemble de test T.
I Lorsque l’ensemble des données annotées n’est pas grand (n I Utiliser l’union des k − 1 sous-ensembles restants comme ensemble
relativement petit). Dans ce cas, il devient difficile de découper en trois
d’entraı̂nement E.
l’ensemble des données annotées et d’obtenir un bon apprentissage.
En changeant chaque fois l’ensemble de validation, on voit qu’une k
Le second cas est souvent rencontré en pratique. En effet, il est en validation croisée permet d’avoir k paires d’échantillons (E, T) et
général difficile d’avoir une grande quantité de données annotées car ainsi k estimations de l’erreur de prédiction.
cela nécessite l’intervention humaine et la tâche d’annotation est
On moyenne l’ensemble des k mesures d’erreurs afin d’avoir une
fastidieuse.
estimation plus robuste de l’erreur de prédiction.
Nous présentons dans la suite des méthodes permettant d’avoir une Si k = n on parle de “leave one out cross validation (LOOCV)”.
bonne estimation de l’erreur en généralisation. On apprend sur n − 1 individus et on teste sur 1 individu (n fois).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 71 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 72 / 285
Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Validation croisée (suite) Mesures d’évaluation

Précédemment, nous avons vu des fonctions de performances pour la
Ensemble des données annotées régression et la catégorisation que l’on cherche à optimiser en
utilisant les données E afin d’inférer des fonctions de prédiction
Découpage aléatoire en 4 sous-ensembles appartenant à une ou plusieurs classes d’hypothèses.
Pour la sélection des modèles on peut avoir recours à d’autres types
1ère paire (en rouge T, le reste E) de critères d’évaluation mesurés sur les données V et/ou T, indiquant
les performances d’une fonction de prédiction. Ces différentes mesures
permettent de mieux comparer les modèles entre eux.
2ème paire
En ce qui concerne la régression, les critières courants sont :
I La somme des carrés des résidus (scr ou “Residual Sum of Squares”).
3ème paire I La moyenne des carrés des résidus (“Mean Squared Error”) .
I La moyenne des résidus en valeurs absolues (“Mean Absolute Error”)
Pour ce qui est du problème de catégorisation :
4ème paire I Le taux d’erreur.
I La précision.
I Le rappel.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 73 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 74 / 285

Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Mesures d’évaluation pour le problème de régression Mesures d’évaluation pour le problème de catégorisation
binaire
La Somme des carrés des résidus ou les Moindres Carrés Ordinaires
(“Residual Sum of Square”) :
Quand il y a uniquement deux classes Y = {C1 , C2 }, beaucoup de
n
X mesures de performance sont décrites par le biais du tableau de
scr (f ) = (yi − f (xi ))2
contingence suivant appelé matrice de confusion :
i=1
La Moyennes des carrés des résidus (“Mean Squared Error”) : fˆ(x)
Total
n C1 C2
1 X
C1 a b a+b
mse(f ) = (yi − f (xi ))2 y
n C2 c d c +d
i=1
Contrairement au scr , le mse permet de comparer les erreurs de Total a+c b+d a+b+c +d =n
prédiction mesurés sur des ensembles de données de tailles différentes a =Nb d’objets C1 correctement catégorisés
La moyenne des résidus en valeurs absolues (“Mean Absolute Error”) :
b =Nb d’objets C1 catégorisés en C2
n
1X c =Nb d’objets C2 catégorisés en C1
mae(f ) = |yi − f (xi )|
n d =Nb d’objets C2 correctement catégorisés
i=1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 75 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 76 / 285
Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Mesures d’évaluation pour le problème de catégorisation Mesures d’évaluation pour le problème de catégorisation
binaire (suite) binaire (suite)
En statistique on interprète souvent une classe comme étant la classe fˆ(x)
“positive” (C1 par exemple) et l’autre classe comme étant la classe Total
C1 C2
“négative” (resp. C2 ). Par exemple C1 =“Malade” et C2 =“Sain”. C1 a b a+b
Dans ce cas, les différentes valeurs du tableau de contingence sont y
C2 c d c +d
aussi connues sous les vocables suivants : Total a+c b+d a+b+c +d =n
fˆ(x)
Total
C1 C2
Taux d’erreur (“Error rate” ou “Misclassification Rate”) :
C1 a b a+b
y b+c
C2 c d c +d
err (fˆ) =
Total a + c b + d a + b + c + d = n n
a =Vrais positifs (“True Positive”, tp) Taux de réussite ou de reconnaissance (“Accuracy Rate”) :
b =Faux négatifs (“False Negative”, fn)
a+d
c =Faux positifs (“False Positive”, fp) acc(fˆ) = = 1 − err (fˆ)
d =Vrais négatifs (“True Negative”, tn) n
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 77 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 78 / 285

Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Mesures d’évaluation pour le problème de catégorisation Courbe ROC

binaire (suite)
Toujours dans le cas binaire, supposons une fonction de prédiction qui
fˆ(x) soit dépendante d’un seuil :
Total
C1 C2
C1 a b a+b ˆ C1 si ĝ (x) ≥ δ (classe “positive”)
y f (x) =
C2 c d c +d C2 si ĝ (x) < δ
Total a+c b+d a+b+c +d =n
A titre illustratif et pour fixer les idées, on pourra interpréter ĝ (x)
Taux de vrais positifs (“True positive rate”) et taux de faux positifs comme étant le score obtenu par x pour la fonction discriminante (cas
(“False positive rate” ou “False alarm rate”) : de la régression linéaire avec variables artificielles C1 ↔ 1 et
a c C2 ↔ −1) associée à C1 et δ le seuil au-dessus duquel on considère
tp(fˆ) = et fp(fˆ) = que x est dans C1 .
a+b c +d
Dans ce contexte, on s’intéresse typiquement aux mesures tp et fp
Sensitivité (“sensitivity”) et spécificité (“specificity”) :
d’un modèle pour son évaluation (toutefois d’autres mesures peuvent
a c être utilisées comme précision et rappel).
sen(fˆ) = tp(fˆ) = et spe(fˆ) = 1 −
a+b c +d
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 79 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 80 / 285
Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Courbe ROC (suite) Courbe ROC (suite)

Le seuil δ est dans ce cas un paramètre à déterminer et on voit qu’en Reprenons l’exemple de catégorisation auquel on a ajouté les données
fonction de sa valeur, les mesures d’erreurs fluctuent. Par exemple, si de test T.
le classifieur est basé sur une fonction discriminante comme
précédemment alors si δ est proche de 1, il sera très difficile d’affecter

1.0
des objets de T dans la classe C1 et dans ce cas fp(fˆ) mais aussi
●
tp(fˆ) auront tendance à être faibles. ● ●
●
●

0.8
●
● ● ●●●
● ●
●
Pour différentes valeurs de δ, on obtient plusieurs valeurs pour la ● ● ●● ●
●
●
●
●
●
● ● ●
paire (fp(fˆ), tp(fˆ)).
● ●● ● ●
● ● ●

0.6
● ● ●
● ●●● ●
● ●● ● ●●
● ● ●
Le graphe de ces différents points dans le repère fp en abscisse et tp ● ● ● ● ●
● ● ● ●

X^2
● ● ●
● ● ●
● ● ● ● ● ●●● ● ●
● ● ● ●
●●●
●● ● ● ●
en ordonnée est appelée courbe ROC “Receiver Operating ● ● ●● ● ● ●

0.4
● ● ● ●● ●●
● ● ●
● ●
● ●● ●● ● ●
Characteristics”. ●
●
● ●
●● ● ●
● ●●● ●
● ●
●
●●
●● ●
● ●
Idéalement on aimerait trouver δ tel que tp(fˆ) = 1 et fp(fˆ) = 0 mais ● ● ● ●
●
●● ●
●

0.2
● ●
● ●●
●●● ●
●
●● ● ●
plus facile à dire qu’à faire ! ● ●
●
●
●
● ● ●
●
●
●
Ainsi, les modèles fˆ relatifs aux δ dont les points de coordonnées
●
●

0.0
● ● ●

(fp(fˆ), tp(fˆ)) sont proches du coin supérieur gauche sont meilleurs 0.0 0.2 0.4 0.6 0.8 1.0
X^1
que les autres.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 81 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 82 / 285

Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Courbe ROC (suite) Courbe ROC (suite)

Régression linéaire simple sur variables artificielles et frontière de Régression linéaire simple sur variables artificielles et frontières de
décision ĝ (x) = 0. décision ĝ (x) = δ avec δ = 0.5, 0, −0.5.
1.0

1.0
● ●
● ●
● ● ● ● ● ●
0.8

0.8
●
● ● ●●● ●
● ● ●●●
● ● ● ●
● ●
● ● ● ●
● ●
● ● ●● ● ● ● ● ● ● ●● ● ● ● ●
● ●
●● ● ● ● ● ●
●● ● ● ●
● ● ● ● ● ●
0.6

0.6
● ● ● ● ● ●
● ●●● ● ● ●●● ●
● ●● ● ●● ● ●● ● ●●
● ● ●●● ● ● ● ● ● ●●● ● ● ●
● ● ● ● ● ● ● ●
X^2

X^2
● ● ●● ● ● ● ● ●● ● ●
● ● ● ● ● ●●● ●● ● ● ● ● ● ●●● ●●
● ● ● ●
●●● ● ● ● ●
●●●
●● ● ● ● ●● ● ● ●
● ● ●● ● ● ● ● ● ●● ● ● ●
0.4

0.4
● ● ● ●● ●● ● ● ● ●● ●●
● ● ● ● ● ●
● ● ● ●
● ●● ●● ● ● ● ●● ●● ● ●
● ● ● ● ● ● ● ● ● ● ● ● ● ●
● ● ● ● ●● ● ● ● ● ● ●● ●
● ● ● ●●● ● ● ● ● ●●● ●
● ● ● ● ● ● ● ●
● ● ● ● ● ● ● ●
●● ● ●● ●
0.2

0.2
● ● ● ●
● ●● ● ●●
●●● ●
● ●●● ●
●
●● ● ● ●● ● ●
● ● ● ● ● ●
● ● ● ● ● ● ● ● ● ●
● ● ● ●
● ● ● ●
● ●
0.0

0.0

● ● ● ● ● ●

0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
X^1 X^1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 83 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 84 / 285
Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Courbe ROC (suite) Courbe ROC (suite)

Pour l’exemple précédent, on obtient la courbe ROC suivante : Les points correspondent aux valeurs pour δ = 0.5, 0, −0.5.
1.0

1.0
●

●
0.8

0.8
●
True positive rate

True positive rate

0.6

0.6
0.4

0.4
0.2

0.2
0.0

0.0
0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
False positive rate False positive rate

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 85 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 86 / 285

Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Courbe ROC (suite) Courbe ROC et AUC “Area Under the Curve”
Courbe ROC pour un classifieur aléatoire (on tire au hasard dans
{C1 , C2 } pour chaque point) : Pour qu’un modèle soit intéressant il faut qu’il soit meilleur qu’un
classifieur aléatoire : la courbe ROC du modèle doit pour cela être
au-dessus de la diagonale.
1.0

On peut comparer deux types de fonction de prédiction en utilisant

les courbes ROC : le modèle dont la courbe est au-dessus de l’autre
0.8

est le meilleur.
La courbe ROC permet une évaluation graphique des performances
True positive rate
0.6

d’un classifieur. On peut par aussi résumer le graphique par un

nombre appelé “Area Under the Curve” qui est l’indice auc. auc(fˆ)
0.4

est la mesure de la surface sous la courbe ROC.

Idéalement on souhaite déterminer un modèle fˆ tel que auc(fˆ) = 1.
0.2

Le modèle fˆ est meilleur que fˆ0 si auc(fˆ) > auc(fˆ0 ).

0.0

0.0 0.2 0.4 0.6 0.8 1.0

Le modèle fˆ est meilleur que le classifieur aléatoire si auc(fˆ) > 0.5.
False positive rate

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 87 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 88 / 285
Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé

Mesures d’évaluation pour le problème de catégorisation Mesures d’évaluation pour le problème de catégorisation
multiclasse multiclasse (suite)
Quand Y = {C1 , C2 , . . . , Cq } avec q > 2, on parle d’un problème de Dans le cas multiclasses on a la matrice de confusion N de taille
catégorisation multiclasse. (q × q) :
La matrice de confusion est alors une matrice carrée N d’ordre q.
fˆ(x)
Le terme N(l, l 0 ) = Nll 0 indique le nombre d’objets x de T
C1 . . . Cq
appartenant à la classe Cl et ayant été affecté à la classe Cl 0 par fˆ(x).
N= C1
Idéalement, il faudrait que les termes hors diagonale ne contiennent ..
y .
que des 0 ce qui conduirait à un taux d’erreur nul.
Le taux de reconnaissance est la somme des termes de la diagonale Cq
divisée par le cardinal de T.
On généralise au cas multiclasses (avec un coût uniforme) le taux
L’analyse de la matrice de confusion permet de déterminer les paires
d’erreur (“Error rate” ou “Misclassification Rate”) et le taux de
de classes les plus difficiles à séparer.
reconnaissance (“Accuracy rate”) :
Des tests statistiques permettent également de comparer les résultats P
de plusieurs modèles et sur plusieurs bases de données l6=l 0 Nll 0
err (fˆ) = P et acc(fˆ) = 1 − err (fˆ)
[Alpaydin, 2010, Cornuéjols and Miclet, 2003]. l,l 0 Nll 0
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 89 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 90 / 285

Apprentissage supervisé Evaluation et comparaison de modèles en apprentissage supervisé Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique

Autres critères pour comparer deux modèles Rappel du Sommaire

Au-delà des critères de performances de type erreur de prédiction ou
en généralisation, il faut également tenir compte de plusieurs autres
critères lorsque l’on compare des algorithmes d’apprentissage 2 Apprentissage supervisé
supervisé :
Définitions, notations et concepts importants
I La complexité en termes de temps de traitement et en termes
d’espace mémoire : on parle d’algorithmes ou de modèles scalables ou Quelques méthodes simples en guise d’illustration
non. Différentes caractéristiques des méthodes d’apprentissage supervisé
I L’inteprétabilité du modèle estimé : au-delà d’une simple prédiction Concepts importants en apprentissage supervisé
de valeurs ou de classe, est-ce que le modèle estimé permet une Evaluation et comparaison de modèles en apprentissage supervisé
meilleure connaissance sur le processus génératif qui engendre les (Quelques) Aspects théoriques en apprentissage automatique
observations (X , Y ) ou s’agit-il d’une “boı̂te noire” ? Les méthodes linéaires et leurs pénalisations (elasticnet ...)
I La capacité des modèles à s’adapter à des données qui peuvent être
Les réseaux de neurones artificiels (“Artificial Neural Networks”)
hétérogènes et/ou manquantes et/ou aberrantes et/ou non
pertinentes vis à vis du problème considéré.
Les machines à vecteurs supports (“Support Vector Machines”)
Principe de simplicité dit du rasoir d’Occam : à erreur de prédiction
comparable, on préfèrera le modèle de complexité la moindre
permettant l’interprétation la plus simple du phénomène étudié.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 91 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 92 / 285
Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique

Dimension de Vapnik-Chervonenkis Dimension de Vapnik-Chervonenkis (suite)

On a parlé de complexité des modèles linéaires. De manière plus
Exemple : la dimension VC de
générale, la notion de complexité d’un espace H peut être
H = {f : R2 → R : f (X ) = a0 + a1 X 1 + a2 X 2 } (polynôme de degré
appréhendée par le concept de dimension de Vapnik-Chervonenkis.
1) est vc(H) = 3
Considérons un problème de catégorisation binaire. Soit E un
ensemble d’apprentissage de n points. Il y a 2n façons différentes
d’attribuer l’une ou l’autre classe à ces n points.
Si pour chacune de ces 2n configurations, il existe h ∈ H qui permet
de réaliser cette dichotomie par une fonction indicatrice alors on dit
que H pulvérise l’ensemble de points.
Pour rappel, une fonction indicatrice ind est telle que ind(A) = 1 si la
proposition A est vraie ; ind(A) = 0 sinon.

Définition. (Dimension VC)

La dimension VC d’un espace d’hypothèses H, notée vc(H), est le cardinal
du plus grand ensemble de points de X que H peut pulvériser.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 93 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 94 / 285

Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique

Dimension de Vapnik-Chervonenkis (suite) Dimension de Vapnik-Chervonenkis (suite)

Soit u1 , . . . , up , v ∈ R où au moins un des ui est non nul. Rappelons

que l’ensemble des points x = (x1 , . . . , xp ) ∈ Rp qui satisfait
l’équation linéaire suivante est appelé un hyperplan de Rp :
Plus la dimension VC est grande plus H est complexe. On dit
u1 x1 + . . . + un xn = v ce qui est équivalent à hu, xi = v
également que H a plus de capacité ou est plus flexible.
où hu, vi = u> v est le produit scalaire canonique de Rp .
Intuitivement, on voit que plus la dimension VC est grande, plus la
Les hyperplans généralisent dans Rp , le point dans R, la droite dans forme de la frontière de décision est onduleuse ce qui permet de
R2 et le plan dans R3 . pulvériser plus de points (en opposition aux hyperplans).
Nous pouvons alors généraliser la dimension VC de l’exemple Autre exemple, l’espace d’hypothèses
précédent : H = {f : Rp → {0, 1} : f (x) = ind(sin(αx) > v ), α ∈ R} est tel que
vc(H) = ∞.
Propriété. (Dimension VC des hyperplans)
L’espace d’hypothèses
H = {f : Rp → {0, 1} : f (x) = ind(hx, ui > v ), u ∈ Rp , v ∈ R} est tel que
vc(H) = p + 1.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 95 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 96 / 285
Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique

Apprentissage PAC Apprentissage PAC et dimension VC

L’apprentissage “Probably Approximately Correct” (PAC) proposé L’un des résultats théoriques majeurs développés par Vapnik et
par Valiant 1 [Valiant, 1984], est un sous-domaine de l’AA de nature Chervonenkis est d’avoir pu déterminer une borne de la probabilité
théorique qui s’intéresse aux propriétés de généralisation des précédente qui dépend de la dimension VC de la méthode utilisée.
méthodes. Pour alléger les formules, on introduit les notations suivantes :
Soit C une classe de Y et soient E = {(x1 , y1 ), . . . , (xn , yn )} des
I risk(f ) = EX ,Y (`(f (X ), Y )) est le risque théorique.
`(fˆ (x ),y )
Pn
exemples générés par une fonction de probabilité inconnue P(X , Y ). I riskemp (fÊ ) = i=1 nE i i est le risque empirique étant donné E.
La question que traite l’apprentissage PAC est la suivante : combien Propriété. (Borne PAC et dim. VC pour un pb de classement binaire)
d’exemples n faut-il pour qu’avec une probabilité 1 − δ, une
hypothèse fÊ ∈ H inférée d’un ensemble E généré par P(X , Y ), Si on estime une fonction de prédiction fÊ ∈ H à partir de E alors avec une
commet en moyenne un taux d’erreur d’au plus ε ? probabilité au moins égale à 1 − δ on a :
Formellement on a :  s 
η ˆ
4riskemp (fE ) 
P(EE (`(fÊ (X ), Y )) < ε) ≥ 1 − δ risk(f ) ≤ riskemp (fÊ ) + 1 + 1 +
2 η
Autrement dit, “avec probabilté plus grande que 1 − δ, on a un taux
d’erreur plus petit que ε”.
n
vc(H) log β vc(H)

+1 −log( δ4 )
1. Prix Nevanlinna 1986, Prix Knuth 1997, Prix Turing 2010 où η = α n , 0 ≤ α ≤ 4 et 0 ≤ β ≤ 2
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 97 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 98 / 285

Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique

Apprentissage PAC et dimension VC (suite) Malédiction de la dimensionalité

Dans les exemples précédents nous avons considéré des problèmes de
faibles dimensions dans le sens où le nombre de dimension de l’espace
La borne PAC précédente constitue un beau résultat théorique en ce de description X est petit.
qu’elle est valable pour n’importe qu’elle probabilité jointe P(X , Y ) et Dans beaucoup de problèmes pratiques, les vecteurs xi appartiennent
qu’elle ne dépend que de la dimension de VC de la classe à un espace de très grande dimension.
d’hypothèses utilisée. C’est le cas notamment lorsque les objets sont des textes ou des
Toutefois : images. Par exemple, l’espace de description d’un texte est
I L’absence de précision sur la forme de P(X , Y ) rend la borne peu potentiellement l’ensemble du vocabulaire de la langue considérée
efficace et on obtient un nombre n qui est surestimé. (soit plus de 60000 descripteurs pour le français).
I Par ailleurs, vc(H) est en général très difficile à calculer. Il arrive parfois que |X| = p est plus grand que |E| = n.
En pratique, il est donc difficile d’utiliser ce résultat. Par ailleurs, on pourrait penser, comme suggérer précédemment, que
Il n’empêche que ces questions de natures théoriques restent si n est très grand alors on est toujours capable d’avoir de bons
importantes. résultats en généralisation.
Dans le cas des données de grande dimension ceci n’est
malheureusement pas vrai notamment pour les méthodes locales
(telles ques les k-ppv ou les méthodes à noyau).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 99 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 100 / 285
Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique

Malédiction de la dimensionalité (suite) Malédiction de la dimensionalité (suite)

Pour p = 1 (intervalle [−1, 1]), on a :
On a l’habitude d’évoluer dans un espace à 3 dimensions au sein
I Pour n = 20 : d(20, 1) ≈ 0.03.
duquel, les distances entre objets nous paraissent “claires”. En I Pour n = 500 : d(500, 1) ≈ 0.001.
revanche, les espaces de grande dimension sont beaucoup plus I Pour n = 20000 : d(20000, 1) ≈ 3 × 10−5 .
“vastes” et les mesures de distances ne s’appréhendent pas de la Pour p = 3 (boule de rayon 1), on a :
même manière qu’en 3 dimensions. I Pour n = 20 : d(20, 3) ≈ 0.32.
Exemple [Hastie et al., 2011] : considérons une hypersphère de rayon I Pour n = 500 : d(500, 3) ≈ 0.11.
unitaire centrée à l’origine d’un espace de dimension p ; considérons I Pour n = 20000 : d(20000, 3) ≈ 0.03.
également un ensemble de n points générés aléatoirement selon une Pour p = 10 (hypersphère de rayon 1), on a :
loi uniforme à l’intérieur de cette hypersphère. I Pour n = 20 : d(20, 10) ≈ 0.71.
I Pour n = 500 : d(500, 10) ≈ 0.52.
On considère les plus proches voisins de l’origine de l’hypersphère et I Pour n = 20000 : d(20000, 10) ≈ 0.36.
on montre que la distance médiane du plus proche voisin de l’origine I Pour n = 2 × 1014 : d(2 × 1014 , 10) ≈ 0.03.
est donnée par la formule suivante :
Ainsi pour avoir la même couverture de l’espace entre un espace de
1/n 1/p
d(n, p) = 1 − 12 petite dimension et un espace de plus grande dimension, le nombre de
points nécessaire croı̂t de façon exponentielle !
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 101 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 102 / 285

Apprentissage supervisé (Quelques) Aspects théoriques en apprentissage automatique Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Malédiction de la dimensionalité (suite) Rappel du Sommaire

Un autre problème associé à la dimensionalité est le suivant : à

mesure que p augmente, les mesures de distances sont de moins en
moins significatives. 2 Apprentissage supervisé
La mesure de distance séparant les deux points les plus éloignés Définitions, notations et concepts importants
(distmax ) et celle séparant les points les plus proches (distmin ) sont de Quelques méthodes simples en guise d’illustration
plus en plus comparables [Beyer et al., 1999] : Différentes caractéristiques des méthodes d’apprentissage supervisé

distmax
Concepts importants en apprentissage supervisé
∀ε > 0 , limp→∞ P distmin − 1 ≤ ε = 1

Evaluation et comparaison de modèles en apprentissage supervisé
Le traitement des données de grandes dimensions forme un (Quelques) Aspects théoriques en apprentissage automatique
sous-domaine particulier de l’AA puisque les méthodes développées Les méthodes linéaires et leurs pénalisations (elasticnet ...)
dans le cas des données de faibles dimensions ne sont pas efficaces. Les réseaux de neurones artificiels (“Artificial Neural Networks”)
Dans ce cas, une façon de procéder est d’appréhender les variables Les machines à vecteurs supports (“Support Vector Machines”)
discriminantes des données en déterminant les sous-espaces de
dimensions plus faibles au sein desquels les distances redeviennent
significatives.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 103 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 104 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Introduction Régression linéaire multiple et MCO

Les méthodes de régression linéaire supposent que la fonction de Rappelons que nous souhaitons déterminer une fonction f modélisant
régression E(Y |X ) est une fonction linéaire des paramètres P. la relation entre la variable cible Y et les variables explicatives
Ce sont des méthodes développées depuis le XVIIIème siècle en {X 1 , X 2 , . . . , X p } qui constituent l’espace de description des objets X.
statistiques et qui sont encore de nos jours très utilisées car elles sont
Le modèle de régression linéaire est le suivant :
simples et permettent une bonne interprétation de l’influence des
variables explicatives sur la variable à expliquer : p
X
X ∂f Y = f (X 1 , . . . , X p ) + = a0 + aj X j +
f (X ) = aj X j ⇒ (X ) = aj j=1
∂X j
j
Pp
Des développements récents sont également proposés permettant On a donc H = {f : Rp → R : f (X ) = a0 + j=1 aj X
j }.

d’enrichir la panoplie de ce type de méthodes. En particulier, certaines Les variables explicatives peuvent être :
méthodes aboutissant à des frontières de décision non-linéaires sont I Les variables initiales.
en fait des généralisations des méthodes linéaires (au sens d’un I Des transformations des variables initiales.
polynôme de degré 1 des paramètres P). I Des expansions de bases des variables initiales [Hastie et al., 2011].
On étudiera pour les problèmes de régression et de catégorisation, les Le modèle reste une fonction linéaire des paramètres P = {aj }pj=0 .
fondements et la mise en oeuvre de méthodes de base et avancées.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 105 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 106 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression linéaire multiple et MCO (suite) Régression linéaire multiple et MCO (suite)
L’étape d’induction consiste à estimer les paramètres P étant données Nous avons :
     
les données d’entraı̂nement E. a0 1 x11 x12 . . . x1p y1
La méthode classique est les Moindres Carrés Ordinaires (MCO) : a1  1 x21 x22 . . . x1p  y2 
a=. ; X = . ; y=.
     
.. .. 
n
X  ..   .. . ... ... .   .. 
scr (f ) = (yi − f (xi ))2 ap 1 xn1 xn2 . . . xnp yn
i=1
n p Notons par ailleurs X> la matrice transposée de X.
Nous avons alors l’écriture matricielle suivante :
X X
= (yi − (a0 + aj xij ))2
i=1 j=1 scr (f ) = (y − Xa)> (y − Xa)
Du point de vue statistique, l’utilisation de ce modèle suppose que les On cherche à déterminer les paramètres P = {aj }pj=0 représentés par
observations yi sont des réalisations de v.a. Yi i.i.d.. le vecteur a qui minimise scr (f ). C’est un problème d’optimisation
Introduisons les notations suivantes : quadratique non contraint :
I a, le vecteur colonne de taille p + 1 contenant les paramètres.
âmco = arg min (y − Xa)> (y − Xa)
I X, la matrice des données de taille (n × (p + 1)) à laquelle on a ajouté a∈Rp+1
une 1ère colonne remplie de 1.
La solution s’obtient en recherchant les points a tel que ∇scr (a) = 0.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 107 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 108 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Rappels en calcul différentiel Régression linéaire multiple et MCO (suite)

Si f : Rp+1 → R est différentiable, alors la fonction ∇f défini par :


∂f
 On développe scr (f ) de la manière suivante :
∂a0 (a)
scr (f ) = (y − Xa)> (y − Xa)
 ∂f
 ∂a1 (a)

∇f (a) =  . 

 ..  = > >
y − (Xa) (y − Xa)

∂f
∂ap (a) = y> y − y> Xa − (Xa)> y + (Xa)> Xa
est appelé gradient de f .
= y> y − y> Xa − a> X> y + a> X> Xa
∇f est une fonction de Rp+1
dans Rp+1
et peut être vue comme un
champ de vecteurs (fonction qui associe à tout point un vecteur). On a donc la solution suivante :
Quelques formules de dérivations dans le cas multivarié. La dérivée est
calculée par rapport à la variable x. A est une matrice de réels de ∇scr (f ) = 0 ⇔ 2X> Xa − 2X> y = 0
taille (m × n) et y un vecteur de réels de taille (m × 1) : −1
⇔ âmco = X> X X> y
I Si f (x) = y> Ax ou si f (x) = x> A> y alors ∇f (x) = A> y.
I Si A est carrée et f (x) = x> Ax alors ∇f (x) = (A + A> )x.
I Si A est carrée symétrique et f (x) = x> Ax alors ∇f (x) = 2Ax.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 109 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 110 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression linéaire multiple et MCO (suite) Régression linéaire multiple et modèle gaussien
Une fois âmco estimé, on peut calculer les prédictions du modèle pour Nous réinterprétons la régression linéaire multiple dans un cadre
un quelconque x ∈ X : probabiliste. Nous avons le modèle suivant pour tout i = 1, . . . , n :
−1
> > >
ˆ
f (x) = x âmco = x X X X> y Yi = Xi> a + i
Pour calculer l’erreur de prédiction on regarde ce que prédit le modèle Nous faisons de plus l’hypothèse que le vecteur
estimé pour les données E données par les lignes de X : = (1 , . . . , n ) ∼ N (0, σ 2 In ) où In est la matrice identité d’ordre n.
−1
Autrement dit les i sont i.i.d. selon N (0, σ 2 ).

ŷ = Xâmco = X X> X X> y
On en déduit la relation suivante :
L’erreur de prédiction est donc donnée par :
n
X P(Y |X ; a, σ 2 ) ∼ N (X > a, σ 2 )
scr (fˆ) = (yi − ŷi )2
i=1
L’étude de la régression linéaire multiple dans un cadre probabiliste
nous permet d’introduire le principe d’inférence de maximum de
= ky − ŷk2
vraisemblance (MV) et des propriétés statistiques des estimateurs
où k.k est la norme euclidienne. associés.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 111 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 112 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression linéaire multiple et modèle gaussien (suite) Régression linéaire multiple et modèle gaussien (suite)
La vraisemblance (“likelihood”) est la probabilité d’observer Il est plus commode de maximiser, de manière équivalente, le
l’échantillon : logarithme de la vraisemblance :
n n
vr (a, σ 2 ) = P(Y1 , . . . , Yn |X1 , . . . , Xn ; a, σ 2 ) 2
Y
2
X
lvr (a, σ ) = log( P(Yi |Xi ; a, σ )) = log(P(Yi |Xi ; a, σ 2 ))
Les Yi sont supposés i.i.d. nous avons alors : i=1 i=1
n
Y Dans le modèle gaussien cela se réduit à :
vr (a, σ 2 ) = P(Yi |Xi ; a, σ 2 ) n > a 2
!!
X 1 Y1i − X
i=1
lvr (a, σ 2 ) = log √ exp − i
n
11

Yi − Xi> a
2 ! 2πσ 2 2 σ
Y i=1
= √ exp − n 1 Y − X > a 2
!
2πσ 2 2 σ √
i
X
i=1 i
= − log 2πσ 2 −
L’estimateur du MV est la valeur des paramètres qui maximise la 2 σ
i=1
probabilité d’observer l’échantillon. On résoud donc le problème : n
n n 1 X 2
n = − log(2π) − log(σ 2 ) − 2 Yi − Xi> a
Y 2 2 2σ
max P(Yi |Xi ; a, σ 2 ) i=1
(a,σ 2 )∈Rp+1 ×R
i=1 Nous avons la propriété suivante : max lvr (a, σ 2 ) ⇔ min scr (f )
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 113 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 114 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression linéaire multiple et modèle gaussien (suite) Régression linéaire multiple et modèle gaussien (suite)
Estimateur du MV : Variance de âmv :
n −1
> >
X
2 VY |X (amv |X) = VY |X X X X Y |X
amv = arg max log(P(Yi |Xi ; a, σ ))
a∈Rp+1 i=1
−1 −1
Prenons ici Y = (Y1 , . . . , Yn ). On a la solution analytique suivante : = X> X X> VY |X (Y |X) X X> X
−1 −1
amv = X> X X> Y = σ 2 X> X
Espérance de amv : Efficacité de l’estimateur du MV :
−1
EY |X (amv |X) = EY |X X> X X> Y |X Théorème. (Théorème de Gauss-Markov)
−1 Sous l’hypothèse que le vecteur des résidus = (1 , . . . , n ) vérifie
= X> X X> EY |X (Y |X) E () = 0 (espérance nulle) et V = σ 2 In (variance constante et
−1 >
−1 non-corrélation), l’estimateur du MV (ou MCO) amv = X> X X Y
= X> X X> Xa = a est, parmi les estimateurs linéaires (çàd fonctions linéaires des {Yi }) qui
L’estimateur du MV est donc sans biais. soient sans biais, celui de variance minimale.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 115 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 116 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régularisation des modèles de régression linéaire Régression ridge

L’estimateur du MV ou des MCO est de variance minimale parmi les Nous sommes toujours dans le même contexte que précédemment et
estimateurs linéaires sans biais. Néanmoins, la variance aboutit dans avons l’espace des hypothèses suivantP :
certains cas à des erreurs de prédiction fortes. Dans ce cas, on H = {f : Rp → R : f (X ) = a0 + pj=1 aj X j }
cherche des estimateurs de variance plus petite quite à avoir un
Soit a\0 le vecteur a1 , . . . , ap .
léger biais. On peut pour cela supprimer l’effet de certaines variables L’estimateur ridge noté âridge est défini de la manière suivante :
explicatives ce qui revient à leur attribuer un coefficient nul.   2 
Par ailleurs, dans le cas où p, le nombre de variables explicatives, est Xn Xp 
2
grand, l’interprétation des résultats obtenus par les MCO est parfois âridge = arg min  yi − (a0 + aj xij ) + λka\0 k`2
a∈Rp+1  
ardu. Ainsi, on pourra préférer un modèle estimé avec moins de i=1 j=1
variables explicatives afin de privilégier l’interprétation du Pp
R(a\0 ) = kak2`2 = j=1 aj2 est appelé fonction de pénalité.
phénomène sous-jacent aux données plutôt que la précision.
λ est un réel positif ou nul qui permet de contrôler l’amplitude des
On étudie ici des méthodes permettant de produire des estimateurs
valeurs {aj }pj=1 (càd la norme du vecteur a\0 ). On parle de
dont les valeurs sont d’amplitudes réduites. Notamment, on parle de
coefficient de pénalité ou de “shrinkage” (rétrécissement).
modèles parcimonieux lorsque des variables ont des coefficients nuls.
Plus λ est grand plus la valeur des coefficients se rapproche de 0 et
Dans ce qui suit nous verrons trois approches : la régression ridge, la
moins la variance de l’estimateur de a est grande.
régression lasso et la régression elasticnet.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 117 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 118 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression ridge (suite) Régression ridge (suite)

Une autre façon équivalente d’introduire la régression ridge est par le

Contrairement à la régression linéaire multiple classique où on ne
biais du problème d’optimisation contraint suivant :
normalise pas nécessairement les variables, ici il est nécessaire de
Pn Pp 2 réduire les variables explicatives avant de résoudre le problème
min Yi − (a0 + a X j)
i=1 j=1 j d’optimisation. En effet, si les variables sont dans des unités de
a∈Rp+1
P p 2 mesures non commensurables le terme de pénalité (càd la contrainte)
slc j=1 aj ≤τ
aura un impact non uniforme sur les X j .
On montre qu’il existe une bijection entre λ et τ ce qui rend En pratique, on centre également la matrice de données X à
équivalent les deux problèmes. laquelle on enlève au préalable la première colonne remplie de 1. On
Cette formulation permet d’exprimer explicitement la contrainte sur supposera donc par la suite que la matrice X est de taille (n × p) et
l’amplitude des coefficients : on voit effectivement qu’il s’agit de est centrée-réduite, ∀j = 1, . . . , p :
minimiser scr (f ) avec la contrainte que a\0 appartienne à une boule
n n
de Rp et de rayon τ . 1X 1X 2
xij = 0 et xij = 1
Géométriquement : si â\0,mco appartient à la boule alors âmco = âridge n n
i=1 i=1
sinon, on projette â\0,mco sur la boule (pour satisfaire la contrainte).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 119 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 120 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression ridge (suite) Régression ridge (suite)

On centre le vecteur y également et on suppose par la suite : L’écriture matricielle de la fonction objectif devient :
n
1 X n
> >
o
yi = 0 âridge = arg min (y − Xa) (y − Xa) + λa a
n a∈Rp
i=1
L’ordonnée à l’origine a0 n’intervient pas dans la fonction de pénalité On a la solution analytique suivante :
car ceci rendrait la fonction de prédiction dépendante d’une ordonnée −1
à l’origine que l’on trouverait pour Y . âridge = X> X + λIp X> y
On montre en fait que si X et y sont centrés, on peut séparer
l’estimation du modèle en deux étapes : Les prédictions sont alors données par :
1 On prend âridge,0 = y (moyenne empirique avant centrage).
2 On estime (a1 , . . . , ap ) en résolvant : ŷ = y 1 + Xâridge et fˆ(x) = y +x> âridge
  2  |{z} n |{z}

X n X p 
 âridge,0 âridge,0
2
âridge = arg min  yi − aj xij  + λkak
a∈Rp   i=1 j=1

 où x est un vecteur quelconque de taille (p × 1) et x est de terme
xj −xj
général : xj = σ̂xj .
où a = (a1 , . . . , ap ) ∈ Rp .
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 121 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 122 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression ridge (suite) Régression ridge (suite)

Espérance de aridge :
−1
EY |X (aridge |X) = a − λ X> X + λIp a Comment choisir la valeur de λ, le coefficient de pénalité ?
| {z } L’approche simple consiste à prendre une séquence de nombres S
biais
allant de 0 jusqu’à un nombre positif maximal, on remplace λ par
L’estimateur ridge de a n’est donc pas sans biais et de ce point de
chacune de ses valeurs, on teste itérativement ces différents modèles
vue il est moins bon que l’estimateur des MCO.
(en utilisant de la validation croisée) et on sélectionne à la fin la
Variance de aridge :
valeur de λ ayant donné le meilleur modèle selon un critère.
−1 −1
2 > > > Il existe en fait des algorithmes efficaces (utilisant la SVD)
VY |X (aridge |X) = σ X X + λIp X X X X + λIp
permettant de déterminer pour toute valeur λ les valeurs des
X> X + λIp et X> X ont mêmes vecteurs propres mais les valeurs différents coefficients âridge . On parle alors de chemin de
propres de X> X + λIp sont plus grandes que celles de X> X. régularisation (“regularization path” ou “solution path”).
On peut alors montrer que la variance de aridge est plus petite que
Ces algorithmes sont notamment implémentés dans la libraire glmnet.
celle de amco . De ce point de vue, on peut attendre de la régression
ridge qu’elle donne des prédictions meilleures que celles de la
régression linéaire classique sur des données non observées.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 123 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 124 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression lasso Régression lasso (suite)

Dans l’idée, la régression lasso est très proche de la régression ridge. La différence de norme dans la fonction de pénalité a en fait un
L’estimateur lasso noté âlasso est défini de la manière suivante : impact important. Il existe ainsi des différences fortes entre régression
  2  lasso et régression ridge :
n p
X X  Contrairement à la régression ridge, il n’y a pas de solution analytique
âlasso = arg min  yi − (a0 + aj xij )  + λka\0 k`1 car la valeur absolue rend le problème non différentiable.
a∈Rp+1  i=1 j=1

On a donc recours à des méthodes d’optimisation numérique ou à des
R(a\0 ) = ka\0 k`1 = pj=1 |aj | est une fonction de pénalité basée algorithmes spécifiques (“Least Angle Regression - Stagewise”
P
sur la norme `1 plutôt que la norme `2 comme c’est le cas pour la [Efron et al., 2004]).
régression ridge. Quand τ est relativement petit, la solution obtenue par la régression
Le problème précédent est aussi équivalent au problème lasso est parcimonieuse càd que certains coefficients estimés seront
d’optimisation contraint : nuls. La régression lasso peut ainsi être vue comme une méthode de
2 sélection de variables. Il s’agit d’un modèle davantage parcimonieux
Pn Pp
min Yi − (a0 + a X j) que les modèles précédents. Lasso : “Least Absolute Shrinkage and
i=1 j=1 j
a∈Rp+1 Selection Operator”.
P p
slc j=1 |aj | ≤ τ Quand τ ≥ kâmco k`1 alors âlasso = âmco .
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 125 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 126 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Comparaison ridge et lasso - domaines de recherche Régression lasso (suite)

En pratique, comme pour la régression ridge, on centre-réduit X et on
centre y. X étant centrée, on peut à nouveau de séparer en deux
3

l’inférence. On retrouve notamment dans ce cas âlasso,0 = y.

En prenant a = (a1 , . . . , ap ), l’estimateur lasso est donné par :

  2 
n p
a2

X 
0

X
âlasso = arg min  yi − aj xij  + λkak`1
a∈Rp 
−1


i=1 j=1
−2

Les prédictions sont calculées de la façon suivante :

−3

−4 −2 0 2 4
ŷ = y 1 + Xâlasso et fˆ(x) = y +x> âlasso
a1
|{z} n |{z}
âlasso,0 âlasso,0

En vert la frontière ridge : a12 + a22 = 2. où x est un objet quelconque et x est un vecteur de taille (p × 1) et
xj −xj
En orange la frontière lasso : |a1 | + |a2 | = 2. de terme général : xj = σ̂xj .

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 127 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 128 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression lasso (suite) Limites de la régression lasso

Comment choisir le coefficient de pénalité ?
On considère le problème équivalent suivant :
2
Pn Pp
minp i=1 Yi − j=1 aj X j Quand p > n (données de grande dimension), la méthode lasso ne
a∈R
Pp sélectionne que n variables (en raison de la nature même du modèle
j=1 |aj |
slc kâmco k`1 ≤τ d’optimisation sous-jacent).
Si plusieurs variables sont corrélées entre elles, la méthode lasso ne
où kâmco k`1 est une constante pré-calculée.
sélectionnera qu’une seule d’entre elles et ignorera les autres.
Une méthode consiste alors à faire varier τ de 0 à 1. On voit que
lorsque τ vaut 1 on a âlasso = âmco . Dans de nombreux cas classiques avec n > p, s’il y a de fortes
corrélations entre les variables explicatives, on trouve empiriquement
On peut alors procéder par validation croisée comme pour ridge.
que la méhode ridge donne de meilleures performances que la
Cependant, le problème n’ayant pas de solution analytique la
méthode lasso.
détermination du chemin de régularisation semble plus ardue.
Néanmoins, l’étude des propriétés du problème lasso a permis de
mettre en place des algorithmes efficaces
[Efron et al., 2004, Friedman et al., 2010].
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 129 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 130 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Mélange de ridge et de lasso La régression elasticnet

On se place dans le même contexte que pour ridge et lasso où X est L’estimateur elasticnet naı̈f (cf plus loin) est défini par
centrée-réduite et y est centrée. [Zou and Hastie, 2005] :
Pour surmonter les problèmes précédents, l’idée est de prendre un  2
X n X p
mélange de ridge et lasso. On obtient alors le problème suivant : ânen = arg min yi − aj xij 
 2 a∈Rp i=1 j=1
n p
+λ αkak`1 + (1 − α)kak2`2
X X
minp yi − aj xij  + λ1 kak`1 + λ2 kak2`2
a∈R
i=1 j=1 où R(a) = αkak`1 + (1 − α)kak2`2 est la fonction de pénalité de la
où λ1 et λ2 sont des paramètres de positifs ou nuls. régression elasticnet.
En posant α = λ1 /(λ1 + λ2 ) on peut montrer que le problème est Ce problème est équivalent au problème contraint suivant :
2
équivalent à : P
minp ni=1 Yi − pj=1 aj X j
P
2 a∈R
slc α pj=1 |aj | + (1 − α) pj=1 |aj |2 ≤ τ
 P P
Xn p
X
aj xij  + λ αkak`1 + (1 − α)kak2`2

minp yi −
a∈R Si α = 0 on a l’estimateur ridge et si α = 1 on a l’estimateur lasso.
i=1 j=1
Les cas nous intéressant sont donc ceux pour lesquels 0 < α < 1.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 131 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 132 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

La régression elasticnet (suite) La régression elasticnet

Lemme.
Ce lemme de [Zou and Hastie, 2005] montre que la solution de la
Soit X la matrice des variables explicatives de taille (n × p), et y le vecteur
régression elasticnet peut être obtenue par la solution de la régression
de la variable cible réelle de taille n. Soit (λ1 , λ2 ) ∈ R+ × R+ . Soient les
lasso avec des données augmentées !
données augmentées X∗ et y∗ de tailles respectives ((n + p) × p) et n + p :
Comme X∗ est de rang p, la solution elasticnet peut donc sélectionner
∗ 1 X ∗ y potentiellement p variables contrairement à la régression lasso.
X =√ √ et y =
1 + λ2 λ2 Ip 0 Ce lemme permet également de montrer que la méthode elasticnet
√ permet de faire de la sélection de variables comme la méthode lasso
Soit γ = λ1 / 1 + λ2 . Alors la fonction objectif de la régression eslaticnet et contrairement à la méthode ridge.
peut s’écrire de façon équivalente :
Dans le cas de grande dimension n << p, on observe souvent un
ky −∗
X∗ a∗ k2`2 + γka k`1∗ effet de groupes entre variables qui ont tendance à être linéairement
dépendantes. La régression elasticnet permet de tenir compte de cet
Soit â∗ le minimiseur de cette fonction on a alors : effet : les variables fortement corrélées ont tendance à avoir la même
valeur de coefficient dans ânen .
1
ânen = √ â∗
1 + λ2
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 133 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 134 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Effet de groupe de la régression elasticnet Ré-échelonnement de l’estimateur elasticnet naı̈f

Théorème. L’estimateur elasticnet vu jusqu’à présent est dit “naı̈f”.
Soient X et y les données du problème de régression où les variables En théorie, il permet de tenir compte des limites du lasso identifiées
explicatives sont supposées centées-réduites et la variable à expliquer précédemment.
centrée. Soit (λ1 , λ2 ) des paramètres non négatifs. Soit ânen (λ1 , λ2 ) la En pratique, il ne donne satisfaction que lorsqu’il est proche de
solution elasticnet naı̈ve. Supposons que ânen,i (λ1 , λ2 )ânen,j (λ1 , λ2 ) > 0 l’estimateur ridge ou de l’estimateur lasso.
alors : Ce comportement est en fait dû à un double effet de
rétrécissement qui porte atteinte au modèle (on a une faible
1 1
q
|ânen,i (λ1 , λ2 ) − ânen,j (λ1 , λ2 )| ≤ 2(1 − ρij ) diminution de la variance pour une forte augmentation du biais).
kyk`1 λ2
L’estimateur elasticnet âen retenu est alors un ré-échelonnement
où ρij = hxi , xj i est le coefficient de corrélation entre les X i et X j . de la solution précédente :
p
âen = (1 + λ2 )ânen = 1 + λ2 â∗
Ce théorème de [Zou and Hastie, 2005] permet de caractériser l’effet
de groupe d’elasticnet : l’écart entre les coefficients de deux variables En pratique, l’estimateur ré-échelonné âen donne de meilleurs
est borné supérieurement par une grandeur qui dépend de la résultats pour 0 < α < 1 et peut ainsi surpasser le lasso.
corrélation linéaire entre celles-ci. Pourquoi ce facteur (1 + λ2 ) ?
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 135 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 136 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Elasticnet vue comme stabilisation du lasso Régression logistique polytomique

On peut écrire la fonction objectif de l’estimateur lasso comme suit : Nous avons traité la régression par le modèle linéaire pénalisé.
Dans le cadre du problème de catégorisation, le modèle linéaire
âlasso = arg min a> (X> X)a − 2y> Xa + λ1 kak`1
a∈Rp (généralisé) adéquat est la régression logistique polytomique.
Nous rappelons ce modèle et présentons sa version pénalisée.
On montre que celle de l’estimateur elasticnet peut s’écrire :
> La régression logistique vise à modéliser la probabilité conditionnelle
> X X + λ2 Ip de chaque classe Cl étant donné le vecteur aléatoire X .
âen = arg min a a − 2y> Xa + λ1 kak`1
a∈R p 1 + λ2 Ce sont en fait le logarithme des odds-ratio qui sont modélisés par des
fonctions linéaires. On a q − 1 fonctions linéaires suivantes :
Les variables étant centrées-réduites, X> X = Σ̂ la matrice
variance-covariance empirique. On a par ailleurs : P(Y = C1 |X = x)
log = a10 + a>
1x
P(Y = Cq |X = x)
X> X + λ2 Ip
= γ Σ̂ + (1 − γ)Ip ..
1 + λ2 .
P(Y = Cq−1 |X = x)
en posant γ = 1/(1 + λ2 ). log = aq−10 + a>
q−1 x
Elasticnet peut donc être vu comme un lasso où la matrice de P(Y = Cq |X = x)
variance-covariance est rétrécie càd proche de la matrice identité. Cq au dénominateur est une classe de référence qui est arbitraire.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 137 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 138 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression logistique polytomique (suite) Régression logistique polytomique (suite)

Les membres de gauche sont des fonctions logit : Dans l’équation précédente, on voit que la classe Cq , prise comme
p référence, est traitée de manière particulière. Afin de rendre les classes
logit(p) = log( ), avec p ∈]0, 1[
1−p uniformes nous poserons plus particulièrement :
Chaque fonction logit compare une classe C1 , . . . , Cq−1 à une classe exp(ak0 + a>k x)
de référence Cq et est modélisée par une fonction affine. ∀k = 1, . . . , q : P(Y = Ck |X = x) = Pq >
l=1 exp(al0 + al x)
Le modèle spécifié précédemment conduit aux propriétés suivantes
∀k = 1, . . . , q − 1 : exp(ak0 +a> k x)
La fonction Pq > x) est appelée fonction softmax et nous
exp(ak0 + a> l=1 exp(al0 +a
k x)
l
dans ce cas ql=1 P(Y = Cl |X = x) = 1.
P
P(Y = Ck |X = x) = Pq−1 voyons que
1 + l=1 exp(al0 + a>
l x) L’appellation softmax vient du fait que s’il existe une classe Ck telle
1 que ak0 + a>
P(Y = Cq |X = x) = Pq−1 k x est largement supérieure aux autres classes Cl 6= Ck
1 + l=1 exp(al0 + a>
l x) alors, la fonction softmax retourne une valeur proche de 1. Ainsi la
fonction agit comme la “fonction max” excepté qu’elle est
Nous pouvons clairement vérifier que ql=1 P(Y = Cl |X = x) = 1.
P
différentiable. De plus, sous cette forme, la relation entre régression
Ici, l’ensemble des paramètre est P = {(al0 , al )}q−1
l=1 . logistique et réseaux de neurones est immédiate (cf plus loin).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 139 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 140 / 285
Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Régression logistique polytomique (suite) Régression logistique polytomique (suite)

Dans le cas multiclasse, nous représentons l’appartenance des objets
aux différentes classes par une matrice binaire Y de taille (n × q) et
de terme général : En remplaçant P(Y = Cl |xi ; al ) par la forme paramétrique introduite
précédemment, on a :

1 si xi ∈ Cl
yil =
0 sinon q X
n
exp(al0 + a>

l xi )
X
On modélise la probabilité par une distribution multinomiale. Sous lvr (P) = yil log Pq >
l’hypothèse i.i.d., la vraisemblance s’écrit alors comme suit : l=1 i=1 k=1 exp(ak0 + ak xi )

q Y
n
Y Nous pouvons utiliser l’algorithme de Newton-Raphson pour
vr (P) = P(Y = Cl |xi ; al )yil déterminer une solution approchée de l’estimateur du MV. Pour cela,
l=1 i=1 il faut déterminer le gradient de la lvr par rapport à al ainsi que la
La log-vraisemblance vaut alors : matrice hessienne. . .
q X
X n
lvr (P) = yil log(P(Y = Cl |xi ; al ))
l=1 i=1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 141 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 142 / 285

Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...) Apprentissage supervisé Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Pseudo-code de l’algorithme de Newton-Raphson Régression logistique pénalisée

Input : f ∈ C 2 , x0 Le principe de régularisation pour obtenir un modèle de faible

1 k ←0 variance et/ou parcimonieux a été également appliqué à d’autres
2 Tant que condition d’arrêt non satisfaite faire fonctions objectif que les MCO telle que la log-vraisemblance.
3 x(k+1) ← x(k) − ∇2 f (x(k) )−1 ∇f (x(k) ) En fait, le principe de pénalisation a été introduit en modélisation
4 k ←k +1 mathématique en 1963 par Tikhonov et en statistique en 1971 par
5 Fin Tant que Good et Gaskins.
6 Output : x(k) Dans le cas plus générale de la régression logistique polytomique,
notons l’ensemble des paramètres P = {(al0 , al ) ∈ Rp+1 }ql=1 nous
où la matrice D 2 f (x) est appelée matrice hessienne de f en x avec : obtenons le modèle pénalisé suivant :
 2 q
∂2f ∂2f

∂ f
X
∂x1 ∂x2 · · · (1 − α)kal k`1 + αkal k2`2

∂x1 ∂x1 ∂x1 ∂xn max lvr (P) − λ
 ∂2f 2f 2f {(a0 ,al )}l ∈R(p+1)q
 ∂x2 ∂x1 ∂x∂2 ∂x · · · ∂x∂2 ∂x

 l=1
2
∇ f = . 2 n
 . . Si α = 1 on retrouve une pénalisation `2 et le problème peut-être
 .. .. ··· .. 
∂2f ∂2f ∂2f estimé par l’algorithme de Newton-Raphson (le fonction objectif étant
∂xn ∂x1 ∂xn ∂x2 ··· ∂xn ∂xn différentiable 2 fois).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 143 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 144 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Rappel du Sommaire Introduction

Ce sont des modèles qui s’inspirent du fonctionnement du cerveau et

2 Apprentissage supervisé de travaux provenant des sciences cognitives et des neurosciences.
Définitions, notations et concepts importants Le cerveau peut être vu comme un système de traitement
Quelques méthodes simples en guise d’illustration d’informations qui possède des capacités extraordinaires dépassant
Différentes caractéristiques des méthodes d’apprentissage supervisé bien évidemment celles d’un ordinateur.
Concepts importants en apprentissage supervisé Le cerveau effectue par exemple des tâches de reconnaissance de
Evaluation et comparaison de modèles en apprentissage supervisé formes visuelles ou sonores, ou est capable d’apprendre à partir
(Quelques) Aspects théoriques en apprentissage automatique d’exemples ou d’un enseignant.
Les méthodes linéaires et leurs pénalisations (elasticnet ...)
Ces quelques tâches que nous venons de citer sont les problèmes que
Les réseaux de neurones artificiels (“Artificial Neural Networks”)
traite l’intelligence artificielle. Puisque le cerveau est capable de
Les machines à vecteurs supports (“Support Vector Machines”) résoudre ces tâches alors il est tentant de modéliser le fonctionnement
du cerveau, de le programmer et de demander à une machine de
reproduire les capacités du cerveau.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 145 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 146 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Introduction (suite) Schéma d’un neurone biologique

Le cerveau est à bien des égards différent d’un ordinateur ! Mais si Dendrites Neurofibrilles Synapse
Microtubules
l’on devait appréhender le cerveau comme un système de traitement Neurotransmetteur
Vésicules Synaptiques
Synapse (Axoaxonique)
d’informations, on voit qu’un ordinateur à un (ou quelques) Récepteur Fente synaptique
Terminaison axonique
RER
processeur alors que le cerveau est composé d’un très large nombre de (Corps de Nissl)

Polyribosomes
“processeurs” que sont les neurones (le cerveau humain en compte Nœud de Ranvier

Synapse
environ 1011 ). Ribosomes
Appareil de Golgi
(Axosomatique)

Toutefois, le neurone en tant qu’unité de traitement est plus “simple”

Gaine de myéline
qu’un processeur. Ce qui fait la particularité du cerveau est sa Axone
(Cellulle de Schwann)

Noyau
capacité à traiter de manière parallèle l’information. Ceci est Nucléole Noyau (de la
cellulle de Schwann)
Membrane
possible par la très grande connectivité entre neurones reliés entre eux Microtubule

par les synapses. Mitochondrie

REL
Les synapses sont les éléments du cerveux qui permettent la Microfilament
Microtubule
transmission (en parallèle) d’information entre neurones. On Synapses
Axone
(Axodendritiques)

compte en moyenne 10000 synapses par neurone.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 147 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 148 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Schéma d’un réseau de neurones artificiel (RN) Le perceptron

Couches cachées Le perceptron est l’élément de base d’un RN : il reçoit des données
en entrée provenant de signaux internes (d’autres perceptrons) ou
externes (données du problème) et donne en sortie un signal qui peut
Données 1ère 2ème 3ème
Sortie être communiqué en interne (à d’autres perceptrons) ou en externe
en entrée couche couche couche
(prédiction du perceptron).
Soit un vecteur (signal) x = x1 , . . . , xp appartenant à X ⊆ Rp qui

x1 io est le signal d’entrée transmis à un perceptron.
A chaque xij on lui associe un poids aj . On a ainsi un vecteur
io
a = a1 , . . . , ap que l’on appelle les coefficients synaptiques.
x2 io io g On a également une constante a0 que l’on appele le biais.
Le signal post-synaptique est défini de la façon suivante :
io
p
io
X
x3 s(x) = a0 + aj x j
i=1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 149 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 150 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron (suite) Le perceptron (suite)

Coeff. Le signal post-synaptique est ainsi une combinaison liénaire des
synaptiques données en entrée : s(x) = a> x.
x0 Le neurone qui reçoit ce signal le transforme par le biais d’une
fonction d’activation, h(s(x)) = o et qui peut prendre plusieurs
a0
x1 formes :
a1 I La fonction identité :
Données Données
en entrée io g en sortie h(s(x)) = h(i) = o = a> x
I Une fonction à seuil comme la fonction d’Heaviside :
1 si a> x > 0

ap h(s(x)) = o =
0 sinon
xp I La fonction sigmoı̈d (fonction inverse de logit) :
1

Dans la suite on notera x = 1, x1 , . . . , xp et a = a0 , a1 , . . . , ap si h(s(x)) = o =
bien que le signal post-synaptique s’écrit : 1 + exp(−a> x)
exp(a> x)
s(x) = i = a> x Rq : 1
1+exp(−a> x)
= 1+exp(a> x)
.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 151 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 152 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron (suite) Problème multiclasse : q perceptrons en parallèle

Nous voyons que le perceptron est une forme d’allégorie permettant
de retrouver les modèles linéaires vus précédemment : Données Données
I Le perceptron associé à la fonction d’activation identité revient à un en entrée en sortie
modèle linéaire pour le problème de régression.
I Le perceptron associé à des fonctions à seuil détermine des frontières x0
de décision linéaires (hyperplans) dans l’espace X ce qui est équivalent
à des modèles linéaires en catégorisation telle que l’Analye Factorielle io g1
Discriminante. x1
I Le perceptron associé à la fonction sigmoı̈d permet d’obtenir en sortie io g2
des valeurs normées entre 0 et 1 ce qui permet une interprétation en
termes de probabilité pour le problème de catégorisation binaire. On
1
remarquera dans ce cas que si P(C1 |X ) = 1+exp(−a > x) alors

exp(−a> x)
P(C2 |X ) = 1 − P(C1 |X ) = 1+exp(−a> x)
(rég. log. binomiale).
Un perceptron permet donc de modéliser le problème de régression et io gq
de catégorisation binaire. Dans ce dernier cas, quand est-il du xp
problème multiclasse ?
⇒ On utilise en parallèle q perceptrons.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 153 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 154 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Problème multiclasse : q perceptrons en parallèle q perceptrons en parallèle et régression logistique

Dans ce cas, nous avons q systèmes de coefficients synaptiques ce qui La régression logistique polytomique est équivalente à un RN avec q
nous conduit à définir la matrice A de taille ((p + 1) × q) dont les perceptrons en parallèle et des fonctions d’activation softmax :
colonnes al sont les coefficients synaptiques du lème perceptron.
exp(a>
k x)
Chaque perceptron reçoit un message post-synaptique défini par gk (x) = h(a>
k x) = Pq >
sl (x) = a> l=1 exp(al x)
l x et chaque perceptron est indépendant des autres.
Globalement, on obtient une fonction vectorielle s : X → Rq qui, Données Données
en entrée en sortie
étant donné un signal en entrée x, calcule les signaux
post-synaptiques de chaque perceptron l de la façon suivante : x0
io g1
s(x) = A> x avec sl (x) = a>
l x x1
Les neurones appliquent ensuite la fonction d’activation et on note : io g2

g(x) = h(A> x) (par abus de notations) avec : gl (x) = h(a>

l x)

La règle de décision est alors la suivante :

io gq
f (x) = Cl ⇔ ∀l 0 6= l : gl (x) ≥ gl 0 (x) xp
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 155 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 156 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Cas de la fonction booléenne “AND” Cas de la fonction booléenne “XOR”

Signal post-synaptique et fonction d’Heaviside : Signal post-synaptique et fonction d’Heaviside :
X1 X2 AND a 1 2 1 2
0 + a1 X + a2 X Q 0 X1 X2 XOR a
0 + a1 X + a2 X Q 0
1 1 1 a0 + a1 + a2 > 0 a0 + a1 + a2 ≤ 0
1 0 0

 1 1 0 

a0 + a1 ≤ 0 a0 + a1 > 0
 
0 1 0 1 0 1
 a0 + a2 ≤ 0 0 1 1  a0 + a2 > 0
0 0 0 

a0 ≤ 0


a0 ≤ 0
0 0 0
−1.5 + X 1 + X 2 = 0 Ensemble de contraintes incompatibles.
X2 X2
x0 1.5 x0
a0 = −1.5 a0 =?
a1 = 1 (0,1) (1,1) a1 =? (0,1) (1,1)
x1 io x1 io
a2 = 1 a2 =?
x2 x2
X1 X1
(0,0) (1,0) 1.5 (0,0) (1,0)
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 157 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 158 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche Le perceptron multicouche (suite)

Nous supposerons :
I p données en entrée plus un biais x0 .
Les modèles précédents définissent des modèles linéaires avec I Une 1ère couche de m perceptrons (la couche cachée).
certaines limites. I Une 2ème couche de q perceptrons (q = 1 dans le cas de la régression).
Le perceptron multicouche (“multilayer perceptron”) est une I La 1ère couche contient (p + 1) × m coefficients synaptiques.
généralisation de ces modèles : I La 2ème couche contient (m + 1) × q coefficients synaptiques.
I En régression il permet de traiter les cas non linéaires de régression. Les données en entrée x sont envoyées à chaque perceptron k de la
I En classification, il permet de déterminer des fonctions de décision non 1ère couche qui combine linéairement celles-ci en un signal
linéaires permettant de résoudre le problème “XOR” précédent par post-synaptique : sk (x) = a> k x.
exemple. Le perceptron k de la 1ère couche applique ensuite la fonction
Il consiste en l’ajout de couches de neurones dites cachées entre d’activation h1 : zk = h1 (sk (x)).
les données en entrée et les données en sortie. Les données z = (z1 , . . . , zm ) sont envoyées à chaque perceptron l de
Dans la suite nous supposerons qu’il y a une seule couche cachée mais la 2ème couche qui combine linéairement celles-ci : sl (z) = b> l z.
d’autres configurations sont possibles (deep learning notamment). Le perceptron l de la 2ème couche applique enfin la fonction
d’activation h2 pour obtenir les données en sortie : gl = h2 (sl (z)).
Remarque : h1 et h2 peuvent être différentes.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 159 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 160 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche (suite) Le perceptron multicouche (suite)

Perceptron avec une couche cachée et coefficients synaptiques : Fonction d’activation de la couche de sortie (deuxième couche) :
I Pour la régression on utilise un seul perceptron de sortie et la fonction
Biais z0 d’identité :

bl,0 h2 (sl (z)) = sl (z) = b>

l z

I Pour la catégorisation en q = 2 classes on utilise un seul perceptron de

Biais x0 io io
bl,1 sortie et la fonction sigmoı̈d :
ak,0 1
h2 (sl (z)) =
1 + exp(−b>
l z)
ak,1 bl,k
x1 io io
zk gl I Pour la catégorisation en q > 2 classes on utilise q perceptrons de
sortie et la fonction softmax :
Données exp(b>
l z)
en entrée h2 (sl (z)) = Pq
ak,p >
l=1 exp(bl z)
bl,m
Pour des problèmes de catégorisation, la variable en sortie gl peut
xp io io
être interprétée telle la probabilité d’appartenir à Cl .
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 161 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 162 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche (suite) Résolution du cas de la fonction booléenne “XOR”

Le perceptron à deux couches peut être vu comme un modèle Définition logique de l’opération binaire “XOR”
comportant une phase de projection non linéaire. La 1ère couche X 1 X 2 XOR
produit une projection de X de dimension p + 1 vers un nouvel espace 1 1 0
de dimension m + 1. La 2ème couche peut être vue comme q 1 0 1
perceptrons en parallèle mais prenant en entrée les données projetées 0 1 1
dans l’espace intermédiaire (et caché). 0 0 0
En statistique, des modèles similaires appelés “projection pursuit” Contraintes linéaires incompatibles (dans l’espace initial) :
ont également
PM été proposés [Hastie et al., 2011] : 
a0 ≤ 0
>

f (X ) = m=1 gm (am X ) où les gm et les am sont respectivement des

a0 + a1 + a2 ≤ 0

fonctions et vecteurs que l’on cherche à estimer. a + a1 > 0
 0

Le perceptron multicouche est un approximateur universel. Toute

a0 + a2 > 0
proposition logique peut être représentée par une disjonction de Ecriture sous la forme normale disjonctive :
conjonctions. Le perceptron à 2 couches peut approximer toute
X 1 XOR X 2 ⇔ (X 1 AND ¬X 2 ) OR (¬X 1 AND X 2 )
proposition logique : chaque conjonction est représentée par un
perceptron de la 1ère couche cachée et la disjonction est représentée Pour résoudre le problème avec un perceptron à 2 couches on prend
par la 2ème couche. m = 2 et h la fonction d’Heaviside.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 163 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 164 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Résolution du cas de la fonction booléenne “XOR” (suite) Le perceptron multicouche (suite)

g L’estimation d’un RN consiste à inférer l’ensemble des paramètres
io
P = {a1 , . . . , am , b1 , . . . , bq } :
-0.5 1 1 I ∀k = 1, . . . , m, ak est de taille (p + 1) × 1
z z
1 = z0 i o 1 i o 2 I ∀l = 1, . . . , q, bl est de taille (m + 1) × 1
Le vecteur z obtenu à l’issue de la 1ère couche est de terme général :
-0.5-0.51 -1 -1 1 zk = h1 (a>
k x ) = h1 (hak , xi)
|{z}
1 = x0 x1 x2 sk (x)

Le vecteur g obtenu à l’issue de la 2ème couche est de terme général :

X2 Z2 gl = h2 (b>
l z ) = h2 (hbl , zi)
−0.5 + Z 1 + Z 2 = 0
|{z}
sl (z)
(0,1) (1,1) (0,1) Ainsi la fonction de décision vectorielle g(x) donnée en sortie du
perceptron à 2 couches est de terme général :
X1 Z1 gl (x) = h2 (b>
(0,0) (1,0) (0,0) (1,0) l z) = h2 (h(bl,0 , . . . , bl,m ), (z0 , h1 (ha1 , xi), . . . , h1 (ham , xi))i)
| {z } | {z }
bl z
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 165 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 166 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche (suite) Le perceptron multicouche (suite)

La fonction objectif est de deux types selon le problème traité : Pour la recherche du minimiseur on utilise une descente de gradient.
I Pour la régression, on utilise la somme des carrés des résidus : En raison de la structure multi-niveaux du perceptron multicouche, on
n
X a une méthode particulière dite de rétro-propagation de l’erreur.
err (g ) = scr (g ) = (yi − g (xi ))2 où ∀i : yi ∈ R
i=1
| {z } Considérons erri l’erreur partielle relative ou locale à l’élément xi .
erri
L’erreur totale notée err vaut donc :
I Pour la catégorisation, on utilise la cross-entropie définie par :
n
q
n X
X
X err (g ) = erri
err (g) = ce(g) = −yil log(gl (xi ))
i=1
i=1 l=1
| {z }
erri Rappel : la descente de gradient consiste à chercher un minimiseur
où ∀i, l : yil = 1 si yi = Cl et yil = 0 sinon. de façon itérative en suivant à chaque étape la direction opposée du
Il s’agit de problèmes de minimisation non contraints mais non gradient de sorte à déterminer un point critique (CNPO).
convexe. Chercher un minimiseur pose parfois des problèmes de Dans ce qui suit nous étudions l’algorithme de rétro-propagation de
sur-apprentissage. Dans ce cas, on ajoute un terme de pénalité ou on l’erreur pour le perceptron multicouche avec une couche cachée tel
arrête la recherche du minimiseur prématurément. que décrit schématiquement au slide 161.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 167 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 168 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche (suite) Le perceptron multicouche (suite)

On définit les gradients relatifs à l’objet xi suivants :
    La rétro-propagation repose sur les règles de dérivation suivantes dites
∂ ∂
∂bl,0 erri ∂ak,0 erri “chaining rule” :
∇bl erri (P) = 
 .. 
 ; ∇a erri (P) = 
 .. 
. k .  q

∂
 
∂
 ∂erri ∂erri ∂gl ∂erri X ∂erri ∂gl ∂zk
∂bl,m erri ∂ak,p erri = et =
∂bl,k ∂gl ∂bl,k ∂ak,j ∂gl ∂zk ∂ak,j
l=1
Les formules itératives de descente de gradient sont données par :
n Intuitivement, pour savoir comment erri varie quand ak,j varie, on voit
(r +1) (r )
X
bl = bl − αr ∇bl erri d’abord comment zk varie quand ak,j varie ; puis comment gl varie
i=1 quand zk varie et enfin on voit comment erri varie quand gl varie.
n Inversement, en lisant la formule de la gauche vers la droite, elle
(r +1) (r )
X
ak = ak − αr ∇ak erri traduit d’une certaine façon, comment erri se propage dans le réseau
i=1 de la 2ème couche vers la 1ère d’où le terme de rétro-propagation.
où l’exposant (r ) indique l’itération r de l’algorithme. Comme les couches se succèdent, ces calculs de dérivées peuvent se
La structure multi-niveaux du perceptron multicouche permet un faire de la même façon d’une couche à une autre.
calcul efficace et local des gradients.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 169 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 170 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche (suite) Le perceptron multicouche : régression

Cas de la régression non linéaire :
Les étapes de l’algorithme de retro-propagation sont les suivantes et I Un seul neurone dans la 2ème couche càd q = 1
I Fonction objectif :
sont typiquement basées sur deux étapes dites “forward” et
n
“backward” qui s’alternent de façon itérative : X
err (g ) = (yi − g (xi ))2
1 On initialise aléatoirement des coefficients synaptiques ak et bl . i=1
| {z
erri
}
(r ) (r )
2 A l’itération r on utilise les valeurs courantes ak et bl et on calcule I Fonction d’activation de la 1ère couche, la fonction sigmoı̈d :
les prédictions g(r ) (x) (étape “forward”).
h1 (sk (xi )) = 1/(1 + exp(− a>
k xi )) = zk
3 On calcule les erreurs au niveau de la sortie et celles-ci sont |{z}
sk (xi )
rétro-propagées vers les perceptrons de la 2ème puis de la 1ère couche
(r +1) (r +1) I Remarque : on a la propriété suivante,
et on ajuste ainsi les coefficients bl et ak en utilisant la
descente de gradient (étape “backward”). ∂sigmoı̈d(x)
= sigmoı̈d(x)(1 − sigmoı̈d(x))
4 On itère 2 et 3 jusqu’à convergence ou jusqu’à la vérification d’un ∂x
critère d’arrêt. I Fonction d’activation de la 2ème couche, la fonction identité :
h2 (s(z)) = b> z = g
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 171 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 172 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche : régression (suite) Pseudo-code (batch) de rétro-propagation : régression

Input : E, αr
Erreur associée à l’objet Xi : 1 Initialiser ak,j et bk aléatoirement par des valeurs dans [−0.01, 0.01]
2 Tant que condition d’arrêt non satisfaite faire
erri = (yi − b> z)2 3 r ←1
4 Pour tout i = 1, . . . , n faire
Dérivées partielles par rapport à b (2ème couche) : 5 Pour tout k = 1, . . . , m faire
6 zk ← 1/(1 + exp(−a>k xi ))
∂erri 7 Fin Pour
= −2(yi − b> z) zk
∂bk | {z } |{z} 8 ŷi ← b> z
∂erri /∂g ∂g /∂bk 9 Fin Pour Pn
10 b(r +1) ← b(r ) − αr i=1 ∇b erri
Dérivées partielles par rapport à ak (1ère couche) : 11 Pour tout k = 1, . . . , m faire
(r +1) (r ) Pn
12 ak = ak − αr i=1 ∇ak erri
∂erri
= −2(yi − b> z) bk zk (1 − zk ) xij 13 Fin Pour
∂ak,j | {z } |{z} | {z } |{z} 14 r ←r +1
∂erri /∂g ∂g /∂zk ∂zk /∂sk ∂sk /∂ak,j
15 Fin Tant que
(r )
16 Output : b(r ) , {ak }m k=1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 173 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 174 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Pseudo-code (on-line) de rétro-propagation : régression Perceptron multicouche : régression (suite)

Input : E, αr
1 Initialiser ak,j et bk aléatoirement par des valeurs dans [−0.01, 0.01] Résultats (version on-line) avec m = 3 après 100, 200 et 400
2 Tant que condition d’arrêt non satisfaite faire itérations
3 L ← sample(n) (permutation aléatoire de 1, 2, . . . , n)
4 r ←1

1.0
5 Pour tout i ∈ L faire
6 Pour tout k = 1, . . . , m faire
zk ← 1/(1 + exp(−a>

0.5
7 k xi ))
8 Fin Pour
9 ŷi ← b> z

0.0
10 b(r +1) ← b(r ) − αr ∇b erri

y
11 Pour tout k = 1, . . . , m faire
(r +1) (r )
12 ak = ak − αr ∇ak erri
−0.5
13 Fin Pour
14 r ←r +1
−1.0

15 Fin Pour
16 Fin Tant que −2 −1 0 1 2 3
x
(r )
17 Output : b(r ) , {ak }m k=1
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 175 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 176 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche : catégorisation Le perceptron multicouche : catégorisation (suite)

Cas de la catégorisation non linéaire avec q classes : Rappelons le schéma d’un perceptron multicouche :
I q neurones dans la 2ème couche.
I Fonction objectif : Biais z0
q
n X
err (g) =
X
−yil log(gl (xi ))
bl,0
i=1 l=1 Biais x0 io io
I Fonction d’activation de la 1ère couche, la fonction sigmoı̈d : bl,1
ak,0
1
h1 (sk (x)) = = zk
1 + exp(−a>
k x) ak,1 bl,k
x1 io io
I Fonction d’activation de la 2ème couche, la fonction softmax : zk gl
exp(b>
l z)
h2 (sl (z)) = Pq > z)
= gl Données
l=1 exp(bl en entrée ak,p
I Remarque : on a aussi la propriété suivante, bl,m
∂softmax(x) xp io io
= softmax(x)(1 − softmax(x))
∂x
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 177 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 178 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche : catégorisation (suite) Le perceptron multicouche : catégorisation (suite)

Erreur associée à l’objet Xi : Rappelons que : zk = h1 (sk (x)) = sigmoı̈d(sk (x)) = 1
.
1+exp(−a>
k x)
q
exp(b>

l z) Dérivées partielles par rapport à ak (1ère couche) :
X
erri = −yil log Pq
l=1
( l=1 exp(b>
l z)) q q
∂erri X ∂erri X ∂gl 0 ∂sl 00 ∂zk ∂sk
Dérivées partielles par rapport à b (2ème couche) : =
∂ak,j 0
∂gl 0 00 ∂sl 00 ∂zk ∂sk ∂ak,i
q q l =1 l =1
∂erri X ∂erri ∂gl 0 X ∂erri ∂gl 0 ∂sl
= = On obtient le résultat suivant :
∂bl,k 0
∂gl 0 ∂bl,k 0
∂gl 0 ∂sl ∂bl,k
l =1 l =1
q q
!
En explicitant chaque calcul on obtient les résultats partiels suivants : ∂erri X X ∂erri ∂gl 0 ∂sl 00 ∂zk ∂sk
=
I ∂erri /∂gl 0 = −yil 0 /gl 0 ∂ak,j ∂gl 0 ∂sl 00 ∂zk ∂sk ∂ak,i
l 00 =1 l 0 =1
I ∂gl 0 /∂sl = gl 0 ind(l = l 0 ) − (gl gl 0 ) (ind étant la fonction indicatrice) | {z }
I ∂sl /∂bl,k = zk −(yil 00 −gl 00 )
Puis en regroupant le tout, on obtient finalement : q
X
∂erri = −(yil 00 − gl 00 ) bl 00 ,k zk (1 − zk ) xj
= −(yil − gl ) zk l 00 =1 P
| {z } |{z} | {z } |{z}
∂bl,k | {z } |{z} l 0 (∂erri /∂gl 0 )(∂gl 0 /∂sl 00 ) ∂sl 00 /∂zk ∂zk /∂sk ∂sk /∂ak,j
∂sl /∂bl,k
P
l 0 (∂erri /∂gl 0 )(∂gl 0 /sl )
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 179 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 180 / 285
Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”)

Le perceptron multicouche : catégorisation (suite) Le perceptron multicouche : catégorisation (suite)

Résultats (version on-line) avec m = 5 et q = 3 après 100 itérations. Résultats (version on-line) avec m = 5 et q = 3 après 100 itérations.

1.0

1.0
0.8

0.8
0.6

0.6
X^2

X^2
0.4

0.4
0.2

0.2
0.0

0.0
0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
X^1 X^1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 181 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 182 / 285

Apprentissage supervisé Les réseaux de neurones artificiels (“Artificial Neural Networks”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Le perceptron multicouche : catégorisation (suite) Rappel du Sommaire

Résultats (version on-line) avec m = 5 et q = 3 après 100 itérations.

2 Apprentissage supervisé
2.0

Définitions, notations et concepts importants

Quelques méthodes simples en guise d’illustration
1.5

Différentes caractéristiques des méthodes d’apprentissage supervisé

1.0

Concepts importants en apprentissage supervisé

Evaluation et comparaison de modèles en apprentissage supervisé
X^2
0.5

(Quelques) Aspects théoriques en apprentissage automatique

0.0

Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Les réseaux de neurones artificiels (“Artificial Neural Networks”)
−0.5

Les machines à vecteurs supports (“Support Vector Machines”)

−1.0

−1.0 −0.5 0.0 0.5 1.0 1.5 2.0

X^1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 183 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 184 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Introduction Hyperplans de séparation entre deux classes

C’est une famille de méthodes “récentes” proposée initialement dans On suppose un problème avec deux catégories C1 et C2 .
[Vapnik, 1995] dans les années 90. Il existe une infinité d’hyperplans permettant de séparer deux nuages
Nous étudierons dans un premier temps l’application de cette de points linéairement séparable.
méthode pour le problème de catégorisation puis nous verrons
comment elle permet également de traiter les problèmes de régression.
C’est une méthode discriminante mais qui estime directement la

1.0
frontière de décision entre deux catégories (ce qui est distinct des

0.8
fonctions discriminantes et de la modélisation probabiliste P(Y |X )).
Cette frontière peut-être définie par des objets de E et non

0.6
X^2
nécessairement par les variables A.

0.4
La méthode repose sur la matrice de Gram càd la matrice des
produits scalaires entre objets de E (et non nécessairement sur la

0.2
représentation vectorielle).

0.0
La méthode cherche à résoudre un problème d’optimisation convexe
0.0 0.2 0.4 0.6 0.8 1.0
et il existe donc une solution unique. X^1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 185 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 186 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Hyperplans de séparation optimale entre deux classes Optimisation de la marge

X2
Dans le cas des svm, on cherche la frontière linéaire représentée par {x ∈ R2 : a0 + a> x = 0}
a0 ∈ R et a ∈ Rp telle que :
C1
a0 + a> x ≥ δ

pour tout x ∈ C1 x
>
a0 + a x ≤ −δ pour tout x ∈ C2 C2
|a0 +a> x|
a kak
avec δ ≥ 0. x0
Contrairement aux fonctions discriminantes où on regardait a0 X1
0 − kak
uniquement le signe par rapport à la frontière (g (x) ≶ 0), on veut
aussi une distance δ par rapport à la frontière.
On appelle la marge, la distance entre la frontière et les objets x les Dans Rp , le vecteur normal de la frontière est a.
plus proches de celle-ci. La distance (signée) entre la frontière et l’origine est −a0 /kak.
L’apprentissage consiste alors à déterminer l’hyperplan permettant de Soit x0 un point de la frontière, la distance entre x et la frontière est :
maximiser la marge (on traduit parfois svm par “Séparateur à Vaste |a> (x − x0 )| |a> x + a0 |
Marge”) afin d’obtenir une meilleure généralisation. =
kak kak
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 187 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 188 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Optimisation de la marge (suite) Exemple

On a alors le problème suivant :
max δ
a0 ,a∈Rp
> x +a )
slc ∀i, yi (a kak
i 0
≥δ
où yi = 1 si xi ∈ C1 et yi = −1 si xi ∈ C2 .
Dans les contraintes, on peut écrire de façon équivalente :
1
yi (a> xi + a0 ) ≥ δkak kak

Puis sans perte de généralité on peut poser :

1 1
δ= kak
kak
Le problème devient alors :
min 1 kak2
a0 ,a∈Rp 2
slc ∀i, yi (a> xi + a0 ) ≥1
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 189 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 190 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Problème quadratique contraint Lagrangien et problème dual

Reprenons le problème primal suivant :

La marge δ = 1/kak donc 2/kak est l’épaisseur de la bande (ou tube).
min p 12 kak2
Il n’y a uniquement que quelques points (ceux marqués d’une croix a0 ,a∈R
dans l’exemple précédent) qui participent à la définition de la slc ∀i, yi (a> xi + a0 ) ≥ 1
frontière (cf plus loin).
Le Lagrangien (primal) est noté lagp (a0 , a, α) où α est le vecteur
Pour maximiser la marge cela revient donc à minimiser la norme
de taille (n × 1) des multiplicateurs de Lagrange. Il est défini par :
euclidienne au carré du vecteur normal a de la frontière. Il s’agit d’un
problème quadratique avec des contraintes d’inégalités linéaires n
1 X
(de type ≥). Il s’agit donc d’un problème convexe que l’on peut lagp (a0 , a, α) = kak2 − αi yi (a> xi + a0 ) − 1
2
résoudre en utilisant des solvers où en appliquant des méthodes i=1
d’optimisation numériques dédiées à ce problème.
Le Lagrangien doit être minimisé selon a0 et a et maximiser par
Toutefois, on peut reformuler de façon équivalente ce problème en rapport à α = (α1 , . . . , αn ).
écrivant le Lagrangien associé et en formant ainsi le dual.
Par conséquent les CNPO impliquent que la solution se trouve en un
point selle.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 191 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 192 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Lagrangien et problème dual (suite) Lagrangien et problème dual (suite)

Le problème étant convexe, il est équivalent de résoudre le dual qui Le problème dual est alors le suivant :
consiste à maximiser le Lagrangien lagd par rapport à α sous les
maxn ni=1 αi − 12 ni=1 nj=1 αi αj yi yj x>
P P P
contraintes que les gradients de lagp par rapport à a0 et a soient nuls : i xj
α∈R
(
∂lagp Pn slc ∀i,
Pnαi ≥ 0
= 0
∂a0
∂lagp ⇔ Pαni yi
i=1 = 0
i=1 αi yi = 0
= 0 a − i=1 i i i = 0
α y x
∂a
En plus de la contrainte sur les multiplicateurs de Lagrange, la
On obtient les relations suivantes ni=1 αi yi = 0 et a = ni=1 αi yi xi
P P
solution optimale du dual doit également satisfaire les conditions
En intégrant ces relations au sein du Lagrangien lagp on obtient : complémentaires de Karush-Kuhn-Tucker (KKT) suivantes :
n
1 2
X
>

lagp (a0 , a, α) = kak − αi yi (a xi + a0 ) − 1 ∀i, αi yi (a> xi + a0 ) − 1 = 0
2
i=1
= ... Ces conditions s’interprètent de la façon suivante :
n n n
X 1 XX I Si αi > 0 alors la contrainte est saturée càd yi (a> xi + a0 ) = 1 et xi se
= αi − αi αj yi yj x>
i xj situe sur une frontière de la bande.
2
i=1 i=1 j=1 I Si yi (a> xi + a0 ) > 1 alors αi = 0 et dans ce cas xi se situe hors de la
| {z }
lagd (α) bande.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 193 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 194 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Interprétation du svm Interprétation du svm (suite)

Rappelons que nous avons âsvm = ni=1 α̂i yi xi .
P

De plus, seuls les xi sur les frontières de la bande sont tels que
α̂i > 0. On les appelle les vecteurs supports.
En d’autres termes, âsvm est défini comme une combinaison linéaire
des vecteurs supports. 1
Les objets xi tel que α̂i = 0 sont des points hors de la bande et ne kak

sont pas intéressants pour définir la frontière entre les deux classes
(ils sont relativement loins de la frontière).
On obtient âsvm,0 à l’ade de l’équation suivante pour n’importe quel
vecteur support (càd tel que αi > 0) :
âsvm,0 = yi − â>
svm xi

La fonction de décision fˆ(x) dépend de ĝ (x) = â>

svm x + âsvm,0 :

C1 si ĝ (x) > 0
fˆ(x)
C2 sinon
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 195 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 196 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Le cas non linéairement séparable Le cas non linéairement séparable (suite)

Nous avons traité précédemment le cas linéairement séparable.
Si dans l’espace de description initial X, les classes se recouvrent ∀i, yi (a> xi + a0 ) ≥ 1 − ξi
alors elles ne sont pas linéairement séparables et le problème
d’optimisation n’a pas de solution.
En effet, il est alors impossible de satisfaire toutes les contraintes : Nous remarquerons les cas particuliers suivants :
I Si ξi = 0 alors il n’y a pas de problème de catégorisation avec xi .
> Si 0 < ξi < 1 alors xi est du bon côté de la frontière mais se situe dans
∀i, yi (a xi + a0 ) ≥ 1 I

la bande.
On cherche alors un hyperplan qui continue à maximiser la marge I Si ξi ≥ 1 alors xi est catégorisée de façon incorrecte.
mais tout en faisant le moins d’erreur possible. |{xi ∈ E : ξi > 1}| est le nb de vecteurs incorrectement classifiés.
Pour ce faire, on intègre des variables d’écart ξi ≥ 0 qui permettent |{xi ∈ E : ξi > 0}| est le nb de vecteurs non linéairement séparables.
des erreurs : On définit alors le “soft error” également appelé “hinge loss” :
∀i, yi (a> xi + a0 ) ≥ 1 − ξi
X X
ξi = max(0, 1 − yi g (xi ))
On parle alors de “soft margin” ou de méthodes discriminantes i i

flexibles. Celui-ci est ajouté dans la fonction objectif comme terme de pénalité.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 197 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 198 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Hyperplan flexible de séparation optimale Lagrangien et problème dual

Nous avons le problème suivant : On doit minimiser le Lagrangien par rapport à a0 , a, ξ et le maximiser
1 2+c
Pn
min kak i=1 ξi par rapport à α et µ.
a0 ,a∈Rp ,ξ∈Rn 2
slc ∀i, yi (a> xi + a0 ) ≥ 1 − ξi Comme précédemment, on peut de façon équivalente maximiser le
∀i, ξi ≥ 0 Lagrangien par rapport à α et µ sous les contraintes que les gradients
de lagp par rapport aux variables primales soient nuls :
où c est une constante positive tel un coefficient de pénalité,
permettant de contrôler l’équilibre entre la maximisation de la marge
 ∂lag  Pn
p
 ∂a0 = 0

Pαni yi
i=1 = 0
et les erreurs. Nous remarquerons que pour un cas linéairement

∂lagp
∂a = 0 ⇔ a − i=1 αi yi xi = 0
séparable les ξi sont nuls et donc “c = ∞”.  ∂lagp = 0 c1 − α − µ = 0
 
Le Lagrangien (primal) est alors donné par : ∂ξ

lagp (a0 , a, ξ, α, µ) où 1 est le vecteur de taille (n × 1) rempli de 1.

On obtient les relations suivantes ni=1 αi yi = 0, a = ni=1 αi yi xi et
P P
=
∀i, αi = c − µi .
Pn Pn
1 2 yi (a> xi + a0 ) − (1 − ξi ) − ni=1 µi ξi
P
2 kak +c i=1 ξi − i=1 αi

où α ∈ R+n et µ ∈ R+n sont les multiplicateurs de Lagrange. Comme ∀i, µi ≥ 0, la dernière condition implique que ∀i, 0 ≤ αi ≤ c.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 199 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 200 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Lagrangien et problème dual (suite) Lagrangien et problème dual (suite)

Après simplification, on obtient le problème dual suivant : Le vecteur normal de la frontière étant :
n
maxn ni=1 αi − 12 ni=1 nj=1 αi αj yi yj x>
P P P
i xj
X
α∈R âsvm = α̂i yi xi
slc ∀i,
Pn0 ≤ αi ≤ c i=1
i=1 αi yi = 0 Nous avons les interprétations suivantes :
Nous obtenons la solution α̂ et le vecteur normal de la frontière de 1 Si α̂i > 0 alors xi participe à la définition de âsvm .
décision âsvm ∈ X, est tel que : 2 Si µ̂i > 0 alors 0 ≤ α̂i < c (car αi = c − µi ).
n Par ailleurs, comme µ̂i ξˆi = 0 (KKT), alors
µ̂i > 0 ⇒ ξˆi = 0 ⇒ α̂i yi (â>

svm xi + âsvm,0 ) − 1 = 0.
X
âsvm = α̂i yi xi
Si de plus α̂i > 0, alors xi est sur une frontière de la bande puisque
i=1
(KKT) yi (â>svm xi + âsvm,0 ) = 1.
Les conditions complémentaires de KKT suivantes permettent par ˆ
3 Si ξi > 0 alors (KKT) µ̂i = 0 et dans ce cas α̂i = c > 0.
ailleurs de caractériser également la solution optimale obtenue vis à Par ailleurs, yi (â> ˆ
svm xi + âsvm,0 ) = 1 − ξi < 1 et en fonction de la valeur
vis du primal : de ξi nous avons : si 0 < ξi < 1 alors xi est dans l’intérieur de la bande

∀i, αi yi (a> xi + a0 ) − (1 − ξi ) = 0
et du bon côté ; si 1 < ξi ≤ 2 alors xi est dans l’intérieur de la bande
mais du mauvais côté et si 2 < ξi alors alors xi est à l’extérieur de la
∀i, µi ξi = 0
bande et du mauvais côté.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 201 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 202 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Lagrangien et problème dual (suite) Choix du paramètre c

On obtient âsvm,0 à l’aide de l’équation suivante pour n’importe quel On remarquera la similitude entre la fonction objectif du svm et les
vecteur support (càd tel que 0 < α̂i < c) : modèles pénalisés précédents :
n
âsvm,0 = yi − â> 1 X
svm xi min kak2 +c ξi
a0 ,a∈Rp ,ξ∈Rn 2 |{z}
i=1
La fonction de décision fˆ(x) dépend alors de la fonction pénalité | {z }
perte
ĝ (x) = â>
svm x + âsvm,0 :
Le svm nécessite également le “tuning” du paramètre c qui arbitre
C1 si ĝ (x) > 0 entre la fonction de perte et la fonction de pénalité.
fˆ(x) =
C2 sinon c peut être sélectionné par validation croisée comme indiquer en slide
124 (mais en utilisant le taux d’erreur comme critère).
Le problème dual est plus simple à résoudre que le problème primal.
Il existe aussi des travaux pour déterminer le chemin de
Le problème dual permet de faire dépendre la compléxité du
régularisation d’un svm, càd le calcul de âsvm (c) pour c ∈ [0, ∞].
problème en fonction de n plutôt qu’en fonction de p !
Dans [Hastie et al., 2004], les auteurs montrent que âsvm (c) est
Les svm peuvent ainsi traiter les problèmes de grande dimension linéaire par morceaux (comme le lasso). Leur algorithme est inspiré de
(n << p) plus efficacement que les modèles linéaires précédents ! lars.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 203 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 204 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Expansions de base et noyaux Expansions de base et noyaux

La solution du dual est donnée par :
Si le problème n’est pas linéairement séparable, nous pouvons
n
appliquer une expansion de base de X dans un espace étendu F :. X
âsvm = α̂i yi φ(xi )
φ:X→F i=1
où âsvm ∈ F.
Dans ce cas un modèle linéaire dans F correspond à un modèle non Par ailleurs :
linéaire dans X. Donc au lieu de manipuler les vecteurs x ∈ X, on
âsvm,0 = yi − â>
svm xi
manipule des vecteurs φ(x) ∈ F.
Les développements précédents sont les mêmes pour obtenir le où xi est un vecteur support càd tel que 0 < α̂i .
problème dual suivant : La fonction de score ou de discrimination du svm est donnée par :
ĝ (x) = â>
svm φ(x) + âsvm,0
max ni=1 αi − 12 ni=1 nj=1 αi αj yi yj φ(xi )> φ(xj )
P P P
α∈F
La fonction de décision reste :
slc ∀i,
Pn0 ≤ αi ≤ c
C1 si ĝ (x) > 0
i=1 αi yi = 0 ˆ
f (x) =
C2 sinon
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 205 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 206 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Expansions de base et noyaux Expansions de base et noyaux

Le problème d’optimisation dual s’écrit donc :
Regardons de plus prés la fonction de score du svm :
max ni=1 αi − 12 ni=1 nj=1 αi αj yi yj K (xi , xj )
P P P
α∈F
ĝ (x) = â>
svm φ(x) + âsvm,0 slc ∀i,
n
Pn0 ≤ αi ≤ c
X i=1 αi yi = 0
= α̂i yi φ(xi )> φ(x) + âsvm,0
i=1
La fonction de score obtenue également :
| {z } n
â>
X
svm ĝ (x) = α̂i yi K (xi , x) + âsvm,0
i=1
En utilisant le dual, les éléments importants dans le cadre du svm
peuvent s’exprimer en termes de produit scalaires dans l’espace La fonction K (., .) est appelée noyau (“kernel”) et les méthodes qui
étendu F : φ(xi )> φ(x). remplacent le produit scalaire dans X par un produit scalaire dans un
espace issu d’une expansion de base F sont dites méthodes à
Posons alors K : X × X → R tel que :
noyaux (“kernel methods” ou “kernel machines”).
K (xi , x) = φ(xi )> φ(x) L’intérêt de ces fonctions est qu’elles ne nécessitent pas de
représenter explicitement x dans F (càd on ne calcule jamais φ(x) -
“kernel trick”).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 207 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 208 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Les noyaux Les noyaux (suite)

K (x, y) représente un produit scalaire et doit satisfaire plusieurs types Soit dans X = R2 deux vecteurs x = (x1 , x2 ) et y = (y1 , y2 ).
de contraintes. Exemple classique de noyau :
Notons K la matrice carrée de taille (n × n) de produits scalaires dont
K (x, y) = (hx, yi + 1)2
le terme général est tel que :
= (x1 y1 + x2 y2 + 1)2
kij = K (xi , xj ) = (x1 y1 )2 + (x2 y2 )2 + 1 + 2x1 y1 x2 y2 + 2x1 y1 + 2x2 y2
= φ(xi )> φ(xj )
Ce noyau correspond à l’expansion de base φ suivante :
= hφ(xi ), φ(xj )i
√ √ √
φ(x) = (x12 , x22 , 1, 2x1 x2 , 2x1 , 2x2 )
On appelle une matrice de produits scalaires une matrice de Gram.
La matrice K doit alors satisfaire les propriétés suivantes : On vérifie bien en effet que : K (x, y) = φ(x)> φ(y).
I Symétrie : ∀i, j, kij = kji . En utilisant K , la complexité de calcul reste en O(dim(X)) plutôt que
I Semi-définie positivité : ∀z ∈ Rn , z> Kz ≥ 0.
O(dim(F)) !

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 209 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 210 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Les noyaux (suite) Les noyaux (suite)

Il existe plusieurs familles de noyaux : Les noyaux permettent donc de travailler implicitement dans un
espace F qui peut être de très grande dimension.
Les noyaux polynomiaux de degré d (“Polynomial kernels”) :
En projetant les données dans F, on espère pouvoir rendre le problème
K (x, y) = (hx, yi + 1)d davantage linéairement séparable que dans X. Ceci permettrait
d’utiliser le concept d’optimisation de la marge dans un espace plus
Ces noyaux sont relatifs à une expansion de base reposant sur des adéquat afin d’avoir de meilleures performances.
polynômes de degré d des composantes initiales. Le cas d = 1 est Dans l’espace F on obtient donc uneP frontière linéaire qui s’exprime à
appelé noyau linéaire (produit scalaire dans l’espace initial X). l’aide de vecteurs supports : ĝ (x) = ni=1 α̂i yi K (xi , x) + âsvm,0 .
Les fonctions à bases radiales (“Radial basis functions” (RBF)) : En revanche, dans l’espace initial X on obtient une frontière de
décision non linéaire.
kx − yk2

Pour un noyau polynomial, plus le paramètre d est petit, plus la
K (x, y) = exp −
2σ 2 frontière dans X que l’on obtient est lisse (“smooth”).
Pour un noyau RBF, plus le paramètre σ 2 est grand, plus la frontière
Ces noyaux reposent sur la notion de voisinage (hypersphère de centre dans X que l’on obtient est lisse.
x et de rayon σ 2 ).
Les paramètres des noyaux peuvent être estimés par validation croisée.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 211 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 212 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Exemple (suite) Exemple (suite)

Avec un noyau polynomial K (x, y) = (hx, yi + 1)2 (d = 2). Avec un noyau polynomial K (x, y) = (hx, yi + 1)10 (d = 10)
SVM classification plot SVM classification plot
oo oo
o o
o o
o x o o
o o
oo o o oo o o
0.8 o o 0.8 o o
o o

1
o oo o o o oo o o
o o
o o o o
o o x o
o o o o o o
o o o o o o o
o
o o o o o o o o
o o x o o o
0.6 0.6
o x o x
o o x o o x
o o
X2

X2
oo o o oo o o
o x o o x o
o o o o o o o o
x o x x
o o o o o o
o o o o x o o o
o o o o o o o o
0.4 o o o 0.4 o o o
oo o oo o
o o o o
x o o o o o
o o o o

−1

−1
o o o o
oo o o oo o oo o o oo o
o o o o
0.2 o o 0.2 o o
o o o o
o o o o
o o
o o
0.2 0.4 0.6 0.8 0.2 0.4 0.6 0.8
X1 X1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 213 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 214 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Exemple (suite) Exemple (suite)

2
2

Avec un noyau RBF K (x, y) = exp − kx−yk
0.5 (σ 2 = 0.25) Avec un noyau RBF K (x, y) = exp − kx−yk
2 (σ 2 = 1)

SVM classification plot SVM classification plot

xo oo
x o
x o
o o o o
o o
xo o o oo o o
0.8 o o 0.8 o o
o o
1

1
x oo o o o oo o o
o o
o o o o
x x x o
x o o o o o
o o o o o o o
o
o oo o o oo o
o o x o o x
0.6 0.6
o x o o
o o x o o x
o o
X2

X2
oo o o oo o o
o x o o x o
o o o o o o o o
x x x o
x o o o o o
x o o o x o o o
o o o x o o o o
0.4 o o o 0.4 o o o
oo o oo o
o o o o
x o o x o o
o o o o
−1

−1
o o o o
oo o o oo x oo o o oo o
o o o o
0.2 x o 0.2 o o
x x o x
o o o o
o o
x o
0.2 0.4 0.6 0.8 0.2 0.4 0.6 0.8
X1 X1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 215 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 216 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Les svm appliqués au problème de régression Fonction de perte

Nous supposons maintenant que Y = R. En comparaison des méthodes précécentes, les svm cherchent à
Les idées de marge, de variables d’écarts, de noyaux. . . peuvent être minimiser la fonction de perte suivante :
généralisées pour le problème de régression.

0 si |y − f (x)| <
Supposons d’abord un noyau linéaire. Nous avons alors la famille l (f (x), y ) =
|y − f (x)| − sinon
d’hypothèses H qui est l’ensemble des fonctions de type : = max(0, |y − f (x)| − ) (“hinge” ou “-insensitive loss”)
f (x) = a0 + a> x où > 0 est un paramètre relatif à une marge d’erreur.
Rappelons que la régression linéaire et le problème des MCO sont : On peut interpréter l de la façon suivante :
I On tolère des erreurs d’ajustement jusqu’à une quantité .
n
X I Au delà de le poids d’une erreur est linéaire et non quadratique.
min (yi − (a0 + a> x))2 I l est plus robuste vis à vis du bruit.
a0 ,a∈Rp
i=1
Les svm pour la régression combinent l (f (x), y ) et la fonction de
Par ailleurs, la régression ridge ajoute au scr une fonction de pénalité : pénalité quadratique :
X n 2 n
yi − (a0 + a> x) + λkak2
X
min p min p c l (f (xi ), yi ) + kak2
a0 ,a∈R a0 ,a∈R
i=1 i=1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 217 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 218 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Fonction de perte (suite) Fonction de perte (suite)

Sortir de l’intervalle de tolérance de taille > 0 se produit quand :
I a0 + a> xi > yi + : le modèle prédit une valeur trop forte.
a0 + a> xi < yi − : le modèle prédit une valeur trop faible.
50

On introduit des variables d’écarts pour formaliser ces “sorties” du

tube. Soient ∀i, ξi+ ≥ 0 et ξi− ≥ 0, les “sorties” possibles sont alors :
Poids de l'erreur dans la fonction de perte

perte quadratique (scr)

perte avec tolérance de epsilon (l_epsilon)

(a0 + a> xi ) − yi > + ξi+

yi − (a0 + a> xi ) > + ξi−

On voit que |yi − (a0 + a> xi )| ≤ ⇔ ξi+ = ξi− = 0.

Minimiser les variables d’écart est équivalent à minimiser l .

Le problème peut donc se reformuler de façon équivalente comme :
10

1 2
Pn + −
min 2 kak + c i=1 (ξi + ξi )
a0 ,a∈Rp ,ξ+ ,ξ− ∈Rn
slc ∀i, (a0 + a> xi ) − yi ≤ + ξi+
0

−6 −4 −2 0
y−f(x) (résidu)
2 4 6
∀i, yi − (a0 + a> xi ) ≤ + ξi−
∀i, ξi+ , ξi− ≥ 0
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 219 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 220 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Lagrangien et problème dual Lagrangien et problème dual (suite)

Le Lagrangien (primal) dépend des variables primales a0 , a, ξ + , ξ − et En injectant les relations précédentes dans la fonction objectif, on
des multiplicateurs de Lagrange α+ , α− , µ+ , µ− qui sont des obtient le problème dual suivant :
vecteurs de Rn . Il est donné par :
max − 12 ni=1 nj=1 (αi− − αi+ )(αj− − αj+ )x>
P P
Pn + − i xj
lagp = 21 kak 2
P ++ c i=1 (ξ>i + ξi )
+ −
α ,α ∈R n

− i=1 (αi− + αi+ ) + ni=1 (αi− − αi+ )yi

Pn
+ Pi αi (a0 + a xi ) − yi − − ξi+
P
+
+ Pi αi− yi − (a0 + a > −
xi ) − − ξi
slc ∀i, 0 ≤ αi ≤ c
+ + − − −
− i µi ξi + µ i ξi ∀i,
Pn0 ≤ α+i ≤ c−
A l’optimum, les gradients de lagp par rapport aux variables primales i=1 (αi − αi ) = 0
sont nuls : Une fois résolu ce problème quadratique contraint, on obtient la

∂lagp fonction de prédiction suivante qui dépend donc de vecteurs supports :
= 0  Pn + −
P(α i − αi ) = 0


 ∂a0  i=1
 ∂lagp = 0
  n − +
a − i=1 (αi − αi )xi = 0 fˆ(x) = â0 + â> x

∂a
∂lagp ⇔

 ∂ξ+ = 0 
 c1 − α+ − µ+ = 0 n
− −
X
∂lag c1 − α − µ = 0 (α̂i− − α̂i+ )x>
 

 −
p
= 0 = âsvm,0 + i x
∂ξ
i=1
où 1 est le vecteur de taille (n × 1) rempli de 1
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 221 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 222 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Lagrangien et problème dual (suite) Exemple

Les relations αi± = c − µ± i , ∀i et les conditions complémentaires de
Avec un noyau linéaire
KKT nous permettent de voir que :
Résultats quand epsilon vaut 0.2
1 Si αi+ = αi− = 0 alors µ+ − +
i = µi = c et donc (KKT) ξi = ξi = 0.
−

1.0
+ − >
Par ailleurs si αi = αi = 0 alors (KKT) + yi − (a0 + a xi ) > 0 et
− yi + (a0 + a> xi ) > 0. xi est donc dans le tube. MCO

2 Si α̂i+ > 0 ou (exclusif) α̂i− > 0, on a alors deux sous-cas :

SVM lin

0.5
SVM lin + eps
a Si α̂i+ 6= c ou α̂i− 6= c alors resp. µ+ −
i > 0 ou µi > 0 et donc (KKT) SVM lin − eps
ξi+ = 0 ou ξi− = 0. xi est donc sur une frontière du tube.

0.0
b Si α̂i+ = c ou α̂i− = c alors resp. µ+ −
i = 0 ou µi = 0 et donc (KKT)

y
ξi+ > 0 ou ξi− > 0. xi est donc à l’extérieur du tube.
Pour la régression, ce sont les points sur ou à l’exterieur du tube −0.5
qui sont des vecteurs supports.
Les points xi sur la frontière (0 < α̂i+ < c ou 0 < α̂i− < c) permettent
−1.0

de calculer âsvm,0 puisque dans ce cas, nous avons (KKT) :

−2 −1 0 1 2 3
+ yi − (âsvm,0 + â> >
svm xi ) = 0 ou − yi + (âsvm,0 + âsvm xi ) = 0 x

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 223 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 224 / 285
Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”)

Les noyaux Exemple (suite)

Comme pour la catégorisation, le problème dual et la fonction de Avec différents types de noyaux et = 0.2.
discrimination s’expriment par le biais de produits scalaires.
Résultats quand epsilon vaut 0.2
Nous pouvons donc étendre l’approche à des noyaux conduisant alors

1.0
à des modèles non linéaires dans X.
Formellement, les svm appliquées au problème de régression MCO

SVM lin

0.5
consistent à résoudre le problème suivant :
SVM pol 2
max − 12 ni=1 nj=1 (αi− − αi+ )(αj− − αj+ )K (xi , xj )
P P
SVM rbf 2
α+ ,α− ∈Rn
− ni=1 (αi− + αi+ ) + ni=1 (αi− − αi+ )yi

0.0
P P

y
slc ∀i, 0 ≤ αi+ ≤ c
−
∀i,
Pn0 ≤ α+i ≤ c−

−0.5
i=1 (αi − αi ) = 0
La fonction de prédiction est alors :

−1.0
X n
ˆ
f (x) = âsvm,0 + (α̂i− − α̂i+ )K (xi , x) −2 −1 0 1 2 3
x
i=1
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 225 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 226 / 285

Apprentissage supervisé Les machines à vecteurs supports (“Support Vector Machines”) Apprentissage non-supervisé

Exemple (suite) Rappel du Sommaire

Avec différents types de noyaux et = 0.1 (moins de tolérance).
Résultats quand epsilon vaut 0.1
1.0

1 Introduction : Apprentissage Automatique (AA)

MCO

SVM lin
0.5

SVM pol 2 2 Apprentissage supervisé

SVM rbf 2
0.0

3 Apprentissage non-supervisé
y
−0.5
−1.0

−2 −1 0 1 2 3
x

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 227 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 228 / 285
Apprentissage non-supervisé Définitions et notations Apprentissage non-supervisé Définitions et notations

Rappel du Sommaire Rappel

Apprentissage automatique :
ISupervisé : on dispose d’un ensemble d’objets et pour chaque objet
3 Apprentissage non-supervisé une valeur cible associée ; il faut apprendre un modèle capable de
prédire la bonne valeur cible d’un objet nouveau.
Définitions et notations
B Non-supervisé : on dispose d’un ensemble d’objets sans aucune valeur
Méthodes à noyaux en apprentissage non-supervisé cible associée ; il faut apprendre un modèle capable d’extraire les
L’ACP à noyaux régularités présentes au sein des objets pour mieux visualiser ou
Les k-means à noyaux appréhender la structure de l’ensemble des données.
Le spectral clustering Une façon “probabiliste” de présenter la différence entre supervisé et
non supervisé est la suivante :
I En supervisé on est intéressé par modéliser P(Y |X ) (discriminatif) ou
P(X , Y ) (génératif).
I En non-supervisé on est plutôt intéressé par modéliser P(X ) en
identifiant notamment les régions denses de X.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 229 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 230 / 285

Apprentissage non-supervisé Définitions et notations Apprentissage non-supervisé Définitions et notations

Deux problèmes classiques Deux solutions classiques

Nous allons considérer deux problèmes classiques en apprentissage Nous allons considérer deux solutions classiques à ces deux
non-supervisé : problèmes :
I Recherche d’espaces latents : Y’a t-il dans X (l’espace de I Recherche d’espaces latents : l’Analyse en Composantes Principales.
description), des sous-espaces où la densité d’objets est plus importante I Classification automatique : la méthode des k-means.
que d’autres ? Comment déterminer et caractériser ces régions ?
I Classification automatique (clustering) : Peut-on déterminer des Les distances/métriques utilisées sont euclidiennes.
groupes homogènes d’objets tels qu’ils soient plus similaires entre eux Hypothèses implicites :
qu’avec les autres. Comment caractériser et déterminer ces groupes ? I ACP : les données appatiennent à des espaces linéaires et non courbés.
L’un ou l’autre des problèmes permet d’appréhender P(X ).
I k-means : les groupes sont représentés dans l’espace par des ellipsoı̈des.

Les notions de similarités/distances entre objets et de B Ces méthodes présentent donc des limites si les données appatiennent
corrélations/association entre variables sont fondamentales pour à des espaces courbés. C’est le cas des données rencontrées en
modéliser le concept de régularité. multimedia, en bio-informatique. . .

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 231 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 232 / 285
Apprentissage non-supervisé Définitions et notations Apprentissage non-supervisé Méthodes à noyaux en apprentissage non-supervisé

Illustration Rappel du Sommaire

Non linear data

1.0

3 Apprentissage non-supervisé
0.5

Définitions et notations
Méthodes à noyaux en apprentissage non-supervisé
0.0
X^2

L’ACP à noyaux
Les k-means à noyaux
−0.5

Le spectral clustering
−1.0

−1.0 −0.5 0.0 0.5 1.0

X^1

Que donnerait l’ACP ici ?

Comment se positionneraient les barycentres des deux classes ?
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 233 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 234 / 285

Apprentissage non-supervisé Méthodes à noyaux en apprentissage non-supervisé Apprentissage non-supervisé L’ACP à noyaux

Introduction Rappel du Sommaire

Les noyaux permettent de projetter implicitement les objects dans des

espaces de grande dimension.
Cette projection peut être vue comme une expansion de base reposant
3 Apprentissage non-supervisé
sur des transformations non-linéaires des variables initiales.
Définitions et notations
Nous avons vu que les noyaux permettaient de traiter plus Méthodes à noyaux en apprentissage non-supervisé
efficacement certains problèmes (les cas non linéairement séparables) L’ACP à noyaux
en apprentissage supervisé. Les k-means à noyaux
Mais de façon plus générale, ils permettent d’étendre plusieurs Le spectral clustering
méthodes classiques et notamment en apprentissage non-supervisé.
Nous voyons ci-après l’application de ces concepts dans le cadre :
I des méthodes de réduction de dimension : l’ACP à noyaux
[Schölkopf et al., 1998],
I des méthodes de clustering : les k-means à noyaux et de façon plus
générale le spectral clustering.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 235 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 236 / 285
Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Rappel des objectifs de l’ACP Données traitées par l’ACP et notations

L’ACP traite des tables de données dont les variables sont

L’ACP est une méthode de réduction de dimension : quantitatives continues.
I Représentation d’un nuage de points décrit initialement dans un espace
Ces données se retrouvent dans la matrice T de taille (n × p) :
euclidien de grande dimension, dans un sous-espace de faible dimension.
I Ce sous-espace de faible dimension doit préserver au maximum
t1 ... tk ... tp
l’information contenue dans l’espace initial.  .. 
I Le concept d’information en ACP est formalisé par la variance ou t1 .
inertie du nuage de points. ..  .. 
.  . 
I La projection sur le sous-espace de faible dimension doit “déformer” le  
moins possible le nuage.
T = ti  ... . . . tik ... ...
..  ..


I La résolution du problème d’optimisation sous-jacent conduit à une .  . 
solution explicite qui est la décomposition spectrale de la matrice des ..
tn .
corrélations (ACP normée).
Dans la suite, nous introduisons brièvement les notations et rappelons On suppose n objets {t1 , . . . , ti , . . . , tn } où ti ∈ Rp .
les résultats de l’ACP normé. On suppose p variables {t1 , . . . , tk , . . . , tp } où tk ∈ Rn .
où ∀i = 1, . . . , n; ∀k = 1, . . . , p : tik ∈ R.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 237 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 238 / 285

Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Proximité et nuage des variables Proximité et nuage des variables (suite)

√
L’ensemble des vecteurs {t1 , . . . , tn } de Rp forme le nuage NO. On centre et on réduit la variable tk puis on divise par n et on
L’ensemble des vecteurs {t1 , . . . , tp } de Rn forme le nuage NA. obtient la variable xk dont le terme général est donné par :
Pour mesurer la liaison entre deux variables k et l on utilise le tik − mk
xik = √
coefficient de corrélation noté r (tk , tl ). sk n
Etant donné une variable tk , on introduit au préalable : On s’intéresse aux relations de “proximité” entre variables et on
k
I sa moyenne empirique notée mk (ie t ) : utilise ici le coefficient de corrélation (empirique) donné par :
n n
1X k l
X tik − mk til − ml
mk = tik r (t , t ) = √ √
n sk n sl n
i=1 i=1 | {z }| {z }
xik xil
I sa variance empirique notée sk2 :
n Remarques sur le coefficient de corrélation :
1X r (tk , tl ) est le produitP scalaire entre les vecteurs xk et xl :
sk2 = (tik − mk )2 I
n
n k l k l
r (t , t ) = hx , x i = i=1 xik xil .
i=1
I ∀k : r (tk , tk ) = hxk , xk i = kxk k2 = 1, donc tous les vecteurs xk sont de
Le vecteur m = (m1 , . . . , mp ) est appelé barycentre de NO. norme unitaire et ils appartiennent tous à une hypersphère.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 239 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 240 / 285
Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Transformation des données et ACP normée Transformation des données et ACP normée (suite)
Dans la suite, les vecteurs représentants les individus seront donc
notés xi et les vecteurs représentants les variables seront notés xk .
Nous supposons désormais que la matrice des données est celle des
√ Les propriétés de X sont alors les suivantes, ∀k = 1, . . . , p :
variables centrées, réduites et divisée par n.
n n
Nous noterons X cette matrice : X
xik = 0 et
X
(xik )2 = 1
i=1 i=1
x1 xk ... ... xp
 .. 
Remarques :
x1 .
..  ..  I m le barycentre de NO calculé dans le repère affine initial devient
.  . 
 l’origine du nouveau repère. L’opération de centrage agit telle une
X = xi  . . . . . . xik
 ... ... translation de NO de l’origine initiale au barycentre.
..  ..

 I Il est intéressant de noter que le centrage ne change pas les distances
.  . 
.. euclidiennes entre objets.
x n . I Après réduction les variables appartiennent à une hypersphère.
I En pratique, la réduction permet aux variables de s’affranchir de leurs
unités de mesure ce qui rend l’analyse plus robuste face aux biais
associés aux différences d’échelles. On parle d’ACP normée.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 241 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 242 / 285

Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Variance ou inertie du nuage des objets Variance ou inertie du nuage des individus

La notion de variance de nuage de points est centrale puisque c’est la

quantité que nous cherchons à préserver. Du fait du centrage, le barycentre devient l’origine du nouveau repère.
On montre que dans ce nouveau repère affine :
Dans le repère initial A, NO a une inertie totale définie par :
n n
n n n 1X 2 1X
1 XX 2 1X 2 intA (NO) = d (xi , 0) = kxi k2
intA (NO) = 2 d (xi , xj ) = d (xi , x) n n
2n n i=1 i=1
i=1 j=1 i=1
Pp Donc dans l’espace affine de Rp dont l’origine est le barycentre,
où d 2 (x, y) = kx − yk2 = j=1 (xj − yj )2 est la dist. eucl. au carré. l’inertie est la moyenne pondérée des normes des vecteurs des
L’information contenue dans NO est mesurée par l’inertie qui indique, individus.
en moyenne, de combien s’éloignent les points du barycentre. B L’objectif est de déterminer des sous-espaces de sorte à ce que la
Si l’inertie est faible alors les points sont en moyenne très proche du projection des xi dans ceux-ci conservent au mieux l’inertie.
barycentre ce qui est peu informatif. Si l’inertie est grande, c’est donc Autrement dit, on souhaite que l’image de NO dans ce sous-espace
qu’il y a bcp de disparités entre les objets. Le but alors est soit le moins déformé possible.
d’appréhender cette information de façon synthétique.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 243 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 244 / 285
Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Ajustement du nuage des individus Détermination des axes factoriels (ou principaux)

Pour déterminer en pratique ces sous-espaces, on cherche une suite On montre que les vecteurs u1 , . . . , us peuvent être obtenus en
de s directions privilégiées (s < p) dans Rp notées u1 , u2 , . . . , us diagonalisant la matrice des coefficients de corrélation que l’on
qui permettent de maximiser l’inertie du nuage projeté. notera par C et qui est de taille (p × p).
Ce sont en fait s vecteurs de Rp appelés axes factoriels (ou En utilisant la matrice de données centrées-réduites X, on a :
principaux) qui ont les propriétés suivantes :
I u1 est le sous-espace de dimension 1 qui maximise l’inertie du nuage C = X> X
projeté.
I u2 est orthogonal à u1 et le plan engendré par {u1 , u2 } est l’espace de où X> est la transposée de X
dimension 2 qui maximise l’inertie du nuage projeté. De façon explicite, nous avons le terme général de C, ∀k, l :
I u3 est orthogonal à u1 et u2 et le sous-espace engendré par {u1 , u2 , u3 }
est l’espace de dimension 3 qui maximise l’inertie du nuage projeté. n
X
I ... Ckl = xik xil (cf slide 240)
Les vecteurs u1 , u2 , . . . , us sont donc orthogonaux entre eux et i=1

permettent de maximiser l’inertie des points images lorsque l’on B Pour tout m = 1, . . . , s, um est le vecteur propre associé à λm la
projette le nuage NO. m-ème plus grande valeur propre de C.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 245 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 246 / 285

Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Extension à des noyaux Extension à des noyaux (suite)

Supposons maintenant qu’au lieu de représenter les objets dans X, Supposons également que les φ(xi ) sont des vecteurs dont les
√
l’espace euclidien initial engendré par les variables A, nous les variables ont été centrées et réduites et divisée par n pour toute
représentions dans un espace de Hilbert de plus grande dimension F dimension k de F (comme dans le slide 241) :
que l’on peut atteindre par l’application φ : X → F.
n n
Pour ne pas alourdir les notations notons X la matrice des
X X
[φ(xi )]k = 0 et [φ(xi )]2k = 1
composantes des vecteurs φ(xi ) dans F : i=1 i=1

1 k ... ... ... On peut exprimer X comme une collection de n vecteurs lignes et
 ..  dans ce cas, C, la matrice des coefficients de corrélations (dans F),
φ(x1 ) .
..  ..  peut être reformulée comme suit :
. 
 . 

φ(x1 )>
 
X = φ(xi )  . . . . . . [φ(xi )]k
 ... ... n
.. ..

C = X> X = φ(x1 ) . . . φ(xn )  ...  =
 X
φ(xi )φ(xi )>
  
.  . 
..
φ(x ) n . φ(xn )> i=1

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 247 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 248 / 285
Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Extension à des noyaux (suite) Extension à des noyaux (suite)

Les axes factoriels u1 , . . . , us (s < dim(F)) sont des vecteurs propres

L’ACP comme toute méthode de réduction de dimensions linéaire
de C et donc, ∀m = 1, . . . , s :
pratiquée en analyse de données reposent sur la SVD (“Singular Value
Cum = λm um Decomposition”) de la matrice de données X.
Les propriétés de la SVD permettent de mettre en lumière le principe
Par ailleurs, u1 , . . . , us ∈ F et sont des combinaisons linéaires des de dualité en ACP. Notons K = XX> . Soit λm la m-ème plus grande
φ(xi ). Il existe donc ∀m, αm = (α1m , . . . , αnm ) tel que : valeur propre de K et αm le vecteur propre associé, on a :
n > m
X XX
| {z } α = λm α
m
⇒ X> XX> αm = λm X> αm
um = αim φ(xi )
K
i=1
Autrement dit :
Autrement dit : um ∈ Vec{φ(x1 ), . . . , φ(xn )}.
I les valeurs propres non-nulles de X> X sont identiques à celles de XX> .
Cependant, l’application φ envoie x ∈ X dans un espace F de très I les vecteurs propres de X> X peuvent être obtenues à partir de ceux de
grande dimension voire de dimension infinie. Il est donc plus complexe XX> : um = X> αm .
voire impossible de diagonaliser C.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 249 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 250 / 285

Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Extension à des noyaux (suite) Composantes principales

L’ACP à noyaux consiste donc à diagonaliser K = XX> qui est la Ces axes étant des vecteurs de F ils sont de très grande dimension. Or
matrice de Gram des objets représentés dans F. ce qui nous intéresse plus particulièrement ce sont les coordonnées
Nous pouvons comme pour les svm utiliser à nouveau le “kernel des objets sur ces axes appelées composantes principales.
trick” afin d’obtenir K par l’utilisation d’une fonction noyau K (cf Soit f m ∈ Rn les composantes principales des objets sur l’axe um .
slide 211) sans avoir à représenter explicement les φ(xi ) dans F ! Ces coordonnées peuvent être déterminées à l’aide de la matrice K !
Comme pour les svm, le problème initial Cum = λm um est dans F On a en effet, ∀i = 1, . . . , n :
alors que le “problème dual”, Kαm = λm αm , est dans Rn (peu n
X n
X
m
importe F). On voit donc que cette approche permet aussi de traiter fi = hφ(xi ), um i = hφ(xi ), αjm φ(xj )i = αjm hφ(xi ), φ(xj )i
les données en grande dimension. j=1 j=1
Une fois K diagonalisée et les vecteurs propres αm associées aux plus n
X
grandes valeurs propres obtenues, on peut déterminer les axes = αjm kij
pincipaux um , m = 1, . . . , s, suivant la relation précédente : j=1

n
X Il n’est donc jamais nécessaire d’avoir à représenter les objets et les
> m
um = X α = αim φ(xi ) axes principaux dans F. Tous les calculs peuvent être effectués à
i=1 partir de la matrice à noyaux K !
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 251 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 252 / 285
Apprentissage non-supervisé L’ACP à noyaux Apprentissage non-supervisé L’ACP à noyaux

Pseudo-code de l’ACP à noyaux Illustration

1 Input : X (données initiales), K (fonction noyau), s (nb d’axes) Non linear data Gaussian−PCA

1.0
2 Calculer la matrice K de terme général kij = K (xi , xj )

2
3 Résoudre Kα = λα (décomposition spectrale).

0.5

1
4 Pour tout m = 1, . . . , s faire

0.0
X^2

X^2
Normaliser αm de sorte que λm hαm , αm i = 1

0
5
6 Pour tout i = 1, . . . ,P
n faire (composantes principales)

−0.5

−1
7 Calculer fi m = nj=1 αjm kij

−2
−1.0
8 Fin Pour −1.0 −0.5 0.0 0.5 1.0 −10.0 −9.5 −9.0 −8.5 −8.0

9 Fin Pour X^1 X^1

13 Ouput : {f 1 , . . . f s }
Résultats de l’ACP avec un noyau RBF avec σ 2 = 2.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 253 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 254 / 285

Apprentissage non-supervisé Les k-means à noyaux Apprentissage non-supervisé Les k-means à noyaux

Rappel du Sommaire Rappel des objectifs des k-means

Les k-means est une méthode de partitionnement qui sépare O en k

classes disjointes.
Notons P(O) = {C1 , . . . , Ck } une partition de O en k classes.
3 Apprentissage non-supervisé On suppose que les objets sont représentés dans un espace euclidien.
Définitions et notations
Les k-means minimisent la somme des carrés des résidus 2 suivantes :
Méthodes à noyaux en apprentissage non-supervisé
L’ACP à noyaux k X
X
Les k-means à noyaux scr (P(O)) = kxi − ml k2
Le spectral clustering l=1 xi ∈Cl

1 P
où ml = |Cl | xi ∈Cl xi est le barycentre de Cl .
Remarques :
I ml est le représentant ou prototype de la classe Cl .
I scr (P(O)) peut être interprétée comme suit : mesure de la perte
d’information si on devait représenter chaque objet par son prototype.
2. Equivalent ici à l’inertie inter-classe.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 255 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 256 / 285
Apprentissage non-supervisé Les k-means à noyaux Apprentissage non-supervisé Les k-means à noyaux

Rappel de l’algorithme des k-means Extension à des noyaux

Le problème est combinatoire (NP-hard).
Supposons maintenant qu’au lieu de représenter les objets dans X,
On utilise une heuristique qui détermine un optimum local.
nous les représentions dans un espace de Hilbert de plus grande
La complexité de l’heuristique est en O(knp).
dimension F que l’on peut atteindre par l’application φ : X → F.
1 Input : X and k Dans F, les k-means minimisent :
2 Initialize P(O) with k different clusters
3 While a stopping criterion is not reached do k
X X
4 For all xi ∈ O do scr (P(O)) = kφ(xi ) − ml k2
5 For all Cl ∈ P(O) do l=1 φ(xi )∈Cl
6 Compute kxi − ml k2
7 End For où ml = 1 P
φ(xi ) est le barycentre de Cl dans F.
|Cl | φ(xi )∈Cl
8 Find Cl ∗ = arg minCl ∈P(O) kxi − ml k2
9 Move xi from its current cluster to Cl ∗ Si on développe la distance euclidienne, il vient :
10 Update the mean vectors accordingly
11 End For kφ(xi ) − ml k2 = hφ(xi ) − ml , φ(xi ) − ml i
12 End While = hφ(xi ), φ(xi )i + hml , ml i − 2hφ(xi ), ml i
13 Ouput : P(O)

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 257 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 258 / 285

Apprentissage non-supervisé Les k-means à noyaux Apprentissage non-supervisé Les k-means à noyaux

Extension à des noyaux (suite) Pseudo-code des k-means à noyaux

Ensuite en considérant ml = |C1l | φ(xi )∈Cl φ(xi ) et en utilisant les
P
propriétés de linéarités du produit scalaire, on a : 1 Input : K and k
1 X X 2 Initialize P(O) with k different clusters
kφ(xi ) − ml k2 =hφ(xi ), φ(xi )i + hφ(xi ), φ(xj )i
|Cl |2 3 While a stopping criterion is not reached do
xi ∈Cl xj ∈Cl
4 For all xi ∈ O do
1 X 5 For all Cl ∈ P(O) do
−2 hφ(xi ), φ(xj )i
|Cl | 6 Compute d 2 (φ(xi ), ml )
xj ∈Cl
7 End For
B Soit K la matrice de Gram avec kij = hφ(xi ), φ(xj )i, alors :
8 Find Cl ∗ = arg minCl ∈P(O) d 2 (φ(xi ), ml )
9 Move xi from its current cluster to Cl ∗
1 X X 1 X
kφ(xi ) − ml k2 = kii + kij − 2 kij 10 End For
|Cl |2 |Cl |
i:xi ∈Cl j:xj ∈Cl j:xj ∈Cl 11 End While
On peut donc calculer les distances euclidiennes en utilisant 12 Ouput : P(O)
uniquement la matrice de Gram K (complexité en n) et non pas la
matrice de données X (complexité en dim(F)).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 259 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 260 / 285
Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Rappel du Sommaire Introduction

Ce sont des méthodes de clustering développées depuis les années
2000.
Ces approches permettent de tenir compte de la géométrie intrinsèque
3 Apprentissage non-supervisé des données (espaces courbées).
Définitions et notations Les notions de graphes de similarités et de voisinage et de
Méthodes à noyaux en apprentissage non-supervisé matrice laplacienne somt importantes.
L’ACP à noyaux Du point de vue méthodologique, le spectral clustering fait usage de
Les k-means à noyaux la décomposition spectrale afin de représenter les données dans un
Le spectral clustering espace euclidien. Il utilise ensuite les k-means afin d’obtenir une
partition des données.
Le spectral clustering englobe d’une certaine façon les méthodes
non-supervisées vues précédemment.
On montre qu’il possède de nombreux liens avec d’autres méthodes
de partitionnement de graphe, ce qui explique également les bons
résultats obtenus par cette famille de méthodes.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 261 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 262 / 285

Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Graphe de similarités Représentation matricielle

Définition. (Matrice d’adjacence)

La modélisation employée est celle de graphe non-orienté pondéré.
Soit G = (V, E) un graphe non-orienté d’ordre n. La matrice
Définition. (Graphe non-orienté pondéré) d’adjacence de G est une matrice carrée binaire d’ordre n notée A. Son
terme général est défini comme suit :
Un graphe non-orienté G est défini par la donnée de deux ensembles :

I V = {v1 , . . . , vn } dont les éléments sont appelés sommets (ou noeuds). 1 si (vi , vj ) ∈ E
|V| = n est le nb de sommets. On dit alors que G est d’ordre n.
aij =
0 sinon
I E = {e1 , . . . , em } dont les éléments sont des paires non-orientées de
sommets que l’on appelle arêtes. |E| = m désigne le nombre d’arêtes. Si G est pondéré nous noterons plutôt par W sa matrice d’adjacence et
dans ce cas, nous avons :
G = (V, E) est pondéré s’il existe une fonction f : E → R donnant une wij = f (vi , vj )
valuation à toute arête de E.
G étant non-orienté, sa matrice d’adjacence est symétrique.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 263 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 264 / 285
Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Exemple de matrice d’adjacence Degré des sommets et matrice des degrés

e2 Si le graphe est pondéré selon

v2 v3 Dans ce qui suit, nous supposons que G est non-orienté et pondéré.
les valuations suivantes :
e4 Nous définissant le degré du sommet vi par :
e1 e2 e3 e4 e5
n
e1 e3 f (ej ) 2 3 1 5 6 X
v4 di = wij
On obtient alors la matrice j=1

v1 v5 d’adjacence pondérée suivante : Pn

e5 Remarque : comme W est symmétrique on a aussi di = j=1 wji .
v1 v2 v3 v4 v5 La matrice des degrés est une matrice carrée diagonale d’ordre n
v1 v2 v3 v4 v5   notée D de terme général :
  v1 0 2 0 0 6
v1 0 1 0 0 1
v2 
2 0 3 0 0
v2 
1 0 1 0 0  di si i = j
 W = v3 
0 3 0 5 1 Dij =
A = v3 
0 1 0 1 1  0 sinon
 v4  0 0 5 0 0
v4  0 0 1 0 0
v5 6 0 1 0 0
v5 1 0 1 0 0
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 265 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 266 / 285

Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Graphe de similarités et de voisinage Matrice laplacienne d’un graphe

En spectral clustering nous avons les correspondances suivantes : Définition. (Matrice laplacienne)
I V = O = ensemble des objets {X1 , . . . , Xj }.
I E = ensemble des paires d’objets (Xi , Xj ) considérés comme voisins. Soit G = (V, E) un graphe non-orienté pondéré de matrice d’adjacence
I wij = mesure de la relation de voisinage pour (Xi , Xj ). W. La matrice laplacienne non normalisée de G , notée L, est une matrice
Suppons une fonction s donnant pour chaque paire (Xi , Xj ) une carré de même ordre que W qui est définie comme suit :
mesure de similarité dans R (une fonction noyau par exemple).
Soit NNk (Xi )= ensemble des k objets ayant les plus fortes valeurs de L=D−W
similarité avec Xi .
Plusieurs façons de construire W à partir de s : où D est la matrice des degrés.
I Graphe écrêté selon un seuil θ ≥ 0 :
Exemple :
wij = s(Xi , Xj ) si s(Xi , Xj ) ≥ θ
v1 v2 v3 v4 v5 v v2 v3 v4 v5
 1
I Graphe des k-plus proches voisins :
  
v1 0 2 0 0 6 v1 8 −2 0 0 −6
wij = s(Xi , Xj ) si Xi ⊂ NN(Xj ) ∨ Xj ⊂ NN(Xi ) v2 
 2 0 3 0 0  v2  −2
 5 −3 0 0 

W = v3  0 3 0 5 1 →L= v3 
 0 −3 9 −5 −1 
I Graphe “connexe” : 
v4  0 0 5 0 0 v4  0 0 −5 5

0 
wij = s(Xi , Xj ) si s(Xi , Xj ) ≥ 0 v5 6 0 1 0 0 v5 −6 0 −1 0 7
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 267 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 268 / 285
Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Propriétés de la matrice laplacienne Propriétés de la matrice laplacienne (suite)

Propriété. Propriété.
Soit L la matrice laplacienne d’un graphe G non-orienté pondéré d’ordre n Soit G un graphe non-orienté pondéré d’ordre n dont les valuations sont
alors : non-négatives. Alors, l’ordre de multiplicité k de la valeur propre 0 de la
Pour tout vecteur f ∈ Rn : matrice laplacienne L est le nombre de composantes connexes du graphe
que l’on notera C1 , . . . , Ck . De plus, le sous-espace propre associé à la
n
> 1 X valeur propre 0 est engendré par les vecteurs indicateurs 1C1 , . . . , 1Ck de
f Lf = wij (fi − fj )2
2 ces composantes.
i,j=1

L est symétrique et semi-définie positive. Rappel : une composante connexe est un sous-graphe tels que ses
La plus petite valeur propre de L est 0 et son vecteur propre associé sommets sont connexes.
est 1 (vecteur rempli de 1). Le vecteur indicateur 1Cl appartient à {0, 1}n et [1Cl ]i = 1 si Xi ∈ Cl .
L a n valeurs propres réelles, non-négatives : Il est intéressante de noter les liens entre ce résultat issu de la théorie
des graphes et la problématique de clustering et notamment le
0 = λ1 ≤ λ2 ≤ . . . ≤ λn partitionnement en k classes à partir d’une matrice de similarités.
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 269 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 270 / 285

Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Matrice laplacienne normalisée d’un graphe Propriétés de la matrice laplacienne normalisée

On démontre qu’une version normalisée de la matrice laplacienne a de Propriété.

meilleures propriétés. Soit Lsym la matrice laplacienne normalisée d’un graphe G non-orienté
pondéré d’ordre n alors :
Définition. (Matrice laplacienne normalisée) Pour tout vecteur f ∈ Rn :
Soit G = (V, E) un graphe non-orienté pondéré de matrice d’adjacence W n
et de matrice laplacienne (non-normalisée) L. La matrice laplacienne > 1 X fi fj
f Lsym f = wij ( √ − p )2
normalisée de G , notée Lsym , est une matrice carré de même ordre que W 2 di dj
i,j=1
qui est définie comme suit :
Lsym est symétrique et sdp et possède n valeurs propres réelles,
−1/2 −1/2 −1/2 −1/2
Lsym = D LD =I−D WD non-négatives :
0 = λ1 ≤ λ2 ≤ . . . ≤ λn
où D est la matrice des degrés.
L’ordre de multiplicité k de la valeur propre 0 est le nombre de
composantes connexes de G que l’on notera C1 , . . . , Ck . Le
Il existe un autre type de normalisation (de type “random walk”) :
sous-espace propre associé à la valeur propre 0 est engendré par les
Lrw = D−1 L [Shi and Malik, 2000] mais nous ne l’étudierons pas.
vecteurs D1/2 1C1 , . . . , D1/2 1Ck .
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 271 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 272 / 285
Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Pseudo-code des méthodes de spectral clustering Lien entre les différentes méthodes
Le spectral clustering réduit implicitement les dimensions puis utilise
les k-means dans l’espace réduit pour partitionner les objets.
1 Input : s, méthode pour W, normalisation ou pas, k (nb de classes) Si la fonction de similarité est un noyau et si W est le graphe de
2 Construire le graphe de voisinage W selon la méthode choisie voisinage “connexe” alors la méthode spectrale utilisée est clairement
3 Construire la matrice laplacienne non-normalisée L ou normalisée Lsym liée aux k-means à noyaux.
4 Calculer f 1 , . . . , f k , les k premiers vecteurs propres de L ou Lsym Si le graphe de voisinage est limité au voisinage proche alors le
1 k n×k

5 Construire F = f . . . f ∈ R la matrice des k vecteurs propres spectral clustering va plus loin que les k-means à noyaux puisque W
mis en colonne permet alors d’encoder implicitement la géométrie intrinsèque des
6 Si Lsym est utilisée, normer les vecteurs lignes de F données. Dans ce cas, le spectral clustering ne fait donc pas
7 Utiliser les k-means pour partitionner les n lignes de F d’hypothèse sur la forme des classes.
8 Ouput : P(O) En revanche, il y a plusieurs paramètres à fixer pour la construction
de W et les résultats peuvent être sensibles à ce paramétrage.
Le spectral clustering est également une approche relaxée du problème
de coupe normalisée de graphe dont la version non-normalisée est le
dual du problème de flot maximal (Ford-Fulkerson).
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 273 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 274 / 285

Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Illustration Mesures d’évaluation pour le problème de partitionnement

Il existe deux types d’évaluation : la validation interne et externe.
Résultats k−means Résultats spectral clustering Nous étudions l’approche externe qui suppose l’existence d’une
partition de référence (“ground-truth”) et le résultat de clustering
1.0

1.0

est d’autant meilleur qu’il se rapproche de cette vérité terrain.

0.5

Notons P(O) = {C1 , . . . , Cq } la partition de référence et

P̂(O) = {Ĉ1 , . . . , Ĉk } la partition obtenue par clustering. Il existe
0.0

0.0
X^2

X^2

plusieurs façon de mesurer la similarité entre deux partitions.

−0.5

Comme pour le pb de catégorisation, nous exploitons l’information

contenue dans la matrice de confusion N de taille (q × k) :
−1.0

−1.0

−1.0 −0.5 0.0 0.5 1.0 −1.0 −0.5 0.0 0.5 1.0
X^1 X^1
P̂(O)
Ĉ1 . . . Ĉk
Résultats des k-means et du spectral clustering avec un noyau N= C1
P(O) ..
gaussien. . Nij
Cq
J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 275 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 276 / 285
Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Mesures d’évaluation pour le problème de partitionnement Mesures d’évaluation pour le problème de partitionnement
(suite) (suite)

Pour tout i = 1, . . . , q et j = 1, . . . , k (k pouvant donc être différent Indice de Rand Corrigé entre P(O) et P̂(O) :
de q), le terme N(i, j) = Nij indique le nombre d’objets appartenant à
P Nij hP Ni. P N.j i n
la classe Ci de P(O) ayant été affectés au cluster Ĉj de P̂(O). i,j 2 − i 2 j 2 / 2
ARI (N) = hP
Ni. = kj=1 Nij est le nb total d’objets dans la classe Ci de P(O)
P i hP i
Ni. N.j Ni. N.j
1
/ n2
P P
2 i 2 + j 2 − i 2 j 2
N.j = qi=1 Nij est le nb total d’objets dans le cluster Ĉj de P̂(O).
P
a a!

où = b!(a−b)! , a et b étant des entiers naturels tels que a ≥ b.
P
i,j Nij = n est le nb total d’objets. b
Deux mesures souvent utiliser pour évaluer la similarité entre P(O) et Information mutuelle normalisée entre P(O) et P̂(O) :
P̂(O) sont l’indice de Rand corrigé (ou ajusté) (ARI ) et
P nNij
l’information mutuelle normalisée (NMI ). Elles sont bornées N
i,j ij log Ni. N.j
supérieurement par 1. Plus elles sont proches de 1 plus forte est la NMI (N) = r
P Ni. P N.j
similarité entre P(O) et P̂(O) et donc meilleur est le résultat de N
i i. log n N
j .j log n
clustering.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 277 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 278 / 285

Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Quelques références I Quelques références II

Abiteboul, S., Bancilhon, F., Bourdoncle, F., Clemencon, S., De La Higuera, C., Saporta, G., and Fogelman Soulié, F.
Breiman, L. (1996).
(2014).
Bagging predictors.
L’émergence d’une nouvelle filière de formation : ” data scientists ”.
Machine learning, 24(2) :123–140.
Interne, INRIA Saclay.

Alpaydin, E. (2010). Breiman, L. (2001).

Introduction to Machine Learning. Random forests.
MIT Press. Machine learning, 45(1) :5–32.

Anderberg, M. (1973). Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984).
Clustering analysis for applications. Classification and Regression Trees.
London, Academic Press. Chapman & Hall, New York, NY.

Asuncion, A. and Newman, D. (2007). Clark, A., Fox, C., and Lappin, S. (2010).
UCI machine learning repository. The Handbook of Computational Linguistics and Natural Language Processing.
Blackwell Handbooks in Linguistics. Wiley.
Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. (1999).
When is Nearest Neighbor Meaningful ? Cleveland, W. S. (2001).
In ICDT. Data science : An action plan for expanding the technical areas of the field of statistics.

Bishop, C. M. (2006a). Cornillon, P.-A. and Matzner-Lober, E. (2010).

Pattern Recognition and Machine Learning. Régression avec R.
Springer.
Cornuéjols, A. and Miclet, L. (2003).
Bishop, C. M. (2006b). Apprentissage artificiel.
Pattern recognition and machine learning. Eyrolles.
Springer, 1st ed. 2006. corr. 2nd printing edition.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 279 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 280 / 285
Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Quelques références III Quelques références IV

Ding, C. and He, X. (2004).
Han, J. and Kamber, M. (2006).
K-means clustering via principal component analysis.
Data Mining Concepts and Techniques.
In ICML ’04 : Proceedings of the twenty-first international conference on Machine learning, page 29, New York, NY,
Morgan Kaufmann.
USA. ACM.
Dreyfus, G. (2008). Hastie, T., Rosset, S., Tibshirani, R., and Zhu, J. (2004).
Apprentissage Statistique. Réseaux de neurones, Cartes topologiques, Machines à vecteurs supports. The entire regularization path for the support vector machine.
Eyrolles. Journal of Machine Learning Research, 5(Oct) :1391–1415.

Efron, B., Hastie, T., Johnstone, I., Tibshirani, R., et al. (2004). Hastie, T., Tibshirani, R., and Friedman, J. (2011).
Least angle regression. The Elements of Statistical Learning.
The Annals of statistics, 32(2) :407–499. Springer.

Filippone, M., Camastra, F., Masulli, F., and Rovetta, S. (2008). Horn, R. and Johnson, C. (1985).
A survey of kernel and spectral methods for clustering. Matrix analysis.
Pattern Recogn., 41(1) :176–190. Cambridge University Press.

Jain, A. K., Murty, M. N., and Flynn, P. J. (1999).

Freund, Y., Schapire, R. E., et al. (1996).
Data clustering : a review.
Experiments with a new boosting algorithm.
ACM Comput. Surv., 31(3) :264–323.
In Icml, volume 96, pages 148–156.
Leskovec, J., Rajaraman, A., and Ullman, J. D. (2014).
Friedman, J., Hastie, T., and Tibshirani, R. (2010).
Mining of massive datasets.
Regularization paths for generalized linear models via coordinate descent.
Cambridge University Press.
Journal of statistical software, 33(1) :1.
Manning, C. D. and Schütze, H. (1999).
Gan, G., Ma, C., and Wu, J. (2007).
Foundations of Statistical Natural Language Processing.
Data Clustering : Theory, Algorithms, and Applications (ASA-SIAM Series on Statistics and Applied Probability). MIT Press.
SIAM, Society for Industrial and Applied Mathematics, illustrated edition edition.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 281 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 282 / 285

Apprentissage non-supervisé Le spectral clustering Apprentissage non-supervisé Le spectral clustering

Quelques références V Quelques références VI

Mirkin, B. (1996). Saporta, G. (2006).
Mathematical classification and clustering. Probabilités, analyses des données et statistiques.
Kluwer academic press, Dordrecht. Editions Technip.

Mitchell, T. (1997). Schölkopf, B., Smola, A., and Müller, K.-R. (1998).
Machine Learning. Nonlinear component analysis as a kernel eigenvalue problem.
McGraw Hill. Neural computation, 10(5) :1299–1319.

Ng, A. Y., Jordan, M. I., Weiss, Y., et al. (2001). Scholkopf, B. and Smola, A. J. (2001).
On spectral clustering : Analysis and an algorithm. Learning with Kernels : Support Vector Machines, Regularization, Optimization, and Beyond.
In NIPS, volume 14, pages 849–856. MIT Press, Cambridge, MA, USA.

Pelleg, D. and Moore, A. (2000). Shi, J. and Malik, J. (2000).

X-means : Extending k-means with efficient estimation of the number of clusters. Normalized cuts and image segmentation.
In In Proceedings of the 17th International Conf. on Machine Learning, pages 727–734. Morgan Kaufmann. IEEE Transactions on pattern analysis and machine intelligence, 22(8) :888–905.

Quinlan, J. (1986). Valiant, L. G. (1984).

Induction of decision trees. A theory of the learnable.
Machine Learning, 1(1) :81–106. Communications of the ACM, 27(11) :1134–1142.

Quinlan, J. R. (1993). Vapnik, V. N. (1995).

C4.5 : programs for machine learning. The nature of statistical learning theory.
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Springer-Verlag New York, Inc., New York, NY, USA.

Rokach, L. (2010). Vert, J., Tsuda, K., and Schölkopf, B. (2004).

Ensemble-based classifiers. A primer on kernel methods.
Artificial Intelligence Review, 33(1-2) :1–39. In Schölkopf, B., K. T. and Vert, J., editors, Kernel Methods in Computational Biology, pages 35–70, Cambridge, MA,
USA. MIT Press.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 283 / 285 J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 284 / 285
Apprentissage non-supervisé Le spectral clustering

Quelques références VII

Von Luxburg, U. (2007).

A tutorial on spectral clustering.
Statistics and computing, 17(4) :395–416.

Xu, R. and Wunsch, D. I. I. (2005).

Survey of clustering algorithms.
IEEE Transactions on Neural Networks, 16(3) :645–678.

Zelnik-Manor, L. and Perona, P. (2005).

Self-tuning spectral clustering.
In Advances in Neural Information Processing Systems 17.

Zou, H. and Hastie, T. (2005).

Regularization and variable selection via the elastic net.
Journal of the Royal Statistical Society : Series B (Statistical Methodology), 67(2) :301–320.

J. Ah-Pine (Univ-Lyon 2) Apprentissage Sup et Non-Sup M2 SISE 2020/2021 285 / 285

Vous aimerez peut-être aussi

Introduction à l'apprentissage automatique
Pas encore d'évaluation
Introduction à l'apprentissage automatique
90 pages
Introduction à l'apprentissage automatique
Pas encore d'évaluation
Introduction à l'apprentissage automatique
90 pages
Comprendre l'apprentissage automatique et IA
Pas encore d'évaluation
Comprendre l'apprentissage automatique et IA
115 pages
Guide Pedagogique AA Complet
Pas encore d'évaluation
Guide Pedagogique AA Complet
34 pages
Introduction à l'apprentissage automatique
Pas encore d'évaluation
Introduction à l'apprentissage automatique
45 pages
Introduction au Machine Learning
Pas encore d'évaluation
Introduction au Machine Learning
6 pages
Apprentissage automatique : principes clés
Pas encore d'évaluation
Apprentissage automatique : principes clés
67 pages
Apprentissage Automatique : Guide Complet
Pas encore d'évaluation
Apprentissage Automatique : Guide Complet
47 pages
COURS - ML - Part 1
Pas encore d'évaluation
COURS - ML - Part 1
41 pages
Introduction à l'Intelligence Artificielle
Pas encore d'évaluation
Introduction à l'Intelligence Artificielle
129 pages
Introduction au Machine Learning
Pas encore d'évaluation
Introduction au Machine Learning
32 pages
IA : Apprentissage Automatique et Profond
Pas encore d'évaluation
IA : Apprentissage Automatique et Profond
4 pages
1Ch1 ML
Pas encore d'évaluation
1Ch1 ML
90 pages
Introduction à l'IA avec Python
100% (2)
Introduction à l'IA avec Python
133 pages
Introduction au Machine Learning en Santé
Pas encore d'évaluation
Introduction au Machine Learning en Santé
67 pages
Fondamentaux de l'Apprentissage Automatique
Pas encore d'évaluation
Fondamentaux de l'Apprentissage Automatique
10 pages
Introduction à l'Apprentissage Automatique
Pas encore d'évaluation
Introduction à l'Apprentissage Automatique
39 pages
Apprentissage Automatique et Complexité
Pas encore d'évaluation
Apprentissage Automatique et Complexité
42 pages
Cours d'Apprentissage Automatique M1 IA
Pas encore d'évaluation
Cours d'Apprentissage Automatique M1 IA
68 pages
Types d'apprentissage automatique expliqués
Pas encore d'évaluation
Types d'apprentissage automatique expliqués
29 pages
Cours d'Apprentissage Automatique 2022-2023
Pas encore d'évaluation
Cours d'Apprentissage Automatique 2022-2023
54 pages
Fondements de l'Apprentissage Machine
Pas encore d'évaluation
Fondements de l'Apprentissage Machine
18 pages
Rapport sur l'apprentissage automatique Python
Pas encore d'évaluation
Rapport sur l'apprentissage automatique Python
29 pages
Génération Automatique de Commentaires Java
Pas encore d'évaluation
Génération Automatique de Commentaires Java
38 pages
Fondements de l'apprentissage machine
Pas encore d'évaluation
Fondements de l'apprentissage machine
148 pages
Fondements de l'apprentissage machine IA
Pas encore d'évaluation
Fondements de l'apprentissage machine IA
16 pages
Introduction au Deep Learning et IA
Pas encore d'évaluation
Introduction au Deep Learning et IA
27 pages
Introduction au Machine Learning
Pas encore d'évaluation
Introduction au Machine Learning
127 pages
Introduction à l'apprentissage automatique
Pas encore d'évaluation
Introduction à l'apprentissage automatique
48 pages
Génie Logiciel pour l'IA - MGL869
Pas encore d'évaluation
Génie Logiciel pour l'IA - MGL869
88 pages
Introduction au machine learning
Pas encore d'évaluation
Introduction au machine learning
5 pages
Techniques d'apprentissage automatique expliquées
Pas encore d'évaluation
Techniques d'apprentissage automatique expliquées
69 pages
Cours Ml Intro 2025
Pas encore d'évaluation
Cours Ml Intro 2025
75 pages
Introduction au Machine Learning
Pas encore d'évaluation
Introduction au Machine Learning
29 pages
Intelligence Artificielle Et Apprentissage Automatique
Pas encore d'évaluation
Intelligence Artificielle Et Apprentissage Automatique
4 pages
Différences entre apprentissage supervisé et non supervisé
Pas encore d'évaluation
Différences entre apprentissage supervisé et non supervisé
6 pages
Types d'apprentissage en machine learning
Pas encore d'évaluation
Types d'apprentissage en machine learning
15 pages
Cours d'Apprentissage Automatique PDF
Pas encore d'évaluation
Cours d'Apprentissage Automatique PDF
22 pages
Sécurité routière et Deep Learning
Pas encore d'évaluation
Sécurité routière et Deep Learning
15 pages
Introduction à la Modélisation IA
Pas encore d'évaluation
Introduction à la Modélisation IA
50 pages
Introduction à l'apprentissage automatique
Pas encore d'évaluation
Introduction à l'apprentissage automatique
78 pages
Machine Learning VJ
Pas encore d'évaluation
Machine Learning VJ
133 pages
Techniques d'Apprentissage Automatique
Pas encore d'évaluation
Techniques d'Apprentissage Automatique
161 pages
Initiation À L'intelligence: Artificielle
Pas encore d'évaluation
Initiation À L'intelligence: Artificielle
30 pages
TP 1 - Exercice 1 - Correction
100% (1)
TP 1 - Exercice 1 - Correction
4 pages
Introduction au Machine Learning 2023
Pas encore d'évaluation
Introduction au Machine Learning 2023
27 pages
Introduction à l'apprentissage automatique
Pas encore d'évaluation
Introduction à l'apprentissage automatique
1 page
Techniques d'apprentissage automatique
Pas encore d'évaluation
Techniques d'apprentissage automatique
170 pages
Cours IA01
Pas encore d'évaluation
Cours IA01
18 pages
Machine Learning : Approches et Applications
Pas encore d'évaluation
Machine Learning : Approches et Applications
18 pages
Apprentissage Non Supervisé en Machine Learning
Pas encore d'évaluation
Apprentissage Non Supervisé en Machine Learning
16 pages
IA et Machine Learning en Logistique
Pas encore d'évaluation
IA et Machine Learning en Logistique
72 pages
IA1 - Chapitre 2 (Partie 1 (Ancienne) - ML Supervisé)
Pas encore d'évaluation
IA1 - Chapitre 2 (Partie 1 (Ancienne) - ML Supervisé)
10 pages
Introduction à l'apprentissage profond
Pas encore d'évaluation
Introduction à l'apprentissage profond
59 pages
Introduction à l'Intelligence Artificielle
Pas encore d'évaluation
Introduction à l'Intelligence Artificielle
77 pages
Introduction au Machine Learning Python
100% (1)
Introduction au Machine Learning Python
8 pages
Apprentissage Automatique avec Mohand Allili
Pas encore d'évaluation
Apprentissage Automatique avec Mohand Allili
37 pages
Recrutement de Stagiaires pour Chatbot INS
100% (1)
Recrutement de Stagiaires pour Chatbot INS
3 pages
Chimiotrophie et glucides chez les plantes
Pas encore d'évaluation
Chimiotrophie et glucides chez les plantes
89 pages
Formation TypeScript à Marseille
0% (2)
Formation TypeScript à Marseille
2 pages
Management des Systèmes d'Information
Pas encore d'évaluation
Management des Systèmes d'Information
36 pages
Relevé de notes - Université de Douala
Pas encore d'évaluation
Relevé de notes - Université de Douala
1 page
Typescript: Notions Fondamentales
0% (1)
Typescript: Notions Fondamentales
15 pages
Corrigé d'exercices en génie logiciel
Pas encore d'évaluation
Corrigé d'exercices en génie logiciel
4 pages
Cours de Probabilités et Statistiques
Pas encore d'évaluation
Cours de Probabilités et Statistiques
95 pages
Modèle de requête universitaire
100% (1)
Modèle de requête universitaire
1 page
Introduction à la Programmation Python
Pas encore d'évaluation
Introduction à la Programmation Python
31 pages
Administration des Réseaux et Protocoles
Pas encore d'évaluation
Administration des Réseaux et Protocoles
14 pages
Commutateur PoE Gigabit 24 ports DH-PFS4428
Pas encore d'évaluation
Commutateur PoE Gigabit 24 ports DH-PFS4428
1 page
Software Engineering
Pas encore d'évaluation
Software Engineering
50 pages
Initiation au langage VHDL
Pas encore d'évaluation
Initiation au langage VHDL
25 pages
Présentation de l'entreprise INSAT et production
Pas encore d'évaluation
Présentation de l'entreprise INSAT et production
21 pages
Évaluation Informatique 3ème 2023-2024
Pas encore d'évaluation
Évaluation Informatique 3ème 2023-2024
2 pages
Sécurité des Réseaux et ACLs
Pas encore d'évaluation
Sécurité des Réseaux et ACLs
5 pages
Guide d'utilisation DVR HDCVI
Pas encore d'évaluation
Guide d'utilisation DVR HDCVI
16 pages
Qlik Sense Administration Cours & Exercices 022018
100% (1)
Qlik Sense Administration Cours & Exercices 022018
80 pages
Cours en Systèmes et Réseaux Avancés
Pas encore d'évaluation
Cours en Systèmes et Réseaux Avancés
2 pages
Système de Comptage de Personnes en Temps Réel
Pas encore d'évaluation
Système de Comptage de Personnes en Temps Réel
41 pages
Épreuve Informatique Modèle 2020
Pas encore d'évaluation
Épreuve Informatique Modèle 2020
11 pages
Supervision des Réseaux Industriels
100% (3)
Supervision des Réseaux Industriels
8 pages
Journée NSI : Découverte Numérique
Pas encore d'évaluation
Journée NSI : Découverte Numérique
6 pages
Prévisions de cours TIC 2022-2023
Pas encore d'évaluation
Prévisions de cours TIC 2022-2023
4 pages
Interrogation sur les variables en Python
Pas encore d'évaluation
Interrogation sur les variables en Python
2 pages
Guide d'utilisation Lenovo T470s
Pas encore d'évaluation
Guide d'utilisation Lenovo T470s
182 pages
Introduction à MATLAB pour TP 2021
Pas encore d'évaluation
Introduction à MATLAB pour TP 2021
31 pages
Modèles de processus de développement logiciel
Pas encore d'évaluation
Modèles de processus de développement logiciel
6 pages
Exercices sur l'Adressage IP
Pas encore d'évaluation
Exercices sur l'Adressage IP
7 pages
Exercices Résolus en Assembleur 8086
Pas encore d'évaluation
Exercices Résolus en Assembleur 8086
33 pages
Cours Internet n3
Pas encore d'évaluation
Cours Internet n3
5 pages
Programmation PIC 16F84A avec MPLAB
Pas encore d'évaluation
Programmation PIC 16F84A avec MPLAB
6 pages
Formation SOLIDWORKS 2018 : Plan de cours
Pas encore d'évaluation
Formation SOLIDWORKS 2018 : Plan de cours
66 pages
Supervision et Administration de Serveurs
Pas encore d'évaluation
Supervision et Administration de Serveurs
23 pages
Comprendre les systèmes d'exploitation
Pas encore d'évaluation
Comprendre les systèmes d'exploitation
1 page
Formation CompTIA Network+ et Cybersécurité
100% (1)
Formation CompTIA Network+ et Cybersécurité
2 pages
CV Uriel A. H. Johnson - Étudiant en Génie
Pas encore d'évaluation
CV Uriel A. H. Johnson - Étudiant en Génie
2 pages
Introduction à la cryptographie et Enigma
Pas encore d'évaluation
Introduction à la cryptographie et Enigma
61 pages
Incubateur Technologique de l'Innovation
Pas encore d'évaluation
Incubateur Technologique de l'Innovation
4 pages

Méthodes en Apprentissage Supervisé

Transféré par

Méthodes en Apprentissage Supervisé

Transféré par

Introduction : Apprentissage Automatique (AA)

Méthodes avancées en apprentissage supervisé et

Introduction : Apprentissage Automatique (AA) Introduction : Apprentissage Automatique (AA)

En quoi consiste l’apprentissage automatique ? Un domaine pluri-disciplinaire

AA et matières connexes AA et matières connexes (suite)

Quelques références et domaines d’application faisant intervenir l’AA :

Introduction : Apprentissage Automatique (AA) Introduction : Apprentissage Automatique (AA)

Plusieurs types de problèmes en AA Plusieurs types de problèmes (suite)

Motivations de ce cours Organisation de ce cours

Dans le cadre de ce cours, nous étudierons des problèmes supervisés

Apprentissage supervisé Apprentissage supervisé Définitions, notations et concepts importants

Rappel du Sommaire Rappel du Sommaire

Apprentissage supervisé symbolique et numérique Apprentissage supervisé numérique

Quelques exemples d’application Notations

Notations (suite) Formalisation du problème

Schéma général Schéma général (suite)

Schéma général (suite) Schéma général (suite)

Dans ce qui suit nous présentons des exemples simples de régression

Schéma général (suite) Rappel du Sommaire

Exemple de problème de régression Régression linéaire simple

pour la fonction fˆ.

(somme des carrés des résidus ou “Residual Sum of Squares”) :

Régression linéaire simple (suite) Régression linéaire simple (suite)

P = {a, b} est l’ensemble des paramètres du modèle et on cherche les

Le modèle de prédiction est alors donné par : −2 −1 0 1 2 3

Régression linéaire multiple (polynôme de degré > 1) Régression linéaire multiple

Exemple de problème de catégorisation Régression linéaire multiple avec variables artificielles

On traite le problème comme une régression linéaire multiple :

Régression linéaire multiple (suite) Régression linéaire multiple (suite)

Nous avons utilisé la régression linéaire associée à des variables k=1

paramétrique : les k plus proches voisins. ●

Etant donné un nouvel objet x, la méthode consiste à déterminer les ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

fˆ(x) = arg max

où Vk (x) est l’ensemble des k plus proches xi de x et

Méthode des k-ppv (suite) Rappel du Sommaire

Définitions, notations et concepts importants

Quelques méthodes simples en guise d’illustration

Les réseaux de neurones artificiels (“Artificial Neural Networks”)

0.0 0.2 0.4 0.6 0.8 1.0

Choix de la méthode d’apprentissage Approches inductives et classes d’hypothèses

Les méthodes que nous voyons sont de type inductif : à partir

Biais inductif Plusieurs types de fonction de performance

Notations Notations (suite)

Fonction de performance et décision statistique Fonction de perte quadratique et fonction de régression

Fonction de perte quadratique et fonction de régression Fonction de performance pour la catégorisation

L(Cl , Cl 0 ) = Lll 0 = Coût associée à une mauvaise affectation

Classifieur bayésien Classifieur bayésien naı̈f

Classifieur bayésien naı̈f (suite) Estimation, décision, zone de rejet

Rappel du Sommaire Généralisation, sous et sur-apprentissage

Le choix d’une méthode revient à choisir un espace d’hypothèses, une

Généralisation, sous et sur-apprentissage (suite) Généralisation, sous et sur-apprentissage (suite)

Compléxité des modèles de régression linéaire Arbitrage biais-variance

Arbitrage biais-variance (suite) Arbitrage biais-variance (suite)

comme la réalisation d’un processus aléatoire et on définit ainsi : h =

fˆE (X ), on peut alors décomposer l’erreur quadratique comme suit :

Arbitrage biais-variance (suite) Arbitrage biais-variance (suite)

Illustration du problème de l’arbitrage biais-variance

Impact de la taille de l’échantillon d’entraı̂nement E Arbitrage triple Complexité - Données d’entraı̂nement -

Arbitrage triple Complexité - Données d’entraı̂nement - Rappel du Sommaire

Différentes caractéristiques des méthodes d’apprentissage supervisé

Evaluation et comparaison de modèles en apprentissage supervisé

Les méthodes linéaires et leurs pénalisations (elasticnet ...)

Les machines à vecteurs supports (“Support Vector Machines”)

Schéma général Protocol expérimental en apprentissage supervisée

Protocol expérimental en apprentissage supervisée (suite) Validation croisée

Validation croisée (suite) Mesures d’évaluation

Mesures d’évaluation pour le problème de catégorisation Courbe ROC

Courbe ROC (suite) Courbe ROC (suite)

Courbe ROC (suite) Courbe ROC (suite)

Courbe ROC (suite) Courbe ROC (suite)

True positive rate

On peut comparer deux types de fonction de prédiction en utilisant

d’un classifieur. On peut par aussi résumer le graphique par un

est la mesure de la surface sous la courbe ROC.

Le modèle fˆ est meilleur que fˆ0 si auc(fˆ) > auc(fˆ0 ).

0.0 0.2 0.4 0.6 0.8 1.0

comme la réalisation d’un processus aléatoire et on définit ainsi : h =