5. Classification linéaire

La classification prédit une étiquette discrète à partir du même score linéaire \(\theta^T x\). Ce module passe en revue les classifieurs linéaires classiques comme un seul menu : les moindres carrés, qui supposent des classes de forme gaussienne et admettent une forme close, et le perceptron et la régression logistique, qui ne supposent rien sur la distribution et s'ajustent par descente de gradient. La régularisation ferme le module.

Objectifs

• Lire un classifieur linéaire comme un hyperplan séparateur dont le score donne le côté, rendant la prédiction aussi rapide qu'un produit scalaire.
• Situer les méthodes classiques selon leur hypothèse (gaussienne ou aucune) et leur ajustement (forme close ou descente de gradient).
• Classer par moindres carrés, en binaire et en multiclasse, et voir où cela casse.
• Entraîner le perceptron à partir de son critère, et connaître sa garantie de convergence et ses limites.
• Distinguer la descente de gradient par lots de la stochastique, et savoir que des optimiseurs plus élaborés existent.
• Ajuster la régression logistique par descente de gradient sur l'entropie croisée, en binaire et en multiclasse.
• Régulariser n'importe lequel de ces ajustements avec une pénalité, la vue maximum a posteriori.

5.1 Le séparateur linéaire

Un classifieur linéaire attribue la classe d'après le signe du score linéaire, et l'ensemble des entrées de score nul est la frontière de décision :

