Apprentissage supervisé #

Bien que nous en ayons parlé en termes purement géométriques jusqu’ici, la régression logistique est en fait une méthode probabiliste : un point est considéré bleu si le modèle calcule que la probabilité qu’il le soit est $\ge 50\%$ (et évidemment vice versa pour rouge). Une probabilité est une valeur nécessairement entre 0 et 1. Pour transformer une fonction arbitraire en une fonction de probabilité, on peut utiliser la fonction sigmoïde (aussi appelée fonction logistique), qui “force” une valeur à être dans la plage 0 et 1 :

Nous allons à partir d’ici changer un peu la notation que nous avons utilisée jusqu’ici, pour la rendre plus générale :

Cette notation classique en apprentissage automatique utilise donc $\mathbf{x}$ pour dénoter les points en 2D sous forme vectorielle ($x_1$ et $x_2$ correspondent aux $x$ et $y$ de la représentation 2D classique, et $\mathbf{x}$ est donc un vecteur, dont les 2 valeurs correspondent aux “caractéristiques” d’un point, sa description numérique). La variable scalaire (donc une valeur numérique simple, par opposition à un vecteur) $y$ est utilisée pour dénoter la vraie classe d’un point (0 ou 1, correspondant arbitrairement à bleu ou rouge). Les paramètres seront représentés par le vecteur $\mathbf{w} = [w_1, w2]$. Il est maintenant possible de réécrire notre fonction de décision à l’aide de cette nouvelle notation vectorielle :

($\mathbf{w}^\top \mathbf{x}$ est le produit vectoriel de $\mathbf{w}$ et $\mathbf{x}$). Notons tout d’abord qu’il y maintenant 3 paramètres ($w1$, $w2$ et $b$), alors que dans l’exemple ci-haut seulement 2 sont mentionnés : $m$ et $b$. On introduit aussi une nouvelle variable $z$ : que veut-elle dire? Pour comprendre cela, on doit faire un peu d’algèbre. Il suffit de noter que notre équation de départ :

est en fait équivalente à :

ce qu’on peut réécrire aisément :

En choisissant ensuite $m = -w_1/w_2$ et $b = -b/w_2$, on peut réécrire :

En multipliant les deux membres de l’équation par $-w_2$, on arrive à :

ce qui constitue la forme générale d’une équation en 2D. Étant donné que ce qui nous intéresse se passe de part et d’autre de la ligne de décision (car il s’agit comme nous l’avons vu d’une inéquation), on introduit le score $z$, pour quantifier la distance à laquelle un point se trouve, de cette ligne de séparation :

En utilisant la fonction logistique que nous avons introduite ci-haut pour transformer ce score (une valeur arbitraire) en une probabilité (donc une valeur contrainte entre 0 et 1), on peut maintenant introduire l’équation de la régression logistique :

avec laquelle il est bien important de comprendre que $\hat{y}$ représente une probabilité (donc que $\hat{y} \in [0, 1]$), tandis que $y$ représente une vraie classe (donc que $y \in {0, 1}$). La régression logistique transforme donc la distance entre un point et la ligne de décision, en une mesure de probabilité. L’algorithme de classification utilisera donc la probabilité calculée pour chaque point de la manière suivante :

Notre but est maintenant de trouver les valeurs optimales pour les paramètres $\mathbf{w}$ (donc deux nombres précis, $w_1$ et $w_2$), celles qui vont faire en sorte de minimiser l’erreur de classification. Nous avons donc besoin de définir tout d’abord cette erreur en tant que fonction précise :

Pour bien comprendre le fonctionnement de cette équation, examinons les différents cas de figure :

1. Un point est en réalité bleu (donc $y = 1$) et la confiance du modèle en ce fait est élevée ($\hat{y} = 0.9$) : $E(y, \hat{y}) = -\log(0.9) \approx 0.1$ (l’erreur est basse).
2. Un point est en réalité bleu (donc $y = 1$) mais la confiance du modèle en ce fait est basse ($\hat{y} = 0.1$) : $E(y, \hat{y}) = -\log(0.1) \approx 2.3$ (l’erreur est élevée).
3. Un point est en réalité rouge (donc $y = 0$) et la confiance du modèle en ce fait est élevée ($\hat{y} = 0.1$) : $E(y, \hat{y}) = -\log(0.9) \approx 0.1$ (l’erreur est basse).
4. Un point est en réalité rouge (donc $y = 0$) mais la confiance du modèle en ce fait est basse ($\hat{y} = 0.9$) : $E(y, \hat{y}) = -\log(0.1) \approx 2.3$ (l’erreur est élevée).

