Séparez les classes avec les modèles linéaires

Une agence immobilière rennaise se pose deux questions sur chaque appartement qu’elle met en vente : à quel prix le proposer, et partira-t-il en moins d’un mois ? La première est une régression, la seconde une classification. Pour les deux, la réponse la plus simple consiste à faire une somme pondérée des caractéristiques : un peu de surface, un peu d’étage, moins pour l’ancienneté, etc.

C’est l’idée des modèles linéaires. Ils sont anciens, rapides, interprétables, et ils restent la première chose à essayer sur beaucoup de problèmes. Ils sont aussi la porte d’entrée vers les réseaux de neurones (chapitre 9), qui empilent des modèles linéaires.

La régression linéaire et les moindres carrés

Le modèle prédit le prix comme une combinaison linéaire des caractéristiques :

$$\hat{y} = w^\top x + b = w_1 x_1 + \dots + w_d x_d + b$$

• $x = (x_1, \dots, x_d)$ décrit l’appartement (surface, étage…) ;
• $w = (w_1, \dots, w_d)$ sont les poids : $w_j$ dit de combien le prix augmente quand $x_j$ augmente d’une unité, les autres caractéristiques restant fixes ;
• $b$ est le biais (ou ordonnée à l’origine), une constante ;
• $w^\top x$ désigne le produit scalaire $\sum_j w_j x_j$.

Pour choisir $w$ et $b$, on minimise l’erreur quadratique moyenne (MSE) sur les $m$ exemples d’apprentissage :

$$\text{MSE}(w, b) = \frac{1}{m} \sum_{i=1}^{m} \big(y_i - w^\top x_i - b\big)^2$$

C’est la méthode des moindres carrés. Elle a une solution exacte : en ajoutant à $X$ (la matrice des exemples, une ligne par appartement) une colonne de 1 pour absorber $b$, on obtient $w^* = (X^\top X)^{-1} X^\top y$, à condition que $X^\top X$ soit inversible.

Exemple

Reprenons les trois ventes du chapitre 2 : 30 m² à 150 k€, 50 m² à 250 k€, 70 m² à 320 k€. Avec une seule caractéristique, la pente vaut $w = \frac{\sum_i (x_i - \bar{x})(y_i - \bar{y})}{\sum_i (x_i - \bar{x})^2}$, où $\bar{x} = 50$ et $\bar{y} = 240$ sont les moyennes.

$$w = \frac{(-20)(-90) + 0 \times 10 + 20 \times 80}{(-20)^2 + 0^2 + 20^2} = \frac{3400}{800} = 4{,}25$$

puis $b = \bar{y} - w \bar{x} = 240 - 212{,}5 = 27{,}5$. Le modèle dit : environ 4 250 € par m², plus 27 500 €. Un 60 m² est estimé à $4{,}25 \times 60 + 27{,}5 = 282{,}5$ k€.

La régression linéaire est interprétable et rapide. Mais elle suppose une relation linéaire, et le carré dans la MSE la rend sensible aux valeurs aberrantes : une seule vente à un prix délirant tire toute la droite vers elle.

À gauche, l'exemple : la droite ŷ = 4,25 x + 27,5 minimise la somme des carrés des résidus (segments roses). À droite, une seule vente aberrante (inventée) suffit à diviser la pente par plus de 1,5, parce que les grands écarts sont élevés au carré.

Régulariser : Ridge et Lasso

Avec beaucoup de caractéristiques, surtout si certaines sont corrélées (la surface et le nombre de pièces, par exemple), les poids appris peuvent devenir énormes et instables : c’est du surapprentissage. La régularisation ajoute à la perte une pénalité sur la taille des poids.

• Ridge (pénalité L2) : on minimise $\text{MSE} + \lambda \lVert w \rVert_2^2$, où $\lVert w \rVert_2^2 = \sum_j w_j^2$. Tous les poids sont réduits vers 0, sans l’atteindre. La solution reste explicite, $w^* = (X^\top X + \lambda I)^{-1} X^\top y$ (avec $I$ la matrice identité), et elle est stable même quand les variables sont corrélées.
• Lasso (pénalité L1) : on minimise $\text{MSE} + \lambda \lVert w \rVert_1$, où $\lVert w \rVert_1 = \sum_j \lvert w_j \rvert$. Cette pénalité met certains poids exactement à 0 : le Lasso fait de la sélection de variables.
• Elastic Net combine les deux pénalités.

