Classification et régression logistique

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

décrire un classifieur par sa frontière de décision, et reconnaître un classifieur linéaire à son score affine $z = w_{0} + w^{⊤} x$ ;
appliquer les moindres carrés à des étiquettes 0/1, calculer le classifieur obtenu sur le jeu B, et expliquer pourquoi un exemple facile et lointain suffit à le dérégler;
écrire le modèle de régression logistique $\overset{p}{^} = σ (w_{0} + w^{⊤} x)$ , interpréter ses coefficients comme des effets sur la , et démontrer que ;

Classer, c'est découper le plan

Le chapitre 1 a posé le problème du filtre à pourriels: seize courriels décrits par deux nombres, $x_{1}$ le taux de mots suspects et $x_{2}$ la part de majuscules, et une étiquette $y \in {0, 1}$ . Il l'a résolu de la façon la plus paresseuse possible, en recopiant l'étiquette du plus proche voisin. Les chapitres 2 et 3 ont ensuite construit, pour la régression, une méthode tout autre: choisir une fonction dans une famille paramétrée en minimisant une perte, par une formule fermée ou par une descente de gradient. Ce chapitre fait la même chose pour la classification. La question est simple à poser: quelle famille de fonctions, et quelle perte?

Un classifieur binaire est une fonction qui associe à chaque point $x$ du plan l'une des deux classes. Il découpe donc le plan en deux régions, celle où il répond 1 et celle où il répond 0, et toute l'information qu'il contient est dans la ligne qui les sépare.

Le mot «linéaire» désigne la forme de la frontière, pas celle du classifieur, qui est une fonction en escalier. La géométrie est celle d'Algèbre linéaire: le vecteur $w$ est normal à la frontière, il pointe vers la région où le score est positif, et le score $z$ d'un point est proportionnel à sa distance signée à la frontière, à savoir $z / ∥ w ∥$ . Multiplier $(w_{0}, w)$ par une constante positive ne change donc pas le classifieur: ce sont les mêmes deux régions, avec des scores plus grands. Cette remarque, anodine en apparence, reviendra à la fin du chapitre sous la forme d'un vrai problème.

Sur le jeu B, un classifieur linéaire est une droite du plan $(x_{1}, x_{2})$ avec un côté «pourriel». La figure 1.1 du chapitre 1 a montré qu'aucune droite ne sépare parfaitement les deux classes, à cause de E8 et de E15. Il faut donc un critère pour choisir la meilleure droite. Le taux d'erreur, c'est-à-dire la moyenne de la perte 0–1, est le critère naturel; il est aussi inutilisable pour l'optimisation, parce qu'il est constant par morceaux: une petite rotation de la droite ne change en général aucune prédiction, et le gradient est nul presque partout. Le chapitre 1 l'avait annoncé: il faut une perte lisse. La première idée qui vient à l'esprit est celle que l'on connaît déjà.

Pour les programmes du chapitre, le jeu B s'écrit comme au chapitre 1. Ce sont des données fictives, construites pour le cours:

# Jeu de données B: ((x1, x2), y), de E1 à E16 dans l'ordre. Données fictives.
courriels = [
    ((1, 0), 0), ((2, 1), 0), ((0, 2), 0), ((3, 0), 0),
    ((1, 3), 0), ((4, 2), 0), ((2, 5),

Première tentative: les moindres carrés

Les étiquettes 0 et 1 sont des nombres. Rien n'empêche de les traiter comme une cible de régression, d'ajuster par moindres carrés un modèle affine $f (x) = w_{0} + w_{1} x_{1} + w_{2} x_{2}$ , exactement comme au chapitre 2, puis de classer un point comme pourriel quand , c'est-à-dire quand il est plus près de 1 que de 0. C'est la (). Elle a deux mérites: elle se calcule par une formule fermée, les équations normales , et elle produit un classifieur linéaire, puisque la frontière est une droite.

Le résultat est bon, et l'on pourrait s'arrêter là. Mais il repose sur une perte, la perte carrée, qui ne mesure pas ce que l'on veut. Elle pénalise l'écart entre le score et l'étiquette dans les deux sens: un pourriel de score $1, 2369$ est puni pour son écart de $0, 2369$ exactement comme le serait un score de $0, 7631$ . Or un score de $1, 24$ pour un pourriel n'est pas une erreur; c'est une prédiction très juste. Une perte qui punit un exemple pour être trop bien classé doit produire des effets curieux, et il suffit d'un exemple pour les voir.

Ajoutons au jeu B un dix-septième courriel, E17, un pourriel caricatural: 30 ‰ de mots suspects et 30 % de majuscules, $x_{17} = (30, 30)$ . Tout le monde le classerait sans hésiter, et la frontière de l'exemple 4.1 le classe déjà correctement, avec un score de $5, 0905$ . Mais ce score est très loin de la cible $y = 1$ : son résidu, $1 - 5, 0905 = - 4, 0905$ , a un carré de , plus que toute la somme des carrés des seize autres. Les moindres carrés vont donc incliner la droite pour réduire ce résidu, au détriment des autres exemples. Refaisons le calcul avec les dix-sept courriels: on obtient

w_{0} = \frac{4 655}{15 284} = 0, 30457, w_{1} = \frac{2 777}{45 852} = 0, 06056, w_{2} = - \frac{5 699}{229 260} = - 0, 02486.

Le score de E17 est ramené à $1, 3758$ . Le prix de ce progrès est lourd: au seuil $1/2$ , cinq courriels sur seize sont désormais mal classés au lieu de deux. Aux erreurs inévitables E8 et E15 s'ajoutent trois pourriels parfaitement ordinaires, E10 (score $0, 4582$ ), E12 ( $0, 4225$ ) et E14 ( $0, 4939$ ). Pire, le coefficient $w_{2}$ est devenu négatif: d'après ce modèle, plus un courriel contient de majuscules, moins il est suspect.

La figure 4.1 montre ce qui s'est passé: un exemple facile et lointain a fait pivoter la frontière. Ce n'est pas un accident de nos données. La perte carrée mesure la distance entre le score et la cible, et un point loin de la frontière, du bon côté, a un score loin de 1; les moindres carrés le traitent comme une erreur grave. Plus le point est lointain, plus il pèse, alors même que sa classe ne fait aucun doute. Ce défaut est classique; le manuel de Bishop l'illustre par une expérience semblable, et il condamne la classification par moindres carrés dès que les données contiennent des exemples extrêmes — ce qui, pour des pourriels, est la règle plutôt que l'exception.

Le diagnostic indique le remède. Il faut un modèle dont la sortie reste dans $[0, 1]$ , qu'on puisse lire comme une probabilité, et une perte qui ne punisse plus un exemple pour être trop bien classé: un pourriel de probabilité prédite $0, 999$ ne doit presque rien coûter, qu'il soit à la distance 5 ou à la distance 50 de la frontière. Les deux sections suivantes construisent ce modèle et cette perte.

Question 4.1

Avec le classifieur des moindres carrés de l'exemple 4.1 (seize courriels, $w_{0} = - 0, 17984$ , $w_{1} = 0, 09348$ , $w_{2} = 0, 08219$ ), calculez le score $f (x)$ d'un nouveau courriel $x = (5, 4)$ . Est-il classé pourriel?

La fonction sigmoïde

Pour qu'un score réel $z = w_{0} + w^{⊤} x$ , qui peut prendre n'importe quelle valeur, devienne une probabilité, il faut le faire passer par une fonction croissante de $R$ dans $] 0, 1 [$ . Le choix standard est le suivant.

La sigmoïde vaut $1/2$ en $0$ , tend vers $1$ quand $z \to + \infty$ et vers $0$ quand $z \to - \infty$ . Elle est presque linéaire autour de l'origine et presque constante loin d'elle: $σ (2) = 0, 8808$ , $σ (5) = 0, 9933$ , et . Le panneau de gauche de la figure 4.2 la montre. Trois propriétés serviront tout au long du chapitre.

Démonstration. 1. En multipliant numérateur et dénominateur par $e^{z}$ ,

1 - σ (z) = \frac{e ^{- z}}{1 + e ^{- z}} = \frac{1}{e ^{z} + 1} = σ (- z) .

2. La fonction $z \mapsto 1 + e^{- z}$ est dérivable et ne s'annule pas; par la dérivée d'un inverse,

σ^{'} (z) = \frac{e ^{- z}}{( 1 + e ^{- z} ) ^{2}} = \frac{1}{1 + e ^{- z}} \cdot \frac{e ^{- z}}{1 + e ^{- z}} = σ (z) (1 - σ (z)),

la dernière égalité venant du calcul fait en 1. Comme $0 < σ (z) < 1$ , le produit est strictement positif, donc $σ$ est strictement croissante. Enfin $u (1 - u) \leq 1/4$ pour tout réel $u$ , puisque $1/4 - u (1 - u) = (u - 1/2)^{2} \geq 0$ , avec égalité si et seulement si , c'est-à-dire , c'est-à-dire .

3. $σ$ est continue, strictement croissante, de limites $0$ en $- \infty$ et $1$ en $+ \infty$ : c'est une bijection de $R$ sur $] 0, 1 [$ . Si $p = 1/ (1 + e^{- z})$ , alors , donc .

La formule $σ^{'} = σ (1 - σ)$ est la raison pour laquelle cette fonction est partout en apprentissage: sa dérivée se calcule à partir de sa valeur, sans nouvelle exponentielle. Elle va rendre le gradient de la perte remarquablement simple. Le chapitre 10 la retrouvera comme fonction d'activation des réseaux de neurones, avec sa faiblesse: une dérivée au plus égale à $1/4$ , qui s'effondre loin de l'origine.

Un modèle probabiliste de l'étiquette

Le modèle de la régression logistique consiste à passer le score linéaire dans la sigmoïde, et à lire le résultat comme la probabilité de la classe 1.

La relation (4.4), conséquence directe du point 3 du théorème 4.1, donne leur sens aux coefficients. Le modèle n'est pas linéaire en la probabilité, mais il l'est en la log-cote: augmenter $x_{j}$ d'une unité, les autres caractéristiques restant fixes, ajoute $w_{j}$ à la log-cote, donc multiplie la cote par $e^{w_{j}}$ . Une cote de 1 correspond à une probabilité de , une cote de 3 à une probabilité de — «trois contre un», comme aux courses. Le coefficient est la log-cote d'un point où toutes les caractéristiques sont nulles.

Il faut prendre la définition au sérieux: c'est une hypothèse sur la façon dont les étiquettes sont produites, au même titre que le bruit gaussien du chapitre 2. Elle dit que, pour un courriel de caractéristiques $x$ données, l'étiquette n'est pas déterminée: parmi tous les courriels qui auraient ces caractéristiques, une proportion $\overset{p}{^} (x)$ serait des pourriels. Les exemples «du mauvais côté» comme E8 et E15 ne sont donc plus des anomalies: le modèle leur attribue une probabilité, faible mais non nulle. Et l'hypothèse est forte: elle impose que la log-cote varie linéairement avec chaque caractéristique, ce qui n'a aucune raison d'être exact. On peut l'assouplir comme on l'a fait en régression, en ajoutant des caractéristiques dérivées ( $x_{1}^{2}$ , $x_{1} x_{2}$ ) dont le modèle reste linéaire en ses paramètres.

Question 4.2

Dans un modèle de régression logistique, le coefficient de la caractéristique $x_{1}$ vaut $w_{1} = ln 2 \approx 0, 693$ . Un courriel a une probabilité prédite $\overset{p}{^} = 0, 5$ . Quelle est la probabilité prédite pour un courriel identique, sauf que $x_{1}$ est plus grand d'une unité?

Vraisemblance et entropie croisée

Un modèle probabiliste se prête à une méthode d'estimation que vous connaissez: le maximum de vraisemblance (Probabilités et statistique, chapitre 10). On choisit les paramètres qui rendent les étiquettes observées les plus probables.

Sous le modèle (4.3), la probabilité d'observer l'étiquette $y_{i}$ pour l'exemple $x_{i}$ est $\overset{p}{^}_{i}$ si $y_{i} = 1$ et si , où . L'astuce d'écriture habituelle réunit les deux cas en une formule, , puisque l'un des deux exposants est nul. Les exemples étant supposés indépendants, la vraisemblance des étiquettes est le produit

L (θ) = i = 1 \prod n \overset{p}{^}_{i}^{y_{i}} (1 - \overset{p}{^}_{i})^{1 - y_{i}},

et la log-vraisemblance est la somme

ln L (θ) = i = 1 \sum n [y_{i} ln \overset{p}{^}_{i} + (1 - y_{i}) ln (1 - \overset{p}{^}_{i})] . (4.5)

Maximiser la log-vraisemblance revient à minimiser son opposé, et en divisant par $n$ on retrouve la forme d'un risque empirique.

La perte (4.6) a exactement le comportement réclamé à la fin de la section des moindres carrés. Pour un pourriel ( $y = 1$ ), elle vaut $- ln \overset{p}{^}$ : zéro si $\overset{p}{^} = 1$ , $0, 105$ si $\overset{p}{^} = 0, 9$ , si , si , et elle tend vers l'infini quand . Un exemple bien classé avec assurance ne coûte presque rien, quelle que soit sa distance à la frontière: il ne peut plus tirer sur la droite comme E17 le faisait. Un exemple mal classé avec assurance coûte cher, sans limite. Le panneau de droite de la figure 4.2 trace les deux branches.

Le nom d'entropie croisée vient de la théorie de l'information: pour deux lois $q$ et $p$ sur un ensemble fini, la quantité $- \sum_{k} q_{k} ln p_{k}$ s'appelle l'entropie croisée de $p$ relativement à . Avec , la loi «certaine» de l'étiquette observée, et , la loi prédite, on retrouve (4.6). Le chapitre 8 utilisera l'entropie, en bits, pour construire des arbres de décision.

Pourquoi ne pas garder la sigmoïde et lui associer la perte carrée, $(\overset{p}{^} - y)^{2}$ ? On le peut, mais on y perd. Dérivons cette perte par rapport au score $z$ , avec $\overset{p}{^} = σ (z)$ et le théorème 4.1:

\frac{\partial}{\partial z} (σ (z) - y)^{2} = 2 (σ (z) - y) σ (z) (1 - σ (z)) .

Prenez un pourriel ( $y = 1$ ) très mal classé, de score $z = - 10$ : $σ (z) = 4, 5 \cdot 1 0^{- 5}$ , et la dérivée vaut environ $- 9 \cdot 1 0^{- 5}$ . L'exemple le plus faux est presque invisible pour une descente de gradient, parce que le facteur écrase tout ce qui est loin de la frontière, dans un sens comme dans l'autre. Avec l'entropie croisée, la même dérivée vaut, nous allons le démontrer, : l'erreur la plus grave produit le signal le plus fort. De plus, la perte carrée composée avec la sigmoïde n'est pas convexe en , alors que l'entropie croisée l'est (théorème 4.3).

Question 4.3

Complétez sigmoide(z), qui doit renvoyer $1/ (1 + e^{- z})$ sans provoquer de dépassement pour un $z$ très négatif, et entropie_croisee(w, donnees), qui renvoie la perte moyenne (4.7) du modèle de coefficients w = (w0, w1, w2) sur une liste d'exemples ((x1, x2), y). Le programme affiche $σ (2)$ , puis l'entropie croisée sur le jeu B pour des poids nuls et pour les poids ajustés de la section suivante.

logistique.py

Le gradient de l'entropie croisée

Pour minimiser $J$ , il faut son gradient. Le calcul est l'un des plus élégants du cours: toutes les dérivées de la sigmoïde se simplifient, et le résultat a exactement la forme du gradient des moindres carrés. Les rappels sur le gradient d'une fonction de plusieurs variables et sur la règle de dérivation en chaîne sont dans l'annexe A.

Démonstration. Fixons un exemple et notons $z = \tilde{x}^{⊤} θ$ son score, $\overset{p}{^} = σ (z)$ . Exprimons d'abord la perte en fonction de $z$ . Par le théorème 4.1, $ln \overset{p}{^} = ln σ (z)$ et , donc

ℓ = - y ln σ (z) - (1 - y) ln σ (- z) .

La dérivée de $ln σ$ est $σ^{'} / σ = 1 - σ$ . Par la règle de dérivation en chaîne,

\frac{d}{d z} ln σ (z) = 1 - σ (z), \frac{d}{d z} ln σ (- z) = - (1 - σ (- z)) = - σ (z),

la seconde égalité utilisant encore $1 - σ (- z) = σ (z)$ . Donc

\frac{d ℓ}{d z} = - y (1 - σ (z)) + (1 - y) σ (z) = σ (z) - y = \overset{p}{^} - y .

Le score dépend de $θ$ linéairement: $\partial z / \partial θ_{j} = \tilde{x}_{j}$ , d'où $\nabla_{θ} ℓ = (\overset{p}{^} - y) \tilde{x}$ par la règle de dérivation en chaîne. En faisant la moyenne sur les exemples, on obtient la première forme de (4.8). La seconde en est l'écriture matricielle: la -ième composante de est .

Comparez avec le chapitre 3: le gradient de l'erreur quadratique moyenne d'un modèle linéaire est $\frac{2}{n} \tilde{X}^{⊤} (\tilde{X} θ - y)$ . C'est la même forme — la matrice $\tilde{X}^{⊤}$ appliquée au vecteur des écarts entre prédictions et étiquettes —, à la différence près que les prédictions sont maintenant , appliquée composante par composante. Chaque exemple tire sur les paramètres dans la direction de , avec une force comprise entre et . Un exemple bien classé avec assurance a et ne tire plus; c'est la propriété qui manquait aux moindres carrés.

Démonstration. Dérivons la $j$ -ième composante du gradient (4.8), $\frac{1}{n} \sum_{i} (\overset{p}{^}_{i} - y_{i}) \tilde{x}_{ij}$ , par rapport à . Seul dépend de , et par le théorème 4.1 et la règle de dérivation en chaîne, . D'où

\frac{\partial ^{2} J}{\partial θ _{j} \partial θ _{k}} = \frac{1}{n} i = 1 \sum n \overset{p}{^}_{i} (1 - \overset{p}{^}_{i}) \tilde{x}_{ij} \tilde{x}_{ik},

qui est le coefficient $(j, k)$ de $\frac{1}{n} \tilde{X}^{⊤} D \tilde{X}$ . Pour tout vecteur $v \in R^{d + 1}$ , posons ; alors

v^{⊤} (\tilde{X}^{⊤} D \tilde{X}) v = u^{⊤} D u = i = 1 \sum n \overset{p}{^}_{i} (1 - \overset{p}{^}_{i}) u_{i}^{2} \geq 0,

car chaque $\overset{p}{^}_{i} (1 - \overset{p}{^}_{i})$ est strictement positif. La hessienne est donc semi-définie positive en tout point, et une fonction deux fois dérivable dont la hessienne est partout semi-définie positive est convexe (Algèbre linéaire, chapitre 11, pour les formes quadratiques; chapitre 3 de ce cours pour la convexité). Si $\tilde{X}$ est de rang , entraîne , donc un , et la somme est strictement positive.

La convexité a la conséquence pratique la plus précieuse qui soit: tout minimum local est global, et une descente de gradient bien réglée ne peut pas se perdre dans un minimum parasite. Il n'y a qu'une difficulté. Annuler le gradient (4.8) donne le système

i = 1 \sum n (σ (\tilde{x}_{i}^{⊤} θ) - y_{i}) \tilde{x}_{i} = 0,

qui ressemble aux équations normales mais n'est pas linéaire en $θ$ , à cause de la sigmoïde. Il n'a pas de solution en forme fermée. On le résout de façon itérative — et c'est ici que le chapitre 3 paie: la descente de gradient, $θ^{(k + 1)} = θ^{(k)} - η \nabla J (θ^{(k)})$ , s'applique telle quelle.

La suite est moins plaisante. Avec ce même pas $η = 0, 1$ , la convergence est lente: après cinq mille pas, on lit $(- 5, 157; 0, 675; 0, 672)$ , contre $(- 5, 1758; 0, 67656; 0, 67502)$ à l'optimum. Le coût, $0, 30816$ contre $0, 30815$ , est déjà à près, mais est encore à de sa valeur optimale, et il en faut 10 000 pour arriver à . Le chapitre 3 a donné la raison: le problème est . À l'optimum, la hessienne (4.9) a des valeurs propres d'environ , et , dans un rapport de plus de 300; la direction la plus plate impose de petits pas dans la plus raide. Et l'on ne peut pas augmenter le pas sans précaution: au départ, la hessienne vaut , de plus grande valeur propre , et le seuil du chapitre 3 vaut alors . Standardiser les caractéristiques, comme au chapitre 3, améliore beaucoup les choses.

La méthode de Newton: six itérations au lieu de cinq mille

Comme $J$ est deux fois dérivable et que sa hessienne (4.9) se calcule aussi facilement que son gradient, on peut faire mieux qu'une descente de gradient: la méthode de Newton pose $θ^{(k + 1)} = θ^{(k)} - (\nabla^{2} J (θ^{(k)}))^{- 1} \nabla J (θ^{(k)})$ , ce qui revient à résoudre à chaque pas un système linéaire de taille — une sorte d'équations normales pondérées par , d'où son autre nom, (, IRLS). Sur le jeu B, en partant de , les coûts successifs sont ; ; ; , après quoi le coût ne bouge plus à la cinquième décimale, et les coefficients sont stables à cinq décimales dès la sixième itération. C'est ainsi qu'ont été calculées les valeurs de référence de ce chapitre. Le prix est un système de taille à résoudre à chaque pas: raisonnable pour quelques centaines de caractéristiques, prohibitif pour des millions, où l'on revient aux méthodes de gradient du chapitre 3.

Question 4.4

Complétez gradient(w, donnees), qui renvoie la liste des trois composantes du gradient (4.8) du coût d'entropie croisée au point w = [w0, w1, w2]. Le programme affiche le gradient en $0$ (exemple 4.2), puis fait 5 000 pas de descente de gradient de pas $η = 0, 1$ sur le jeu B et affiche les coefficients obtenus.

descente_logistique.py

Le modèle ajusté sur le jeu B

Minimisée jusqu'au bout, l'entropie croisée sur le jeu B donne les coefficients

w_{0} = - 5, 1758, w_{1} = 0, 67656, w_{2} = 0, 67502,

pour une log-vraisemblance de $- 4, 9305$ et une entropie croisée moyenne de $J = 0, 30815$ . Comme le coût est convexe et que $\tilde{X}$ est de rang 3, ce minimum est unique. Lisons ce modèle.

Revenons enfin à E17, le pourriel lointain qui avait fait basculer les moindres carrés. Ajouté au jeu B, il reçoit une probabilité qui ne diffère de 1 que d'environ $4 \cdot 1 0^{- 16}$ ; sa contribution $(\overset{p}{^}_{17} - 1) \tilde{x}_{17}$ au gradient est négligeable, et les coefficients recalculés sur dix-sept courriels coïncident avec les précédents à quatre décimales près. C'était tout l'enjeu.

Explorateur 4.1 · Régler à la main une régression logistique

Réglez les trois coefficients du score $z = w_{0} + w_{1} x_{1} + w_{2} x_{2}$ . Le trait plein est la frontière $\overset{p}{^} = 0, 5$ , les deux tirets les lignes $\overset{p}{^} = 0, 1$ et $\overset{p}{^} = 0, 9$ ; le pointillé est la frontière du maximum de vraisemblance, qui ne bouge pas. En bas, la probabilité prédite pour chaque courriel. L'entropie croisée moyenne ne descend jamais sous son minimum: cherchez-le, puis regardez ce que coûtent E8 et E15.

w₀ (constante)−5,18

w₁ (mots suspects)0,68

w₂ (majuscules)0,68

Entropie croisée moyenne

0,3082

Minimum (maximum de vraisemblance)

0,3082

Bien classés au seuil 0,5

14 sur 16

Courriel le plus coûteux

E15: 1,936

L'explorateur part du modèle ajusté, arrondi au centième. Le trait plein est la frontière $\overset{p}{^} = 1/2$ , et les deux tirets les lignes de niveau $\overset{p}{^} = 0, 1$ et $\overset{p}{^} = 0, 9$ ; ces trois lignes sont , parce que équivaut à , une équation affine en . Multipliez , et par deux, à peu près, en gardant leurs rapports: la frontière ne bouge pas, mais les lignes et se resserrent, le modèle devient plus tranché, et l'entropie croisée à cause de E8 et E15, qui deviennent des erreurs plus confiantes. Inversement, divisez les trois coefficients par deux: le modèle devient timide, et l'entropie croisée remonte aussi. Le maximum de vraisemblance règle donc deux choses à la fois: la position de la frontière et la de la transition.

Question 4.5

Avec la régression logistique ajustée sur le jeu B ( $w_{0} = - 5, 1758$ , $w_{1} = 0, 67656$ , $w_{2} = 0, 67502$ ), quelle est la probabilité prédite qu'un courriel $x = (3, 4)$ soit un pourriel?

La frontière de décision et le choix du seuil

La régression logistique produit une probabilité; il faut encore décider. La règle par défaut classe un courriel comme pourriel quand $\overset{p}{^} (x) > 1/2$ . Comme $σ$ est strictement croissante et $σ (0) = 1/2$ ,

\overset{p}{^} (x) > \frac{1}{2} ⟺ w_{0} + w_{1} x_{1} + w_{2} x_{2} > 0,

et la régression logistique est un classifieur linéaire au sens de la définition 4.1. Sur le jeu B, la frontière est la droite $- 5, 1758 + 0, 67656 x_{1} + 0, 67502 x_{2} = 0$ , qui coupe l'axe $x_{1}$ en et l'axe en : à peu près la droite . Toute la non-linéarité de la sigmoïde sert à fabriquer des probabilités; elle ne courbe pas la frontière.

Rien n'oblige à couper à $1/2$ . Plus généralement, un seuil $s \in] 0, 1 [$ donne la règle $\overset{p}{^} > s$ , c'est-à-dire $z > logit (s)$ — un point exactement sur la frontière, $\overset{p}{^} = s$ , est attribué à la classe 0, comme dans la définition 4.1 (le chapitre 5 note ce seuil ): la frontière glisse parallèlement à elle-même. Le bon seuil dépend de ce que coûtent les erreurs. Reprenons les coûts de l'exercice 1.4: écarter un courriel légitime coûte 5, laisser passer un pourriel coûte 1. Si est la vraie probabilité que le courriel soit un pourriel, l'écarter coûte en moyenne et le garder coûte . On l'écarte donc si , c'est-à-dire si

\overset{p}{^} > \frac{5}{6} = 0, 8333 ⟺ z > ln 5 = 1, 6094.

Sur le jeu B, ce seuil ne signale plus que cinq courriels, E9, E10, E11, E13 et E14. E8, le courriel légitime le plus menacé, est épargné; en contrepartie, trois pourriels passent, E12, E15 et E16 ( $\overset{p}{^} = 0, 8299$ , juste sous le seuil). Trois erreurs au lieu de deux, mais des erreurs moins chères: c'est le prix d'un filtre prudent. Le chapitre 5 étudie systématiquement ce compromis, en faisant varier le seuil de 0 à 1 et en traçant la courbe ROC.

Une probabilité prédite n'est pas automatiquement calibrée

Le raisonnement sur le seuil $5/6$ suppose que $\overset{p}{^}$ est une vraie probabilité: que, parmi les courriels auxquels le modèle attribue $\overset{p}{^} = 0, 8$ , environ 80 % soient effectivement des pourriels. On dit alors que le modèle est calibré (). Rien ne le garantit. Le modèle (4.3) peut être faux — la log-cote n'a aucune raison d'être exactement linéaire —, il est estimé sur seize exemples, et les probabilités sont évaluées sur les mêmes données qui ont servi à l'ajustement. La régression logistique est souvent assez bien calibrée quand le modèle est raisonnable et les données nombreuses; beaucoup d'autres méthodes, comme les machines à vecteurs de support du chapitre 9, ne produisent même pas de probabilité. Avant de fonder une décision coûteuse sur , on vérifie la calibration sur des données de test, en comparant les probabilités annoncées aux fréquences observées.

Données séparables: des poids qui divergent

Le jeu B n'est pas séparable, grâce à E8 et E15. Que se passerait-il s'il l'était?

Retirons E8 et E15 du jeu B. Les quatorze courriels restants sont séparables: les sept légitimes ont $x_{1} + x_{2} \leq 7$ , les sept pourriels $x_{1} + x_{2} \geq 9$ , et la droite les sépare, avec .

Démonstration. Pour un exemple de score $z$ , la perte s'écrit $ℓ = - ln σ (z)$ si $y = 1$ et $- ln σ (- z)$ si $y = 0$ (démonstration du théorème 4.2). Posons $m_{i} = z_{i}$ si et si : c'est la de l'exemple, positive s'il est bien classé, et la perte vaut . Si sépare les données, toutes les marges sont strictement positives, et les marges de sont les . Chaque terme est strictement décroissant en et tend vers quand ; leur moyenne aussi. Donc . Enfin, chaque perte est strictement positive, puisque : pour tout , et la borne n'est jamais atteinte.

Sur les quatorze courriels séparables, avec $θ = t (- 8, 1, 1)$ , le coût vaut $0, 17786$ pour $t = 0, 5$ , $0, 07195$ pour $t = 1$ , $0, 02098$ pour et pour . Une descente de gradient ne s'arrête donc jamais: elle fait croître la norme des poids indéfiniment. Avec en partant de , la norme de vaut après 1 000 itérations, après 10 000 et après 100 000, tandis que le coût passe de à puis à . La frontière, elle, se stabilise; ce sont les probabilités qui dégénèrent vers 0 et 1, et la sigmoïde vers une marche d'escalier.

Ce comportement n'est pas un bogue, c'est la conséquence logique du maximum de vraisemblance: si une droite sépare parfaitement les exemples, le modèle le plus vraisemblable est celui qui en est infiniment sûr. Mais c'est presque toujours une mauvaise conclusion. Seize courriels séparables ne prouvent pas qu'un courriel de score légèrement positif est un pourriel avec une probabilité de 0,999999. Trois remèdes existent, et ils reviendront: arrêter la descente avant la convergence (arrêt précoce, chapitre 6); pénaliser la norme des poids en minimisant $J (θ) + λ ∥ w ∥_{2}^{2}$ , ce qui rétablit un minimum unique — la pénalité ajoute $2 λ I$ au bloc de la hessienne qui concerne $w$ , et rend le coût coercif (exercice 4.4) — le chapitre 6 étudie cette pénalité, dite ridge, en régression; ou changer de critère et chercher, parmi toutes les droites séparatrices, celle qui a la plus grande marge (chapitre 9).

Question 4.6

On entraîne une régression logistique sans régularisation, par descente de gradient, sur un jeu de données linéairement séparable. Que se passe-t-il au fil des itérations? (Plusieurs réponses possibles.)

Plusieurs réponses possibles

Plus de deux classes

Un filtre réel distingue souvent plus de deux catégories. Imaginons que la messagerie veuille séparer trois classes: les courriels légitimes (classe 0), les lettres d'information auxquelles on s'est abonné (classe 1), et les pourriels (classe 2). Les étiquettes deviennent $y \in {0, 1, \dots, K - 1}$ , ici avec $K = 3$ . Pour fixer les idées, utilisons quinze exemples T1 à T15, décrits par les deux mêmes caractéristiques que le jeu B. Ce sont des données fictives, construites pour ce chapitre, et distinctes du jeu B:

	T1	T2	T3	T4	T5	T6	T7	T8
$x_{1}$ (‰)	1	2	0	3	4	1	2	3
$x_{2}$ (%)	1	0	2	2	5	6	8	7
$y$	0	0	0	0	0	1	1	1

	T9	T10	T11	T12	T13	T14	T15
$x_{1}$ (‰)	0	6	7	8	6	9	2
$x_{2}$ (%)	5	4	2	5	6	3	3
$y$	1	1	2	2	2	2	2

Les lettres d'information ont beaucoup de majuscules (des titres) et peu de mots suspects; les pourriels ont beaucoup de mots suspects. Chaque classe contient un intrus, comme E8 et E15 dans le jeu B: T5, légitime parmi les lettres; T10, lettre parmi les pourriels; T15, pourriel parmi les légitimes.

Un contre tous

La façon la plus simple de traiter $K$ classes est de se ramener à $K$ problèmes binaires. Pour chaque classe $k$ , on entraîne une régression logistique qui sépare «la classe $k$ » (étiquette 1) de «toutes les autres» (étiquette 0); elle produit un score $z_{k} = w_{k 0} + w_{k}^{⊤} x$ . Pour classer un nouveau point, on choisit la classe dont le classifieur est le plus sûr de lui:

\overset{y}{^} = k arg max σ (z_{k}) = k arg max z_{k},

les deux formes étant équivalentes parce que $σ$ est croissante. C'est la méthode un contre tous (one-vs-rest, OvR). Sur les quinze exemples, les trois régressions logistiques ajustées classent correctement 12 exemples sur 15; les trois erreurs sont les trois intrus. La figure 4.3 montre les régions obtenues.

La figure révèle le défaut principal de la méthode. Les trois classifieurs ont été entraînés séparément, chacun sur son propre problème, et rien ne les coordonne. Dans le cadre de la figure, une partie du plan n'est revendiquée par aucun d'eux ( $σ (z_{k}) < 1/2$ pour les trois $k$ ), une autre par deux à la fois. Leurs probabilités ne s'additionnent pas non plus à 1: au point $(5, 5)$ , elles valent $0, 060$ , $0, 310$ et $0, 447$ , de somme . On peut les renormaliser, mais c'est un expédient. Un modèle conçu d'emblée pour classes fait mieux.

La fonction softmax

Les sorties de la softmax sont strictement positives et de somme 1 par construction: c'est une loi de probabilité sur les $K$ classes. Son nom vient de ce qu'elle est une version «douce» de l'arg max: si l'un des scores dépasse nettement les autres, sa probabilité est proche de 1 et les autres proches de 0. Avec $z = (2; 1; 0, 1)$ , on obtient $(0, 659; 0, 242; 0, 099)$ ; avec $z = (20; 10; 1)$ , la première probabilité vaut déjà .

Deux propriétés méritent d'être notées. La première: ajouter une même constante $c$ à tous les scores ne change pas la softmax, puisque $e^{z_{k} + c} = e^{c} e^{z_{k}}$ et que le facteur se simplifie. On s'en sert pour calculer sans dépassement, en soustrayant le plus grand score avant de prendre les exponentielles; et l'on en déduit que les vecteurs de poids ne sont pas tous identifiables — on peut fixer l'un d'eux à zéro sans perdre de généralité. La seconde: . Avec deux scores et ,

softmax (z)_{1} = \frac{e ^{z_{1}}}{e ^{z_{0}} + e ^{z_{1}}} = \frac{1}{1 + e ^{- (z_{1} - z_{0})}} = σ (z_{1} - z_{0}),

et la régression logistique binaire est la régression multinomiale dont on a fixé $z_{0} = 0$ . L'exercice 4.5 démontre de plus que le gradient de l'entropie croisée catégorielle par rapport au score $z_{k}$ d'un exemple vaut $\overset{p}{^}_{k} - 1 [y = k]$ , exactement comme dans le cas binaire: les prédictions moins les cibles, encore une fois. Il n'y a toujours pas de forme fermée, le coût est encore convexe, et on le minimise encore par descente de gradient. La softmax est la dernière couche habituelle des réseaux de neurones de classification, et elle reviendra au chapitre 11, au cœur du mécanisme d'attention.

Question 4.7

Complétez softmax(z), qui renvoie la liste des probabilités (4.10) sans dépassement même si un score vaut 1000, et predire(W, x), qui calcule les scores $z_{k} = w_{k 0} + w_{k 1} x_{1} + w_{k 2} x_{2}$ pour chaque ligne W[k] et renvoie le couple (classe la plus probable, liste des probabilités). Le programme reprend l'exemple 4.4.

softmax.py

Avec une bibliothèque

Pour information, voici l'équivalent dans scikit-learn, que vous n'avez pas à exécuter ici. Attention à un réglage par défaut: LogisticRegression régularise (pénalité $ℓ_{2}$ , paramètre C=1.0, inversement proportionnel à $λ$ , chapitre 9), et ne donne donc pas exactement les coefficients du maximum de vraisemblance de ce chapitre; penalty=None les rétablit dans les versions récentes. Avec plus de deux classes, elle ajuste par défaut le modèle multinomial (softmax).

from sklearn.linear_model import LogisticRegression

modele = LogisticRegression(penalty=None).fit(X, y)
print(modele.intercept_, modele.coef_)

Synthèse

Un classifieur binaire découpe l'espace des caractéristiques par une frontière de décision; il est linéaire si la frontière est l'hyperplan ${w_{0} + w^{⊤} x = 0}$ . La perte 0–1 étant inutilisable pour l'optimisation, on cherche une perte lisse.
La classification par moindres carrés régresse les étiquettes 0/1 et coupe à $1/2$ . Sur le jeu B, elle classe 14 courriels sur 16; mais un seul pourriel évident et lointain, E17 en $(30; 30)$ , fait passer ses erreurs à 5, parce que la perte carrée punit un exemple pour être trop bien classé.
La régression logistique modélise , avec et ; la log-cote est linéaire, et est le facteur multiplicatif de la cote par unité de .

Série d'exercices du chapitre 4Exercice 1 sur 5

Question 4.8

Calculez $σ (ln 3)$ .

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 4.1 · Lire un modèle logistique

On utilise la régression logistique ajustée sur le jeu B: $w_{0} = - 5, 1758$ , $w_{1} = 0, 67656$ , $w_{2} = 0, 67502$ .

Exercice 4.2 · Qui paie la perte?

On reprend les probabilités de l'exemple 4.3.

Calculez, avec les probabilités non arrondies du modèle, la perte d'entropie croisée de E13 ( $\overset{p}{^} = 0, 9965$ ), de E7 ( $\overset{p}{^} = 0, 3899$ ), de E8 ( $\overset{p}{^} = 0, 7127$ ) et de E15 ().

Exercice 4.3 · Les moindres carrés à une dimension

On classe des points de la droite réelle avec une seule caractéristique $x$ . Les points $x = 1, 2, 3$ sont de classe 0 et les points $x = 4, 5, 6$ de classe 1.

Calculez, par les formules du chapitre 2 ( $w_{1} = \sum (x_{i} - \overset{x}{ˉ}) (y_{i} - \overset{y}{ˉ}) / \sum (x_{i} - \overset{x}{ˉ})^{2}$ , ), la droite des moindres carrés , et la frontière .

Exercice 4.4 · Le coût le long d'une droite séparatrice

On retire E8 et E15 du jeu B; il reste quatorze courriels, séparés par la droite $x_{1} + x_{2} = 8$ .

Pour $θ = (- 8, 1, 1)$ , calculez les marges signées des quatorze courriels (définies dans la démonstration du théorème 4.4).

Exercice 4.5 · Le gradient de l'entropie croisée catégorielle (démonstration)

Pour un exemple de classe $y \in {0, \dots, K - 1}$ et de scores $z = (z_{0}, \dots, z_{K - 1})$ , on note et .

Références

Bishop, C. M., Pattern Recognition and Machine Learning, Springer, 2006, chap. 4 (classification par moindres carrés et sa sensibilité aux points éloignés, régression logistique, méthode IRLS, softmax).
Hastie, T., Tibshirani, R. et Friedman, J., The Elements of Statistical Learning, Springer, 2ᵉ éd., 2009, chap. 4 (régression d'un indicateur, régression logistique et son ajustement par Newton).
James, G., Witten, D., Hastie, T. et Tibshirani, R., An Introduction to Statistical Learning, Springer, 2ᵉ éd., 2021, chap. 4 (classification, régression logistique, interprétation des coefficients par la cote).
Murphy, K. P., Probabilistic Machine Learning: An Introduction, MIT Press, 2022, chap. 10 (régression logistique binaire et multinomiale, données séparables).
Azencott, C.-A., Introduction au Machine Learning, Dunod, 2ᵉ éd., 2022 (la régression logistique et la classification multiclasse, en français).

	E1	E2	E3	E4	E5	E6	E7	E8
$y$	0	0	0	0	0	0	0	0
$f (x_{i})$	$- 0, 0864$	$0, 0893$	$- 0, 0155$	$0, 1006$	$0, 1602$	$0, 3585$	$0, 4181$	$0, 6276$

	E1	E2	E3	E4	E5	E6	E7	E8
$y$	0	0	0	0	0	0	0	0
$\overset{p}{^}$	$0, 0110$	$0, 0412$	$0, 0213$	$0, 0412$	$0, 0777$	$0, 2461$	$0, 3899$	$0, 7127$