Le classifieur de Bayes et les plus proches voisins

La régression logistique a donné une façon de tracer une frontière. Avant de la comparer à d’autres, il vaut la peine de savoir à quoi ressemble la meilleure frontière possible - parce qu’il en existe une, qu’elle est imbattable, et que toutes les méthodes de ce parcours sont autant de tentatives de la deviner.

Le classifieur qu’on ne peut pas battre

Supposons que vous connaissiez, pour chaque point $x$, la vraie probabilité conditionnelle de chaque classe, $P(Y = j \mid X = x)$. Le classifieur de Bayes affecte $x$ à la classe dont cette probabilité est la plus grande.

Cette règle minimise le taux d’erreur, et l’argument est presque trop court pour mériter le nom de preuve. En chaque $x$ pris isolément, la probabilité de se tromper vaut $1 - \max_j P(Y = j \mid X = x)$, et aucune autre règle ne peut la rendre plus petite en ce point. Une règle optimale en chaque point est optimale en moyenne. L’erreur qui en résulte,

$$1 - E\left[\max_j P(Y = j \mid X)\right],$$

est le taux d’erreur de Bayes : l’analogue en classification de l’erreur irréductible. Il n’est pas nul, parce que les classes se recouvrent véritablement dans la population.

Remarquez ce que la règle exige. Il lui faut $P(Y \mid X)$ - précisément la quantité que toute méthode réelle cherche à estimer. Le classifieur de Bayes est donc une référence qu’on ne peut évaluer qu’en simulation, sur des données qu’on a soi-même construites. Ce n’est pas une raison de l’ignorer ; c’est la raison pour laquelle les simulations valent d’être menées.

Le calcul sur la droite

Prenons deux classes sur la droite réelle. La classe 1 est $N(-1{,}25, 1)$, la classe 2 est $N(1{,}25, 1)$, et elles sont également probables. Où est la frontière ?

Les lois a posteriori sont égales là où $\pi_1 f_1(x) = \pi_2 f_2(x)$. Avec des a priori égaux et des variances égales, les densités sont symétriques l’une de l’autre : la frontière est donc le milieu, $x = 0$. Tout ce qui est à gauche de zéro est déclaré classe 1.

Le taux d’erreur suit immédiatement. Une observation de classe 2 est mal classée lorsqu’elle tombe sous zéro, ce qui arrive avec probabilité $\Phi(-1{,}25) = 0{,}105650$, et par symétrie il en va de même pour la classe 1. Le taux d’erreur de Bayes vaut donc

$$0{,}105650 .$$

Environ une prédiction sur dix est fausse, et aucune méthode, si sophistiquée soit-elle, ne fera mieux sur ce problème. Intégrer numériquement le mélange sur quatre millions de points de la droite renvoie la même valeur à six décimales.

Ce que font les a priori

Rendons maintenant la classe 1 plus fréquente, avec $\pi_1 = 0{,}7$. La frontière résout $\pi_1 f_1(x) = \pi_2 f_2(x)$, et le passage au logarithme donne

$$x = \frac{\sigma^2 \log(\pi_1/\pi_2) + (\mu_2^2 - \mu_1^2)/2}{\mu_2 - \mu_1} = +0{,}338919 .$$

La frontière s’est déplacée vers la classe la plus rare, agrandissant la région de la classe 1. C’est le bon sens, et il vaut la peine de s’y arrêter, car le contraire est une supposition naturelle : puisque la classe 1 est plus fréquente, sa région ne devrait-elle pas rétrécir pour ne pas noyer la classe 2 ? Non - un point proche de zéro a désormais plus de chances de venir de la classe 1, simplement parce qu’il y a davantage de points de classe 1 dont il peut venir, et la règle optimale suit la loi a posteriori, non la densité.