Pénaliser revient à chercher le point de plus faible MSE dans une région autour de l'origine. Le disque de Ridge est rond : les poids rétrécissent mais restent non nuls. Le losange du Lasso a des coins sur les axes : l'ellipse les touche souvent là, et un poids tombe exactement à zéro.

Le coefficient $\lambda \geq 0$ règle le compromis biais-variance : $\lambda = 0$ redonne les moindres carrés, un $\lambda$ très grand écrase tous les poids (sous-apprentissage). On le choisit par validation croisée. Comme la pénalité traite tous les poids de la même façon, il faut normaliser les variables avant : sinon, une variable en euros et une autre en milliers d’euros seraient pénalisées très différemment.

from sklearn.linear_model import LassoCV, RidgeCV
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

# X : caractéristiques des appartements, y : prix (en k€)
ridge = make_pipeline(StandardScaler(), RidgeCV(alphas=[0.01, 0.1, 1, 10, 100]))
lasso = make_pipeline(StandardScaler(), LassoCV(cv=5))   # choisit lambda par validation croisée
ridge.fit(X, y)
lasso.fit(X, y)
print(lasso[-1].coef_)   # certains coefficients valent exactement 0

Dans scikit-learn, le coefficient $\lambda$ s’appelle alpha.

Classer avec une frontière linéaire

Passons à la seconde question : l’appartement partira-t-il en moins d’un mois ? On code les deux classes $y = +1$ (oui) et $y = -1$ (non), et on calcule un score $s(x) = w^\top x + b$. La prédiction est le signe du score, et la frontière de décision est l’ensemble des points où $s(x) = 0$ : une droite en dimension 2, un plan en dimension 3, un hyperplan en général.

La quantité $y \, s(x)$ s’appelle la marge de l’exemple : elle est positive si l’exemple est bien classé, et d’autant plus grande qu’il est loin de la frontière, du bon côté.

Le perceptron

Le perceptron est l’algorithme historique pour trouver $w$ et $b$. On parcourt les exemples ; à chaque exemple mal classé (marge $y \, s(x) \le 0$), on corrige :

$$w \leftarrow w + \eta \, y \, x \qquad b \leftarrow b + \eta \, y$$

où $\eta > 0$ est le pas d’apprentissage. Intuitivement, on fait pivoter la frontière pour rapprocher le score de l’exemple du bon signe. Si les données sont linéairement séparables, le perceptron converge vers une frontière sans erreur ; sinon, il ne s’arrête jamais de corriger.

La régression logistique

Le perceptron donne une réponse sèche. La régression logistique transforme le score en probabilité grâce à la fonction sigmoïde :

$$P(y = 1 \mid x) = \sigma(w^\top x + b), \qquad \sigma(z) = \frac{1}{1 + e^{-z}}$$

La sigmoïde écrase n’importe quel réel entre 0 et 1 : $\sigma(0) = 0{,}5$, $\sigma(z)$ tend vers 1 quand $z$ est grand et vers 0 quand $z$ est très négatif. On apprend $w$ et $b$ en minimisant la perte logistique (log-loss, ou entropie croisée binaire), par descente de gradient, puisqu’il n’existe pas de formule exacte. Malgré son nom, c’est bien un modèle de classification, discriminant, dont les poids s’interprètent : $e^{w_j}$ est le facteur par lequel la cote $P / (1 - P)$ est multipliée quand $x_j$ augmente d’une unité.

La sigmoïde transforme le score en probabilité. Le seuil de 0,5 correspond au score nul, c'est-à-dire à la frontière w⊤x + b = 0 ; plus l'exemple est loin de la frontière, plus la probabilité est tranchée.

Pour plus de deux classes, on calcule un score par classe et on les transforme en probabilités avec la fonction softmax, $P(y = j \mid x) = e^{s_j} / \sum_k e^{s_k}$. Un classifieur strictement binaire peut aussi être étendu en entraînant un modèle par classe contre toutes les autres (un-contre-tous).

Les fonctions de perte

Ce qui distingue vraiment ces modèles, c’est la perte qu’ils minimisent, en fonction de la marge $z = y \, s(x)$ :