La fonction d’erreur $E$ que nous avons s’applique à un seul point. Nous avons besoin de la généraliser à l’ensemble des $n$ points que nous avons, en en faisant simplement la somme. Ceci est une nouvelle fonction nommée $J$, qui utilise des indices $(i)$ pour dénoter les valeurs associées aux points particuliers de notre ensemble d’entraînement :

Vous pouvez remarquer qu’on spécifie cette fois les paramètres $\mathbf{w}$ et $b$ pour la fonction $J$ : la raison est que nous voulons maintenant optimiser la fonction $J$, c’est-à-dire trouver les valeurs de ses paramètres ($\mathbf{w}$ et $b$) qui vont faire en sorte de la minimiser (c-à-d que sa valeur soit la plus petite possible, quand on considère l’ensemble de toutes ses valeurs possibles, donc indirectement via l’ensemble de toutes les valeurs possibles pour ses paramètres $\mathbf{w}$ et $b$). Cette opération d’optimisation est l’essence même de l’apprentissage automatique. Apprendre, c’est optimiser une fonction d’erreur, de manière à la rendre la plus petite possible. On fait cela à l’aide de la technique de la descente de gradient, qui consiste à déterminer tout d’abord la “direction” (c-à-d le vecteur) dans laquelle la valeur de la fonction change le plus, à un point donné. Si on utilise la métaphore d’un terrain montagneux pour représenter une fonction d’erreur en 3 dimensions, l’altitude d’un point à un endroit particulier représente la valeur de la fonction, tant que les coordonnées géographiques du point (x et y, ou lat/lon si on utilise un GPS), représentent les paramètres. Le gradient, dans cette métaphore, représente la direction dans laquelle le changement d’altitude sera le plus abrupt.

Le symbole $\partial$ peut faire un peu peur à priori, mais sa signification devient claire quand on le traduit en mots : le gradient de la fonction $J$ par rapport au paramètre $w$ (ou $b$). Et son calcul, dans le cas de la régression logistique, est très simple : pour chaque point, on considère :

1. La différence entre la probabilité produite par le modèle et la vraie étiquette : $\hat{y}^{(i)} - y^{(i)}$
2. Le produit de cette différence et du vecteur d’entrée : $(\hat{y}^{(i)} - y^{(i)}) \mathbf{x}^{(i)}$ (rappelons que $\mathbf{x} = [x_1, x_2]$ est un vecteur à deux dimensions, donc ce produit sera également bi-dimensionnel, tout comme l’est également $\mathbf{w}$)
3. On veut la moyenne de ces produits (donc la somme et une division)

Nos règles de mise à jour (la mise à jour, qui est un concept généralement plus associé à la programmation qu’aux mathématiques, est représentée ici par le symbole $\leftarrow$) pour les paramètres sont donc :

L’algorithme d’optimisation (apprentissage) de la régression logistique consiste donc en l’application itérative (répétée) de ces règles de mise à jour des paramètres, qui feront en sorte de changer graduellement les valeurs de $\mathbf{w}$ et $\mathbf{b}$, tout en diminuant également progressivement la valeur de l’erreur cumulée, c’est-à-dire la valeur de la fonction $J$. $\alpha$ est le taux d’apprentissage (une simple valeur numérique), qui fait en sorte de limiter la taille des “pas” qu’on prend dans la direction du gradient, à chaque itération. Pour le distinguer des paramètres ($\mathbf{w}$ et $\mathbf{b}$), on appelle $\alpha$ un hyper-paramètre.

Si cela vous intéresse, voici du code Python qui met en oeuvre la régression logistique que nous venons d’étudier. Le code est délibérément détaillé et assez “bas niveau”, car il utilise seulement numpy, une librairie pour faire des opérations basées sur l’algèbre linéaire (ainsi que Matplotlib pour faire les visualisations). Si on utilisait une librairie d’apprentissage automatique spécialisée, comme Scikit-learn par exemple, le code serait plus simple et compact, étant donné que le niveau d’abstraction serait plus élevé (bien qu’il s’agirait toujours de Python, le code serait de plus “haut niveau”). Il n’est pas nécessaire de comprendre ce code dans les détails, mais il peut s’avérer intéressant d’en avoir un aperçu, car il est très représentatif de ce qui se fait dans de vrais environnements de programmation.

Chaque couple dimension + classe sera modélisé par une gaussienne à une dimension (donc 4 modèles en tout : un pour la classe rouge sur la dimension $x$, un pour la classe bleue aussi sur $x_1$, et la même chose pour la dimension $x_2$). Une gaussienne (aussi appelée distribution normale) est la fameuse “courbe en cloche”, qui détermine comment la “masse de probabilité” est répartie autour d’une valeur centrale (qu’on appelle la moyenne) :

