5. Classification linéaire
La classification prédit une étiquette discrète à partir du même score linéaire \(w^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.
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 :
\[\boxed{ h_w(x) = \mathrm{sign}(w^T x), \qquad w^T x = 0 \ \text{est la frontière} }\]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 \(w = (-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.
L'hyperplan \(w^T x = 0\) coupe l'espace d'entrée en deux : avec \(w = (-4, 1, 2)\) la frontière est la droite \(-4 + x_1 + 2x_2 = 0\), normale à \((w_1, w_2)\). Le point \((3, 2)\) obtient \(3\) et tombe devant, \((1, 1)\) obtient \(-1\) et tombe derrière, et la grandeur du score croît avec la distance à la frontière (pointillés).
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 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 :
\[\boxed{ w = (X^T X)^{-1}X^T y, \qquad h_w(x) = \mathrm{sign}(w^T x) }\]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é :
\[\boxed{ W = (X^T X)^{-1}X^T Y, \qquad \hat{y} = \arg\max_k \; (W^T x)_k }\]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.3 Le perceptron
5.3.1 Le modèle : un neurone
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 :
\[\boxed{ h_w(x) = \mathrm{sign}(w^T x), \qquad y \in \{-1, +1\} }\]
À gauche : le perceptron est un seul neurone, les entrées pondérées sommées dans le score \(w^T x\) puis passées dans une activation signe dure. À droite : ce signe coupe l'espace d'entrée le long de l'hyperplan \(w^T x = 0\).
5.3.2 La fonction de perte : le critère du perceptron
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)}\,w^T x^{(i)} < 0\), donc sur l'ensemble \(\mathcal{M}\) des points mal classés :
\[\boxed{ E(w) = -\sum_{i \in \mathcal{M}} y^{(i)}\, w^T x^{(i)} }\]toujours positif et linéaire par morceaux.
5.3.3 Optimisation : la descente de gradient
Minimiser le critère 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\) :
\[\boxed{\,w \leftarrow w - \alpha\,\nabla_w E(w)\,}\]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,
\[\boxed{ w \leftarrow w + \alpha\, y^{(i)} x^{(i)} }\]et aucune mise à jour sinon. Dans le codage \(\{0, 1\}\) c'est la mise à jour résidu fois l'entrée \(w_j \leftarrow w_j + \alpha\,(y^{(i)} - h_w(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.3.4 Perceptron multiclasse
Avec \(k\) classes, on garde un vecteur de poids \(w_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 :
\[\boxed{ \hat{y} = \arg\max_c w_c^T x, \qquad w_{y} \mathrel{+}= \alpha x, \quad w_{\hat{y}} \mathrel{-}= \alpha x }\]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 \(w_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\) :
\[ W^T x = \begin{bmatrix} -2 & -4 & 1 \\ -4 & 2 & 4 \\ -6 & 4 & -5 \end{bmatrix}\begin{bmatrix} 1 \\ 1{,}1 \\ -2{,}0 \end{bmatrix} = \begin{bmatrix} -8{,}4 \\ -9{,}8 \\ 8{,}4 \end{bmatrix} \]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 \(w_3^T x = -6 + 4 \times 1{,}1 + (-5) \times (-2{,}0) = 8{,}4\).
5.3.5 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.4 La régression logistique
5.4.1 Le modèle : 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\}\)). On la note toujours \(\hat{y}\), mais l'estimation de l'étiquette est désormais douce : le \(\hat{y}\) du perceptron était une classe dure, celui de la régression logistique est une probabilité, et le seuiller à \(\tfrac{1}{2}\) redonne une classe quand il en faut une :
\[\boxed{ \hat{y} = p(y = 1 \mid x; w) = \sigma(w^T x) = \frac{1}{1 + e^{-w^T x}} }\]
Le même neurone avec l'échelon remplacé par la sigmoïde : la sortie devient la probabilité \(\hat{y} = p(y = 1 \mid x)\), et la seuiller à \(\tfrac{1}{2}\) redonne la même frontière \(w^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.4.2 La fonction de perte : l'entropie croisée
La vraisemblance d'étiquettes de Bernoulli, passée au \(-\log\), donne la perte d'entropie croisée :
\[\boxed{ L(w) = -\sum_{i=1}^{m}\left[ y^{(i)}\log \hat{y}^{(i)} + (1 - y^{(i)})\log(1 - \hat{y}^{(i)}) \right] }\]Preuve : le maximum de vraisemblance donne l'entropie croisée
Le modèle dit que chaque étiquette est un tirage de Bernoulli de probabilité de succès \(\hat{y}^{(i)} = \sigma(w^T x^{(i)})\), et les deux cas se replient en une seule expression :
\[p(y^{(i)} \mid x^{(i)}; w) = \left(\hat{y}^{(i)}\right)^{y^{(i)}}\left(1 - \hat{y}^{(i)}\right)^{1 - y^{(i)}}\]puisque \(y^{(i)} \in \{0, 1\}\) sélectionne le facteur : l'expression vaut \(\hat{y}^{(i)}\) quand \(y^{(i)} = 1\) et \(1 - \hat{y}^{(i)}\) quand \(y^{(i)} = 0\). Les exemples sont i.i.d., la vraisemblance de l'ensemble d'entraînement se factorise donc, comme dans la Régression linéaire :
\[p(y \mid X; w) = \prod_{i=1}^{m} \left(\hat{y}^{(i)}\right)^{y^{(i)}}\left(1 - \hat{y}^{(i)}\right)^{1 - y^{(i)}}\]Le logarithme préserve l'argmax, transforme le produit en somme et fait descendre les exposants :
\[\ell(w) = \sum_{i=1}^{m}\left[ y^{(i)}\log \hat{y}^{(i)} + (1 - y^{(i)})\log(1 - \hat{y}^{(i)}) \right]\]Maximiser \(\ell\) revient à minimiser \(-\ell\), qui est exactement \(L(w)\). L'entropie croisée est l'opposé de la log-vraisemblance de Bernoulli, le même principe d'estimation qui faisait des moindres carrés la réponse sous bruit gaussien. \(\blacksquare\)
5.4.3 Optimisation : la descente de gradient
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 :
\[\boxed{ w_j \leftarrow w_j - \alpha \sum_{i=1}^{m}\left(\hat{y}^{(i)} - y^{(i)}\right)x_j^{(i)} }\]Preuve : le gradient se réduit au résidu fois l'entrée
Notons le score \(z^{(i)} = w^T x^{(i)}\), de sorte que \(\hat{y}^{(i)} = \sigma(z^{(i)})\). La dérivation repose sur une seule identité, la sigmoïde qui se dérive en elle-même :
\[\sigma'(z) = \frac{e^{-z}}{\left(1 + e^{-z}\right)^2} = \frac{1}{1 + e^{-z}} \cdot \frac{e^{-z}}{1 + e^{-z}} = \sigma(z)\left(1 - \sigma(z)\right)\]puisque \(\tfrac{e^{-z}}{1 + e^{-z}} = 1 - \sigma(z)\). Prenons maintenant la perte d'un seul exemple, \(L^{(i)} = -\left[y^{(i)}\log \hat{y}^{(i)} + (1 - y^{(i)})\log(1 - \hat{y}^{(i)})\right]\), et suivons la règle de dérivation en chaîne à travers ses trois étages, de la perte à la sortie, de la sortie au score, du score au poids :
\[\frac{\partial L^{(i)}}{\partial \hat{y}^{(i)}} = -\frac{y^{(i)}}{\hat{y}^{(i)}} + \frac{1 - y^{(i)}}{1 - \hat{y}^{(i)}} = \frac{\hat{y}^{(i)} - y^{(i)}}{\hat{y}^{(i)}\left(1 - \hat{y}^{(i)}\right)}, \qquad \frac{\partial \hat{y}^{(i)}}{\partial z^{(i)}} = \hat{y}^{(i)}\left(1 - \hat{y}^{(i)}\right), \qquad \frac{\partial z^{(i)}}{\partial w_j} = x_j^{(i)}\](la première égalité met les deux fractions au dénominateur commun \(\hat{y}^{(i)}(1 - \hat{y}^{(i)})\), et la deuxième est l'identité de la sigmoïde ci-dessus). En multipliant les trois, le dénominateur du premier facteur est exactement le deuxième facteur, et tout se simplifie :
\[\frac{\partial L^{(i)}}{\partial w_j} = \frac{\hat{y}^{(i)} - y^{(i)}}{\hat{y}^{(i)}\left(1 - \hat{y}^{(i)}\right)} \cdot \hat{y}^{(i)}\left(1 - \hat{y}^{(i)}\right) \cdot x_j^{(i)} = \left(\hat{y}^{(i)} - y^{(i)}\right) x_j^{(i)}\]Sommer sur l'ensemble d'entraînement donne \(\partial L / \partial w_j = \sum_{i=1}^{m} (\hat{y}^{(i)} - y^{(i)})\, x_j^{(i)}\), et brancher ce gradient dans la règle de descente \(w \leftarrow w - \alpha\, \nabla_w L\) est la mise à jour encadrée. \(\blacksquare\)
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 \(\hat{y}^{(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.4.4 Multiclasse : la softmax
Pour \(k\) classes, la sigmoïde se généralise en la softmax : un vecteur de poids \(w_c\), donc un score, par classe, des exponentielles qui rendent les scores positifs, et une normalisation qui en fait une distribution. En notant \(\hat{y}_c\) la probabilité prédite de la classe \(c\), comme \(\hat{y}\) était la probabilité de la classe positive ci-dessus :
\[\boxed{ \hat{y}_c = p(y = c \mid x; w) = \frac{\exp(w_c^T x)}{\sum_{j=1}^{k}\exp(w_j^T x)} }\]
Le réseau multiclasse à tête softmax : chaque classe note l'entrée, les exponentielles rendent les scores positifs, et la normalisation les transforme en probabilités de somme 1. C'est le réseau du perceptron multiclasse avec l'argmax remplacé par une tête lisse et dérivable.
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.
| sigmoïde | softmax | |
|---|---|---|
| classes | 2 | \(k\) |
| sortie | une probabilité \(\hat{y}\) | une distribution sur \(k\) classes |
| relation | la softmax à \(k = 2\) se réduit à la sigmoïde | généralise la sigmoïde |
Preuve : la softmax à k = 2 est la sigmoïde
Avec deux classes, la softmax note l'entrée deux fois, \(w_1\) pour la classe positive et \(w_0\) pour la classe négative :
\[p(y = 1 \mid x; w) = \frac{e^{w_1^T x}}{e^{w_1^T x} + e^{w_0^T x}}\]Diviser le numérateur et le dénominateur par \(e^{w_1^T x}\) laisse
\[p(y = 1 \mid x; w) = \frac{1}{1 + e^{-(w_1 - w_0)^T x}} = \sigma\!\left((w_1 - w_0)^T x\right)\]la sigmoïde appliquée à la différence des scores. Seule la différence \(w = w_1 - w_0\) compte (le fait général derrière cela : décaler chaque \(w_c\) du même vecteur laisse la softmax inchangée), un seul vecteur de poids suffit donc, exactement le modèle binaire par lequel cette section a commencé. Lue dans l'autre sens, c'est la recette de la généralisation : donner à chaque classe son propre score \(w_c^T x\), exponentier pour rendre les scores positifs, normaliser pour qu'ils somment à un, et le cas à deux classes se replie en une seule sigmoïde. \(\blacksquare\)
5.5 La classification régularisée
Rien ne fixe l'échelle de \(w\) : 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 :
\[\boxed{ J_\lambda(w) = \sum_{i=1}^{m} L\!\left(h_w(x^{(i)}),\,y^{(i)}\right) + \lambda\,\Omega(w), \qquad \Omega(w) = \lVert w \rVert_2^2 \ \text{ou} \ \lVert w \rVert_1 }\]Pour l'entropie croisée avec la pénalité L2, le gradient gagne simplement une traction vers zéro, \(\sum_i (\hat{y}^{(i)} - y^{(i)})\,x^{(i)} + 2\lambda w\).
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.6 Résumé
Les méthodes classiques ajustent toutes le même 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, le perceptron et la régression logistique ne supposent rien et le paient d'une optimisation itérative. Algorithme par algorithme, les formules qui définissent chacun :
Les moindres carrés, la méthode avec hypothèse et forme close :
| Formule | |
|---|---|
| Hypothèse sur les données | classes de forme gaussienne |
| Activation | identité pour entraîner (régression sur des cibles \(\pm 1\)), puis \(\mathrm{sign}(w^T x)\) pour prédire |
| Perte | erreur quadratique \(\sum_{i=1}^{m}\left(w^T x^{(i)} - y^{(i)}\right)^2\) |
| Ajustement | forme close \(w = (X^T X)^{-1}X^T y\), aucune itération |
| Multiclasse | lignes one-hot de \(Y\), \(W = (X^T X)^{-1}X^T Y\), prédire \(\arg\max_k\,(W^T x)_k\) |
Le perceptron, guidé par les erreurs et sans hypothèse :
| Formule | |
|---|---|
| Hypothèse sur les données | aucune |
| Activation | échelon, \(h_w(x) = \mathrm{sign}(w^T x)\), \(y \in \{-1, +1\}\) |
| Perte | critère du perceptron \(E(w) = -\sum_{i \in \mathcal{M}} y^{(i)}\, w^T x^{(i)}\), points mal classés seulement |
| Gradient | \(\nabla_w E = -\sum_{i \in \mathcal{M}} y^{(i)} x^{(i)}\) |
| Mise à jour | \(w \leftarrow w + \alpha\, y^{(i)} x^{(i)}\) sur une erreur, rien sinon |
| Multiclasse | \(\hat{y} = \arg\max_c\, w_c^T x\), puis \(w_{y} \mathrel{+}= \alpha x\) et \(w_{\hat{y}} \mathrel{-}= \alpha x\) |
| Convergence | finie si les données sont séparables, oscille sinon |
La régression logistique, probabiliste et sans hypothèse :
| Formule | |
|---|---|
| Hypothèse sur les données | aucune |
| Activation | sigmoïde, \(\hat{y} = \sigma(w^T x) = \tfrac{1}{1 + e^{-w^T x}}\), une probabilité, \(y \in \{0, 1\}\) |
| Perte | entropie croisée \(L(w) = -\sum_{i=1}^{m}\left[ y^{(i)}\log \hat{y}^{(i)} + (1 - y^{(i)})\log(1 - \hat{y}^{(i)}) \right]\) |
| Gradient | \(\nabla_{w_j} L = \sum_{i=1}^{m}\left(\hat{y}^{(i)} - y^{(i)}\right)x_j^{(i)}\), chaque point tire selon son résidu |
| Mise à jour | \(w_j \leftarrow w_j - \alpha \sum_{i=1}^{m}\left(\hat{y}^{(i)} - y^{(i)}\right)x_j^{(i)}\) |
| Multiclasse | softmax \(\hat{y}_c = \tfrac{\exp(w_c^T x)}{\sum_{j}\exp(w_j^T x)}\) et l'entropie croisée catégorielle |
Remarque : lues côte à côte, la mise à jour du perceptron (dans son codage \(\{0, 1\}\)) et celle de la régression logistique sont la même formule, le résidu fois l'entrée, et seule l'activation change (l'échelon pour le perceptron, la sigmoïde pour la régression logistique, et l'identité de la régression linéaire complète la famille). Le cours de Deep Learning reprend précisément ce fil, en empilant de telles unités en couches. Une perte manque volontairement à ce menu, la charnière \(\max(0,\,1 - y\,w^T x)\), qui pénalise les petites marges autant que les erreurs : elle appartient à la SVM.
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