Apprentissage supervisé

L'apprentissage supervisé ( SL ) est un paradigme de l'apprentissage automatique dans lequel des objets d'entrée (par exemple, un vecteur de variables prédictives) et une valeur de sortie souhaitée (également appelée signal de supervision étiqueté par l'homme ) entraînent un modèle. Les données d'apprentissage sont traitées, créant une fonction qui mappe les nouvelles données aux valeurs de sortie attendues. Un scénario optimal permettra à l'algorithme de déterminer correctement les valeurs de sortie pour les instances invisibles. Cela nécessite que l'algorithme d'apprentissage généralise à partir des données d'apprentissage à des situations invisibles de manière « raisonnable » (voir biais inductif ). Cette qualité statistique d'un algorithme est mesurée par ce que l'on appelle l' erreur de généralisation .

Pour résoudre un problème donné d'apprentissage supervisé, il faut effectuer les étapes suivantes :

1. Déterminer le type d'exemples d'entraînement. Avant toute chose, l'utilisateur doit décider quel type de données doit être utilisé comme ensemble d'entraînement. Dans le cas d' une analyse de l'écriture manuscrite , par exemple, il peut s'agir d'un seul caractère manuscrit, d'un mot manuscrit entier, d'une phrase entière d'écriture manuscrite ou peut-être d'un paragraphe complet d'écriture manuscrite.
2. Rassembler un ensemble d'apprentissage . L'ensemble d'apprentissage doit être représentatif de l'utilisation réelle de la fonction. Ainsi, un ensemble d'objets d'entrée est rassemblé et les sorties correspondantes sont également rassemblées, soit à partir d'experts humains, soit à partir de mesures.
3. Déterminer la représentation des caractéristiques d'entrée de la fonction apprise. La précision de la fonction apprise dépend fortement de la manière dont l'objet d'entrée est représenté. En général, l'objet d'entrée est transformé en un vecteur de caractéristiques , qui contient un certain nombre de caractéristiques descriptives de l'objet. Le nombre de caractéristiques ne doit pas être trop important, en raison de la malédiction de la dimensionnalité ; mais doit contenir suffisamment d'informations pour prédire avec précision la sortie.
4. Déterminer la structure de la fonction apprise et l'algorithme d'apprentissage correspondant. Par exemple, l'ingénieur peut choisir d'utiliser des machines à vecteurs de support ou des arbres de décision .
5. Terminez la conception. Exécutez l'algorithme d'apprentissage sur l'ensemble d'entraînement collecté. Certains algorithmes d'apprentissage supervisé nécessitent que l'utilisateur détermine certains paramètres de contrôle . Ces paramètres peuvent être ajustés en optimisant les performances sur un sous-ensemble (appelé ensemble de validation ) de l'ensemble d'entraînement, ou via une validation croisée .
6. Évaluer la précision de la fonction apprise. Après le réglage des paramètres et l'apprentissage, les performances de la fonction résultante doivent être mesurées sur un ensemble de test distinct de l'ensemble d'apprentissage.

Il existe une large gamme d'algorithmes d'apprentissage supervisé, chacun avec ses forces et ses faiblesses. Il n'existe pas d'algorithme d'apprentissage unique qui soit le plus efficace pour résoudre tous les problèmes d'apprentissage supervisé (voir le théorème « Pas de repas gratuit »).

Il y a quatre points majeurs à prendre en compte dans l’apprentissage supervisé :

Un premier problème est le compromis entre biais et variance . Imaginons que nous ayons à disposition plusieurs ensembles de données d'apprentissage différents, mais tout aussi bons. Un algorithme d'apprentissage est biaisé pour une entrée particulière si, lorsqu'il est formé sur chacun de ces ensembles de données, il est systématiquement incorrect lorsqu'il prédit la sortie correcte pour . Un algorithme d'apprentissage a une variance élevée pour une entrée particulière s'il prédit des valeurs de sortie différentes lorsqu'il est formé sur différents ensembles d'apprentissage. L'erreur de prédiction d'un classificateur appris est liée à la somme du biais et de la variance de l'algorithme d'apprentissage. En général, il existe un compromis entre biais et variance. Un algorithme d'apprentissage avec un faible biais doit être « flexible » pour pouvoir bien s'adapter aux données. Mais si l'algorithme d'apprentissage est trop flexible, il s'adaptera différemment à chaque ensemble de données d'apprentissage et aura donc une variance élevée. Un aspect clé de nombreuses méthodes d'apprentissage supervisé est qu'elles sont capables d'ajuster ce compromis entre biais et variance (soit automatiquement, soit en fournissant un paramètre de biais/variance que l'utilisateur peut ajuster).

