Analyse de données au moyen d’algorithmes

d’apprentissage automatique (« Machine Learning »)

Patrick SIBILLE
[Link]@[Link]

Département d’Automatique
Faculté des Sciences et Technologies
Campus Sciences
BP 70239 - 54506 Vandoeuvre-les-Nancy Cedex
France

26 septembre 2023

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 1 / 277

 Chapitre 1 : Introduction

Plan du cours I

1 Chapitre 1 : Introduction
Généralités
Les grands types d’apprentissage
Contexte du cours
La phase de caractérisation

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 2 / 277

 Chapitre 1 : Introduction Généralités

Plan du cours

1 Chapitre 1 : Introduction
Généralités
Les grands types d’apprentissage
Contexte du cours
La phase de caractérisation

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 3 / 277

 Chapitre 1 : Introduction Généralités

Qu’est-ce qu’un algorithme de « Machine Learning » ?

Définition (Wikipédia)
L’apprentissage automatique (en anglais machine learning, littéralement
« l’apprentissage machine ») ou apprentissage statistique, champ d’étude
de l’intelligence artificielle, concerne la conception, l’analyse, le développe-
ment et l’implémentation de méthodes permettant à une machine (au sens
large) d’évoluer par un processus systématique, et ainsi de remplir des tâches
difficiles ou problématiques par des moyens algorithmiques plus classiques.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 4 / 277

 Chapitre 1 : Introduction Généralités

Principe général des algorithmes de « Machine Learning » ?

Principe (Wikipédia)
Les algorithmes utilisés permettent, dans une certaine mesure, à un système
piloté par ordinateur (un robot éventuellement), ou assisté par ordinateur,
d’adapter ses analyses et ses comportements en réponse, en se fondant sur
l’analyse de données empiriques provenant d’une base de données ou de
capteurs.

■ L’algorithme d’apprentissage automatique permet de fournir une ré-

ponse adaptée à la perception de l’environnement
■ Cette perception peut-être donnée par : vision, reconnaissance d’objets
(visages, schémas, langages naturels, écriture, signaux, artéfacts. . .)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 5 / 277

 Chapitre 1 : Introduction Généralités

Le principe de l’apprentissage

Il s’agit de construire un algorithme de façon à ce que celui-ci réalise la

tâche qui lui est assignée :
■ classification, identification, prédiction, simulation. . .
Pour atteindre cet objectif, il faut fournir à l’outil :
1 une base de données judicieusement choisie : un jeu de données d’en-
traînement d’où le nom d’apprentissage
2 il faut choisir un algorithme
3 il faut choisir une mesure de performance : une erreur à minimiser
4 il faut ensuite valider la phase d’apprentissage par la mesure de perfor-
mance du modèle par rapport à l’objectif fixé

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 6 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Plan du cours

1 Chapitre 1 : Introduction
Généralités
Les grands types d’apprentissage
Contexte du cours
La phase de caractérisation

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 7 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Les grands types d’apprentissage I

1 Apprentissage supervisé
Comment ça marche ?
Le processus comporte deux étapes :
(a) Un expert du domaine fournit une base de données d’apprentissage.
L’algorithme est choisi et est paramètré lors de la phase d’apprentissage
sur ces données :
Recherche d’un modèle représentant les données,
Ou encore extraction de caractéristiques représentant les données,
Autrement dit : construction de grandeurs « simples » permettant la
caractérisation des données,
Cette étape est généralement réalisée hors-ligne.
(b) Le modèle obtenu est soumis à d’autres bases de données : phase de
test.
Les performances de l’algorithme sont analysées via les experts.
Cette étape est réalisée hors-ligne ou en ligne suivant les applications.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 8 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Les grands types d’apprentissage II

2 Apprentissage non supervisé

Quand l’utilise-t-on ?
(a) Lorsque l’on ne peut pas disposer d’une base de données classées, ex-
pertisées
Comment ça marche ?
(a) On dispose donc d’une base de données a priori qui n’est pas « labellisée
» (« expertisée » ou « triée »)
(b) L’algorithme recherche « seul » les similarités entre les observations
(c) Le type d’algorithme sous-jacent est souvent construit en utilisant les
techniques de classification :
Répartition des observations en classes : classement des observations en
groupes « homogènes ».
Cette similarité est calculée en s’appuyant sur une fonction de mesures
de distance entre observations.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 9 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Schématisation de l’apprentissage supervisé

Démarche

Non
Choix modèle
et Erreur ?
paramétrage
Satisfaisante
Expertise
Modèle

Non

Modèle Résultat ?

Satisfaisant

Objectifs
atteints

Figure 1 – Apprentissage supervisée

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 10 / 277
 Chapitre 1 : Introduction Les grands types d’apprentissage

Quels sont les facteurs qui influencent la qualité des

résultats ? I
1 La « qualité » des données est le premier des impératifs
Celle-ci conditionne grandement les résultats des futurs traitements
▶ Nombre d’observations : moins il y en a, plus l’analyse est difficile, mais
plus il y en a, plus le besoin en ressources est élevé et plus longue est
l’analyse
▶ Pas de données manquantes si possible !
▶ Bruit de mesure à minimiser
▶ Mesures ou observations représentatives du fonctionnement « modélisé
»
▶ Valeurs aberrantes éliminées
▶ Qualité des observations : observations porteuses d’information
▶ L’expert doit épurer la base de données de telle sorte que celle-ci ne
comporte pas d’observations sujettes à discussion
2 Les choix du modèle et de l’algorithme doivent être en cohérence avec
les objectifs et le type de données traitées
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 11 / 277
 Chapitre 1 : Introduction Les grands types d’apprentissage

Domaines d’application de l’apprentissage automatique

Ils sont multiples et très divers !

■ Reconnaissance de la parole, d’images
■ Reconnaissance de l’écriture manuscrite (CAPTCHA)
■ Moteur de recherche
■ Robotique
■ Aide au diagnostic (médical, par exemple)
■ ...

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 12 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Problème de reconnaissance d’images I

Il s’agit d’automatiser la reconnaissance d’images.

Définition de la problématique
■ Des images d’animaux sont analysées et il s’agit de les reconnaître !

Figure 2 – Programme de reconnaissance d’une image

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 13 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Problème de reconnaissance d’images II

Comment faire de façon automatique ?

Une approche traditionnelle est très délicate !
Pourquoi ?
■ Exemples de difficultés, pour la catégorie « oiseaux » :
▶ par rapport à la diversité des caractéristiques morphologiques de l’animal,
▶ la couleur,
▶ la photo représente une partie ou l’animal entier,
▶ le fond de l’image,
▶ l’éclairage,
▶ l’angle de prise de vue. . .
Solution : exploiter une « bonne » de base de données pour « apprendre » !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 14 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Exemple d’une base de données d’apprentissage I

■ La base de données CIFAR-10 :

▶ Un exemple classique de jeu de données (images) de la littérature
▶ Chaque image est une observation de la base de données
▶ La base est constituée de 60 000 images réparties en 10 catégories
▶ Cette base de données est segmentée en 2 parties :
La première partie (50 000) est labellisée (classée) et est utilisée pour
entraîner un algorithme de « machine learning »
Ces données sont généralement appelées « données d’entraînement ».
La seconde partie (10 000) n’est pas classée, elle constitue la base de
test (base de validation)
Ces données sont aussi appelées « données de test ».

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 15 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Exemple d’une base de données d’apprentissage II

■ 2 étapes :
▶ Objectif liminaire : réaliser l’apprentissage sur la première partie :
Choisir un modèle statistique représentant « au mieux » les données,
Paramétrage du modèle statistique est réalisé par l’algorithme d’appren-
tissage à partir des données d’apprentissage
▶ Objectif final : reconnaître les images donc réaliser la classification sur
la deuxième partie.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 16 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Comment choisir un bon modèle d’apprentissage ? I

Compromis entre la minimisation de l’erreur et la complexité

■ Le modèle est une « simplification », une approximation de la réalité :

▶ Il n’est donc pas parfait !
■ Le modèle ne doit pas comporter trop de paramètres :
▶ Il doit être parcimonieux !
■ Cette parcimonie assure un bon pouvoir de prédiction donc une bonne
capacité d’apprentissage sur de nouvelles données :
▶ Une bonne capacité de généralisation :
Validation du modèle sur d’autres données

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 17 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Exemple d’une base de données d’apprentissage : CIFAR-10

