Pense-bête d'apprentissage supervisé
Par Afshine Amidi et Shervine Amidi
Introduction à l'apprentissage supervisé
Étant donné un ensemble de points associés à un ensemble d'issues , on veut construire un classifieur qui apprend à prédire depuis .
Type de prédiction Les différents types de modèles prédictifs sont résumés dans le tableau ci-dessous :
Régression | Classifieur | |
Issue | Continu | Classe |
Exemples | Régression linéaire | Régression logistique, SVM, Naive Bayes |
Type de modèle Les différents modèles sont présentés dans le tableau ci-dessous :
Modèle discriminant | Modèle génératif | |
But | Estimer directement | Estimer puis déduire |
Ce qui est appris | Frontière de décision | Distribution de probabilité des données |
Illustration | ![]() |
![]() |
Exemples | Régressions, SVMs | GDA, Naive Bayes |
Notations et concepts généraux
Hypothèse Une hypothèse est notée et est le modèle que l'on choisit. Pour une entrée donnée , la prédiction donnée par le modèle est .
Fonction de loss Une fonction de loss est une fonction prenant comme entrée une valeur prédite correspondant à une valeur réelle , et nous renseigne sur la ressemblance de ces deux valeurs. Les fonctions de loss courantes sont récapitulées dans le tableau ci-dessous :
Erreur des moindres carrés | Loss logistique | Hinge loss | Cross-entropie |
![]() |
![]() |
![]() |
![]() |
Régression linéaire | Régression logistique | SVM | Réseau de neurones |
Fonction de coût La fonction de coût est communément utilisée pour évaluer la performance d'un modèle, et est définie avec la fonction de loss par :
Algorithme du gradient En notant le taux d'apprentissage (en anglais learning rate), la règle de mise à jour de l'algorithme est exprimée en fonction du taux d'apprentissage et de la fonction de cost de la manière suivante :

Remarque : L'algorithme du gradient stochastique (en anglais Stochastic Gradient Descent ou SGD) met à jour le paramètre à partir de chaque élément du jeu d'entrainement, tandis que l'algorithme du gradient de batch le fait sur chaque lot d'exemples.
Vraisemblance La vraisemblance d'un modèle de paramètre est utilisée pour trouver le paramètre optimal par le biais du maximum de vraisemblance. En pratique, on utilise la log vraisemblance qui est plus facile à optimiser. On a :
Algorithme de Newton L'algorithme de Newton est une méthode numérique qui trouve tel que . La règle de mise à jour est :
Remarque : la généralisation multidimensionnelle, aussi connue sous le nom de la méthode de Newton-Raphson, a la règle de mise à jour suivante :
Modèles linéaires
Régression linéaire
On suppose ici que
Équations normales En notant la matrice de design, la valeur de qui minimise la fonction de coût a une solution de forme fermée tel que :
Algorithme LMS En notant le taux d'apprentissage, la règle de mise à jour d'algorithme des moindres carrés (LMS) pour un jeu de données d'entrainement de m points, aussi connu sous le nom de règle de Widrow-Hoff, est donné par :
Remarque : la règle de mise à jour est un cas particulier de l'algorithme du gradient.
LWR Issue de l'anglais Locally Weighted Regression et souvent notée LWR, cette méthode est une variante de la régression linéaire appliquant un coefficient à chaque exemple dans sa fonction de coût via , qui est défini avec un paramètre de la manière suivante :
Classification et régression logistique
Sigmoïde La sigmoïde , aussi connue sous le nom de fonction logistique, est définie par :
Régression logistique On suppose ici que . On a la forme suivante :
Remarque : il n'y a pas de solution fermée dans le cas de la régression logistique.
Régression softmax Une régression softmax, aussi appelée un régression logistique multi-classe, est utilisée pour généraliser la régression logistique lorsqu'il y a plus de 2 classes à prédire. Par convention, on fixe , ce qui oblige le paramètre de Bernoulli de chaque classe à être égal à :
Modèles linéaires généralisés
Famille exponentielle Une classe de distributions est issue de la famille exponentielle lorsqu'elle peut être écrite en termes d'un paramètre naturel, aussi appelé paramètre canonique ou fonction de lien , d'une statistique suffisante et d'une fonction de log-partition de la manière suivante :
Remarque : on aura souvent . Aussi, peut être vu comme un paramètre de normalisation s'assurant que les probabilités somment à un.
Les distributions exponentielles les plus communément rencontrées sont récapitulées dans le tableau ci-dessous :
Distribution | ||||
Bernoulli | ||||
Gaussien | ||||
Poisson | ||||
Geometrique |
Hypothèses pour les GLMs Les modèles linéaires généralisés (en anglais Generalized Linear Models ou GLM) ont pour but de prédire une variable aléatoire comme une fonction de et reposent sur les 3 hypothèses suivantes :
Remarque : la méthode des moindres carrés ordinaires et la régression logistique sont des cas spéciaux des modèles linéaires généralisés.
Support Vector Machines
Le but des support vector machines est de trouver la ligne qui maximise la distance minimum des points à cette même ligne.
Classifieur à marges optimales Le classifieur à marges optimales est tel que :
où est une solution du problème d'optimisation suivant :