Perte	Formule	Utilisée par
0-1	1 si $z \le 0$, 0 sinon	l’évaluation (non dérivable)
Perceptron	$\max(0, -z)$	le perceptron
Charnière (hinge)	$\max(0, 1 - z)$	les SVM
Logistique	$\log(1 + e^{-z})$	la régression logistique
Exponentielle	$e^{-z}$	AdaBoost (chapitre 8)

La perte 0-1 est celle qu’on voudrait minimiser (le nombre d’erreurs), mais elle est plate presque partout, donc inutilisable pour une descente de gradient. Les autres sont des substituts (surrogates) continus qui la majorent ou l’approchent.

Toutes les pertes pénalisent les marges négatives (erreurs), mais pas de la même façon. La charnière exige en plus une marge d'au moins 1, et l'exponentielle punit très fort les grosses erreurs, ce qui rend AdaBoost sensible aux étiquettes fausses.

Les SVM : chercher la plus grande marge

Quand les données sont séparables, une infinité d’hyperplans séparent les classes. Lequel choisir ? Les machines à vecteurs de support (SVM) choisissent celui qui passe le plus loin possible des exemples des deux classes : l’hyperplan de marge maximale.

On fixe l’échelle de $w$ pour que les exemples les plus proches vérifient $y_i (w^\top x_i + b) = 1$. La largeur de la bande vide autour de la frontière vaut alors $2 / \lVert w \rVert$, et la maximiser revient à résoudre :

$$\min_{w, b} \; \frac{1}{2} \lVert w \rVert^2 \quad \text{sous les contraintes} \quad y_i (w^\top x_i + b) \geq 1 \text{ pour tout } i$$

Les exemples situés sur le bord de la marge sont les vecteurs de support : ce sont les seuls qui déterminent la solution. On pourrait supprimer tous les autres sans rien changer.

La marge souple et le paramètre C

Les vraies données sont rarement séparables. La marge souple autorise des exemples à franchir la marge, moyennant une pénalité :

$$\min_{w, b} \; \frac{1}{2} \lVert w \rVert^2 + C \sum_{i=1}^{m} \max\big(0, \, 1 - y_i (w^\top x_i + b)\big)$$

Le second terme est la somme des pertes charnière, et $C > 0$ règle le compromis. Avec $C$ petit, on tolère beaucoup de violations pour garder une marge large (modèle plus simple, risque de sous-apprentissage). Avec $C$ grand, on veut classer chaque exemple correctement, quitte à réduire la marge (risque de surapprentissage).