Le deuxième problème concerne la quantité de données d'apprentissage disponibles par rapport à la complexité de la « vraie » fonction (classificateur ou fonction de régression). Si la vraie fonction est simple, alors un algorithme d'apprentissage « inflexible » avec un biais élevé et une faible variance sera capable de l'apprendre à partir d'une petite quantité de données. Mais si la vraie fonction est très complexe (par exemple parce qu'elle implique des interactions complexes entre de nombreuses caractéristiques d'entrée différentes et se comporte différemment dans différentes parties de l'espace d'entrée), alors la fonction ne pourra apprendre qu'avec une grande quantité de données d'apprentissage couplée à un algorithme d'apprentissage « flexible » avec un biais faible et une variance élevée.

Un troisième problème est la dimensionnalité de l'espace d'entrée. Si les vecteurs de caractéristiques d'entrée ont de grandes dimensions, l'apprentissage de la fonction peut être difficile même si la vraie fonction ne dépend que d'un petit nombre de ces caractéristiques. En effet, les nombreuses dimensions « supplémentaires » peuvent perturber l'algorithme d'apprentissage et entraîner une variance élevée. Par conséquent, les données d'entrée de grandes dimensions nécessitent généralement de régler le classificateur pour avoir une faible variance et un biais élevé. En pratique, si l'ingénieur peut supprimer manuellement les caractéristiques non pertinentes des données d'entrée, cela améliorera probablement la précision de la fonction apprise. En outre, il existe de nombreux algorithmes de sélection de caractéristiques qui cherchent à identifier les caractéristiques pertinentes et à éliminer celles qui ne le sont pas. Il s'agit d'un exemple de la stratégie plus générale de réduction de la dimensionnalité , qui cherche à mapper les données d'entrée dans un espace de dimension inférieure avant d'exécuter l'algorithme d'apprentissage supervisé.

Un quatrième problème est le degré de bruit dans les valeurs de sortie souhaitées (les variables cibles de supervision ). Si les valeurs de sortie souhaitées sont souvent incorrectes (en raison d'une erreur humaine ou d'erreurs de capteur), l'algorithme d'apprentissage ne doit pas tenter de trouver une fonction qui corresponde exactement aux exemples d'apprentissage. Tenter d'ajuster les données avec trop de soin conduit à un surajustement . Vous pouvez surajuster même lorsqu'il n'y a pas d'erreurs de mesure (bruit stochastique) si la fonction que vous essayez d'apprendre est trop complexe pour votre modèle d'apprentissage. Dans une telle situation, la partie de la fonction cible qui ne peut pas être modélisée « corrompt » vos données d'apprentissage - ce phénomène a été appelé bruit déterministe . Lorsque l'un ou l'autre type de bruit est présent, il est préférable d'opter pour un estimateur à biais plus élevé et à variance plus faible.

En pratique, il existe plusieurs approches pour atténuer le bruit dans les valeurs de sortie, comme l'arrêt précoce pour éviter le surapprentissage ainsi que la détection et la suppression des exemples d'entraînement bruyants avant l'entraînement de l'algorithme d'apprentissage supervisé. Il existe plusieurs algorithmes qui identifient les exemples d'entraînement bruyants et la suppression des exemples d'entraînement suspectés d'être bruyants avant l'entraînement a réduit l'erreur de généralisation avec une signification statistique .

D’autres facteurs à prendre en compte lors du choix et de l’application d’un algorithme d’apprentissage sont les suivants :

• Hétérogénéité des données. Si les vecteurs de caractéristiques comprennent des caractéristiques de nombreux types différents (discrètes, discrètes ordonnées, comptages, valeurs continues), certains algorithmes sont plus faciles à appliquer que d'autres. De nombreux algorithmes, notamment les machines à vecteurs de support , la régression linéaire , la régression logistique , les réseaux neuronaux et les méthodes du plus proche voisin , nécessitent que les caractéristiques d'entrée soient numériques et mises à l'échelle sur des plages similaires (par exemple, sur l'intervalle [-1,1]). Les méthodes qui utilisent une fonction de distance, telles que les méthodes du plus proche voisin et les machines à vecteurs de support avec noyaux gaussiens , sont particulièrement sensibles à ce problème. L'un des avantages des arbres de décision est qu'ils gèrent facilement des données hétérogènes.
• Redondance dans les données. Si les entités d'entrée contiennent des informations redondantes (par exemple, des entités fortement corrélées), certains algorithmes d'apprentissage (par exemple, la régression linéaire , la régression logistique et les méthodes basées sur la distance ) seront peu performants en raison d'instabilités numériques. Ces problèmes peuvent souvent être résolus en imposant une certaine forme de régularisation .
• Présence d'interactions et de non-linéarités. Si chacune des caractéristiques apporte une contribution indépendante à la sortie, alors les algorithmes basés sur des fonctions linéaires (par exemple, la régression linéaire , la régression logistique , les machines à vecteurs de support , Bayes naïf ) et les fonctions de distance (par exemple, les méthodes du plus proche voisin , les machines à vecteurs de support avec noyaux gaussiens ) fonctionnent généralement bien. Cependant, s'il existe des interactions complexes entre les caractéristiques, les algorithmes tels que les arbres de décision et les réseaux neuronaux fonctionnent mieux, car ils sont spécifiquement conçus pour découvrir ces interactions. Les méthodes linéaires peuvent également être appliquées, mais l'ingénieur doit spécifier manuellement les interactions lors de leur utilisation.