Le gain est mesurable. À la frontière déplacée, le taux d’erreur vaut $0{,}093565$ ; garder la frontière à zéro en ignorant l’a priori donne $0{,}105650$, l’erreur coûte donc $0{,}012084$. À $\pi_1 = 0{,}9$ la frontière atteint $+0{,}878890$ et l’erreur tombe à $0{,}050496$, tandis que la frontière à zéro donne toujours $0{,}105650$ - à ce stade, ignorer l’a priori fait plus que doubler l’erreur.

Vérifiée contre une grille de 240 001 seuils candidats, la frontière dérivée est bien la meilleure disponible. C’est une petite chose à contrôler, et elle attrape les erreurs de signe, faciles à commettre ici et invisibles ensuite.

Imiter le classifieur de Bayes en comptant

Les données réelles n’arrivent pas avec $P(Y \mid X)$. Les k plus proches voisins l’estiment de la façon la plus directe qui soit : regarder les $k$ points d’entraînement les plus proches de $x_0$, et utiliser les proportions parmi eux.

$$P(Y = j \mid X = x_0) = \frac{1}{k} \sum_{i \in \mathcal{N}_0} I(y_i = j)$$

Puis appliquer la règle de Bayes à cette estimation. Rien n’est ajusté à l’avance - le jeu d’entraînement est le modèle, ce qui rend l’entraînement instantané et la prédiction coûteuse.

k est le bouton de flexibilité

Prenons un problème bidimensionnel dont le taux d’erreur de Bayes, obtenu par intégration, vaut $0{,}092708$. Ajustement sur 200 points d’entraînement, évaluation sur 20 000 points de test :

Lisez d’abord les deux extrémités. À $k = 1$, chaque point d’entraînement est son propre plus proche voisin : l’erreur d’entraînement est donc exactement nulle - et l’erreur de test, $0{,}138200$, est la pire du tableau hormis le $k = 199$ dégénéré. Cette seule paire de nombres est la démonstration la plus nette que vous verrez du fait que l’erreur d’entraînement n’est pas une estimation de l’erreur de test.

À $k = 199$ sur 200 points d’entraînement, presque tout l’échantillon vote à chaque prédiction. Le classifieur a cessé de dépendre de $x$ et renvoie simplement la classe majoritaire : son erreur, $0{,}504850$, est donc essentiellement l’a priori de classe. Biais maximal, variance minimale, aucune information.

Entre les deux, la courbe est en U, avec un plancher peu marqué de $k = 9$ à $k = 45$ et une meilleure valeur de $0{,}097150$ en $k = 15$ - à moins d’un demi-point du plancher de Bayes, pour une méthode qui n’a rien supposé sur la forme de la frontière. Il n’existe pas de formule pour le meilleur $k$ ; on le choisit par validation croisée, et la platitude du plancher fait qu’il suffit en général d’être à peu près juste.

Ce que cela coûte

La méthode n’impose aucune forme à la frontière : elle peut donc suivre des courbes et des régions disjointes qu’aucun modèle linéaire n’exprime. En échange, elle n’a aucun moyen d’ignorer une variable non pertinente : chaque dimension entre dans la distance, si bien que la précision se dégrade à mesure qu’on ajoute des variables non informatives. En grande dimension, les « plus proches » voisins ne sont proches de $x_0$ en aucun sens utile, ce qui est un visage du fléau de la dimension.

Et comme la distance est euclidienne, une variable mesurée en grandes unités la domine. Standardiser n’est pas ici un raffinement ; c’est une condition pour que la méthode signifie quoi que ce soit.

Avant le quiz

Le classifieur de Bayes retient la classe la plus probable en chaque point et ne peut être battu ; ce qu’il laisse derrière lui est le taux d’erreur de Bayes, $0{,}105650$ pour l’exemple unidimensionnel. Les a priori déplacent la frontière vers la classe la plus rare, et les ignorer coûte de façon mesurable. Les k plus proches voisins imitent la règle en comptant des voisins, $k$ étant le bouton de flexibilité : $k = 1$ mémorise, $k \approx n$ renvoie la classe majoritaire, et les valeurs utiles sont entre les deux.