Remarque : la ligne est définie par .
Hinge loss Le hinge loss est utilisé dans le cadre des SVMs et est défini de la manière suivante :
Noyau Étant donné un feature mapping , on définit le noyau (en anglais kernel) par :
En pratique, le noyau défini par est nommé noyau gaussien et est communément utilisé.

Remarque : on dit que l'on utilise "l'astuce du noyau" (en anglais kernel trick) pour calculer la fonction de coût en utilisant le noyau parce qu'il se trouve que l'on n'a pas besoin de trouver le mapping explicite, qui est souvent compliqué. Il suffit de connaître les valeurs de .
Lagrangien On définit le lagrangien par :
Remarque : les coefficients sont appelés les multiplicateurs de Lagrange.
Apprentissage génératif
Un modèle génératif essaie d'abord d'apprendre comment les données sont générées en estimant , nous permettant ensuite d'estimer par le biais du théorème de Bayes.
Gaussian Discriminant Analysis
Cadre Le Gaussian Discriminant Analysis suppose que et et sont tels que :
Estimation Le tableau suivant récapitule les estimations que l'on a trouvées lors de la maximisation de la vraisemblance :
Naive Bayes
Hypothèse Le modèle de Naive Bayes suppose que les caractéristiques de chaque point sont toutes indépendantes :
Solutions Maximiser la log vraisemblance donne les solutions suivantes, où
Remarque : Naive Bayes est couramment utilisé pour la classification de texte et pour la détection de spams.
Méthode à base d'arbres et d'ensembles
Ces méthodes peuvent être utilisées pour des problèmes de régression et de classification.
CART Les arbres de classification et de régression (en anglais CART - Classification And Regression Trees), aussi connus sous le nom d'arbres de décision, peuvent être représentés sous la forme d'arbres binaires. Ils ont l'avantage d'être très interprétables.
Random forest C'est une technique à base d'arbres qui utilise un très grand nombre d'arbres de décisions construits à partir d'ensembles de caractéristiques aléatoirement sélectionnés. Contrairement à un simple arbre de décision, il n'est pas interprétable du tout mais le fait qu'il ait une bonne performance en fait un algorithme populaire.
Remarque : les random forests sont un type de méthode ensembliste.
Boosting L'idée des méthodes de boosting est de combiner plusieurs modèles faibles pour former un modèle meilleur. Les principales méthodes de boosting sont récapitulées dans le tableau ci-dessous :
Boosting adaptif | Boosting par gradient |
• Connu sous le nom d'Adaboost • De grands coefficients sont mis sur les erreurs pour s'améliorer à la prochaine étape de boosting |
• Les modèles faibles sont entrainés sur les erreurs résiduelles |
Autres approches non-paramétriques
-nearest neighbors L'algorithme des plus proches voisins (en anglais -nearest neighbors), aussi connu sous le nom de -NN, est une approche non-paramétrique où la réponse d'un point est déterminée par la nature de ses voisins du jeu de données d'entrainement. Il peut être utilisé dans des cadres de classification et de régression.
Remarque : Plus le paramètre est élevé, plus le biais est élevé, et plus le paramètre est faible, plus la variance est élevée.

Théorie d'apprentissage
Inégalité de Boole Soit évènements. On a :

Inégalité d'Hoeffding Soit variables iid tirées d'une distribution de Bernoulli de paramètre . Soit leur moyenne empirique et fixé. On a :
Remarque : cette inégalité est aussi connue sous le nom de borne de Chernoff.
Erreur de training Pour un classifieur donné , on définit l'erreur d'entrainement , aussi connu sous le nom de risque empirique ou d'erreur empirique, par :
Probablement Approximativement Correct (PAC) PAC est un cadre dans lequel de nombreux résultats d'apprentissages ont été prouvés, et contient l'ensemble d'hypothèses suivant :
- les jeux d'entrainement et de test suivent la même distribution
- les exemples du jeu d'entrainement sont tirés indépendamment
Éclatement Étant donné un ensemble , et un ensemble de classifieurs , on dit que brise si pour tout ensemble de labels , on a :
Théorème de la borne supérieure Soit une hypothèse finie de classe telle que , soit , et soit la taille fixée d'un échantillon. Alors, avec une probabilité d'au moins , on a :
Dimension VC La dimension de Vapnik-Chervonenkis (VC) d'une classe d'hypothèses de classes infinies donnée , que l'on note , est la taille de l'ensemble le plus grand qui est brisé par .
Remarque : la dimension VC de est égale à 3.

Théorème (Vapnik) Soit donné, avec avec le nombre d'exemples d'entrainement. Avec une probabilité d'au moins , on a :