La frontière est un hyperplan : une droite avec deux caractéristiques, un plan avec trois. Le signe du score dit de quel côté de l'hyperplan l'entrée tombe, et sa grandeur à quelle distance de la frontière elle se trouve. Avec \(\theta = (-4, 1, 2)\) (biais en tête, sur l'entrée augmentée), le point \(x = (3, 2)\) obtient \(-4 + 3 + 4 = 3\) et tombe devant l'hyperplan, tandis que \(x = (1, 1)\) obtient \(-4 + 1 + 2 = -1\) et tombe derrière.

Remarque : deux avantages pratiques en découlent. Une fois l'entraînement terminé, l'ensemble d'entraînement peut être jeté, et prédire coûte un seul produit scalaire.

5.2 Un menu de méthodes

Les méthodes classiques ajustent cet hyperplan, et elles se séparent nettement selon ce qu'elles supposent des données et la façon dont elles se résolvent.

Les moindres carrés héritent du confort de la forme close de la Régression linéaire et le paient d'une hypothèse de distribution. Les deux autres ne supposent rien et le paient d'une optimisation itérative.

5.3 Les moindres carrés comme classifieur

Codons les deux classes \(y \in \{-1, +1\}\), traitons-les comme des cibles de régression, et tout le module Régression linéaire s'applique tel quel, forme close comprise :

Pour \(K > 2\) classes, on code chaque étiquette comme une ligne one-hot de \(Y \in \mathbb{R}^{m \times K}\) et on réutilise les prédictions multiples de la Régression linéaire, en prédisant la classe au score le plus élevé :

Cela peut fonctionner, mais la perte quadratique pénalise les grands scores même loin du bon côté, si bien que les points qui font le moins de doute tirent sur la frontière. C'est l'hypothèse gaussienne à l'œuvre : les moindres carrés traitent les étiquettes comme des cibles gaussiennes, et des données loin de cette histoire les cassent.

Sans points extrêmes, moindres carrés et régression logistique concordent. Ajouter des points lointains et pourtant bien classés fait basculer la frontière des moindres carrés dans l'erreur, tandis que la régression logistique bouge à peine.

5.4 Le perceptron

5.4.1 Modèle, perte et mise à jour

La première méthode sans hypothèse prend la définition du classifieur linéaire au pied de la lettre, un produit scalaire suivi d'une activation dure, le neurone historique :

À gauche : le perceptron est un seul neurone, les entrées pondérées sommées dans le score \(\theta^T x\) puis passées dans une activation signe dure. À droite : ce signe coupe l'espace d'entrée le long de l'hyperplan \(\theta^T x = 0\).

L'ajustement demande une perte, et compter les erreurs ne fonctionne pas : le compte est constant par morceaux, son gradient est donc nul presque partout. Le critère du perceptron pénalise plutôt chaque point mal classé selon la distance à laquelle il se trouve du mauvais côté. Une erreur signifie \(y^{(i)}\,\theta^T x^{(i)} < 0\), donc sur l'ensemble \(\mathcal{M}\) des points mal classés :

toujours positif et linéaire par morceaux. Le minimiser introduit l'outil de base de tout ce qui, dans ce cours, n'a pas de forme close, la descente de gradient : avancer les paramètres à répétition à l'opposé du gradient de la perte, mis à l'échelle par un taux d'apprentissage \(\alpha > 0\) :

La variante par lots calcule le gradient sur tout l'ensemble d'entraînement avant chaque pas, une descente lisse qui relit chaque exemple à chaque fois. La variante stochastique (SGD) avance sur un exemple à la fois, peu coûteuse et bruitée, et c'est le choix par défaut sur les grands jeux de données. Si \(\alpha\) est trop grand les itérés peuvent diverger, s'il est trop petit la convergence se traîne.

Remarque : des optimiseurs plus élaborés existent, momentum, Adam et leurs cousins, des raffinements de cette même règle qui comptent pour les réseaux profonds (Optimisation dans le cours de Deep Learning). Tout ce module se contente de la version simple.

Sur un seul exemple mal classé le gradient du critère vaut \(-y^{(i)} x^{(i)}\), le pas stochastique est donc la mise à jour du perceptron : sur une erreur,

et aucune mise à jour sinon. Dans le codage \(\{0, 1\}\) c'est la mise à jour résidu fois l'entrée \(\theta_j \leftarrow \theta_j + \alpha\,(y^{(i)} - h_\theta(x^{(i)}))\,x_j^{(i)}\).

Le perceptron trouve un hyperplan séparateur, pas nécessairement celui de marge maximale que la machine à vecteurs de support choisira.

5.4.2 Perceptron multiclasse

Avec \(k\) classes, on garde un vecteur de poids \(\theta_c\) par classe et on prédit celle au plus fort score. Sur une erreur, on récompense la vraie classe et on pénalise la classe prédite :

La vue en réseau s'étend naturellement : un neurone de score par classe, et un argmax là où le perceptron binaire avait un signe. En rassemblant les \(\theta_c\) comme colonnes d'une matrice \(W \in \mathbb{R}^{(n+1) \times k}\), un seul produit \(W^T x\) calcule tous les scores à la fois, et les scores découpent l'espace d'entrée en \(k\) régions, chacune revendiquée par la classe au score le plus élevé.

Un neurone de score par classe et un argmax au sommet. Chaque colonne de \(W\) (chaque ligne de \(W^T\)) est l'hyperplan, normale et biais, d'une classe.

Un exemple chiffré avec \(k = 3\) classes et l'entrée \(x = (1{,}1,\ -2{,}0)\), augmentée de \(x_0 = 1\) :

Le troisième score l'emporte, l'entrée est donc affectée à la classe 3. En lisant la troisième ligne, ce score vaut \(\theta_3^T x = -6 + 4 \times 1{,}1 + (-5) \times (-2{,}0) = 8{,}4\).

5.4.3 Convergence et limites

Si les données sont linéairement séparables, le perceptron converge en un nombre fini de mises à jour, sinon les poids oscillent indéfiniment. Et comme le critère vaut zéro sur tout hyperplan séparateur, tous comptent comme « optimaux », y compris ceux qui frôlent les données.

Remarque : trois améliorations corrigent ces limites, et chacune ouvre un module. Une activation et une perte lisses donnent la régression logistique, section suivante. Les marges et les fonctions de base mènent à la machine à vecteurs de support. Empiler les neurones en couches donne les réseaux de neurones multi-couches, point de départ du cours de Deep Learning.

5.5 La régression logistique

5.5.1 Une activation lisse

La régression logistique garde le neurone mais remplace l'échelon dur par la sigmoïde lisse, si bien que la sortie est la probabilité de la classe positive (\(y \in \{0, 1\}\)) :

Le même neurone avec l'échelon remplacé par la sigmoïde : la sortie devient la probabilité \(\phi = p(y = 1 \mid x)\), et la seuiller à \(\tfrac{1}{2}\) redonne la même frontière \(\theta^T x = 0\).

Remarque : la sigmoïde n'est pas un choix de compression arbitraire. Écrire l'a posteriori avec la règle de Bayes donne \(p(C_1 \mid x) = 1/(1 + e^{-a})\) avec \(a = \ln \frac{p(x \mid C_1)\,p(C_1)}{p(x \mid C_0)\,p(C_0)}\), donc une sortie logistique bien entraînée est exactement une probabilité a posteriori.

5.5.2 L'entropie croisée et son gradient

La vraisemblance d'étiquettes de Bernoulli, passée au \(-\log\), donne la perte d'entropie croisée :

Contrairement aux moindres carrés, cette perte n'a pas de minimiseur en forme close : la sigmoïde rend les équations de stationnarité transcendantes, l'ajustement revient donc à la même descente de gradient que le perceptron. Dériver l'entropie croisée à travers la sigmoïde récompense l'effort : presque tout se simplifie et le gradient se réduit au résidu fois l'entrée :

Remarque : contrairement au perceptron, le gradient fait intervenir chaque point d'entraînement, pas seulement les mal classés : chaque point tire proportionnellement à son résidu \(\phi^{(i)} - y^{(i)}\). C'est ce qui rend la régression logistique plus stable que le perceptron et utilisable sur des données non séparables.

À gauche : la sigmoïde envoie tout score dans l'intervalle (0, 1). À droite : la frontière de décision et la probabilité prédite.

5.5.3 Multiclasse : la softmax

Pour \(k\) classes, la sigmoïde se généralise en la softmax, un vecteur de poids par classe, normalisé en une distribution :

Avec des étiquettes one-hot, la perte est l'entropie croisée catégorielle \(L = -\sum_i \log p(y^{(i)} \mid x^{(i)})\), dont le gradient garde la même forme résidu fois l'entrée.

5.6 La classification régularisée

Rien ne fixe l'échelle de \(\theta\) : le doubler ne déplace aucune frontière du perceptron et ne fait qu'affûter les probabilités de la régression logistique, et des vecteurs de poids différents peuvent produire des scores identiques. La recette du maximum a posteriori de la Régression linéaire s'applique telle quelle, en ajoutant une pénalité à la perte minimisée, quelle qu'elle soit :

Pour l'entropie croisée avec la pénalité L2, le gradient gagne simplement une traction vers zéro, \(\sum_i (\phi^{(i)} - y^{(i)})\,x^{(i)} + 2\lambda\theta\).

Remarque : les bibliothèques exposent exactement ce menu, une perte plus une pénalité (le SGDClassifier de scikit-learn prend un argument loss et un argument penalty). L'intensité \(\lambda\) se choisit par la validation de Concepts généraux, et le comportement sélectif du lasso est couvert dans la Régression linéaire.

5.7 Résumé

Les méthodes sans hypothèse partagent une seule mise à jour, le résidu fois l'entrée :

Remarque : seule l'activation diffère (échelon, identité, sigmoïde ou softmax). Le cours de Deep Learning reprend précisément ce fil, en empilant de telles unités en couches.

Et les pertes en un coup d'œil :

Les modèles linéaires étant couverts, le module suivant empile ces briques en réseaux de neurones multi-couches.

Suivant : Réseaux de neurones multi-couches · Vue d'ensemble du cours