La gaussienne est une fonction continue 1D car elle n’a qu’une seule valeur dépendante (l’axe horizontal). L’axe vertical, la valeur de la fonction, correspond à la masse de la probabilité. Remarquez un aspect important : la valeur de la fonction à un point précis donné sur l’axe horizontal (par exemple la moyenne) ne correspond PAS à la probabilité de ce point, malgré ce que l’intuition voudrait croire. Étant donné que la masse de probabilité est une fonction continue, pour obtenir une probabilité donnée il faut calculer l’intégrale de la fonction entre deux points donnés. Étant donné que la totalité de la masse (l’aire sous la courbe) est 1, on peut dire que la probabilité qu’un événement soit plus petit que la moyenne (ou plus grand) est de 50% (c-à-d que l’aire sous la courbe, ou l’intégrale, de la partie à droite ou à gauche de la barre verticale de la moyenne totalise 0.5).

Mais donc que veut-on dire par la modélisation par une gaussienne?

La première étape consiste à projeter les points sur l’axe $x_1$, ce qui les rend uni-dimensionnels.

Une fois les points projetés, on peut modéliser (c-à-d décrire mathématiquement) les classes de points à l’aide de gaussiennes, dont l’épaisseur correspondra à la densité (ou quantité) de points projetés sur l’axe, pour chaque classe.

On répète la procédure pour les deux classes, sur l’axe $x_2$.

À ce stade, nous avons donc quatre modèles :

où $\mathcal{N}$ représente la gaussienne, et $\mu$ et $\sigma$ représentent ses paramètres (qui déterminent sa forme particulière). L’apprentissage d’un modèle de classification naive bayésienne constitue donc le calcul des valeurs optimales pour ces différents paramètres, que l’on peut faire directement dans ce contexte (en contraste de la méthode itérative que nous avons utilisée pour l’apprentissage des paramètres de la régression logistique) :

On peut combiner les modèles :

ou encore, pour simplifier :

Notez qu’on change ici la notation de $p$ à $P$, pour mettre l’emphase sur le fait que nous passons d’une fonction de densité à une fonction de probabilité. Ce modèle est génératif, car il génère un point $\mathbf{x}$ (donc ses coordonnées $x_1$ et $x_2$), à partir d’une classe donnée $y$ (rouge ou bleue). On dit aussi que ce que ce modèle est la probabilité de $\mathbf{x}$ conditionnelle à $y$.

Mais ce qui nous intéresse, dans un contexte de classification, est l’équivalent de ce que nous avons calculé pour le modèle de régression logistique, soit :

Il semble donc que notre modèle génératif soit le contraire de ce qu’on l’on veut. Est-il possible de “l’inverser”, pour obtenir le modèle que l’on souhaite, soit la probabilité d’une classe étant donné un point?

Il est possible de faire cela à l’aide du théorème de Bayes (ce qui explique donc le nom de l’algorithme), qui stipule que :

Nous connaissons déjà évidemment $P(\mathbf{x} \mid y)$, que nous avons calculé ci-haut, et $P(y)$ est simple à calculer : il s’agit simplement de la probabilité à priori (sans aucune autre connaissance) que les points soient rouges ou bleus (ce qui est possiblement 50%, équiprobable, si notre ensemble d’entraînement est balancé, moitié rouge moitié bleu). $P(\mathbf{x})$ est moins clair (la probabilité à priori des données?), mais étant donné que cette valeur ne dépend pas de $y$, on peut simplement l’ignorer pour obtenir un algorithme de classification final :

Tout comme la régression logistique que nous avons étudiée, cet algorithme produit une décision linéaire, pour des raisons mathématiques que nous n’allons pas explorer plus à fond.

Question intéressante à se poser : pourquoi la décision est une ligne?

Le modèle probabiliste : multinomial #

Dans le cas du classificateur naïf bayésien pour les données en deux dimensions, nous avions supposé que chaque classe (par exemple bleu et rouge) était associée à une distribution gaussienne. Autrement dit, nous modélisions la distribution des variables continues $x_1$ et $x_2$ à l’aide d’une loi normale. Ce modèle est génératif dans le sens où il génère les données d’une classe (vecteurs 2D pour les classes bleu ou rouge, et vecteurs en dimension $|V|$ pour les classes pourriel ou courriel).

