Apprentissage automatique
Cours complet · informatique (MP2I/MPI), chapitre 26 · MP2I et MPI
Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre
26.1 Ce que le programme demande, et ce qu'il n'attend pas
Ce chapitre est le plus jeune du livre, et le programme y met une mise en garde qu'il faut lire avant tout le reste : « la connaissance des théories sous-jacentes aux algorithmes de cette section n'est pas un attendu du programme. Les étudiants acquièrent une familiarité avec les idées qu'ils peuvent réinvestir dans des situations où les modélisations et les recommandations d'implémentation sont guidées. »
Autrement dit : on apprend ce que font ces algorithmes, on sait les écrire quand on est guidé, et l'on ne démontre ni leur convergence ni leurs garanties statistiques. Le programme écarte d'ailleurs explicitement la démonstration de convergence des -moyennes.
- Supervisé : les données d'apprentissage portent une étiquette — une réponse connue — et l'on veut prédire celle de données nouvelles.
- Non supervisé : aucune étiquette ; on cherche une structure dans les données, typiquement des paquets.
26.2 Apprentissage supervisé
26.2.1 Les plus proches voisins
Méthode : L'algorithme le plus simple qui soit
Pour classer un point nouveau : trouver ses plus proches voisins parmi les données étiquetées, et lui donner l'étiquette majoritaire. Le programme fixe la distance : euclidienne.
(* Étiquette prédite pour x par les k plus proches voisins.
Précondition : k >= 1, donnees non vide. Complexité : O(n·d + n log n). *)
let knn donnees k x =
let d2 (p, _) =
Array.fold_left (+.) 0.0
(Array.mapi (fun i xi -> (xi -. p.(i)) ** 2.0) x)
in
let triees = List.sort (fun a b -> compare (d2 a) (d2 b)) donnees in
let voisins = prendre k triees in
majoritaire (List.map snd voisins)Il n'y a pas de phase d'entraînement : le modèle est l'ensemble des données. Tout le coût est reporté sur la prédiction, qui parcourt les points à chaque requête. C'est l'inverse des méthodes suivantes, longues à entraîner et instantanées à interroger.
Le choix de arbitre entre deux défauts : recopie le bruit des données ; trop grand lisse jusqu'à ignorer les structures fines. Aucune règle ne le fixe — on l'évalue.
Le programme cite les arbres dimensionnels (-d trees), qui accélèrent la recherche des voisins. L'idée est celle de la dichotomie du chapitre chap:diviser, portée en dimension : on découpe l'espace par un hyperplan perpendiculaire à un axe, en alternant les axes à chaque niveau, et l'on construit ainsi un arbre binaire.
La recherche descend vers la région du point, puis ne remonte explorer la région voisine que si la distance à l'hyperplan est inférieure au meilleur candidat trouvé — c'est un élagage, exactement au sens du chapitre chap:exploration. On passe de à en moyenne, en petite dimension.
26.2.2 Les arbres de décision et l'algorithme ID3
Un arbre de décision pose une question à chaque nœud interne et porte une étiquette à chaque feuille. Classer un exemple, c'est descendre selon ses réponses. Le programme restreint « au cas d'arbres binaires » : chaque question est un test à deux issues.
Méthode : ID3 : choisir la question qui informe le plus
À chaque nœud, on choisit le test qui réduit le plus le désordre des étiquettes. La mesure employée est l'entropie : pour un ensemble où la proportion de chaque classe vaut ,
Elle vaut quand toutes les étiquettes coïncident — aucun désordre — et quand deux classes sont à parts égales. Le gain d'information d'un test séparant en et est
et ID3 retient le test de gain maximal, puis recommence sur chaque moitié.
(* Arbre de décision d'ID3. Précondition : exemples non vide.
La récursion s'arrête quand toutes les étiquettes coïncident ou qu'aucun
test ne subsiste. *)
let rec id3 exemples tests =
if homogene exemples || tests = [] then Feuille (majoritaire exemples)
else
let t = argmax (fun t -> gain exemples t) tests in
let (oui, non) = separer exemples t in
Noeud (id3 non (retirer t tests), t, id3 oui (retirer t tests))ID3 est un glouton au sens du chapitre chap:gloutons : il choisit le meilleur test local et ne le remet jamais en cause. Il ne produit donc pas l'arbre le plus petit — trouver celui-là est np-difficile.
26.2.3 Évaluer : la matrice de confusion
Elle croise l'étiquette réelle et l'étiquette prédite. En deux classes :
| prédit positif | prédit négatif | |
|---|---|---|
| réellement positif | vrais positifs (VP) | faux négatifs (FN) |
| réellement négatif | faux positifs (FP) | vrais négatifs (VN) |
Voici pourquoi la matrice existe, et pourquoi un seul chiffre ne suffit jamais. Sur un dépistage où des sujets sont malades, l'algorithme qui répond toujours « sain » atteint de bonnes réponses — et ne détecte aucun malade. Sa matrice le dit immédiatement : , tous les malades sont en faux négatifs.
Deux quantités séparent les cas : la précision — « quand je dis positif, ai-je raison ? » — et le rappel — « ai-je trouvé tous les positifs ? ». L'algorithme ci-dessus a un rappel nul.
26.2.4 Le sur-apprentissage
Un modèle sur-apprend quand il retient les particularités — voire le bruit — des données d'entraînement au lieu de la régularité qu'on cherche. Il est alors excellent sur ce qu'il a vu et mauvais sur le reste.
L'erreur sur les données d'entraînement décroît toujours quand le modèle se complique — un arbre de décision assez profond finit par les classer toutes correctement, en isolant chacune dans sa propre feuille. L'erreur sur des données nouvelles, elle, remonte.
D'où la règle qui gouverne toute la discipline : on n'évalue jamais un modèle sur les données qui ont servi à l'entraîner. On réserve une partie des données, jamais vue pendant l'apprentissage, et c'est sur elle qu'on mesure. Le programme demande d'ailleurs qu'on « observe des situations de sur-apprentissage sur des exemples ».
26.3 Apprentissage non supervisé
26.3.1 Les -moyennes
Méthode : Deux étapes, répétées
On cherche à partager points en paquets. On tire centres au hasard, puis on répète :
- affectation : chaque point rejoint le centre le plus proche ;
- mise à jour : chaque centre se replace au barycentre de son paquet.
jusqu'à ce que plus rien ne bouge.
(* Partition de points en k paquets. Précondition : k >= 1, points non vide.
Complexité : O(iterations · n · k · d). *)
let k_moyennes points k =
let centres = ref (tirer_au_hasard points k) in
let affectation = ref [||] in
let stable = ref false in
while not !stable do
let neuve = Array.map (fun p -> plus_proche p !centres) points in
stable := (neuve = !affectation);
affectation := neuve;
if not !stable then
centres := Array.init k (fun c -> barycentre points !affectation c)
done;
!affectationLe programme est explicite sur les deux points : « la démonstration de la convergence n'est pas au programme » et « on observe des convergences vers des minima locaux ».
L'algorithme s'arrête toujours — chaque étape diminue la somme des carrés des distances aux centres, et le nombre de partitions est fini. Mais le résultat dépend du tirage initial : deux exécutions sur les mêmes données peuvent donner deux partitions différentes, dont l'une est meilleure que l'autre.
La parade pratique : relancer plusieurs fois et garder la partition de moindre coût. C'est un algorithme de Las Vegas au sens du chapitre chap:probabilistes — sauf qu'il ne garantit pas l'optimalité, seulement une chance accrue de la frôler.
26.3.2 La classification hiérarchique ascendante
Méthode : Fusionner les plus proches, jusqu'au bout
Chaque point forme d'abord son propre paquet. Puis, tant qu'il en reste plus d'un : fusionner les deux paquets les plus proches. On obtient un arbre de fusions — le dendrogramme.
(* Dendrogramme des points. Précondition : points non vide.
Complexité : O(n³) en version naïve. *)
let hierarchique points =
let paquets = ref (List.map (fun p -> Feuille p) points) in
while List.length !paquets > 1 do
let (a, b) = couple_le_plus_proche !paquets in
paquets := Noeud (a, b) :: retirer_deux !paquets a b
done;
List.hd !paquets| -moyennes | Hiérarchique | |
|---|---|---|
| Nombre de paquets | fixé avant | choisi après, en coupant l'arbre |
| Résultat | dépend du tirage | déterministe |
| Ce qu'on obtient | une partition | toutes les partitions emboîtées |
| Coût | naïvement |
La deuxième ligne est décisive quand la reproductibilité compte. La quatrième explique pourquoi les -moyennes dominent sur les grands jeux de données.
C'est l'un des usages d'arbre que le chapitre chap:arbres annonçait. Sa force est qu'on décide a posteriori : couper le dendrogramme à une hauteur donnée produit un nombre de paquets qu'on n'avait pas à connaître d'avance. Couper haut donne peu de gros paquets, couper bas en donne beaucoup de petits.
26.4 Ce qu'il faut retenir
- plus proches voisins : aucun entraînement, tout le coût à la prédiction. Les arbres -d l'accélèrent par élagage.
- ID3 est un glouton qui choisit le test de gain d'information maximal. Il ne produit pas l'arbre minimal — c'est np-difficile.
- La matrice de confusion existe parce qu'un taux global ment : à de malades, répondre toujours « sain » donne de réussite et zéro détection.
- Le sur-apprentissage : l'erreur d'entraînement décroît toujours, celle de test remonte. On n'évalue jamais sur les données d'entraînement.
- -moyennes converge vers un minimum local, dépend du tirage — on relance. La classification hiérarchique est déterministe et laisse choisir le nombre de paquets après coup, au prix de .