Lorsqu'il envisage une nouvelle application, l'ingénieur peut comparer plusieurs algorithmes d'apprentissage et déterminer expérimentalement lequel fonctionne le mieux sur le problème en question (voir validation croisée ). Le réglage des performances d'un algorithme d'apprentissage peut prendre beaucoup de temps. Étant donné les ressources fixes, il est souvent préférable de passer plus de temps à collecter des données de formation supplémentaires et des fonctionnalités plus informatives que de passer plus de temps à régler les algorithmes d'apprentissage.

Les algorithmes d’apprentissage les plus utilisés sont :

• Machines à vecteurs de support
• Régression linéaire
• Régression logistique
• Bayes naïf
• Analyse discriminante linéaire
• Arbres de décision
• Algorithme des K plus proches voisins
• Réseaux neuronaux ( Perceptron multicouche )
• Apprentissage par similarité

Étant donné un ensemble d' exemples d'apprentissage de la forme telle que est le vecteur de caractéristiques du -ième exemple et est son étiquette (c'est-à-dire sa classe), un algorithme d'apprentissage recherche une fonction , où est l'espace d'entrée et est l'espace de sortie. La fonction est un élément d'un espace de fonctions possibles , généralement appelé espace d'hypothèses . Il est parfois pratique de représenter à l'aide d'une fonction de notation telle que définie comme renvoyant la valeur qui donne le score le plus élevé : . Soit l'espace des fonctions de notation.

Bien que et puissent être n'importe quel espace de fonctions, de nombreux algorithmes d'apprentissage sont des modèles probabilistes où ils prennent la forme d'un modèle de probabilité conditionnelle ou prennent la forme d'un modèle de probabilité conjointe . Par exemple, l'analyse naïve de Bayes et l'analyse discriminante linéaire sont des modèles de probabilité conjointe, tandis que la régression logistique est un modèle de probabilité conditionnelle.

Il existe deux approches de base pour choisir la fonction ou le paramètre : la minimisation du risque empirique et la minimisation du risque structurel . La minimisation du risque empirique recherche la fonction qui correspond le mieux aux données d'apprentissage. La minimisation du risque structurel comprend une fonction de pénalité qui contrôle le compromis biais/variance.

Dans les deux cas, on suppose que l'ensemble d'apprentissage est constitué d'un échantillon de paires indépendantes et identiquement distribuées , . Afin de mesurer dans quelle mesure une fonction s'adapte aux données d'apprentissage, une fonction de perte est définie. Pour l'exemple d'apprentissage , la perte de prédiction de la valeur est .

Le risque de fonction est défini comme la perte attendue de . Cela peut être estimé à partir des données d'entraînement comme

Dans la minimisation du risque empirique, l'algorithme d'apprentissage supervisé recherche la fonction qui minimise . Par conséquent, un algorithme d'apprentissage supervisé peut être construit en appliquant un algorithme d'optimisation pour trouver .

Lorsque la distribution de probabilité conditionnelle est présente et que la fonction de perte est la vraisemblance logarithmique négative : , alors la minimisation du risque empirique est équivalente à l'estimation du maximum de vraisemblance .

Lorsque l'ensemble d'apprentissage contient de nombreuses fonctions candidates ou n'est pas suffisamment grand, la minimisation du risque empirique conduit à une variance élevée et à une mauvaise généralisation. L'algorithme d'apprentissage est capable de mémoriser les exemples d'apprentissage sans bien généraliser. C'est ce qu'on appelle le surapprentissage .

La minimisation des risques structurels vise à empêcher le surapprentissage en incorporant une pénalité de régularisation dans l'optimisation. La pénalité de régularisation peut être considérée comme la mise en œuvre d'une forme de rasoir d'Occam qui privilégie les fonctions plus simples aux fonctions plus complexes.

Une grande variété de pénalités a été utilisée, correspondant à différentes définitions de la complexité. Par exemple, considérons le cas où la fonction est une fonction linéaire de la forme

Une pénalité de régularisation courante est , qui est la norme euclidienne au carré des poids, également connue sous le nom de norme. D'autres normes incluent la norme, , et la « norme » , qui est le nombre de s non nuls . La pénalité sera notée .

Le problème d'optimisation de l'apprentissage supervisé consiste à trouver la fonction qui minimise

Le paramètre contrôle le compromis biais-variance. Lorsque , cela donne une minimisation empirique du risque avec un biais faible et une variance élevée. Lorsque est grand, l'algorithme d'apprentissage aura un biais élevé et une variance faible. La valeur de peut être choisie empiriquement via la validation croisée .

La pénalité de complexité a une interprétation bayésienne comme la probabilité a priori négative de , , auquel cas est la probabilité a posteriori de .

Les méthodes d'apprentissage décrites ci-dessus sont des méthodes d'apprentissage discriminatives , car elles cherchent à trouver une fonction qui discrimine bien les différentes valeurs de sortie (voir modèle discriminatif ). Pour le cas particulier où est une distribution de probabilité conjointe et la fonction de perte est le logarithme de vraisemblance négatif, un algorithme de minimisation des risques est dit effectuer un apprentissage génératif , car il peut être considéré comme un modèle génératif qui explique comment les données ont été générées. Les algorithmes d'apprentissage génératifs sont souvent plus simples et plus efficaces en termes de calcul que les algorithmes d'apprentissage discriminatifs. Dans certains cas, la solution peut être calculée sous forme fermée comme dans l'analyse naïve de Bayes et l'analyse discriminante linéaire .

Il existe plusieurs façons de généraliser le problème standard d'apprentissage supervisé :

• Apprentissage semi-supervisé ou supervision faible : les valeurs de sortie souhaitées ne sont fournies que pour un sous-ensemble des données d'apprentissage. Les données restantes sont non étiquetées ou étiquetées de manière imprécise.
• Apprentissage actif : au lieu de supposer que tous les exemples de formation sont donnés au début, les algorithmes d'apprentissage actif collectent de nouveaux exemples de manière interactive, généralement en adressant des requêtes à un utilisateur humain. Souvent, les requêtes sont basées sur des données non étiquetées, ce qui constitue un scénario qui combine l'apprentissage semi-supervisé et l'apprentissage actif.
• Prédiction structurée : lorsque la valeur de sortie souhaitée est un objet complexe, tel qu'un arbre d'analyse ou un graphique étiqueté, les méthodes standard doivent être étendues.
• Apprendre à classer : Lorsque l'entrée est un ensemble d'objets et que la sortie souhaitée est un classement de ces objets, les méthodes standard doivent à nouveau être étendues.

• Apprentissage analytique
• Réseau neuronal artificiel
• Rétropropagation
• Boosting (méta-algorithme)
• Statistiques bayésiennes
• Raisonnement basé sur des cas
• Apprentissage par arbre de décision
• Programmation logique inductive
• Régression par processus gaussien
• Programmation génétique
• Méthode de groupe pour le traitement des données
• Estimateurs de noyau
• Automates d'apprentissage
• Apprentissage des systèmes de classification
• Apprentissage de la quantification vectorielle
• Longueur minimale des messages ( arbres de décision , graphiques de décision, etc.)
• Apprentissage multilinéaire des sous-espaces
• Classificateur bayésien naïf
• Classificateur à entropie maximale
• Champ aléatoire conditionnel
• Algorithme du voisin le plus proche
• Apprentissage probablement approximativement correct (PAC)
• Ripple down rules , une méthodologie d'acquisition de connaissances
• Algorithmes d'apprentissage automatique symbolique
• Algorithmes d'apprentissage automatique sous-symboliques
• Machines à vecteurs de support
• Machines à complexité minimale (MCM)
• Forêts aléatoires
• Ensembles de classificateurs
• Classification ordinale
• Prétraitement des données
• Gestion des ensembles de données déséquilibrés
• Apprentissage statistique relationnel
• Proaftn , un algorithme de classification multicritère

• Bioinformatique
• Chimioinformatique
  • Relation quantitative structure-activité
• Marketing de base de données
• Reconnaissance de l'écriture manuscrite
• Recherche d'informations
  • Apprendre à classer
• Extraction d'informations
• Reconnaissance d'objets en vision par ordinateur
• Reconnaissance optique de caractères
• Détection de spam
• Reconnaissance des formes
• Reconnaissance vocale
• L'apprentissage supervisé est un cas particulier de causalité descendante dans les systèmes biologiques
• Classification des reliefs à l'aide d'images satellites
• Classification des dépenses dans les processus d'approvisionnement

• Théorie de l'apprentissage informatique
• Biais inductif
• Surapprentissage (apprentissage automatique)
• Probabilités d'appartenance à une classe (non étalonnée)
• Apprentissage non supervisé
• Espaces de versions