Dans le cas du texte d’un courriel, la situation est différente. Les variables $n_i$ sont des comptes de mots, et il est naturel de les modéliser par une distribution multinomiale. Si on lance un dé à 6 faces 1000 fois, la distribution multinomiale permet de calculer la probabilité d’obtenir $X_1$ fois la face, $X_2$ fois la face 2, et ainsi de suite. Il s’agit donc d’une distribution qui modélise des événements discrets (des comptes entiers) par opposition à la distribution normale qui modélise des valeurs continues.

Si un courriel appartient à la classe pourriel, alors la probabilité d’observer un vecteur $\mathbf{x}$ de comptes de mots est :

où :

• $N = \sum_{i=1}^{V} n_i$ est le nombre total de mots du courriel,
• $p_i$ est la probabilité à priori qu’un mot de classe pourriel soit le mot $i$ (cette probabilité à priori est probablement plus grande pour le mot “prix” que pour le mot “parent”, par exemple).

De la même façon, on définit un modèle multinomial pour la classe courriel.

Rappel : hypothèse de naïveté #

Comme dans le modèle gaussien naïf bayésien, nous faisons l’hypothèse que les mots sont générés indépendamment les uns des autres. Cette hypothèse est évidemment fausse (certains mots apparaissent souvent ensemble), mais elle rend le modèle beaucoup plus simple et efficace en pratique.

Décision du classificateur #

Pour classer un courriel, nous utilisons la règle de Bayes :

ce qui permet, en ignorant $P(\mathbf{x})$ pour la même raison que celle expliquée ci-haut, d’obtenir un algorithme de classification similaire à celui que nous avons déjà vu :

Cela montre que la décision finale est une combinaison linéaire pondérée des fréquences de mots, ce qui fait le lien avec la régression logistique étudiée précédemment.

Mathématiquement, pour $n$ points de données :

Cette fonction $J$ est comme une “carte topographique” de l’erreur : pour chaque paire de valeurs $(m, b)$, elle donne une hauteur représentant le niveau d’erreur. L’objectif est de trouver le point le plus bas de cette carte – les valeurs optimales de $m$ et $b$ qui minimisent $J$. Dans l’exemple interactif, quand vous déplacez la ligne avec la souris, vous modifiez $m$ et $b$ manuellement, et vous voyez l’erreur diminuer (ou augmenter) en temps réel. Mais un algorithme fait ça automatiquement, de manière systématique.

Minimiser l’erreur : deux approches principales #

Il existe deux façons classiques de trouver ces paramètres optimaux : une méthode analytique (exacte et rapide pour des cas simples) et une méthode itérative (plus générale, surtout utile pour des problèmes complexes ou en haute dimension).

1. La méthode des moindres carrés (analytique) #

C’est la plus traditionnelle, inventée par Gauss au 19e siècle. L’idée est de résoudre directement l’équation qui met les dérivées partielles de $J$ à zéro (les points où la pente de la “carte topographique” est nulle, donc un minimum). Pour notre cas simple en une dimension :

En résolvant ces équations, on obtient des formules fermées pour $m$ et $b$ :

• $ m = \frac{n \sum (x_i y_i) - \sum x_i \sum y_i}{n \sum x_i^2 - (\sum x_i)^2} $
• $ b = \frac{\sum y_i - m \sum x_i}{n} $

C’est comme appuyer sur un bouton “calculer” : pas d’itérations, juste un résultat exact. Ça marche super bien pour des données pas trop volumineuses, et c’est ce que font la plupart des tableurs comme Excel quand vous ajoutez une “tendance linéaire” à un graphique.

2. La descente de gradient (itérative) #

C’est la même technique que nous avons vue pour la régression logistique ! On imagine $J(m, b)$ comme une vallée montagneuse en 3D (avec $m$ et $b$ comme coordonnées x et y, et l’erreur comme altitude). On commence avec des valeurs aléatoires pour $m$ et $b$, puis on calcule le gradient (la direction de la pente la plus raide vers le bas) et on fait un petit pas dans cette direction. On répète jusqu’à ce que l’erreur ne diminue plus beaucoup.

Les règles de mise à jour sont :

Où $\alpha$ est le taux d’apprentissage (un hyper-paramètre que l’on ajuste : trop grand, et on risque de “sauter” par-dessus le minimum ; trop petit, et ça prend une éternité). Les dérivées partielles sont :

Cette méthode est puissante car elle s’étend facilement à plus de dimensions (par exemple, prédire le prix d’une maison avec superficie, âge, et nombre de chambres – on aurait alors $y = w_1 x_1 + w_2 x_2 + w_3 x_3 + b$, avec un vecteur de poids $\mathbf{w}$). C’est aussi la base de l’entraînement des réseaux de neurones modernes.