Figure 3 – Base de données CIFAR (https ://[Link]/ kriz/[Link])

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 18 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Quelques éléments de réflexion relatifs à la construction de

CIFAR-10 I
Comment construire une « bonne » base de données pour l’apprentissage ?

■ Chacune des catégories doit être suffisamment représentée

■ La base de données doit être suffisamment « exhaustive »
■ Les observations trop ressemblantes, voire identiques n’ont pas d’intérêt
■ Si les catégories sont trop « proches » : le problème deviendra plus
complexe (ajout de la catégorie : panthère)
■ Si les variations intra-classe (dans une même catégorie) sont impor-
tantes alors le problème se complexifie
▶ Pour chaque catégorie, la diversité doit être présente :
Elle doit contenir toutes les particularités que l’algorithme doit être ca-
pable de classifier
■ Algorithme de classification : l’élément est rangé dans la classe du plus
proche voisin
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 19 / 277
 Chapitre 1 : Introduction Les grands types d’apprentissage

Eléments de classification des algorithmes d’apprentissage

2 grands types

■ La première catégorie est construite sur des méthodes de régression

linéaire ou pseudo-linéaire :
▶ Cette première catégorie est utilisée pour rendre des valeurs numériques
▶ Par exemple : une température prédite, une vitesse prédite. . .
■ La seconde s’appuie sur des méthodes de classification :
▶ Il s’agit de regrouper des observations qui sont « similaires »
C’est-à-dire qu’elles ont certaines caractéristiques communes,
Ces caractéristiques sont proches vis à vis de celles qui sont considérées
comme discriminantes.
▶ Les classes sont définies préalablement et les observations sont ensuite
affectées à une classe par rapport à la minimisation d’une distance intra-
classe
▶ Les méthodes de cette classe rendent un résultat discret : appartenance
ou non à une classe ou une catégorie
▶ Par exemple, en reconnaissance de caractères : une lettre, un chiffre. . .

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 20 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

Exemples d’illustration : régression et classification

4.5
1
Données
0.9 Modèle
rouge
0.8 4 vert

0.7

0.6 3.5
Proportion

x2
0.5

0.4 3

0.3

0.2 2.5

0.1

0 2
2000 2500 3000 3500 4000 4500 4 4.5 5 5.5 6 6.5 7 7.5 8
Poids x1

(a) Résultat obtenu par régression (b) Résultat obtenu par classification

Figure 4 – Exemples d’illustration : régression et classification

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 21 / 277

 Chapitre 1 : Introduction Les grands types d’apprentissage

En résumé
En quelques lignes

Algorithme d’apprentissage automatique ou de « machine learning »

Pour résoudre une tâche, une mesure de performance est construite par
rapport à cette tâche. Un algorithme apprend (est paramétré) à partir d’une
base de données d’apprentissage.
Si lorsque de nouvelles observations d’entraînement sont fournies, cet algo-
rithme s’améliore (mesure de performance plus élevée) alors celui-ci est un
algorithme d’apprentissage : il apprend au fur et à mesure des expériences !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 22 / 277

 Chapitre 1 : Introduction Les phases de l’apprentissage

2 phases : Caractérisation et Estimation

Démarche analogue à l’identification !

1 La phase dite de caractérisation (ou de paramétrisation) :

▶ déterminer une classe de modèles : choix des variables, nature des rela-
tions qui lient ces variables
2 La seconde est la phase d’estimation des paramètres du modèle :
▶ déterminer les valeurs numériques des paramètres du modèle choisi

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 23 / 277

 Chapitre 1 : Introduction Contexte du cours

Plan du cours

1 Chapitre 1 : Introduction
Généralités
Les grands types d’apprentissage
Contexte du cours
La phase de caractérisation

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 24 / 277

 Chapitre 1 : Introduction Contexte du cours

Hypothèse par rapport à la nature des données observées

Dans les cours précédents :

■ Les signaux et systèmes considérés étaient supposés parfaitement connus
(de manière déterministe)
■ Dans de nombreuses applications, les signaux à traiter ne peuvent être
modélisés de la sorte (déterministe)
▶ Tout signal mesuré, par nature, n’est pas connu de façon exacte. Le
signal observé est une forme corrompue du signal dit «utile»
Dans ce cours, on prendra en compte la nature incertaine des signaux ob-
servés
■ Signal observé = signal déterministe + bruit
■ Signaux échantillonnés

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 25 / 277

 Chapitre 1 : Introduction Contexte du cours

Hypothèses par rapport à la nature des perturbations

(bruits de mesure) I

Les bruits sont perçus comme des phénomènes incertains (imprévisibles)

■ Ces perturbations sont néanmoins assimilables à des variables aléatoires
■ Elles ne sont donc connues que par des propriétés moyennes (statis-
tiques)
■ Ces bruits sont supposés indépendants du phénomène observé
On suppose, la plupart du temps, que les perturbations obéissent à une den-
sité de probabilité f (x ) normale. Elle est caractérisée par ses deux premiers
moments statistiques :
■ L’espérance et la variance

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 26 / 277

 Chapitre 1 : Introduction Contexte du cours

Hypothèses par rapport à la nature des perturbations

(bruits de mesure) II

Rappel du cas monovariable :

 2
1 x (t)−E(x (t))
−2
d.d.p. : f (x (t)) = √ 1 e σx (t)
2πσx (t)
R −∞
Moment d’ordre 1 : E(x (t)) = −∞ xf (x )dx
R −∞ 2
Moment d’ordre 2 : E(x 2 (t)) = −∞ x f (x )dx
 2 
Variance : E x − E(x (t)) = σx2(t)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 27 / 277

 Chapitre 1 : Introduction Contexte du cours

Exemples de signaux : un signal temporel

65

60
Débit produit fini (t/h)

55

50

45

40

35

0 500 1000 1500 2000 2500 3000

temps (mn)
Figure 5 – Signal de débit en fonction du temps

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 28 / 277

 Chapitre 1 : Introduction Contexte du cours

Exemples de signaux : un signal temporel

Zoom
70

65

60
Débit produit fini (t/h)

55

50

45

40

35

30
0 100 200 300 400 500 600 700 800 900 1000
temps (mn)
Figure 6 – Signal de débit en fonction du temps
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 29 / 277
 Chapitre 1 : Introduction Contexte du cours

Exemples de signaux : histogramme

50 Paramètres de la loi normale :

40
Effectif

30

20

10

0
30 35 40 45 50 55 60 65 70
Débit en (t/h)
Figure 7 – Signal de débit : histogramme

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 30 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Plan du cours

1 Chapitre 1 : Introduction
Généralités
Les grands types d’apprentissage
Contexte du cours
La phase de caractérisation

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 31 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Eléments d’aide au choix de la structure du modèle I

L’utilisateur doit choisir une structure de modèle en adéquation avec les

données observées. Ce choix est le fruit de compromis !
■ Cette structure (de modèle) doit être suffisamment riche pour prendre
en compte la complexité de la réalité
■ Cette structure ne doit pas comporter pas un trop grand nombre de
paramètres
■ Cette structure ne sera donc qu’une approximation de la réalité
■ Cette structure sera donc un dilemme entre simplicité et réalité
■ La complexité de la structure dépendra notamment de :
▶ L’objectif visé
▶ La qualité des données

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 32 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Eléments d’aide au choix de la structure du modèle II

■ La complexité de la structure prendra en compte les contraintes d’uti-

lisation :
▶ Temps de calcul,
▶ Facilité de calage des paramètres :
Complexité de la phase d’optimisation
▶ Nombre de mesures nécessaires. . .
■ La complexité de la structure sera principalement guidée par :
▶ La nature des erreurs de prédiction, de simulation. . .
L’idéal étant que ces erreurs soient indépendantes du phénomène mo-
délisé.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 33 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Eléments d’aide au choix de la structure du modèle III

■ Pour résumer le choix de la structure du modèle, les observations de-

vraient obéir à l’équation symbolique suivante :
▶ Mesure = Modèle + Bruit (indépendant)
▶ Modèle : extrait l’information utile dans la mesure
▶ Bruit : concentre l’information jugée inexplicable par rapport au phéno-
mène modélisé

Exemples
1 Il existe des modèles non-paramétriques mais la plupart du temps les
modèles paramétriques leur sont préférés !
2 Généralement, plus l’amplitude du bruit sera faible, meilleur sera le
modèle

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 34 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Objectif de l’algorithme d’apprentissage I

L’utilisateur ayant choisi une structure de modèle en adéquation avec les

données observées.
On aura 2 étapes dans la méthodologie de « machine learning ».
1 La première est la phase dite d’apprentissage qui consiste à trouver le
« meilleur » modèle c’est-à-dire celui qui falsifie le mieux possible les
données d’apprentissage.
▶ Il doit saisir l’information mais pas le bruit !
2 La seconde est la phase dite de généralisation. Elle consiste à utiliser
un nouveau jeu de données pour mesurer le pouvoir de prédiction du
modèle.
▶ Les performances sur ce nouveau jeu de données doivent être compa-
rables à celles obtenues sur le jeu d’apprentissage.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 35 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Objectif de l’algorithme d’apprentissage II

1 La phase d’apprentissage :
▶ La structure choisie du modèle comporte un certain nombre de para-
mètres. Ceci peuvent être regroupés dans un vecteur souvent dénommé
θ. Cette structure ne doit pas être trop simple, ni trop compliquée. Elle
résultera d’un compromis : biais-variance.
▶ Il s’agit alors trouver la valeur dite « optimale », celle qui permettra au
modèle de se rapprocher « le plus possible » des données d’apprentissage.
▶ Autrement dit, il s’agit de minimiser la perte d’information.
▶ Cette perte d’information est mesurée au moyen d’un critère construit
sur l’erreur entre la mesure et la sortie prédite par le modèle.
2 La phase de généralisation :
▶ Dans le cas de la classification d’images, il s’agira de reconnaître une
image sans que celle-ci ait été dans la base de données d’apprentissage.
C’est tout l’interêt d’un algorithme de « machine learning ».

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 36 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Exemples d’illustration : choix d’une structure de modèles

Cas d’un modèle affine

Données
Modèle affine
200

150
y

100

50

1800 1820 1840 1860 1880 1900 1920 1940 1960 1980
x
Figure 8 – Modèle affine inadapté aux données
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 37 / 277
 Chapitre 1 : Introduction La phase de caractérisation

Exemple d’illustration : choix d’une structure de modèles

Cas d’un modèle polynomial

Données
Modèle poly 2

200

150
y

100

50

1800 1820 1840 1860 1880 1900 1920 1940 1960 1980
x
Figure 9 – Modèle polynomial d’ordre 2 mieux adapté aux données
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 38 / 277
 Chapitre 1 : Introduction La phase de caractérisation

Mesure de la qualité du modèle ? I

Mesure de l’adéquation du modèle aux données ?

La mesure de la perte d’information est généralement construite à partir

d’un critère d’erreur quadratique.
Les algorithmes d’apprentissage utilisent classiquement ce critère dans une
procédure d’optimisation de façon à trouver la valeur « optimale » du vecteur
de paramètres.
■ La valeur dite « optimale » est celle qui permet au modèle de se rap-
procher « le plus possible » des données d’apprentissage au sens du
critère choisi.
■ L’erreur est estimée en calculant la différence entre la mesure et la
valeur donnée par le modèle pour un vecteur de paramètres choisis.
Cette erreur dépend donc des paramètres du modèle.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 39 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Mesure de la qualité du modèle ? II

Mesure de l’adéquation du modèle aux données ?

■ La minimisation, à tout prix, de cette erreur n’est pas la meilleure des

choses puisque les mesures ne sont exactes, elles sont faites avec une
certaine incertitude (bruit de mesure).
■ La phase d’apprentissage revient à résoudre un problème d’optimisa-
tion.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 40 / 277

 Chapitre 1 : Introduction La phase de caractérisation

Qu’est-ce que l’optimisation ? I

Quelques éléments

Pour une structure de modèle choisi et un critère donné, il s’agit de trouver

le jeu de paramètres qui minimisent le critère.
■ Si les paramètres interviennent de façon linéaire dans la structure du
modèle alors le vecteur de paramètres est facilement estimable.
■ Sinon l’estimation du vecteur de paramètres ne peut-être faite que de
façon itérative.
■ Dans ce cas, le critère à minimiser peut comporter des minima mul-
tiples. Il est alors compliqué de trouver le minimum des minima !
■ Une façon de trouver une solution à ce problème d’optimisation est
d’adjoindre un terme ou des termes pour rendre le critère convexe
▶ Il n’y aura alors plus qu’un seul minimum !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 41 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle

Plan du cours I

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

Les étapes d’une démarche classique
Problèmes typiques
Autres modèles
Cas des modèles non-linéaires en les paramètres

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 42 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Les étapes d’une démarche classique

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

Les étapes d’une démarche classique
Problèmes typiques
Autres modèles
Cas des modèles non-linéaires en les paramètres

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 43 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Les étapes d’une démarche classique

Les étapes d’une démarche classique d’analyse de données I

Dans cette section, nous présentons le cas de la régression linéaire.

1 En premier lieu, il faut répondre à la question :
▶ Quelle est la structure de modèle qui est adaptée à mes données ?
▶ Plus précisément : Quelle est la plus simple (la plus parcimonieuse) ?
2 En second lieu, il faut déterminer les paramètres de cette structure :
▶ Choix du critère à minimiser : critères simple ou composite ?
▶ Choix de la technique d’estimation
3 Enfin, il faut valider le modèle obtenu :
▶ La validation est effectuée sur un lot de données qui n’a pas servi à
l’estimation.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 44 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

Les étapes d’une démarche classique
Problèmes typiques
Autres modèles
Cas des modèles non-linéaires en les paramètres

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 45 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques dans le cas d’une régression linéaire I

Première exemple

Mise en évidence des effets d’une sur-paramétrisation du modèle

Comparaison des modèles polynomiaux ordres 2 et 6

Données
Modèle poly 2
Modèle poly 6
200

150
y

100

50

1800 1820 1840 1860 1880 1900 1920 1940 1960 1980
x
Figure 10 – Comparaison des modèles polynomiaux d’ordres 2 et 6
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 46 / 277
 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques dans le cas d’une régression linéaire II

Première exemple
Comparaison résidus des modèles polynomiaux ordres 2 et 6
4

-2

-4

Modèle poly 2
-6
droite zéro
Modèle poly 6

1800 1820 1840 1860 1880 1900 1920 1940 1960 1980
x
Figure 11 – Comparaison des résidus des modèles polynomiaux d’ordres 2 et 6

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 47 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques dans le cas d’une régression linéaire III

Première exemple
Comparaison des prédictions des modèles polynomiaux ordres 2 et 6 - Horizon 2050
450
Données
400 Modèle poly 2
Modèle poly 6
350

300

250
y

200

150

100

50

0
1800 1850 1900 1950 2000 2050
x
Figure 12 – Comparaison des prédictions des modèles d’ordres 2 et 6

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 48 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques dans le cas d’une régression linéaire IV

Première exemple

Conclusion :
■ Le modèle d’ordre 6 colle très bien aux données mais est incapable de
faire des prédictions fiables !
■ Dans le monde du « Machine Learning », on dira aussi que le modèle
d’ordre 6 n’a pas le pouvoir de généraliser !
■ Le modèle d’ordre 2 colle bien aux données et il a la capacité à faire
des prédictions fiables !
■ Dans le monde du « Machine Learning », on dira que le modèle d’ordre
2 a le pouvoir de généraliser !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 49 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques d’une régression linéaire I

Deuxième exemple

Mise en évidence des effets de la sur-paramétrisation

Position du problème
On désire ajuster au mieux un polynôme d’ordre N à un signal sinusoïdal
assez fortement bruité. Sur cet exemple, on teste l’influence de 2 facteurs :
■ L’ordre du polynôme,
■ Le nombre d’observations.

Dans un premier temps, le nombre d’observations Nobs est fixe et égal à 10.
Le RSB est approximativement égal à 6, c’est-à-dire que le signal utile est
6 plus grand en moyenne que le bruit.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 50 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques d’une régression linéaire II

Deuxième exemple
Signal Sinusoïdal Test - Nobs = 10
1.5

1
Amplitude

0.5

-0.5

-1
1

9
0

1
0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 13 – Signal sinusoïdal de test

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 51 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques d’une régression linéaire III

Deuxième exemple

Le modèle recherché est de la forme :

M
X
y (t, θ) = θ0 + θ1 t + θ2 t 2 + . . . + θM t M = θj t j (1)
j=0

A noter que : dim(θ) = M + 1

Le choix de l’ordre (M) est discuté après.

Choisissons a priori un polynôme d’ordre 3. Si les paramètres sont estimés
par la méthode des moindres carrés, on trouve le polynôme suivant :

y (t, θ) = 0.09 + 7.65t − 23.52t 2 + 15.67t 3 (2)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 52 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques d’une régression linéaire IV

Deuxième exemple
Données d'Entraînement (Identification)
Approximation polynomiale - Ordre = 3 - Nobs = 10
1
Mesures
Prédictions

0.5
Amplitude

-0.5
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 14 – Signal sinusoïdal et Modèle d’ordre 3 - Identification

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 53 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Problèmes typiques d’une régression linéaire V

Deuxième exemple
Données de Test (Validation)
Approximation polynomiale - Ordre = 3 - Nobs = 10

0.5
Amplitude

-0.5

Mesures
Estimations
-1
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 15 – Signal sinusoïdal et Modèle d’ordre 3 - Validation

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 54 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Influence de l’ordre du modèle I

Deuxième exemple

Conditions expérimentales
■ On dispose toujours de N observations.
■ Le bruit est inchangé.

Démarche :
■ On cherche différentes approximations en augmentant petit à petit
l’ordre.
■ A chaque fois, les paramètres sont estimés par la méthode des moindres
carrés.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 55 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Influence de l’ordre du modèle II

Deuxième exemple
Données de Test (Validation)
Approximation polynomiale - Nobs = 40
Mesures
1
Ordre=3
0.5 Ordre=6

0
Amplitude

-0.5

-1

-1.5 Ordre = 3 : EQM = 0.12

-2 Ordre = 6 : EQM = 0.40

-2.5
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 16 – Signal sinusoïdal et Modèles d’ordre 3 et 6 - Validation

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 56 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Influence de l’ordre du modèle III

Deuxième exemple
Données de Test (Validation)
Approximation polynomiale - Nobs = 40
Mesures
1.5 Ordre=3

1
Amplitude

0.5

-0.5

-1

-1.5

-2
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 17 – Signal sinusoïdal et Modèle d’ordre 3 et avec ses Incertitudes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 57 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Influence de l’ordre du modèle IV

Deuxième exemple
Données de Test (Validation)
Approximation polynomiale - Nobs = 40

1
Amplitude

-1

-2

-3 Mesures
Ordre=6
-4
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 18 – Signal sinusoïdal et Modèle d’ordre 6 et avec ses Incertitudes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 58 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Influence de l’ordre du modèle V

Deuxième exemple
Données d'Entraînement (Identification)
Influence de l'ordre - Nobs = 10
1
Mesures
Ordre=1
Ordre=3
0.5 Ordre=5
Ordre=7
Amplitude

Ordre=9

-0.5
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 19 – Signal sinusoïdal et Modèles d’ordre 1 à 9

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 59 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Influence de l’ordre du modèle VI

Deuxième exemple
Moyenne des erreurs au carré en fonction de l'ordre du modèle
0.6
Entraînement
Test
0.5

0.4
MSE

0.3

0.2

0.1

0
1 2 3 4 5 6 7 8 9
Ordre du modèle

Figure 20 – Evolution de l’EQM en fonction de l’ordre - Entraînement et Test

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 60 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Influence de l’ordre du modèle VII

Deuxième exemple
Approximation polynomiale - Ordre = 9 - Nobs = 100
Mesures
Estimations
1

0.5
Amplitude

-0.5

-1
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 21 – Signal sinusoïdal et Modèle d’ordre 9 - Entraînement

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 61 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Paramètres estimés des modèles

M=1 M=3 M=5 M=7 M=9
θ̂0 0.77 0.09 0.08 0.03 0.02
θ̂1 -1.70 7.65 2.37 31.22 118.27
θ̂2 -23.51 40.33 -462.92 -2693.9
θ̂3 15.67 -215.25 2960.1 24845
θ̂4 321.69 -9258.7 -1.20e+05
θ̂5 -152.06 14797 3.37e+05
θ̂6 -11640 -5.75e+05
θ̂7 3577.7 5.85e+05
θ̂8 -3.27e+05
θ̂9 77424

Table 1 – Résultats d’estimation en fonction de l’ordre du polynôme - Nobs = 10

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 62 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Compromis Biais-Variance

Figure 22 – Illustration du compromis Biais-Variance

 2
EQM(θ̂) = Biais(θ̂) + Var(θ̂) (3)
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 63 / 277
 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Conclusion par rapport à l’ordre du modèle I

Conclusion
■ Etant donné le nombre d’observations et le niveau de bruit, sans pousser
l’analyse, le résultat obtenu semble satisfaisant !
■ L’observation des graphiques (15) et (17) confirme cette analyse.
■ En validation, le modèle d’ordre 3 donne une variance plus faible que
le modèle d’ordre 6.
■ Les graphiques (16), (17) et (18) montrent clairement qu’un ordre 6
conduit à un phénomène de sur-paramétrisation typique :
▶ Absence de pouvoir de prédiction : le modèle ne donne pas de résultats
satisfaisants.
▶ Si on augmente le nombre d’observations les prédictions divergent !
▶ Les valeurs numériques des paramètres sont grandes et sont connus avec
une grande incertitude.
▶ A noter que le modèle d’ordre 9 est totalement instable !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 64 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Conclusion par rapport à l’ordre du modèle II

Conclusion - Suite
■ Il faut au moins un modèle d’ordre 3 pour avoir un résultat satisfaisant.
■ Un modèle d’ordre trop élevé falsifie trop bien le bruit (Voir figure (19)).
■ Les modèles d’ordre élevé ont des coefficients qui ont de très grandes
valeurs numériques (Voir tableau (1)).
■ Si on regarde les t-valeurs correspondantes à ces coefficients, elles sont
faibles.
■ L’ordre du modèle doit être, notamment, choisi en fonction du nombre
d’observations (Voir figure (21)).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 65 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Code Matlab I

Code Matlab relatif à l’estimation d’un modèle polynomial d’ordre 3 :

%% Génération du signal
A=1;f0=1;
Duree=1;Nobs=10;
Te=Duree/Nobs;fe=1/Te;
t=(0:Nobs−1)'*Te;
y=A*sin(2*pi*f0*t);
rng default; e=randn(Nobs,1); % Pour la reproductibilité
e=(e−mean(e))/std(e); % v.a. centrée réduite
alpha=.3; % facteur permettant d'ajuster le niveau de bruit
yb=y+alpha*e;
%% Estimation
T=table(t,yb); % création d'une table
ordre=3;
nomvar={'$c$','$t$','$t^2$','$t^3$'};
str_ordre=int2str(ordre);
str_modele=['yb~t^' str_ordre]; % Structure du modèle
mdl = fitlm(T,str_modele)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 66 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Paramètres estimés des modèles I

Ordmax=9;
pas=2;
ordre=1;
ermc=zeros(Ordmax,1);
str_leg=cell(ceil(Ordmax/pas)+1,1);
str_leg{1}=['Mesures'];
plot(t,yb,'MarkerSize',8,'Marker','v','MarkerFaceColor','#E0115F','LineStyle','none
','Color','#E0115F','LineWidth',2);% red
grid,hold on
for i=1:pas:Ordmax
str_ordre=int2str(ordre);
str_modele=['yb~t^' str_ordre];
mdl = fitlm(T,str_modele);
ermc(i)=mean((yb−[Link]).^2); % EQM, variance de l'erreur si moyenne nulle
plot(t,[Link],'MarkerSize',6,'LineStyle','−−','LineWidth',1);
str_leg{ceil(i/pas)+1}=['Ordre=' int2str(ordre)];
ordre=ordre+pas;
end
ax1=gca;
[Link]=20;
xlabel('Temps (s)')
ylabel('Amplitude')

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 67 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Problèmes typiques

Paramètres estimés des modèles II

title({['Données d''Entraînement (Identification)'],['Influence de l''ordre − Nobs

= ' int2str(Nobs)]})
xtickangle(45)
legend(str_leg,'Location','Best')
axis tight
hold off

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 68 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Autres modèles

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

Les étapes d’une démarche classique
Problèmes typiques
Autres modèles
Cas des modèles non-linéaires en les paramètres

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 69 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Autres modèles

Modèles décisionnels I
Exemple : les arbres de décision

Contexte
Dans le contexte de la modélisation décisionnelle, par modèle on entend
généralement un modèle construit en utilisant une ou des règles de décision.
■ Prenons l’exemple de la séparation de deux populations : il s’agit de
trouver une frontière qui permettra de séparer les points rouges et les
points verts.
■ Pour chaque observation, la valeur de la variable expliquée est soit
« rouge » soit « vert »,
■ Autrement dit : chaque observation appartient soit à la classe des points
« rouges » ou à celle points « verts »,

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 70 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Autres modèles

Modèles décisionnels II
Exemple : les arbres de décision

■ Le trait bleu est la frontière de discrimination qui sépare (de façon

imparfaite) les points rouges des points verts. Cette frontière est simple
et linéaire. On pourrait envisager des frontières plus complexes, non
linéaires présentant des courbures.
■ Une nouvelle observation est affectée à la classe correspondante en
fonction de sa position par rapport à cette frontière.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 71 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Autres modèles

Modèles décisionnels III

Exemple : les arbres de décision
3
Rouge
Vert
Frontière
2

-1

-2

-3
-3 -2 -1 0 1 2 3 4 5

Figure 23 – Exemple de classification en 2 classes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 72 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Autres modèles

Arbres de décision I

■ Un arbre de décision est un outil d’aide à la décision représentant un

ensemble de choix sous la forme graphique d’un arbre.
■ Cet outil est utilisé dans l’exploration de données et par exemple en
maintenance (arbre de défaillance).
■ Représentation hiérarchique de la structure des données sous forme de
séquences de décision (tests) en vue de la prédiction d’une classe ou
d’un résultat.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 73 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Autres modèles

Arbres de décision II

Type de problèmes solvables

■ Segmentation d’une population d’individus :
▶ Par exemples : clients, images, utilisateurs . . .
■ En classes homogènes selon un ensemble de variables discriminantes :
▶ Par exemples : âge, qualité des images, utilisation du temps . . .
■ En fonction d’un objectif fixé
▶ Variable de sortie
▶ Par exemples : classer des images, reconnaître des caractères manuscrits,
probabilité d’acheter un produit . . .

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 74 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

Les étapes d’une démarche classique
Problèmes typiques
Autres modèles
Cas des modèles non-linéaires en les paramètres

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 75 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Généralités I

Contexte applicatif :

Dans un contexte applicatif d’analyse de données, on est souvent confronté à

des modèles qui font apparaître des modèles non-linéaires en les paramètres.
Ainsi, il n’est plus possible d’utiliser des méthodes dérivées de la méthode
des moindres carrés puisque la sortie ne s’écrit plus sous la forme d’une
régression linéaire comme :
Y = Φ.θ (4)
Il n’existe donc plus de solution explicite, une solution à ce problème d’es-
timation peut-être obtenue de façon itérative au moyen d’algorithmes de
recherche d’un optimimum.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 76 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Généralités II

Principe des techniques d’optimisation :

■ On minimise un critère quadratique fondé sur l’erreur de sortie
■ On ajuste les paramètres du modèle pour obtenir une bonne conformité
entre le modèle et le système
■ On opère de manière itérative (procédure bouclée)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 77 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Généralités III

Avantages :
■ Il existe de nombreux algorithmes de type gradient : méthodes du gra-
dient et dérivés, méthodes de quasi-Newton. . .
■ Dans le cas de modèles dynamiques construits sur des séries tempo-
relles, ces techniques d’optimisation minimisent une erreur de sortie.
Ce type d’erreur est très sensible à une erreur de structure de modèle,
ainsi la minimisation du critère ne sera pas satisfaisante :
▶ Si la structure est mal choisie
▶ Si une ou des entrées sont oubliées
■ Il est possible d’utiliser des modèles décrits à temps discret mais aussi
à temps continu

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 78 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Généralités IV
Inconvénients :
■ Bon nombre d’algorithmes sont construits sur un développement limité.
Ce sont donc des méthodes locales qui nécessitent une bonne initiali-
sation.
■ Les modèles étant non-linéaires en les paramètres, les algorithmes ité-
ratifs sont évidemment gourmands en calculs.
■ Il est également difficile d’obtenir le minimum global car il existe de
nombreux minima locaux (le critère est multimodal).
■ Certains algorithme requiert le calcul de l’inverse du hessien du critère
(dérivée seconde du critère) ce qui peut conduire à des problèmes nu-
mériques : matrice hessienne mal conditionnée.
▶ Ce mauvais conditionnement peut résulter de grandes différences de sen-
sibilité entre les paramètres. Certains paramètres seront estimés avec une
grande incertitude.
▶ Si le modèle choisi est non identifiable, par exemple lorsqu’il comporte
trop de paramètres, alors la matrice hessienne est non inversible.
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 79 / 277
 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Hypothèse I

Soit un modèle non-linéaire par rapport aux paramètres écrit sous la forme
suivante :

y (k, θ) = f (k, θ) où f est une fonction N.L. par rapport à θ (5)

Si on dispose d’une estimation, le modèle s’écrit alors :

ŷ (k, θ̂) = f (k, θ̂) (6)

Au voisinage d’une valeur initiale θ0 :

ŷ (k, θ̂) = ŷ (k, θ0 + δθ)

(7)
≈ ŷ (k, θ0 ) + grad(f (k, θ))T δθ
θ=θ0

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 80 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Hypothèse II

Ou encore :

ŷ (k, θ̂) = ŷ (k, θ0 + δθ)

dim(θ)
X ∂f (k, θ) (8)
≈ ŷ (k, θ0 ) + δθi
i=1
∂θi
θ=θ0

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 81 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Fonction de sensibilité I
Définition

La fonction de sensibilité par rapport au paramètre θi , au point θ0 , est définie

comme :
∂f (k, θ)
σθi (k)|θ=θ0 = (9)
∂θi θ=θ0

Pour des valeurs de δθ faibles, on peut alors utiliser l’estimation suivante :

∂ŷ (k, θ) ŷ (k, θ0 + δθ) − ŷ (k, θ0 )

≈
∂θ θ=θ0 δθ (10)
= grad (f (k, θ)|θ=θ0 = σŷ (k, θ)|θ=θ0

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 82 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Position du problème I

Le critère à minimiser s’écrit de façon classique :

N
(y (k) − ŷ (k, θ))2
X
J(θ) = où N représente le nombre d’observations
k=1
(11)
En supposant que θ est au voisinage de la valeur « vraie » θ⋆ , écrivons un
D.L. au premier ordre :

ŷ (k, θ) = ŷ (k, θ⋆ + δθ) ≈ ŷ (k, θ⋆ ) + σŷT (k, θ⋆ ) δθ

∂ŷ (k, θ) T (12)
≈ ŷ (k, θ⋆ ) + δθ
∂θ θ=θ⋆

Si on suppose que l’on a la bonne structure de modèle alors :

ŷ (k, θ⋆ ) = y (k, θ⋆ ) = y (k) (13)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 83 / 277
 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Position du problème II

Le critère devient alors :

N
(y (k, θ⋆ ) − ŷ (k, θ))2
X
J(θ) =
k=1
(14)
XN h  i2
≈ y (k, θ⋆ ) − y (k, θ⋆ ) + σŷT (k, θ⋆ ) δθ
k=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 84 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Position du problème III

Si le critère est réécrit en fonction de l’erreur, celui-ci devient :
N
(y (k, θ⋆ ) − ŷ (k, θ))2
X
J(θ) =
k=1
N
(ε(k, θ))2
X
=
k=1
XN
= εT (k, θ)ε(k, θ) (15)
k=1
XN
≈ δθT σŷ (k, θ⋆ ) σŷT (k, θ⋆ ) δθ
k=1
N 
X 
≈ δθT σŷ (k, θ⋆ ) σŷT (k, θ⋆ ) δθ
k=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 85 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Position du problème IV

Posons :
N  
(P ⋆ )−1 =
X
σŷ (k, θ⋆ ) σŷT (k, θ⋆ )
k=1

alors le critère est approximé par :

J(θ) ≈ δθT (P ⋆ )−1 δθ (16)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 86 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Position du problème V

Remarque :
■ Le critère est un paraboloïde (si dim(θ)=2) uniquement au voisinage
de l’optimum
■ Si δθ est grand trop grand c’est-à-dire que l’on est trop loin de l’opti-
mum alors la forme est quelconque
■ La matrice (P ⋆ )−1 est une matrice définie positive par construction

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 87 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthodes d’optimisation I
Quelques exemples

Méthodes du premier ordre :

■ Algorithmes du : gradient, Gauss-Siedel . . .
Extension des méthodes du premier ordre :
■ Méthode du gradient conjugué
Méthodes du second ordre :
■ Algorithmes de : Newton, Gauss - Newton, Levenberg - Marquardt . . .
Extension des méthodes du second ordre :
■ Méthodes de quasi-Newton :
▶ Algorithmes de : Davidson - Fletcher - Powell (DFP), Broyden - Fletcher
- Goldfarb - Shanno (BFGS)

Hypothèse :
Le critère est « suffisamment » différentiable à θ
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 88 / 277
 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthodes du gradient I

■ Origine :
▶ 17ème siècle
▶ Fermat
■ Méthode extrêmement simple
■ Méthode à éviter sauf si le critère est relativement « sphérique » :
▶ Sensibilité du même ordre de grandeur dans toutes les directions
■ Méthode intéressante car les problèmes posés se retrouvent dans d’autres
techniques plus sophistiquées

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 89 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthodes du gradient II

Principe :
■ Si on désigne θ ⋆ la solution du problème de minimisation, la méthode
consiste à chercher θ(i) qui converge vers θ⋆
■ L’algorithme est tout d’abord initialisé en choisissant une valeur θ0
■ Développement limité du critère au premier ordre
■ Autour de ce point θ0 , on détermine la ligne de plus grande pente et
on se déplace en sens opposée
■ On cherche un nouveau vecteur θ(1), noté aussi θ1 tel que :

∂J(θ)
θ1 = θ0 + α tel que : ≈0 (17)
∂θ θ=θ1

■ A chaque itération, on cherche un nouveau point sur le même principe

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 90 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthodes du gradient III

Supposons que nous ayons calculé (i) itérations, pour des δθ « suffisamment
» petits, alors au voisinage de J(θ̂(i)), le critère J(θ̂(i + 1)) peut s’écrire :
T
∂J(θ)
J(θ̂(i + 1)) = J(θ̂(i)) + (δ θ̂) + o(∥δ θ̂∥) (18)
∂θ θ=θ̂i

avec
δ θ̂ = θ̂(i + 1) − θ̂(i)
et
∂J(θ)
grad(J(θ)) =
∂θ
On cherche à l’itération (i + 1), une solution telle que :

J(θ̂(i + 1)) < J(θ̂(i)) (19)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 91 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthodes du gradient IV
Il faut donc :
T
∂J(θ)
(δ θ̂) < 0
∂θ θ=θ̂i
T
(20)
∂J(θ)  
ou encore θ̂(i + 1) − θ̂(i) < 0
∂θ θ=θ̂i

Pour garantir la décroissance du critère, il faut donc choisir :

∂J(θ)
θ̂(i + 1) − θ̂(i) = −λ avec λ > 0 (21)
∂θ θ=θ̂i

L’algorithme du gradient est donc donné par :

∂J(θ)
θ̂(i + 1) = θ̂(i) − λ avec λ > 0 (22)
∂θ θ=θ̂i

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 92 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthodes du gradient V

(a) Premier cas (b) Deuxième cas

Figure 24 – Principe de la méthode du gradient

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 93 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthodes du gradient - Aspects pratiques I

Choix du pas λ :
■ Il ne doit pas être trop grand (à cause du D.L.)
■ Il conditionne la vitesse et la convergence
■ Compromis rapidité de déplacement / convergence
Propriétés de l’algorithme du gradient :
■ Algorithme simple, robuste
■ Il possède un grand domaine de convergence
■ Compromis rapidité de déplacement / convergence
■ Convergence de plus en plus lente quand on s’approche du minimum
■ Algorithme adapté pour l’initialisation de la recherche (loin de l’opti-
mum)
Direction de recherche orthogonale à l’iso-critère
■ Méthode bien adaptée si les iso-critères sont « sphériques », c’est-à-dire
hessien du critère bien conditionné !
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 94 / 277
 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Aspects pratiques - Calcul du gradient du critère I

La dérivée première du critère s’écrit :

hP i
N 2 N
∂J(θ) ∂ k=1 (ε(k, θ)) X ∂ε(k, θ)
= =2 ε(k, θ) (23)
∂θ ∂θ k=1
∂θ

N N
X ∂ŷ (k, θ) X
grad (J (θ)) = −2 ε(k, θ) = −2 σŷ (k, θ)ε(k, θ) (24)
k=1
∂θ k=1

Avec :
" #T
∂ŷ (k, θ) ∂ŷ (k, θ) ∂ŷ (k, θ)
σŷ (k, θ) = = ··· dim(θ) = px 1
∂θ ∂θ1 ∂θp
(25)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 95 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Aspects pratiques - Calcul du gradient du critère II

2 techniques de calcul du gradient :

■ Méthode des différences finies
■ Méthode des fonctions de sensibilité

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 96 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul du gradient par différences finies I

Approximation numérique centrée de la dérivée pour des δθi petits :

   
δθi δθi
∂J(θ) J θ1 , · · · , θi + 2 ,··· , θp − J θ1 , · · · , θi − 2 ,··· , θp
≈
∂θi δθi
(26)
Avantages de cette technique de calcul du gradient :
■ Méthode générique : valable quelle que soit la structure du modèle qu’il
soit linéaire ou non par rapport aux paramètres ou aux variables
■ Il est facile de changer l’approximation de la dérivée (gauche ou droite)
Inconvénients de cette technique de calcul du gradient :
■ Le gradient n’est pas calculé de façon exact !
■ Très couteuse en calcul car elle demande 2x dim(θ) simulations du mo-
dèle (au moins dim(θ))

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 97 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul du gradient par différences finies II

■ La qualité de cette approximation dépend du choix de δθi :

▶ Ce choix n’est pas toujours aisé, il est fait p fois !
▶ Une valeur trop grande conduit à une très mauvaise approximation de la
dérivée
▶ Une valeur trop faible peut conduire à des problèmes numériques : nu-
mérateur quasi-nul, déniminateur quasi-nul

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 98 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul du gradient par fonction de sensibilité

Avantages de cette technique de calcul du gradient :

■ Conduit théoriquement à un résultat exact
■ Simple à mettre œuvre dans le cas dans le cas de modèles linéaires par
rapport aux paramètres
■ Demande dim(θ) simulations du modèle
Inconvénients de cette technique de calcul du gradient :
■ Pas de généricité de la méthode, le calcul doit être refait à chaque fois
que le modèle change
▶ Le calcul formel des dérivées du modèle par rapport aux paramètres doit
être réalisé
■ La mise en œuvre engendre généralement des approximations dues à la
simulation numérique du modèle

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 99 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthode de Newton I

Principe :
■ Même principe que le gradient
■ Développement limité du critère au deuxième ordre
■ On approche localement le critère par une « quadrique »
■ L’algorithme est tout d’abord initialisé en choisissant une valeur θ(0)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 100 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthode de Newton II

Supposons que nous ayons calculé (i) itérations, pour des δθ « suffisamment
» petits, alors au voisinage de J(θ̂(i)), le critère J(θ̂(i + 1)) peut s’écrire :
T
    ∂J(θ)
J θ̂(i + 1) = J θ̂(i) + (δ θ̂)
∂θ θ=θ̂i
(27)
1  T ∂ 2 J(θ) 
2

+ δ θ̂ (δ θ̂) + o ∥δ θ̂∥
2 ∂θ2 θ=θ̂i

avec
δ θ̂ = θ̂(i + 1) − θ̂(i)
Posons :
∆J(θ) = J(θ̂(i + 1)) − J(θ̂(i))

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 101 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthode de Newton III

Cherchons le δθ qui conduit à la diminution la plus forte du critère, c’est-à-
dire celle qui conduit à l’annulation de la dérivée par rapport à δθ :

∂ (∆J(θ))
=0
∂ (δθ) δθ=δ θ̂
(28)
∂J(θ) ∂ 2 J(θ)
≈ + (δ θ̂)
∂θ θ=θ̂i ∂θ2 θ=θ̂i

Si le hessien du critère est inversible, il vient alors :

−1
∂ 2 J(θ) ∂J(θ)
δ θ̂ = θ̂(i + 1) − θ̂(i) = −
∂θ2 θ=θ̂i
∂θ θ=θ̂i
−1
(29)
∂ 2 J(θ) ∂J(θ)
θ̂(i + 1) = θ̂(i) −
∂θ2 θ=θ̂i
∂θ θ=θ̂i

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 102 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Propriétés de la méthode de Newton I

■ Nécessite le calcul du hessien et de son inversion à chaque pas :

▶ Calculs lourds
▶ Le calcul exact est rarement mis en œuvre de façon exact
Calcul approché du hessien
■ Le domaine de convergence est plus réduit que dans le cas de la tech-
nique du gradient car rien ne garantit que δθ est petit
■ Si modèle linéaire par rapport aux θ alors le critère est quadratique par
rapport aux θ :
▶ Méthode de Newton est équivalente à un moindres carrés et la méthode
converge en un coup vers l’optimum
■ Proche de l’optimum la convergence est généralement très rapide (≈
5 itérations, loin une vingtaine d’itérations)
■ Elle garantit simplement d’aboutir en un point où la dérivée est nulle,
si pas de problème numérique de calcul

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 103 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Propriétés de la méthode de Newton II

Si le hessien calculé est défini positif, alors son inverse l’est aussi et l’angle
entre les vecteurs gradient et la direction de Newton est inférieure en valeur
absolue à π2 :
* +
∂J(θ) ∂ 2 J(θ) −1 ∂J(θ)
∂θ θ=θ̂ , ∂θ2 θ=θ̂i ∂θ
i θ=θ̂i
= cos(ϕ) > 0 (30)
∂J(θ) ∂ 2 J(θ) −1 ∂J(θ)
∂θ θ=θ̂
i
∂θ2 θ=θ̂i ∂θ
θ=θ̂i

■ En général, la direction de Newton est quelconque par rapport à celle

du gradient
■ Si le hessien est quasi-diagonale alors la direction de Newton et le
gradient sont quasi-colinéaires

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 104 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Propriétés de la méthode de Newton III

■ Elle peut-être quasi-orthogonale à celle du gradient

■ Ainsi, si la méthode de Newton diverge et si on choisit un déplacement
« suffisamment » petit alors le critère diminue
▶ Introduction d’un gain λ(i) dans l’algorithme qui tend vers 1 quand on
est proche de l’optimum

−1
∂ 2 J(θ) ∂J(θ)
θ̂(i + 1) = θ̂(i) − λ(i) (31)
∂θ2 θ=θ̂i
∂θ θ=θ̂i

■ Au voisinage du point de convergence, l’inverse du hessien donne des

informations sur l’incertitude des paramètres :
▶ Il donne un intervalle d’incertitude voire, sous certaines hypothèses, in-
tervalle de confiance

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 105 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul du hessien I

Il faut donc calculer la dérivée seconde du critère

■ On a montré que la dérivée première est donnée par :
N N
∂J(θ) X ∂ε(k, θ) X
=2 ε(k, θ) = −2 σŷ (k, θ)ε(k, θ) (32)
∂θ k=1
∂θ k=1

■ La dérivée seconde s’écrit donc :

N
!
∂ ∂J(θ) ∂
  X
= −2 T σŷ (k, θ)ε(k, θ) (33)
∂θT ∂θ ∂θ k=1

N N
∂ 2 J(θ) X ∂σŷ (k, θ) X ∂ε(k, θ)
T
= −2 T
ε(k, θ) − 2 σŷ (k, θ) (34)
∂θ ∂θ k=1
∂θ k=1
∂θT

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 106 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul du hessien II

Ou encore, en faisant apparaître la dérivée seconde de l’erreur (ou de la

fonction de sensibilité), il vient l’expression :
N N
∂ 2 J(θ) ∂ ∂ε(k, θ)
X   X
T
= 2 ε(k, θ) + 2 σŷ (k, θ)σŷT (k, θ) (35)
∂θ ∂θ k=1
∂θT ∂θ k=1

■ Les dérivées première et seconde des fonctions de sensibilité appa-

raissent :
▶ Il y a donc nécessité de les évaluer pour un calcul exact du hessien
▶ Il faut calculer dim(θ)x dim(θ)/2 dérivées. La division par 2 est liée à
l’exploitation de la symétrie de la matrice hessienne.
Les calculs à effectuer sont très lourds et coûteux surtout si la dimension
du vecteur θ est importante !
Il peut-être intéressant de trouver une approximation du hessien qui mi-
nimise ces calculs

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 107 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul approché du hessien I

Quelques éléments de justification :

■ Le calcul exact ne garantit pas la condition de positivité. Or, si cette
condition n’est pas assurée à chaque itération, la convergence vers un
optimum n’est pas garantie
■ En effet, dans le cas d’un modèle N.L. par rapport aux paramètres, le
critère n’est pas quadratique. Il peut être considéré comme tel seule-
ment au voisinage de l’optimum
■ Les dérivées des fonctions de sensibilité sont négligeables au voisinage
de l’optimum :
▶ Si les erreurs de sortie ε(k, θ) sont petites
▶ Si les erreurs ε(k, θ) sont blanches et si le nombre d’observations est
relativement « grand »
■ Le calcul approché du hessien repose sur celui des fonctions de sensi-
bilité

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 108 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthode de Gauss-Newton - Calcul approché du hessien I

Principe :
■ Version simplifiée de la méthode de Newton
La simplification repose sur :
■ Le calcul approché du hessien en négligeant les dérivées secondes des
fonctions de sensibilité
■ Ainsi, le hessien approché est calculé à l’aide des dérivées premières des
fonctions de sensibilité
■ Et, le hessien approché est défini positif par construction
π
cos(ϕ) > 0 donc |ϕ| < (36)
2

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 109 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthode de Gauss-Newton - Calcul approché du hessien II

■ Si le pas est choisi « suffisamment » petit, on garantit que le critère

diminue    
J θ̂(i + 1) < J θ̂(i) (37)

Notons Ha le hessien approché du critère. Etant donné l’équation (35), il

vient :
N
∂ 2 J(θ) X
Ha (θ) ≈ T ≈2 σŷ (k, θ)σŷT (k, θ) (38)
∂θ ∂θ k=1

La remise à jour de l’estimation est donc donnée par :

∂J(θ)
θ̂(i + 1) = θ̂(i) − λ(i) Ha (θ)|−1
θ=θ̂
(39)
i ∂θ θ=θ̂i

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 110 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Méthode de Levenberg - Marquardt I

Méthode pouvant utiliser le calcul approché du hessien

Principe :
■ Cet algorithme allie les méthodes du gradient et de Newton (ou Gauss-
Newton)
La remise à jour de l’estimation du vecteur θ est donc donnée par :
 −1
∂ 2 J(θ) ∂J(θ)
θ̂(i + 1) = θ̂(i) −  + µ(i)I  (40)
∂θ2 θ=θ̂i
∂θ θ=θ̂i

Mise en œuvre :
■ Le hessien est généralement calculé de manière approchée
■ Initialement, on choisit µ(i) grand

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 111 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Avantages de la Méthode de Levenberg - Marquardt I

■ Combine les avantages des 2 techniques :

▶ Loin de l’optimum, c’est à dire µ(i) est grand
L’algorithme se comporte comme une technique de gradient
▶ Proche de l’optimum, c’est à dire µ(i) est petit
L’algorithme se comporte comme une technique de Newton
■ Régularise les problèmes mal posés en évitant la singularité du hessien
si µ(i) différent de 0
■ Particularités :
▶ Politique d’adaptation du pas µ(i) identique à celle de l’algorithme du
gradient
▶ Le pas µ(i) doit toujours être maintenu différent de 0 pour éviter que le
hessien devienne singulier

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 112 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Qualité de l’estimation fournie par les algorithmes

d’optimisation ? I
Précision de l’estimation du vecteur θ

Hypothèses
■ Supposons que les mesures soient entachées d’un bruit blanc de va-
riance connue σε2 .
■ Supposons qu’à l’issue de l’estimation, on obtienne une erreur de simu-
lation qui soit également un bruit blanc donc une estimation de σε2 .

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 113 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Qualité de l’estimation fournie par les algorithmes

d’optimisation ? II
Précision de l’estimation du vecteur θ

■ Sous ces hypothèses, le critère s’écrit alors :

N
(y (k, θ⋆ ) − ŷ (k, θ))2
X
J(θ) =
k=1
N
(ε(k, θ))2
X
= (41)
k=1
N
1 X
= Nσε2 avec σε2 = (ε(k, θ))2
N k=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 114 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Qualité de l’estimation fournie par les algorithmes

d’optimisation ? III
Précision de l’estimation du vecteur θ

■ Conséquences :
▶ L’optimisation ne doit donc surtout pas chercher à obtenir un critère
inférieur à cette valeur Nσε2
▶ Ainsi, plus le bruit sera important plus le critère sera grand
▶ Le lieu des θ tels que :

J(θ) ≤ χ25% (N) loi du χ2 N degrés de liberté (42)

Ce lieu fournit une région de confiance à 95% pour le vecteur θ

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 115 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ I

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Supposons que le bruit perturbe la mesure de la façon suivante :

y (k) = yd (k) + v (k) (43)

Avec
▶ yd (k) : la mesure non bruitée (variable déterministe)
▶ v (k) : un bruit quelconque (blanc ou coloré) à moyenne nulle
■ Soit θ une valeur qui diffère de la valeur « vraie » θ ⋆ de la quantité δθ :

θ = θ⋆ + δ θ̂ (44)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 116 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ II

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Pour la sortie non bruitée, l’expression linéarisée s’écrit :

∂yd (k, θ) T
yd (k, θ) = yd (k, θ⋆ + δθ) ≈ yd (k, θ⋆ ) + δθ
∂θ θ=θ⋆ (45)
≈ yd (k, θ⋆ ) + σyTd (k, θ⋆ ) δθ

■ De la même manière, pour la sortie du modèle linéarisé par rapport à

θ, on a :

∂ŷ (k, θ) T
ŷ (k, θ) = ŷ (k, θ⋆ + δθ) ≈ ŷ (k, θ⋆ ) + δθ
∂θ θ=θ⋆ (46)
≈ ŷ (k, θ⋆ ) + σŷT (k, θ⋆ ) δθ

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 117 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ III

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Si on suppose que l’on a la bonne structure de modèle alors :

ŷ (k, θ⋆ ) = yd (k, θ⋆ ) = yd (k) et σŷT (k, θ⋆ ) = σyTd (k, θ⋆ ) (47)

■ Ainsi, l’erreur de simulation prend la forme :

ε(k, θ) = y (k) − ŷ (k, θ) = yd (k) + v (k) − ŷ (k, θ)

 
≈ yd (k) + v (k) − ŷ (k, θ⋆ ) + σŷT (k, θ⋆ ) δθ (48)
≈ v (k) − σŷT (k, θ⋆ ) δθ

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 118 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ IV

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Le critère devient alors :

N
(ε(k, θ))2
X
J(θ) =
k=1
N
(ε(k, θ))T (ε(k, θ))
X
= (49)
k=1
XN  T  
≈ v (k) − σŷT (k, θ⋆ ) δθ v (k) − σŷT (k, θ⋆ ) δθ
k=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 119 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ V

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ A noter que : σŷT (k, θ ⋆ ) δθ = δθ T σŷ (k, θ ⋆ ) est un scalaire

N N
(v (k))2 − 2
X X
J(θ) ≈ δθT σŷ (k, θ⋆ ) v (k)
k=1 k=1
N
!
X
T ⋆
+ δθ σŷ (k, θ ) σŷT ⋆
(k, θ ) δθ (50)
k=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 120 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ VI

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ On cherche à minimiser le critère par rapport au vecteur θ :

∂J(θ)
=0 (51)
∂θ
N N
!
∂J(θ) X X
= −2 σŷ (k, θ⋆ ) v (k) + 2 σŷ (k, θ⋆ ) σŷT (k, θ⋆ ) δθ
∂θ k=1 k=1
(52)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 121 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ VII

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

P 
N
■ Si k=1 σŷ (k, θ⋆ ) σŷT (k, θ⋆ ) est inversible alors :

N
!−1 N
X X
⋆ ⋆
δθ = θ̂ − θ = σŷ (k, θ ) σŷT ⋆
(k, θ ) σŷ (k, θ⋆ ) v (k)
k=1 k=1
!−1 N (53)
N
X X
θ̂ = θ⋆ + σŷ (k, θ⋆ ) σŷT (k, θ⋆ ) σŷ (k, θ⋆ ) v (k)
k=1 k=1

■ Cas no 1 : idéal - irréaliste

▶ Les données sont pures déterministes

v (k) = 0 ∀k alors θ̂ = θ⋆ (54)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 122 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de l’erreur d’estimation sur le vecteur θ VIII

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Cas no 2 : Les données sont bruitées

▶ v (k) est un bruit quelconque (blanc ou coloré) de moyenne nulle et de
variance σ 2
▶ Calculons le biais :
Sachant que le modèle est déterministe, il vient :
N
!−1 N
X X
E(θ̂) = θ⋆ + σŷ (k, θ⋆ ) σŷT (k, θ⋆ ) σŷ (k, θ⋆ ) E(v (k))
k=1 k=1
(55)
∂ŷ (k, θ)
Avec σŷ (k, θ⋆ ) = (56)
∂θ θ=θ ⋆

L’estimateur est alors non biaisé :

E(θ̂) = θ⋆ (57)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 123 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de la variance d’estimation du vecteur θ I

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Par définition, la variance du vecteur θ est donnée :

  T 
Var(θ̂) = E θ̂ − E(θ̂) θ̂ − E(θ̂) (58)

■ Supposons que l’estimateur soit non biaisé, alors : E(θ̂) = θ ⋆

■ Supposons que l’estimation de θ s’écrive : θ̂ = θ ⋆ + δθ
■ La variance du vecteur θ devient :
 
Var(θ̂) = E δθδθT (59)
P 
N
■ Posons : H(θ ⋆ ) = k=1 σŷ (k, θ⋆ ) σŷT (k, θ⋆ )

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 124 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de la variance d’estimation du vecteur θ II

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Alors δθ s’écrit :
N
δθ = H(θ⋆ )−1
X
σŷ (k, θ⋆ ) v (k) (60)
k=1

■ La variance du vecteur θ devient :

  N
E δθδθT = E H(θ⋆ )−1
X
σŷ (k, θ⋆ ) v (k)
k=1
 T 
N
H(θ ⋆ )−1
X
σŷ (j, θ⋆ ) v (j)  (61)

j=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 125 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de la variance d’estimation du vecteur θ III

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

  N
⋆ −1
X
T
E δθδθ = E H(θ ) σŷ (k, θ⋆ ) v (k)
k=1

N
σŷT (j, θ⋆ ) H(θ⋆ )−T  (62)
X
v (j)T
j=1

■ Le modèle étant déterministe et H(θ ⋆ ) symétrique, la variance du vec-

teur θ s’écrit :
N  
Var(θ̂) = H(θ⋆ )−1
X
σŷ (k, θ⋆ ) E v (k)v (j)T
k=1
N
σŷT (j, θ⋆ ) H(θ⋆ )−1 (63)
X

j=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 126 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de la variance d’estimation du vecteur θ IV

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Si le bruit v (k) est un bruit blanc (e(k)) indépendant et identiquement

distribué (i.i.d.) alors :
 
E v (k)v (j)T = 0 ∀k ̸= j (64)
 
E v (k)v (j)T = σe2 ∀k = j (65)

■ Si l’estimateur n’est pas biaisé, la variance du vecteur θ prend l’expres-

sion simplifiée suivante :

Var(θ̂) = σe2 H(θ⋆ )−1 (66)

N
!−1
X
= σe2 σŷ (k, θ⋆ ) σŷT (k, θ⋆ ) (67)
k=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 127 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de la variance d’estimation du vecteur θ V

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

■ Or, l’équation du hessien approché est donnée par :

N
X
Ha (θ̂) ≈ 2 σŷ (k, θ̂)σŷT (k, θ̂) (68)
k=1

■ En pratique l’erreur de simulation est inconnue, elle doit être remplacée

par son estimation. Une approximation de la variance de θ̂ est alors
obtenue :

J(θ̂)
Var(θ̂) ≈ 2σ̂e2 Ha (θ̂)−1 avec σ̂e2 = (69)
N − dim(θ)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 128 / 277

 Chapitre 2 : Démarche classique de recherche d’un modèle Cas des modèles non-linéaires en les paramètres

Calcul de la variance d’estimation du vecteur θ VI

Cas d’un modèle déterministe non linéaire par rapport aux paramètres θ

Remarque
■ Cette estimation a été obtenue à partir d’hypothèses réductrices :
▶ Critère linéarisé autour de l’optimum
▶ Erreur d’estimation assimilable à un bruit blanc
▶ Hessien calculé de façon approchée

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 129 / 277

 Chapitre 3 : Cadre de l’apprentissage

Plan du cours I

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

Spécificités d’une démarche d’apprentissage
Comment réaliser l’étape de validation croisée ?
Comment choisir une structure de modèle ?

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 130 / 277

 Chapitre 3 : Cadre de l’apprentissage Spécificités d’une démarche d’apprentissage

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

Spécificités d’une démarche d’apprentissage
Comment réaliser l’étape de validation croisée ?
Comment choisir une structure de modèle ?

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 131 / 277

 Chapitre 3 : Cadre de l’apprentissage Spécificités d’une démarche d’apprentissage

Spécificités d’une démarche d’apprentissage I

Contrairement à l’approche classique, la recherche de la structure de modèle

doit être automatisée !
■ Il faut donc détecter cette sur-paramétrisation !
■ Comment ?
▶ En ajoutant au critère classique de régression un terme pénalisant la
complexité du modèle,
Ces techniques sont également connues sous le vocable : techniques de
régularisation.
▶ Il s’agit de réaliser un compromis entre l’« erreur » et la complexité du
modèle,
▶ Cette règle est appelée classiquement « le rasoir d’Occam » ou principe
de simplicité, principe d’économie ou encore principe de parcimonie.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 132 / 277

 Chapitre 3 : Cadre de l’apprentissage Spécificités d’une démarche d’apprentissage

Spécificités d’une démarche d’apprentissage II

 
θ̂ = arg min Ê[ℓ(Y , θ(X ))] + λΩ(θ) (70)
θ∈Rdim(θ) | {z } | {z }
Terme d’erreur Pénalisation

Remarques :
1 Ces approches existent aussi dans le cadre usuel de l’analyse de données.
2 Les techniques construites sur ce type de critère composite donnent
naissance à plusieurs classes de méthodes :
▶ Les techniques regroupées sous le terme de « ridge regression » ou de
Tikhonov,
▶ Les techniques regroupées sous le vocable « lasso »,
▶ Les techniques regroupées sous le vocable « Elastic Net ».

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 133 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

Spécificités d’une démarche d’apprentissage
Comment réaliser l’étape de validation croisée ?
Comment choisir une structure de modèle ?

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 134 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Partitionnement du jeu de données I

L’objectif de cette phase est de s’assurer que :

■ Notre modèle ne souffre pas de sur-apprentissage,
■ Il est capable d’effectuer des prédictions sur de nouvelles données avec
des performances comparables à celles obtenues lors de l’apprentissage.
Classiquement, le jeu de données est scindé en 2 parties inégales. Pour la
totalité de ce jeu de données, les données sont « labellisées ».
■ La première partie sert à la phase d’entraînement. A l’aide de ces don-
nées, l’algorithme « extraira » les caractéristiques des données : le mo-
dèle sera estimé ou l’algorithme segmentera ou classifiera les données.
■ La seconde est exploitée dans l’étape dite de test. Ce lot de données
permettra de détecter un éventuel sur-apprentissage. La mesure de per-
formance est possible car les données de test sont expertisées.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 135 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Partitionnement du jeu de données II

■ Un découpage classique consiste à prendre 80% des données pour

l’étape d’entraînement et les autres 20% pour la phase de test. Mais,
un découpage 70% et 30% peut également constituer une solution ! En
fonction de la taille des données disponibles, l’organisation diffère.
1 Si on a suffisamment de données, on peut utiliser les données de façon
classique.

Figure 25 – Validation classique

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 136 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Partitionnement du jeu de données III

2 Si on a moins de données, on subdivise alors l’apprentissage en 2 parties.

Figure 26 – Validation croisée à plis

■ Cette opération de découpage est une opération importante qui doit

être faite avec soin car elle conditionnera la qualité des résultats des
étapes en aval.
▶ La division en 2 lots de données doit notamment assurer la présence de
toutes les caractéristiques des données dans chacun des lots.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 137 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Partitionnement du jeu de données IV

▶ Même en respectant cette contrainte, il est possible que le partionnement

ne soit pas pertinent.
■ Pour améliorer l’exploitation du lot de données initiales et pour limiter
l’effet du partionnement arbitraire, le jeu de données est découpé en k
parties (ou plis) à peu près égales (en anglais : folds).
▶ Chacune des parties jouant, tour à tour, le rôle de données d’entraîne-
ment et de test.
▶ Chacune des parties est successivement jeu de test (1 seule fois) puis jeu
d’entraînement ((k − 1) fois).
1 La première partie est utilisée, par exemple, en validation (test), les autres
parties sont alors prises pour la phase d’entraînement.
2 Ensuite, la seconde partie est utilisée en validation et les autres sont alors
prises pour la phase d’entraînement.
3 Ainsi, de suite jusqu’à arriver à la dernière partie qui est prise pour la
validation alors que les (k − 1) premières partitions sont exploitées pour
l’entraînement.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 138 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Principe de la validation croisée à plis I

Le jeu de données est partitionné en k parties (ou plis).
Test Entraînement

erreur_1

Test

erreur_2

Test
erreur_3

Test
erreur_4

e=Serreur_k/Ncamp
Figure 27 – Validation croisée à 4 plis (k = 4 folds)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 139 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Avantages et résumé de la validation croisée I

La validation croisée assure une utilisation optimale de notre jeu de données

pour l’entraînement et pour la validation !
Avec cette manière de faire, on évite une évaluation unique (un jeu de test
unique) qui pourrait conduire à valider un modèle biaisé. A la fin de cette
étape :
■ Chaque observation (ou individu) a été utilisée 1 fois dans un jeu de
test, (k − 1) fois dans un jeu d’entraînement.
■ On a donc 1 prédiction par point du jeu initial,
■ Le principe même de la validation est respecté puisqu’aucune de ces
prédictions n’a été réalisée avec un jeu d’entraînement qui contient
cette observation.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 140 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Avantages et résumé de la validation croisée II

■ Cette méthode permet de réduire l’effet du découpage arbitraire des

données en données d’apprentissage et de test.
■ Etant donné que les observations sont « labellisées », ces prédictions
permettent de mesurer la performance de mon modèle.

Inconvénients :
■ Cette méthode induit l’évaluation de multiples modèles ce qui entraîne
une charge supplémentaire de calcul.
■ Malheureusement, cette approche ne peut pas s’appliquer à des jeux
de données qui contiendraient des séries temporelles !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 141 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Validation croisée - Cas de la classification I

Problème spécifique

La création de partitions, dans un problème de classification, doit être réa-

lisée en prenant en compte la présence de toutes les classes dans toutes les
partitions :
■ On s’évertue donc à construire k partitions qui contiennent chacune
la même proportion d’individus de chaque classe que dans le jeu de
données complet.

M M M M M

M M M M M

Figure 28 – Validation croisée - Cas de la classification

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 142 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment réaliser l’étape de validation croisée ?

Validation croisée - Cas de la classification II

Problème spécifique

Remarque :
Souvent, les jeux de données présentent un déséquilibre entre les classes.
Pour pallier ce problème, il est possible d’utiliser une méthode de rééchan-
tillonnage pour créer un jeu équilibré de données.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 143 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

Spécificités d’une démarche d’apprentissage
Comment réaliser l’étape de validation croisée ?
Comment choisir une structure de modèle ?

4 Chapitre 4 : Méthodes d’apprentissage

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 144 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Comment choisir le bon modèle ? I

Nature du problème à résoudre

Une des premières questions à se poser :

■ S’agit-il d’un problème de régression ou de classification ?
▶ Prédire la température d’un four.
▶ Reconnaître des objets.
Nature de la variable à prédire :
■ S’agit-il d’une variable qualitative ou quantitative ?
▶ Prédire le confort d’un siège.
▶ Prédire la température d’un four.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 145 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Comment choisir le bon modèle ? II

Nature du problème à résoudre

Il faut choisir une structure de représentation « assez » simple :

■ Permettant d’aboutir à de « bons » résultats au cours de la phase
d’apprentissage.
■ Mais, il faut surtout que celle-ci donne également de « bons » résultats
lors de la phase de généralisation.
■ Les modèles qui correspondent à ce choix sont des modèles qui res-
pectent un compromis biais-variance, c’est-à-dire :
▶ Des modèles pas trop « simples » (dont le biais sera important) ne
permettront pas de capturer les caractéristiques principales des données.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 146 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Comment choisir le bon modèle ? III

Nature du problème à résoudre

▶ Des modèles pas trop « compliqués » (dont la variance sera grande)

falsifieront trop bien les données si bien qu’ils capteront également des
informations (une partie du bruit, par exemple) qui ne sont pas caracté-
ristiques des données.
▶ Dans ces 2 cas, les modèles conduiront à de mauvais résultats dans la
phase de généralisation. Le premier à cause d’une sous-paramétrisation
(sous-apprentissage) et le second à cause d’une sur-paramétrisation (sur-
apprentissage).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 147 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Comment choisir le bon modèle ? IV

Nature du problème à résoudre

Figure 29 – Choix du nombre de paramètres d’un modèle pour une classe donnée
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 148 / 277
 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Comment choisir le bon modèle ? I

Y-a-t-il une seule structure ? La vraie ?

Quand on a trouvé un premier modèle, des questions peuvent se poser :

■ Est-il unique ?
▶ Est-il possible d’en trouver un autre ?
■ Est-ce le meilleur ?
▶ Peut-on trouver un autre modèle plus performant ?
■ Comment choisir le « bon » ?
▶ Le bon modèle existe-t-il ?
▶ Le « vrai » modèle existe-t-il ?
■ Les hypothèses faites sont-elles les bonnes ?

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 149 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Comment choisir le bon modèle ? II

Y-a-t-il une seule structure ? La vraie ?

Que se passe-t-il si on change les hypothèses ?

■ Par exemple, si on choisit une structure plus complexe :
▶ Un modèle polynomial d’ordre plus élevé ?
▶ Un modèle non-linéaire par rapport aux variables ?
▶ Un modèle non-linéaire par rapport aux paramètres ?
■ Si une ou des variables explicatives supplémentaires sont ajoutées ?
■ Toutes ces hypothèses peuvent (et devraient !) être explorées.
■ Généralement, les problèmes d’apprentissage correspondent à des pro-
blèmes mal posés.
▶ Ce sont des problèmes qui n’ont pas une solution unique.
▶ Pour les résoudre, on est amené à apporter de l’information (contraintes
ou hypothèses complémentaires) pour que le problème ait une solution.
▶ Par exemple, par le choix a priori d’une structure de modèle.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 150 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

Comment choisir le bon modèle ? III

Y-a-t-il une seule structure ? La vraie ?

Trouver la configuration la plus pertinente, en terme de performances, re-

vient du coup à tester les différents éléments :
■ Structures différentes,
■ Régressions linéaire ou non-linéaire,
■ Tests de divers algorithmes.
D’autres éléments doivent être pris en compte pour mettre en œuvre le
modèle et l’algorithme choisis :
■ Le temps de calcul,
■ La mémoire nécessaire.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 151 / 277

 Chapitre 3 : Cadre de l’apprentissage Comment choisir une structure de modèle ?

En résumé par rapport aux algorithmes d’apprentissage I

Corollaire
Les algorithmes d’apprentissage (machine learning) sont construits en ex-
ploitant différents champs disciplinaires :
■ Les statistiques,
■ La théorie de l’optimisation,
■ L’analyse numérique : stabilité numérique, méthodes numériquement
efficaces

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 152 / 277

 Chapitre 4 : Méthodes d’apprentissage

Plan du cours I

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

Organisation des données
Maximum de vraisemblance
Les méthodes de régularisation
La régression logistique
Les méthodes ensemblistes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 153 / 277

 Chapitre 4 : Méthodes d’apprentissage Organisation des données

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

Organisation des données
Maximum de vraisemblance
Les méthodes de régularisation
La régression logistique
Les méthodes ensemblistes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 154 / 277

 Chapitre 4 : Méthodes d’apprentissage Organisation des données

Organisation des données : Structure classique des données

Individus (ou Variables (ou caractères)

Observations) X1 X2 ··· Xk ··· Xp

1 x11 x12 ··· x1k ··· x1p

2 x21 x22 ··· x2k ··· x2p

.. .. .. .. .. ..
. . . . . .

i xi1 xi2 ··· xik ··· xip

.. .. .. .. .. ..
. . . . . .

N xN1 xN2 ··· xNk ··· xNp

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 155 / 277

 Chapitre 4 : Méthodes d’apprentissage Organisation des données

Organisation des données : Structure des données (suite)

A quoi correspond la valeur xik ?

■ Elle correspond à la ligne i ième et la k ième .
■ C’est donc la i ième observation de la k ième variable.
■ Ou dit autrement : C’est la valeur prise par la k ième variable lors de la
i ième observation.
■ Ou encore dit autrement : C’est la valeur prise par la k ième variable
pour le i ième individu.
■ Généralement le nombre d’observations N est beaucoup plus grand que
le nombre de variable p.
■ Ce tableau de données est généralement transformé en matrice, elle
porte alors le nom de matrice d’observations ou simplement de données.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 156 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

Organisation des données
Maximum de vraisemblance
Les méthodes de régularisation
La régression logistique
Les méthodes ensemblistes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 157 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Démarche exploitant le maximum de vraisemblance I

Cas du maximum de vraisemblance

D’autres méthodes d’estimation s’appuient sur la statistique.

■ La maximisation de la vraisemblance (Maximum Likelihood Estimation)
en est un exemple.
■ Cette technique est fondée sur les probabilités : on cherche la valeur
d’un vecteur de paramètres θ pour lequel il est le plus vraisemblable
d’observer le jeu de données {Y , X } où Y désigne la variable de sortie
et X la matrice des variables explicatives.
■ La vraisemblance décrit la plausibilité d’une valeur des paramètres d’un
modèle, étant donné l’observation d’un certain nombre de réalisations
d’une variable aléatoire.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 158 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Démarche exploitant le maximum de vraisemblance II

Cas du maximum de vraisemblance

▶ La fonction de vraisemblance L ({Y , X } , θ) d’un jeu de N observa-

tions (N lignes) composant la matrice (ou le vecteur) Y , notée Y =
{y (1), y (2), · · · , y (N)}, par rapport à un modèle donné, est définie par
la fonction suivante :

L ({Y , X } , θ) = P ({Y , X } |θ) (71)

avec

Y = {y (1), y (2), · · · , y (N)} (72)

n o
X = x (1) , x (2) , · · · , x (N) (73)

x (i) : représente la i ème ligne de la matrice d’observations.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 159 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Démarche exploitant le maximum de vraisemblance III

Cas du maximum de vraisemblance

Ou dit autrement :
▶ Cette valeur représente la probabilité d’avoir le jeu d’observations {Y , X }
sachant le vecteur de paramètres θ.
■ Objectif de l’algorithme : il doit trouver la valeur du vecteur θ qui assure
la maximisation de la fonction de vraisemblance sur le jeu d’observa-
tions Y considéré.
▶ On cherche donc la valeur du vecteur de paramètres θ telle que la pro-
babilité P ({Y , X } |θ) soit maximale.
θ̂ = arg max {L ({Y , X } , θ)} (74)
θ

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 160 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Lien entre maximum de vraisemblance et moindres carrés I

■ Mathématiquement, sous des hypothèses de normalité (des erreurs, du

bruit), maximiser la vraisemblance est en fait équivalent à minimiser la
fonction quadratique de l’erreur.
■ Hypothèse usuelle : on suppose que les observations sont indépendantes
et identiquement distribuées.
▶ L’indépendance des observations permettra d’écrire :
nn o n oo  Y N n o 
P y (1), x (1) , · · · , y (N), x (N) |θ = P y (i), x (i) |θ
i=1
(75)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 161 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Lien entre maximum de vraisemblance et moindres carrés II

Rappel : produit de probabilité conditionnelle

Notation : la probabilité d’avoir les événements A et B sachant C est notée
P ({A, B} |C )
Règle du produit :

P ({A, B} |C ) = P (A| {B, C }) .P (B|C ) (76)

= P (B| {A, C }) .P (A|C ) (77)

▶ Par définition, la probabilité conditionnelle s’écrit :

n o   n o  
P y (i), x (i) | θ = P y (i)| x (i) , θ .P x (i) |θ (78)

■ Il faut trouver la valeur de θ qui maximise l’équation (74).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 162 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Lien entre maximum de vraisemblance et moindres carrés

III

   
■ Or, si on suppose que x (i) ne dépend pas de θ alors P x (i) |θ = P x (i) ,
le vecteur θ cherché se réduit donc à la maximisation du premier terme
de l’équation (78) :
(N )
Y  n o
(i)
θ̂ = arg max P y (i)| x ,θ (79)
θ
i=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 163 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Lien entre maximum de vraisemblance et moindres carrés

IV

■ Etant donné que l’on a un produit et que le logarithme est une fonction
monotone croissante,les calculs se simplifient et c’est le logarithme de
cette fonction qui sera maximisé.
(N )
X   n o
θ̂ = arg max ln P y (i)| x (i) , θ (80)
θ
i=1

■ Si on ajoute l’hypothèse de normalité (des erreurs, du bruit), e ∼ N 0, σ 2

avec σ connu, alors maximiser le logarithme de la vraisemblance est

équivalent à minimiser la fonction quadratique de l’erreur.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 164 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Interprétations des résultats fournis par les techniques de

moindres carrés I
Cas des modèles linéaires

Ces techniques peuvent également apparaître dans la littérature sous le

terme de régression linéaire.

Interprétations simples :
■ Si on travaille sur des variables mises à l’échelle, par exemple, centrées
et réduites, la lecture des résultats en est simplifiée.
■ Si les variables introduites dans le modèle sont indépendantes (les unes
des autres).
▶ La valeur des coefficients reflète directement la contribution de chacune
des variables vis à vis de la grandeur à prédire.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 165 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Interprétations des résultats fournis par les techniques de

moindres carrés II
Cas des modèles linéaires

▶ Les variables qui sont affectées de grandes valeurs de coefficients corres-

pondent aux variables prépondérantes.
Elles sont indispensables à une bonne prédiction de la variable à expli-
quer !
▶ Les variables qui sont associées à de petites valeurs de coefficients cor-
respondent aux variables peu influentes.
Sont-elles vraiment utiles ?

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 166 / 277

 Chapitre 4 : Méthodes d’apprentissage Maximum de vraisemblance

Les limitations de ces techniques I

Les problèmes classiques :

■ La recherche du vecteur θ est délicate lorsque le modèle intègre des
variables corrélées entre-elles.
▶ Le modèle comporte alors trop de variables,
▶ On parle alors de sur-paramétrisation !
■ La solution n’est pas unique lorsque le nombre de variables est plus
grand que le nombre d’observations.
La solution classique :
■ Ajout d’un terme de régularisation (terme de pénalité).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 167 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

Organisation des données
Maximum de vraisemblance
Les méthodes de régularisation
La régression logistique
Les méthodes ensemblistes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 168 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation I

Choix de l’hyperparamètre : λ

Rappel : le critère a la forme suivante :

 
θ̂ = arg min Ê[ℓ(Y , θ(X ))] + λΩ(θ) (81)
θ∈Rdim(θ) | {z } | {z }
Terme d’erreur Pénalisation

Un choix de la valeur du paramètre de pénalité doit être fait, contrairement

à l’approche classique.
■ Ce paramètre permet de régler le poids relatif des termes composant
le critère :
▶ Terme d’erreur de prédiction
▶ Terme de pénalisation

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 169 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation II

Choix de l’hyperparamètre : λ

■ Comment doit-il être choisi ?

▶ Si la valeur de λ augmente, le terme de pénalisation prend plus d’impor-
tance et la solution θ̂ tend vers 0.
On accepte alors d’avoir une augmentation du critère construit sur l’er-
reur de prédiction.
▶ De façon symétrique, si la valeur de λ diminue, le terme relatif à l’erreur
de prédiction prend plus d’importance.
On accepte d’avoir un terme de pénalité plus «important».
Une valeur nulle de λ correspond à une régression classique.

Rôle de l’hyperparamètre :
■ Ce paramètre de régularisation permet de faire un compromis entre les
2 termes du critère composite.
■ De façon équivalente, ce paramètre permet contrôler les poids relatifs
des 2 termes du critère composite.
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 170 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Compromis Biais - Variance I

Parcimonie

Figure 30 – Critère composite : Compromis Biais - Variance

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 171 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation I

Choix de la fonction de pénalité Ω(θ)

Il existe plusieurs fonctions de pénalité.

1 La plus classique consiste à minimiser la norme 2 du vecteur paramètre
θ, la fonction de pénalité est donnée par :

dim(θ)
X
Ω(θ) = ∥θ∥22 = θj2 (82)
j=1

▶ Cette technique est appelée régularisation de Tikhonov.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 172 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation II

Choix de la fonction de pénalité Ω(θ)

▶ Dans le cas d’une régression linéaire, le critère s’écrit :

J(θ) = (Y − X θ)⊤ (Y − X θ) + λ∥θ∥22 avec λ > 0 (83)

La solution qui minimise ce critère composite est alors :

−1
θ̂ = X ⊤ X + λI X ⊤Y (84)

où, I représente la matrice identité.

▶ L’ajout du terme de pénalité garantit l’inversibilité de X ⊤ X + λI et

conduit à une solution unique.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 173 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation III

Choix de la fonction de pénalité Ω(θ)

Conclusion :
▶ La régression de Tikhonov assure une solution analytique unique car le critère
est convexe.
▶ Cette régression permet d’éviter le sur-paramétrage en restreignant la valeur
des paramètres : réduction de l’amplitude des coefficients.
▶ Cette régression peut avoir un effet de sélection groupée des variables. En
effet, lorsque les variables sont corrélées, elles sont affectées de valeurs de
coefficients proches.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 174 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation IV

Choix de la fonction de pénalité Ω(θ)

2 La technique du lasso (Least Absolute Shrinkage and Selection Opera-

tor)
▶ Cette technique a pour objectif de diminuer d’obtenir un modèle parci-
monieux, c’est-à-dire un modèle avec peu de paramètres donc avec peu
de variables.
▶ La norme 2 réduit l’amplitude des coefficients mais ne les annule pas.
▶ La technique du lasso est construite sur la norme 1. Cette norme va
permettre d’annuler certains coefficients, ce qui aboutira à un modèle
de complexité réduite.
▶ Le terme de régularisation Ω(θ) prend donc la forme suivante :
dim(θ)
X
Ω(θ) = ∥θ∥1 = |θj | (85)
j=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 175 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation V

Choix de la fonction de pénalité Ω(θ)

▶ Le critère à minimiser s’écrit alors :

J(θ) = ∥Y − X θ)∥22 + λ∥θ∥1 avec λ > 0 (86)

▶ On cherche donc la valeur θ̂ telle que :

θ̂ = arg min ∥Y − X θ)∥22 + λ∥θ∥1


(87)
θ

Inconvénients :
Le critère composite construit ainsi n’est plus convexe
Ce critère n’a donc pas nécessairement de solution unique
Ce critère n’admet plus de solution explicite

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 176 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation VI

Choix de la fonction de pénalité Ω(θ)

▶ On peut montrer que la minimisation du critère défini par (86) revient à

minimiser :

J(θ) = ∥Y − X θ∥22 tel que ∥θ∥1 ≤ δ(λ) avec δ(λ) > 0 (88)

▶ La valeur de δ dépend naturellement de celle de λ. Si λ augmente alors

δ(λ) diminue.
▶ Il s’agit donc de minimiser un critère quadratique sous contraintes.
▶ La solution sera donc celle qui minimisera la norme 2 de l’erreur et qui
respectera la contrainte de norme 1 !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 177 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Les méthodes de régularisation VII

Choix de la fonction de pénalité Ω(θ)

Interprétation géométrique :
Les courbes "iso-critère" correspondant au terme de norme 2 sont de type "ellipsoï-
dal".
La région définie par la norme 1 est un "hypercube".
La solution sera donc l’intersection d’une iso-critère avec le domaine défini par la
contrainte de norme 1.
Cette solution a plus de chance d’être sur un des sommets de l’"hypercube". Ça
dépend notamment du choix du terme de pénalité.
Il faut donc essayer différentes valeurs de λ et observer le résultat de la minimisation.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 178 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Schéma de principe de la méthode de Tikhonov

Minimum du
critère composite

Région
admissible Minimum du
critère
quadratique

Figure 31 – Critère composite : terme de pénalité en norme-2 (Méthode

Tikhonov)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 179 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Exemple 2 : approximation polynomiale Sinus (Suite) I

Objectif
Mise en évidence des effets de la sur-paramétrisation.
Montrer l’intérêt de la régularisation par rapport à ce problème.

Le nombre d’observations Nobs est fixe et égal à 15. Le RSB est environ de
6, c’est-à-dire que le signal utile est 6 plus grand que le bruit en moyenne.
Le modèle est de la forme :
9
X
y (t, θ) = θj t j (89)
j=0

A noter que : dim(θ) = 9 + 1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 180 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Exemple 2 : approximation polynomiale Sinus (Suite) II

Pour un modèle d’ordre 3, par la méthode des moindres carrés, on trouve

les paramètres suivants :

y (t, θ) = 0.09 + 7.65t − 23.52t 2 + 15.67t 3 (90)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 181 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Exemple 2 : approximation polynomiale Sinus (Suite) III

Données d'Entraînement (Identification)
Approximation polynomiale - Ordre = 3 - Nobs = 10
1
Mesures
Prédictions

0.5
Amplitude

-0.5
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)

Figure 32 – Signal sinusoïdal et Modèle d’ordre 3

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 182 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Application de la régularisation de Tikhonov I

Conditions expérimentales
■ On dispose de 16 observations.
■ Le niveau de bruit est important.

Démarche :
■ On cherche différentes approximations en augmentant petit à petit
l’ordre.
■ A chaque fois, les paramètres sont estimés par la méthode Ridge.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 183 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Application de la régularisation de Tikhonov II

Les résultats sont présentés dans un tableau (cf. Table (2)) et les figures
(nos (33),(34) et (35)).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 184 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Application de la régularisation de Tikhonov III

Conclusion
■ Quel que soit l’ordre (à partir de 3) du polynôme, le modèle est satis-
faisant (voir figure (35)).
■ Une augmentation du facteur de régularisation permet de faire tendre
les paramètres vers 0 (voir figure (33)).
■ Le facteur de régularisation évite l’explosion des paramètres (voir figure
(33) et le tableau (2)).
■ Un modèle d’ordre élevé ne modélise plus le bruit. Le modèle est une
version "filtrée" de la mesure (voir figure (35)).
■ Les figures (33) et (34) permettent de choisir le facteur de régularisa-
tion.
■ Lorsque la valeur de λ augmente alors le modèle "colle" moins bien aux
données.
■ Si λ vaut 0 alors la méthode se réduit à la minimisation de l’erreur
quadratique.
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 185 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Régularisation de Tikhonov : résultats graphiques I

Chemin de régularisation (Ridge)
80

60

40
Standardized Coefficient

20

-20

-40

-60

-80
10-6 10-5 10-4 10-3 10-2
Ridge Parameter
Figure 33 – Méthode Ridge - Chemin de régularisation
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 186 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Régularisation de Tikhonov : résultats graphiques II

Moyenne des erreurs au carré en fonction de
0.066

0.0655

0.065

0.0645
MSE

0.064

0.0635

0.063

0.0625

0.062
-6 -5 -4 -3 -2
10 10 10 10 10
Ridge Parameter
Figure 34 – Méthode Ridge - Erreur Quadratique Moyenne (EQM)
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 187 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Régularisation de Tikhonov : résultats graphiques III

Données de Test (Validation)
Régularisation - Influence de l'ordre - Nobs = 15

1 Mesures
Ordre=1
Ordre=3
0.5 Ordre=5
Ordre=7
Amplitude

Ordre=9
0

-0.5

-1
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)
Figure 35 – Résultats donnés par la méthode Ridge

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 188 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Exemple d’application de la méthode de Tikhonov

M=1 M=3 M=5 M=7 M=9
θ̂0 0.83 -0.08 0.06 0.06 0.04
θ̂1 -1.77 9.33 4.90 5.77 6.70
θ̂2 -26.72 -2.32 -15.46 -21.53
θ̂3 17.28 -29.11 29.53 32.32
θ̂4 32.80 -59.04 -20.00
θ̂5 -6.12 3.64 -34.68
θ̂6 90.43 3.42
θ̂7 -55.20 49.07
θ̂8 42.11
θ̂9 -58.38

Table 2 – Paramètres estimés des modèles avec régularisation - λ = 10−5

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 189 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Schéma de principe de la méthode lasso I

Minimum du
critère composite

Région
admissible Minimum du
critère
quadratique

Figure 36 – Critère composite : terme de pénalité en norme-1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 190 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Application de la régularisation lasso I

Conditions expérimentales identiques à Tikhonov

■ On dispose de 15 observations.
■ Le niveau de bruit est important.

Démarche :
■ On cherche différentes approximations en augmentant petit à petit
l’ordre.
■ A chaque fois, les paramètres sont estimés par la méthode lasso.

Les résultats sont présentés dans un tableau (cf. les figures (nos (37),(38),(39)
et (40)).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 191 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Application de la régularisation lasso II

Conclusion
■ Le modèle obtenu par la méthode lasso est parcimonieux et est tout à
fait satisfaisant ! (voir les figures (39) et (40)).
■ Une augmentation du facteur de régularisation permet de faire tendre
les paramètres vers 0 (voir figure (37)).
■ Le facteur de régularisation de la méthode lasso permet d’annuler les
paramètres du modèle alors que celui-ci dans la méthode ridge évite
l’explosion des paramètres (voir figure (37)).
■ Les figures (37) et (38) permettent de choisir le facteur de régularisa-
tion.
■ Si λ vaut 0 alors la méthode se réduit à la minimisation de l’erreur
quadratique.
■ Par la méthode lasso, le modèle parcimonieux a les paramètres sui-
vants :
y (t, θ) = 0.1 + 5.28t − 10.66t 2 + 5.71t 6 (91)
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 192 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Régularisation lasso : résultats graphiques I

Chemin de régularisation (lasso)
15

10
Standardized Coefficient

-5

-10

-15
10-5 10-4 10-3 10-2 10-1
Lasso Parameter

Figure 37 – Méthode lasso - Chemin de régularisation

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 193 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Régularisation lasso : résultats graphiques II

Moyenne des erreurs au carré en fonction de
0.2

0.15
MSE

0.1

0.05
10 -5 10 -4 10 -3 10 -2 10 -1
Lasso Parameter

Figure 38 – Méthode lasso - Erreur Quadratique Moyenne (EQM)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 194 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Régularisation lasso : résultats graphiques III

Données d'Entraînement (Identification)
Approximation polynomiale - Ordre = 9 - Nobs = 15
Mesures
MC
0.5 lasso
Amplitude

-0.5

-1
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)
Figure 39 – Résultats donnés par la méthode lasso - Identification

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 195 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Régularisation lasso : résultats graphiques IV

Données de Test (Validation)
Approximation polynomiale - Ordre = 9 - Nobs = 15

1 Mesures
MC
lasso
0.5
Amplitude

-0.5

-1
1

9
0

0.

0.

0.

0.

0.

0.

0.

0.

0.
Temps (s)
Figure 40 – Résultats donnés par la méthode lasso - Validation

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 196 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Tikhonov : Evolution du minimum du critère régularisé I

Figure 41 – Méthode ridge : λ = 0

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 197 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Tikhonov : Evolution du minimum du critère régularisé I

Figure 42 – Méthode ridge : λ = 6

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 198 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Tikhonov : Evolution du minimum du critère régularisé I

Figure 43 – Méthode ridge : λ = 10

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 199 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Tikhonov : Evolution du minimum du critère régularisé I

Figure 44 – Méthode ridge : λ = 14

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 200 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation
Evolution du minimum du critère composite
en fonction de :

3.5

2.5

1.5

0.5

0 Iso
Mini
-0.5

-1
-1 0 1 2 3

Figure 45 – Méthode ridge : λ évolue de 0 à 19

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 201 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

lasso : Evolution du minimum du critère régularisé I

Figure 46 – Méthode lasso : λ = 6

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 202 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

lasso : Evolution du minimum du critère régularisé I

Figure 47 – Méthode lasso : λ = 10

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 203 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

lasso : Evolution du minimum du critère régularisé I

Figure 48 – Méthode lasso : λ = 14

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 204 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation
Evolution du minimum du critère composite
en fonction de :

3.5

2.5

1.5

0.5

0 Iso
=0 Mini
-0.5 1

-1
-1 0 1 2 3

Figure 49 – Méthode lasso : λ évolue de 0 à 14

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 205 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Evolution du minimum du critère composite

en fonction de :

3.5 Iso
Mini
3

2.5

1.5

0.5

-0.5

-1
-2 -1 0 1 2

Figure 50 – Méthode ridge : λ évolue de 0 à 60

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 206 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

Evolution du minimum du critère composite

en fonction de :

3.5 Iso
Mini
3

2.5

1.5

0.5

0
=0
1
-0.5

-1
-2 -1 0 1 2

Figure 51 – Méthode lasso : λ évolue de 0 à 9

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 207 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes de régularisation

L’algorithme Elastic Net I

L’Elastic Net combine les normes 1 et 2 pour obtenir une solution moins
parcimonieuse que le lasso.
■ On cherche donc la valeur θ̂ telle que :
n  o
θ̂ = arg min ∥Y − X θ)∥22 + λ (1 − α)∥θ∥1 + α∥θ∥22 (92)
θ

Inconvénients :
▶ Le critère composite est encore un peu plus complexe !
▶ Un nouvel hyper-paramètre α est introduit !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 208 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

Organisation des données
Maximum de vraisemblance
Les méthodes de régularisation
La régression logistique
Les méthodes ensemblistes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 209 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Schéma général

Figure 52 – Démarche de classification

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 210 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

La régression logistique I
Approche intuitive

On veut classifier des individus dans 2 classes : il s’agit donc d’un problème
de classification binaire.
1 Première solution : essayons de construire un modèle linéaire simple.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 211 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

La régression logistique II
Approche intuitive

Figure 53 – Approche fondée sur un modèle linéaire : cas de données

décrites par 2 variables
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 212 / 277
 Chapitre 4 : Méthodes d’apprentissage La régression logistique

La régression logistique III

Approche intuitive

▶ On pourrait essayer de prédire l’appartenance à une classe en utilisant

un modèle linéaire mais ce n’est pas un modèle adapté.
▶ Pourquoi ?
Beaucoup d’individus ont des coordonnées différentes mais la sortie doit
toujours avoir la même valeur, à savoir 0 ou 1. La valeur 0 représentant
une classe et la valeur 1, l’autre classe.
Le problème est clairement non-linéaire : dans la zone frontière où les
individus sont susceptibles d’appartenir à une classe ou l’autre, la fonction
doit passer assez brutalement de 0 à 1 ou 1 à 0.
Cette approche n’est donc pas adaptée !
2 Deuxième solution : une approche fondée sur une probabilité d’appar-
tenance à une classe est plus adéquation avec la problématique.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 213 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

La régression logistique IV
Approche intuitive

Figure 54 – Approche fondée sur une probabilité

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 214 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

La régression logistique V
Approche intuitive

Figure 55 – Allure de la fonction de probabilité

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 215 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Définition de la fonction logistique I

■ Il faut donc trouver un modèle paramétrique qui permette d’avoir cette

allure.
■ Idée :
▶ Transformer la fonction linéaire en une fonction non-linéaire.
■ Comment ?
▶ En utilisant une fonction logistique définie de la façon suivante :
1
Flog (z) = (93)
1 + e −z

Corollaire
▶ Il existe plusieurs fonctions de type sigmoïdal qui pourraient convenir.
▶ Dans les logiciels d’analyse de données, il est possible de choisir sa fonction
logistique.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 216 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Définition de la fonction logistique II

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-8 -6 -4 -2 0 2 4 6 8
z

Figure 56 – Allure d’une fonction de type logistique

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 217 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Définition de la fonction logistique III

■ On cherche donc à déterminer la valeur de θ d’un modèle linéaire telle
que :
 
dim(θ)
X
P(Y = 1|x ) = Flog  θi xi + θ0  (94)
i=1
1
=  P
dim(θ)
 (95)
1 + exp − i=1 θi xi + θ0

■ On cherche donc un modèle dans lequel les variables interviennent sous

la forme d’une régression linéaire d’où le nom de régression logistique.
■ Les paramètres du modèle n’interviennent pas de manière linéaire par
rapport à P(Y = 1|x ).
■ On peut trouver les valeurs de θ par la méthode du maximum de vrai-
semblance.
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 218 / 277
 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique I

■ La fonction de vraisemblance L ({Y , X } , θ) d’un jeu de N observa-

tions (N lignes) composant la matrice (ou le vecteur) Y , notée Y =
{y (1), y (2), · · · , y (N)}, par rapport à un modèle donné, est définie
par la fonction suivante :

L ({Y , X } , θ) = P ({Y , X } |θ) (96)

avec

Y = {y (1), y (2), · · · , y (N)} (97)

n o
X = x (1) , x (2) , · · · , x (N) (98)

x (i) : représente la i ème ligne de la matrice d’observations.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 219 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique II

■ Hypothèse usuelle : on suppose que les observations sont indépendantes

et identiquement distribuées.
▶ L’indépendance des observations permettra d’écrire :
N
Y n o 
P ({Y , X } |θ) = P y (i), x (i) |θ (99)
i=1

■ Par définition, la probabilité conditionnelle s’écrit :

n o   n o  
P y (i), x (i) | θ = P y (i)| x (i) , θ .P x (i) (100)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 220 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique III

 
■ Or, P x (i) ne dépend pas de θ, le vecteur θ cherché est donc donné
par :
(N )
Y  n o
(i)
θ̂ = arg max P Y = y (i)| x ,θ (101)
θ
i=1

■ Comme précédemment, on maximisera le logarithme :

(N )
X   n o
(i)
θ̂ = arg max ln P Y = y (i)| x ,θ (102)
θ
i=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 221 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique IV

■ Dans notre cas, y (i) ne peut prendre que 2 valeurs, on utilisera donc
la notation suivante :
 n o
pi = P Y = y (i)| x (i) , θ pour y (i) = 1
 n o
1 − pi = P Y = y (i)| x (i) , θ pour y (i) = 0
 n o  n o
puisque : P Y = 1| x (i) , θ + P Y = 0| x (i) , θ =1
(103)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 222 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique V

Le critère a alors pour expression :

N
X   n o
J(θ) = ln P Y = y (i)| x (i) , θ (104)
i=1
XN    n o
= (1 − y (i)) ln P Y = 0| x (i) , θ
i=1
  n o
+ y (i) ln P Y = 1| x (i) , θ

■ L’équation (104) peut encore s’écrire en utilisant les notations définies

en (103) :
N 
X 
J(θ) = (1 − y (i)) ln (1 − pi ) + y (i) ln (pi ) (105)
i=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 223 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique VI

■ Sachant que x (i) désigneh un vecteur

i ligne correspondant à la i
ième ob-

servation. Posons xiT = x (i) 1

■ De plus, θ est un vecteur colonne, la probabilité pi s’écrit alors :
 n o 1
pi = P Y = 1| x (i) , θ = (106)
1 + exp −xiT θ

■ La valeur cherchée de θ est donc donnée par :

(N !
X 1
θ̂ = arg max (1 − y (i)) ln 1 − (107)
1 + exp −xiT θ


θ
i=1
!!)
1
+ y (i) ln (108)
1 + exp −xiT θ

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 224 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique VII

■ Cette expression peut se simplifier et on obtient :

(N  )
 
−xiT θ
X
θ̂ = arg max − (1 − y (i))xiT θ − ln 1 + e (109)
θ
i=1

■ Maximiser l’équation (109) revient à minimiser :

(N  )
 
−xiT θ
X
θ̂ = arg min (1 − y (i))xiT θ + ln 1 + e (110)
θ
i=1

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 225 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Estimation des paramètres d’une régression logistique VIII

Corollaire
■ Le critère à minimiser n’est pas convexe !
■ Les paramètres du modèle interviennent de façon non-linéaire, on a
donc pas de solution explicite.
■ Néanmoins, il est donc possible de trouver une solution numérique
approchée en utilisant des méthodes de type : gradient, Levenberg-
Marquardt, quasi-Newton. . .
■ Pour les mêmes raisons que précédemment, il est également envisa-
geable de mettre en œuvre les techniques de régularisation en normes
1 ou 2 pour la régression logistique.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 226 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Point de vue de Bayes I

Le classifieur de Bayes

■ Le classifieur de Bayes est construit sur la comparaison de probabilités

a posteriori. L’observation x (i) est affectée à la classe de plus grande
probabilité a posteriori.
■ La décision binaire par rapport à l’observation x (i) est formulée comme
suit : 
P (C1 |x (i) )
 C1

si >1
D(x (i) ) = P (C2 |x (i) ) (111)
 C2

sinon

■ D’une façon générale, la variable y (i), représentant la décision D(x (i) ),

peut prendre 2 valeurs {C1 , C2 }, par exemple, vrai ou faux . . .

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 227 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Point de vue de Bayes II

Le classifieur de Bayes

P (C1 |x (i) )
■ Le rapport représente un rapport de chance (en anglais :
P (C2 |x (i) )
odds). Par exemple, si ce rapport vaut 2, cela signifie que la décision
D(x (i) ) à 2 fois plus de chance de prendre la valeur C1 que la valeur
C2 .
Corollaire
▶ La décision pourrait être construite différemment !
  
 C1 si P C1 |x (i) > 0.5
D(x (i) ) = (112)
 C sinon
2

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 228 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Point de vue de Bayes III

Le classifieur de Bayes

■ Pour construire la décision D(x (i) ), il faut évaluer ce rapport de pro-

babilité en utilisant les règles de Bayes :
   
P C1 |x (i) P(x (i) ) = P x (i) |C1 P(C1 ) (113)
   
P C2 |x (i) P(x (i) ) = P x (i) |C2 P(C2 ) (114)

Le rapport s’écrit donc :

   
P C1 |x (i) P x (i) |C1 P(C1 )

= (115)
P C2 |x (i) P x (i) |C2 P(C2 )

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 229 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Point de vue de Bayes IV

Le classifieur de Bayes

■ La fonction logarithme étant monotone et croissante, la régression lo-

gistique est construite sur le logarithme de ce rapport de probabilité a
posteriori. Ce rapport (115) est supposé être une combinaison linéaire
des variables, comme précédemment.
■ Ainsi, posons :
  
P C1 |x (i) h i
ln  (i)

 = x (i) 1 θ = xiT θ (116)
P C2 |x

■ Comme la décision dépendra de θ, on écrira :

  n o 
P Y = C1 | x (i) , θ
ln 
 = xiT θ (117)
P Y = C2 | x (i) , θ


P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 230 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Point de vue de Bayes V

Le classifieur de Bayes

■ Mais, on a aussi :
 n o  n o
P Y = C1 | x (i) , θ + P Y = C2 | x (i) , θ =1 (118)

■ De plus, l’exponentielle de l’équation (117) donne :

 n o
P Y = C1 | x (i) , θ T

= e xi θ (119)
P Y = C2 | x (i) , θ


P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 231 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Point de vue de Bayes VI

Le classifieur de Bayes

■ En combinant les équations (118) et (119), il vient :

 
 n o exp xiT θ 1
P Y = C1 | x (i) , θ =
= (120)
1 + exp xiT θ
1 + exp −xiT θ


 n o 1
P Y = C2 | x (i) , θ = (121)
1 + exp xiT θ

Corollaire
▶ L’équation (120) est la même que celle donnée en (106).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 232 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Point de vue de Bayes VII

Le classifieur de Bayes

■ Soit la variable zi telle que :

zi = 1 quand y (i) = C1 (122)

zi = 0 quand y (i) = C2 (123)

■ Alors le critère à minimiser s’écrit :

(N  )
 
−xiT θ
X
θ̂ = arg min (1 − zi )xiT θ + ln 1 + e (124)
θ
i=1

Cette dernière équation est analogue à l’équation (110).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 233 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Allure des densités de probabilité a posteriori

1 1

0.9 0.9

0.8 0.8

0.7 0.7

0.6 0.6

0.5 0.5

0.4 0.4

0.3 0.3

0.2 0.2

0.1 0.1

0 0
-8 -6 -4 -2 0 2 4 6 8 -8 -6 -4 -2 0 2 4 6 8
z z




(a) P Y = C1 | x (i) , θ (b) P Y = C2 | x (i) , θ

Figure 57 – Représentation des 2 densités de probabilité complémentaire

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 234 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Résumé de la régression logistique I

■ La régression logistique, malgré son nom, permet de résoudre un pro-

blème de classification binaire et pas de prédiction.
■ La régression logistique s’applique donc à des variables qui ont 2 mo-
dalités : vrai ou faux, succès ou échec, malade ou pas malade, en panne
ou pas en panne. . .
■ La régression logistique retourne une probabilité qu’une observation
appartienne à une classe.
■ La régression logistique exploite une fonction logistique construite sur
une combinaison linéaire des variables servant à opérer la classification.
On parlera donc d’un classifieur linéaire.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 235 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Résumé de la régression logistique II

■ La frontière séparant les données en 2 classes est un hyperplan : droite,

plan. . .
■ L’estimation des paramètres d’une régression logistique est effectuée
par la maximisation de la fonction de vraisemblance.
■ L’estimation est obtenue par la mise œuvre de techniques itératives.
■ Pour éviter le sur-apprentissage ou créer des modèles parcimonieux, les
méthodes de régularisation peuvent être exploitées.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 236 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur I

D’une manière simplifiée, le classifieur retourne une réponse qui est soit
mauvaise, notée (-), soit bonne, notée (+).

Ŷ +̂ −̂ Total
Y

+ VP FN VP+FN

- FP VN FP+VN

Total VP+FP FN+VN n=VP+FP+FN+VN

Table 3 – Forme générique de la matrice de confusion

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 237 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur II

Négatifs
Positifs
Seuil
Probabilité

- +

0
Seuil
Valeurs
Figure 58 – Allure des distributions des classes "+" et "-" (Hypothèse :
distributions normales)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 238 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur III

Vrais Négatifs
Faux Négatifs
Faux Positifs
Vrais Positifs
Seuil Seuil

Probabilité
Probabilité

VN VP

0 0
Seuil Seuil
Valeurs Valeurs

(a) Définition des domaines : FN et FP (b) Définition des domaines : VP et VN

Figure 59 – Définition des domaines pour un seuil donnant un pourcentage de

FN ≈ 5%

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 239 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur - suite I

■ A partir de la matrice de confusion on peut dériver tout un tas de

critères de performance. De manière générale, on préfère donner une
fraction d’erreurs à un nombre total d’erreurs (5% d’erreurs).
■ Ces indicateurs peuvent être déduits pour rendre compte de la concor-
dance entre les valeurs observées et les valeurs prédites.
■ Le terme VP représente les vrais positifs c’est-à-dire les observations
qui ont été classées positives et qui le sont réellement.
■ Le terme FP compte les faux positifs c’est-à-dire les individus classés
positifs et qui sont réalité des négatifs.
■ De la même manière, Le terme FN est le nombre de faux négatifs et
VN est le nombre de vrais négatifs.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 240 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur - suite II

Corollaire
▶ Les termes VP, FP, FN et VN dépendent du seuil de décision choisi.

■ Quel que soit le seuil choisi s, on a les 2 relations suivantes :

VP(s) + VN(s) = c1 avec c1 : constante (125)

FP(s) + FN(s) = c2 avec c2 : constante (126)

■ On considère 2 types d’erreur :

▶ Erreur de type I (α) : faux négatifs, ce sont des non détections !
Probabilité de rejeter l’hypothèse alors qu’elle est vraie !
▶ Erreur de type II (β) : faux positifs, ce sont des fausses alarmes !
Probabilité d’accepter l’hypothèse alors qu’elle est fausse !

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 241 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur - suite III

■ le taux d’erreur est égal au nombre de mauvais classement rapporté à

l’effectif total, il est donc défini par :

FN + FP VP + VN
ϵ= =1− (127)
n n
Il estime la probabilité de mauvais classement du classifieur.
■ Le taux de succès correspond au nombre de bon classement rapporté
à l’effectif total, il est donc défini par :

VP + VN FN + FP
η= =1− (128)
n n
C’est donc le complémentaire au taux d’erreur.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 242 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur - suite IV

■ La sensibilité (ou rappel) indique la capacité du modèle à retrouver les

positifs, c’est-à-dire la proportion de positifs que l’on a correctement
identifiés. On l’appelle également "Taux de Vrais Positifs" :

VP
TVP = Sensibilité = (129)
VP + FN

Attention !
On peut facilement avoir une très bonne sensibilité en prédisant
systématiquement "positif", mais notre modèle ne sert pas à grand chose.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 243 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur - suite V

■ La précision, c’est la proportion de vrais positifs parmi les individus qui

ont été prédits "positifs". Elle estime la probabilité d’un individu d’être
réellement positif lorsque le modèle le classe comme tel :

VP
Précision = (130)
VP + FP
■ On s’intéresse aussi souvent à la spécificité, qui est le taux de vrais
négatifs détectés :
VN
Spécificité = (131)
VN + FP
■ Pour finir cette liste, on définit le "Taux de Faux Négatifs" qui corres-
pond à la proportion de négatifs qui ont été classés positifs :

FP
TFP = = 1 − Spécificité (132)
VN + FP
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 244 / 277
 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Evaluation des performances du classifieur - suite VI

■ Pour évaluer un compromis entre sensibilité et précision, on peut cal-

culer la "F-mesure", qui est leur moyenne harmonique.

1 + β 2 × rappel × Précision


F-mesureβ = (133)
β 2 × Précision + rappel

Pour β = 1, on accorde la même importance à la précision qu’au rappel,

la "F-mesure" devient :
2 × rappel × Précision
F-mesureβ=1 = (134)
Précision + rappel

Si β > 1, on accorde plus d’importance au rappel qu’à la précision. Si

β < 1 alors c’est l’inverse.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 245 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

En résumé par rapport à tous ces indicateurs I

■ Un "bon" modèle doit avoir des valeurs faibles de taux d’erreur et

de taux de faux positifs (≈ 0), des valeurs élevées de sensibilité, de
précision et de spécificité (proche de 1).
■ A noter que la sensibilité et la précision accordent un rôle particulier
aux positifs, alors que le taux d’erreur donne la même importance aux
faux positifs et aux faux négatifs.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 246 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Mesure de la qualité d’un classifieur : la courbe ROC I

■ La courbe ROC (Receiver Operating Characteristic) a pour origine la

théorie du signal. Mais elle est très largement utilisée dans de multiples
contextes.
■ Elle met en balance le taux de faux positifs (TFP) en abscisse, et la
sensibilité (le rappel, le taux de vrais positifs) en ordonnée.
■ Elle est monotone croissante. Les coordonnées extrêmes sont (0, 0) et
(1, 1).
■ A partir de cette courbe, un indicateur synthétique est calculé : l’aire
sous la courbe (AUC).
■ Dans le pire des cas, les scores attribués sont identiques chez les po-
sitifs et chez les négatifs, la courbe est confondue avec la diagonale
principale.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 247 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Mesure de la qualité d’un classifieur : la courbe ROC II

■ Pour un seuil de décision, le classifieur donne la probabilité que chaque
individu soit dans une classe, si on fait varier ce seuil on obtient alors
plusieurs matrices de confusion qui vont nous permettre de tracer la
courbe ROC.
▶ Autrement dit, pour construire cette courbe, on choisit une grille de
seuils et on calcule pour chaque seuil s, le TVP (Taux VP, sensibilité)
et le TFP (Taux FP).
■ Plus la courbe ROC s’approche du coin supérieur gauche, meilleur est
le modèle, car il permet de capturer le plus possible de vrais positifs
avec le moins possible de faux positifs.
■ Si le classification est idéale alors AUC = 1
■ Si le classification est aléatoire alors AUC = 1/2
■ Cette courbe sert également à comparer différents classifieurs. Plus une
courbe a des valeurs élevées, plus l’aire sous la courbe est grande, moins
le classifieur fait d’erreur.
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 248 / 277
 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Mesure de la qualité d’un classifieur : la courbe ROC III

Figure 60 – Allures de courbes ROC : TVP = f (TFP) (source :wikipédia)

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 249 / 277

 Chapitre 4 : Méthodes d’apprentissage La régression logistique

Mesure de la qualité d’un classifieur : la courbe ROC IV

Choix du seuil s
■ On utilise parfois la courbe ROC pour choisir le seuil. En pratique, on
peut prendre le seuil qui correspond au point de la courbe le plus éloigné
de la première bissectrice et le plus près du point supérieur gauche de
coordonnées (0, 1). Ou encore le seuil correspondant au point où la
pente de la courbe est la plus proche de 0.
■ On peut également choisir le seuil qui optimise un critère de perfor-
mance comme le taux d’erreur, le risque empirique, la F-mesure. . .

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 250 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Plan du cours

1 Chapitre 1 : Introduction

2 Chapitre 2 : Démarche classique de recherche d’un modèle

3 Chapitre 3 : Cadre de l’apprentissage

4 Chapitre 4 : Méthodes d’apprentissage

Organisation des données
Maximum de vraisemblance
Les méthodes de régularisation
La régression logistique
Les méthodes ensemblistes

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 251 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Introduction

■ Les méthodes ensemblistes sont regroupées en deux sous-familles prin-

cipales. Celles qui fonctionnent en parallèles et celles qui fonctionnent
de manière séquentielle.
■ Principe : combiner des modèles avec des performances faibles pour
obtenir un modèle prédictif plus efficace.
■ Ces méthodes exploitent la technique du bootstrap.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 252 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

La méthode du bootstrap I

■ A la fin des années 70, les statisticiens se sont penchés sur la technique
d’échantillonnage (sampling), pour créer une nouvelle famille de mé-
thodes, appelées « bootstrap ».
■ Ces techniques sont basées sur la réplication multiple des données à par-
tir du jeu de données étudié, selon les techniques de ré-échantillonnage.
■ Principe : on crée des « nouveaux échantillons » statistiques, mais
uniquement par tirage avec remise, à partir du jeu de données initial.
▶ Par exemple, on remplace une observation par la moyenne de 2 autres
observations.
■ Intérêt : le bootstrap ne nécessite pas d’autres informations que celles
disponibles sur les individus de l’échantillon originel.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 253 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

La méthode du bootstrap II

■ Pour un grand jeu de données engendrées, on peut alors calculer la

moyenne sur chacune de ces populations.
■ L’histogramme des moyennes sur ces différentes populations donnera
alors une idée de la variabilité de la moyenne.
■ C’est cette méthode dite du « bootstrap » qui a donnée naissance à la
famille des méthodes dites « parallèles ».
■ C’est pour signifier qu’en fait, nous allons entraîner plusieurs modèles
de manière indépendante (en parallèle) pour ensuite les regrouper afin
de prendre une décision.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 254 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les apprenants faibles

■ La théorie des méthodes ensemblistes est construite sur l’hypothèse que

l’on peut améliorer ce qu’on appelle des « apprenants faibles » (« weak
learners ») en les combinant.
■ Un apprenant faible désigne un modèle qui fait seulement légèrement
mieux que le hasard. Par faible, nous entendons une règle (par exemple
de classification) dont le taux d’erreur est légèrement meilleur que celui
d’une règle purement aléatoire (penser à un tirage de type appartient
ou n’appartient pas).
■ Ces apprenants sont en général plus faciles à créer, et lorsqu’ils sont
combinés avec des méthodes « intelligentes », ils sont plus performants
qu’un modèle unique.
■ Les arbres de décision sont considérés comme des apprenants faibles
quand ils sont de petite taille.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 255 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Première méthode ensembliste : le bagging I

Principe du bagging

■ Le bagging qui est un contraction de « Bootstrap AGGregatING » est

une méthode permettant de combiner des apprenants faibles.
■ Il faut créer différents jeux de données qui permettront d’entraîner nos
apprenants faibles.
■ Ces jeux de données sont créés par la méthode statistique du bootstrap.
■ On échantillonne donc N fois notre jeu de données initial (avec repla-
cement) afin d’obtenir un nouveau jeu de données de taille N.
■ Chaque observation a une probabilité 1/N d’être tirée et on répète ce
processus N fois.
■ La notion de « faible » désigne notamment le fait que nos modèles
possèdent une forte variance.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 256 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Première méthode ensembliste : le bagging II

Principe du bagging

■ Le bagging (la combinaison) permet de réduire la variance des esti-

mateurs individuels, cette diminution dépend du nombre d’apprenants
faibles utilisés.
■ Les apprenants faibles peuvent être de différentes natures et avoir des
performances variées, mais ils doivent être indépendants les uns des
autres.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 257 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Deuxième méthode ensembliste : le boosting I

Dans la communauté de l’apprentissage, le boosting (Freund et Schapire

(1996)) se révèle être l’une des idées les plus puissantes des 20 dernières et
continue de faire l’objet d’une littérature abondante.
■ Le terme «boosting» s’applique à des méthodes générales capables de
produire des décisions très précises à partir de règles peu précises (qui
font légèrement mieux que le hasard).
■ Le terme «boosting» désigne une famille d’algorithmes, il regroupe à la
fois les méthodes de régression ou de classification supervisée.
■ Les algorithmes de boosting sont construits sur le même principe que
ceux de bagging.
■ La différence apparaît lors de la création des apprenants faibles.
■ Pour le boosting, les apprenants faibles ne sont plus construits indé-
pendamment les uns des autres.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 258 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Deuxième méthode ensembliste : le boosting II

■ Au contraire, chaque apprenant faible est construit pour corriger les

erreurs des apprenants faibles précédents.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 259 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Deuxième méthode ensembliste : le boosting

Principe du boosting

Le principe général du «boosting» consiste à construire une famille d’esti-

mateurs qui sont ensuite agrégés par une moyenne pondérée des estimations
(en régression) ou un vote à la majorité (en classification).
L’idée consiste à appliquer une règle de classification simple plusieurs fois
en affectant «judicieusement» un poids différent aux observations à chaque
itération.
■ Les estimateurs sont construits de manière itérative : chaque estimateur
est une version adaptative du précédent en donnant plus de poids aux
observations mal ajustées ou mal prédites.
■ L’algorithme connu sous le nom «AdaBoost» (Adaptive Boosting) est
l’exemple le plus emblématique de cette famille.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 260 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Le principe de l’algorithme «AdaBoost»

Dans un contexte de classification (discrimination), le principe général de

l’algorithme «AdaBoost» consiste à affecter à chaque observation une pon-
dération 1/n à la première itération.
A la seconde itération, le poids des observations pour lesquelles l’observation
est bien classée est conservé, pour les autres la pondération est augmentée
pour mieux prendre en compte ces observations mal classées.
A compléter

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 261 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision I

■ Les forêts aléatoires combinent des arbres de décision à l’aide de mé-

thodes ensemblistes.
■ C’est une des méthodes d’apprentissage supervisé les plus populaires
pour les problèmes de classification de données.
■ Qu’est-ce qu’un arbre de décision ?

Définition (Wikipédia)
Un arbre de décision est un outil d’aide à la décision représentant un en-
semble de choix sous la forme graphique d’un arbre.
Les différentes décisions possibles sont situées aux extrémités des branches
(les «feuilles» de l’arbre), et sont atteintes en fonction de décisions prises à
chaque étape.
Autrement dit, en parcourant l’ensemble des branches de cet arbre, on abou-
tit aux différentes décisions possibles.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 262 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision II

■ Il a l’avantage d’être lisible et rapide à exécuter.
■ Les formes les plus simples sont binaires.
■ Si on ajoute trop de tests (trop de branches), on aboutit à des arbres
de trop grandes dimensions qui modélisent les bruits.
■ Un arbre de décision modélise une hiérarchie de tests pour prédire un
résultat.
■ Il existe deux principaux types d’arbre de décision :
▶ Les arbres de régression (Regression Tree) permettent de prédire une
quantité réelle, une valeur numérique (par exemple, le prix d’une maison
ou la durée de séjour d’un patient dans un hôpital)
▶ Les arbres de classification (Classification Tree) permettent de prédire à
quelle classe la variable de sortie appartient (cela permet par exemple de
répartir une population d’individus, comme des clients d’une entreprise
en différents types de profils).
■ Ce sont des modèles non paramétriques.
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 263 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision III

Figure 61 – Exemple d’arbre de décision

Un ensemble d’individus décrits par plusieurs variables catégorielles (Dou-

leur, Toux, Fièvre). La variable cible (diagnostic) se retrouve dans les feuilles.
P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 264 / 277
 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision (suite) I

Représentation - Construction

■ Représentation :
▶ Chaque nœud correspond à un attribut.
▶ Chaque nœud teste l’attribut correspondant et engendre plusieurs branches.
Variable catégorielle : une branche par valeur de l’attribut
Variable numérique : test sur valeur
▶ Les feuilles spécifient les classes.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 265 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision (suite) II

Représentation - Construction

■ Principe de construction :
▶ L’arbre est construit par partition récursive de la base d’apprentissage
en fonction de la valeur de l’attribut testé à chaque itération (top-down
induction).
▶ Un arbre est constitué de nœuds connectés entre eux par des branches.
▶ Un arbre de décision est constitué de nœuds de décision.
▶ Une branche entre deux nœuds est orientée : l’un des nœuds de la
connexion est dit « nœud parent » et l’autre « nœud enfant ».
▶ Chaque nœud est connecté à un et un seul nœud parent, sauf le nœud
racine qui n’a pas de parent.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 266 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision (suite) I

Comment ça marche ?

■ Les décisions possibles sont situées aux extrémités des branches (les «
feuilles » de l’arbre) et sont atteintes en fonction de décisions prises à
chaque étape.
■ Un arbre de décision fonctionne en appliquant de manière itérative des
règles logiques très simples (typiquement des séparations de données
par « hyperplan », généralisation d’un plan à 2 dimensions), chaque
règle étant choisie en fonction du résultat de la règle précédente.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 267 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision (suite) II

Comment ça marche ?

■ Avantages :
▶ Les arbres de décision ont pour avantage d’être simple à interpréter,
très rapide à entrainer et de nécessiter très peu de pré-traitement des
données.
▶ Ils peuvent être calculés automatiquement par des algorithmes d’appren-
tissage supervisé capables de sélectionner automatiquement les variables
discriminantes au sein de données non-structurées et potentiellement vo-
lumineuses.
▶ Ces algorithmes permettent aussi d’extraire des règles logiques qui n’ap-
paraissaient pas dans les données brutes.
■ Pour classer une nouvelle observation, il suffit de parcourir l’arbre en
partant de la racine jusqu’à atteindre une feuille.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 268 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Les arbres de décision (suite) III

Comment ça marche ?

■ Un autre usage en machine learning consiste à construire non pas un

arbre, mais une forêt d’arbres de décision.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 269 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Algorithmes pour construire des arbres de décision I

■ Il existe plusieurs algorithmes pour fabriquer des arbres de décision.

▶ L’algorithme CART (Classification And Regression Trees) : méthode des
arbres de segmentation et de régression (Breiman, Friedman, Olshen et
Stone, 1984). La méthode CART permet d’engendrer des arbres binaires
(toujours deux branches par nœuds non-feuilles).
▶ C’est un des algorithmes parmi les plus performants et les plus répandus.
▶ Il a pour but de construire un arbre de décision de façon récursive en
choisissant l’attribut qui minimise la perte d’information. Dans le cas
d’un arbre de régression (Regression Tree), un modèle très simple est
estimé sur chaque partition (sur chaque région), par exemple la prédiction
est la moyenne des observations dans la région considérée.
▶ Une évolution de cet algorithme permet de construire des arbres qui ne
sont pas nécessairement binaires (0 à n branches par nœud).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 270 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

Algorithmes pour construire des arbres de décision II

Figure 62 – Exemple de construction par divisions successives de l’espace des

variables. Arbre typique renvoyé par l’algorithme CART.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 271 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

L’algorithme CART I
Principe de l’algorithme

Principe de l’algorithme : principe de construction de l’arbre

1 Sélectionner une variable «pertinente»
2 Diviser de façon «intelligente» en 2 parties l’espace suivant cette va-
riable.
Le découpage est choisi de manière à minimiser une fonction de coût
particulière : minimisation de la somme des variances des 2 groupes
obtenus par découpage. La prédiction est alors :
▶ Pour un arbre de régression (Regression Tree) : la moyenne des observa-
tions dans la feuille correspondant à la variable sélectionnée
▶ Pour un arbre de classification (Classification Tree) : la classe majoritaire
dans la feuille
3 Revenir à l’étape 1 ci-dessus pour traiter les sous-arbres ainsi obtenus

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 272 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

L’algorithme CART II
Principe de l’algorithme

Questions :
■ Quand s’arrêter ?
■ Comment sélectionner la variable ?
■ Comment choisir les valeurs définissant les régions (partitions) ?

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 273 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

L’algorithme CART (suite) I

3 étapes dans cet algorithme :

■ Construire l’arbre de décision «maximal» (nombre de feuilles trop
grand) : une seule observation dans chaque nœud ou toutes les ob-
servations dans un nœud appartiennent à la même classe.
■ Élaguer : Créer une suite de sous-arbres à l’aide l’arbre «maximal» en
utilisant un critère pénalisé, ajout d’un terme de pénalité qui vise à
diminuer la complexité (le nombre de feuilles) de l’arbre. On obtient
alors plusieurs sous-arbres et il faut en choisir un.
■ Sélectionner de l’arbre final au moyen d’une validation croisée ou en
utilisant une base de données de test.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 274 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

L’algorithme CART I
Cas d’un arbre de régression

Objectif :
■ Découper l’espace des variables explicatives en J régions, notées R1 ,...,
RJ . Elles correspondent aux feuilles de l’arbre.
■ Les feuilles de l’arbre (les régions) sont déterminées en minimisant un
critère quadratique classique.
■ Le critère s’écrit alors :

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 275 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

L’algorithme CART II
Cas d’un arbre de régression

J X
(yi − ybj )2
X
J = (135)
j=1 i∈Rj

avec, dans le cas de la version standard, l’estimation de yj est calculée ainsi :

ybj = n1j i∈Rj yi , nj est le nombre d’observations dans la feuille Rj .
P

Remarque :
Ce problème d’optimisation n’a pas de solution analytique. En pratique, on
utilise une approche récursive (et donc mathématiquement sous-optimal)
pour trouver une solution.

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 276 / 277

 Chapitre 4 : Méthodes d’apprentissage Les méthodes ensemblistes

La méthode des forêts aléatoires I

■ Les forêts aléatoires sont constituées d’arbres de décision qui sont com-
binées à l’aide de méthodes ensemblistes.
■ Les forêts aléatoires sont une évolution du bagging.
Principe :
■ Une décision est prise en construisant un ensemble d’arbres et en
choisissant la réponse majoritaire (classification, choix discret) ou la
moyenne des réponses (regression, variable continue).
■ Les résultats ainsi obtenus sont remarquables notamment lorsque les
arbres de décision sont utilisés en forêts aléatoires (Random Forest).

P. Sibille (Université de Lorraine) Machine Learning 26 septembre 2023 277 / 277