Seuls les points cerclés (sur le bord de la marge ou à l'intérieur) déterminent la frontière. Un C grand refuse les violations et resserre la marge ; un C petit les tolère et élargit la marge (données simulées).

L’astuce du noyau

Et si la frontière n’est pas du tout linéaire ? On peut envoyer les données dans un espace de plus grande dimension, par une transformation $\Phi$, où elles deviennent séparables. Or l’optimisation des SVM ne fait intervenir les exemples qu’à travers des produits scalaires $\langle x, x' \rangle$. L’astuce du noyau (kernel trick) remplace ce produit par une fonction $K(x, x') = \langle \Phi(x), \Phi(x') \rangle$ calculée directement, sans jamais construire $\Phi$. Les noyaux usuels :

• linéaire : $K(x, x') = x^\top x'$ ;
• polynomial : $K(x, x') = (x^\top x' + c)^p$, où $c$ est une constante et $p$ le degré ;
• gaussien (RBF) : $K(x, x') = \exp(-\gamma \lVert x - x' \rVert^2)$, où $\gamma > 0$ règle la portée de l’influence de chaque exemple. Un $\gamma$ grand donne une frontière très sinueuse (surapprentissage), un $\gamma$ petit une frontière presque linéaire.

Aucune droite ne sépare deux cercles concentriques ; le noyau gaussien, si. Un γ modéré donne une frontière régulière ; un γ très grand fait de chaque point un îlot : parfait en apprentissage, moins bon en test (données simulées).

from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

# X, y : caractéristiques et classe (vendu en moins d'un mois ou non)
svm = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
grille = {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.001, 0.01, 0.1, 1]}
recherche = GridSearchCV(svm, grille, cv=5, scoring="f1").fit(X, y)
print(recherche.best_params_)

On règle $C$ et $\gamma$ ensemble, sur une grille en échelle logarithmique. Les SVM exigent des variables normalisées, et leur entraînement devient lent au-delà de quelques dizaines de milliers d’exemples.

À retenir

Tous les modèles de ce chapitre calculent un score linéaire $w^\top x + b$ ; ils diffèrent par la perte minimisée et la régularisation. Régression linéaire : MSE ; Ridge et Lasso : MSE plus pénalité L2 ou L1 ; régression logistique : perte logistique ; SVM : perte charnière plus maximisation de la marge. Les noyaux rendent les SVM non linéaires.

En entretien

« L1 met des coefficients exactement à zéro et sélectionne des variables ; L2 les réduit tous et stabilise le modèle quand les variables sont corrélées. Dans les deux cas, on normalise les variables et on règle la pénalité par validation croisée. »

En résumé

• La régression linéaire prédit $w^\top x + b$ et s’ajuste par moindres carrés ; elle est interprétable mais sensible aux valeurs aberrantes.
• Ridge (L2) réduit tous les poids, Lasso (L1) en annule certains ; $\lambda$ se règle par validation croisée, après normalisation.
• Un classifieur linéaire prédit le signe de $w^\top x + b$ ; la marge $y \, s(x)$ est positive pour un exemple bien classé.
• Le perceptron corrige les poids à chaque erreur et converge si les données sont séparables ; la régression logistique produit des probabilités grâce à la sigmoïde.
• Les SVM cherchent l’hyperplan de marge maximale ; $C$ règle la tolérance aux erreurs, et les noyaux (polynomial, RBF) donnent des frontières non linéaires.

Exercices

Exercice · Lire une régression logistique

facile

L’agence a appris le modèle $P(\text{vendu en moins d'un mois} \mid x) = \sigma(4 - 0{,}02 \times \text{prix})$, avec le prix en milliers d’euros. Quelle est la probabilité pour un appartement à 250 k€ ? À quel prix la probabilité vaut-elle exactement 0,5 ?

Voir la solution

Pour 250 k€, le score vaut $4 - 0{,}02 \times 250 = -1$, et $\sigma(-1) = 1 / (1 + e^{1}) \approx 1 / 3{,}718 \approx 0{,}27$. Il y a environ 27 % de chances qu’il parte en moins d’un mois.

La probabilité vaut 0,5 quand le score est nul, puisque $\sigma(0) = 0{,}5$ : $4 - 0{,}02 \times \text{prix} = 0$, soit un prix de 200 k€. C’est la frontière de décision du modèle avec un seuil de 0,5.

En code

Python

import numpy as np

def sigmoide(z):
    return 1 / (1 + np.exp(-z))

def proba_vente(prix):                  # prix en k€
    return sigmoide(4 - 0.02 * prix)

print(round(proba_vente(250), 3))       # 0.269
print(proba_vente(200))                 # 0.5 : score nul pour 4 / 0,02 = 200 k€

R

proba_vente <- function(prix) plogis(4 - 0.02 * prix)   # plogis est la sigmoïde

round(proba_vente(250), 3)      # 0.269
proba_vente(200)                # 0.5 : score nul pour 4 / 0,02 = 200 k€

Exercice · Deux pas de perceptron

moyen

On part de $w = (1, -1)$, $b = 0$ et d’un pas $\eta = 0{,}5$. Appliquez la règle du perceptron à l’exemple $x_1 = (1, 2)$ de classe $y_1 = +1$, puis à l’exemple $x_2 = (3, 1)$ de classe $y_2 = -1$. L’exemple $x_1$ est-il encore bien classé à la fin ?

Voir la solution

Exemple 1 : $s(x_1) = 1 \times 1 + (-1) \times 2 + 0 = -1$, donc $y_1 s(x_1) = -1 \le 0$ : mal classé. Correction : $w \leftarrow (1, -1) + 0{,}5 \times (1, 2) = (1{,}5 ; 0)$ et $b \leftarrow 0 + 0{,}5 = 0{,}5$. Vérification : $s(x_1) = 1{,}5 + 0{,}5 = 2 > 0$, bien classé.

Exemple 2 : $s(x_2) = 1{,}5 \times 3 + 0 \times 1 + 0{,}5 = 5$, donc $y_2 s(x_2) = -5$ : mal classé. Correction : $w \leftarrow (1{,}5 ; 0) - 0{,}5 \times (3, 1) = (0 ; -0{,}5)$ et $b \leftarrow 0{,}5 - 0{,}5 = 0$.

À la fin, $s(x_1) = 0 \times 1 - 0{,}5 \times 2 + 0 = -1$ : $x_1$ est de nouveau mal classé. Corriger un exemple peut en dérégler un autre ; c’est pourquoi le perceptron parcourt les données plusieurs fois. Ici, les deux points sont séparables (par exemple par $w = (-1, 1)$, $b = 0$), donc l’algorithme finira par converger.

En code

Python

import numpy as np

w, b, eta = np.array([1.0, -1.0]), 0.0, 0.5
exemples = [(np.array([1, 2]), +1), (np.array([3, 1]), -1)]

for x, y in exemples:
    marge = y * (w @ x + b)
    if marge <= 0:                     # mal classé : on corrige
        w, b = w + eta * y * x, b + eta * y
    print(f"marge {marge}, puis w = {w}, b = {b}")

x1 = exemples[0][0]
print(w @ x1 + b)                      # -1.0 : x1 est de nouveau mal classé
# marge -1.0, puis w = [1.5 0. ], b = 0.5
# marge -5.0, puis w = [ 0.  -0.5], b = 0.0

R

w <- c(1, -1); b <- 0; eta <- 0.5
X <- rbind(c(1, 2), c(3, 1)); y <- c(+1, -1)

for (i in 1:2) {
  marge <- y[i] * (sum(w * X[i, ]) + b)
  if (marge <= 0) {                    # mal classé : on corrige
    w <- w + eta * y[i] * X[i, ]
    b <- b + eta * y[i]
  }
  cat("marge", marge, ", puis w =", w, ", b =", b, "\n")
}
sum(w * X[1, ]) + b                    # -1 : x1 est de nouveau mal classé
# marge -1 , puis w = 1.5 0 , b = 0.5
# marge -5 , puis w = 0 -0.5 , b = 0

Exercice · Marge et perte charnière

difficile

Un SVM a appris $w = (3, 4)$ et $b = -10$.

1. Quelle est la largeur de la marge ?
2. Pour l’exemple $x = (2, 3)$ de classe $+1$, calculez sa distance à la frontière et sa perte charnière.
3. Même question pour $x' = (2, 1)$ de classe $+1$.

Voir la solution

1. $\lVert w \rVert = \sqrt{3^2 + 4^2} = 5$, donc la largeur de la marge vaut $2 / \lVert w \rVert = 0{,}4$.
2. $s(x) = 3 \times 2 + 4 \times 3 - 10 = 8$. La distance à la frontière vaut $\lvert s(x) \rvert / \lVert w \rVert = 8 / 5 = 1{,}6$. La marge $y \, s(x) = 8 \geq 1$, donc la perte charnière $\max(0, 1 - 8)$ est nulle : l’exemple est bien classé et hors de la marge, il n’influence pas la solution.
3. $s(x') = 6 + 4 - 10 = 0$ : l’exemple est sur la frontière, à distance 0. Sa perte charnière vaut $\max(0, 1 - 0) = 1$. Il viole la marge et contribue à la fonction objectif avec le poids $C$ : c’est un vecteur de support.

En code

Python

import numpy as np

w, b = np.array([3, 4]), -10
norme = np.linalg.norm(w)
print(norme, 2 / norme)                            # 5.0  0.4 (largeur de la marge)

for x, y in [(np.array([2, 3]), +1), (np.array([2, 1]), +1)]:
    s = w @ x + b                                  # score
    distance = abs(s) / norme
    charniere = max(0, 1 - y * s)
    print(f"x = {x} : score {s}, distance {distance}, perte charnière {charniere}")
# x = [2 3] : score 8, distance 1.6, perte 0 ; x = [2 1] : score 0, distance 0.0, perte 1

R

w <- c(3, 4); b <- -10
norme <- sqrt(sum(w^2))
c(norme = norme, largeur_marge = 2 / norme)      # 5  0.4

X <- rbind(c(2, 3), c(2, 1)); y <- c(+1, +1)
s <- as.vector(X %*% w + b)                      # scores : 8 et 0
data.frame(score = s,
           distance = abs(s) / norme,            # 1.6 et 0
           charniere = pmax(0, 1 - y * s))       # 0 et 1