Hyperplans séparateurs et marge

La régression logistique ajuste une frontière en rendant probables les étiquettes observées. Cette leçon adopte un tout autre point de départ : parmi toutes les frontières qui séparent les classes, préférer celle qui est la plus éloignée de chaque observation. Cette seule idée produit un classifieur doté d’une propriété inhabituelle : presque toutes les données se révèlent sans importance pour lui.

Un hyperplan est une règle de décision

En dimension $p$, un hyperplan est l’ensemble plat, de dimension $(p-1)$,

$$\beta_0 + \beta_1 x_1 + \beta_2 x_2 + \cdots + \beta_p x_p = 0 .$$

En deux dimensions c’est une droite, en trois un plan. Un point qui ne s’y trouve pas rend le membre de gauche soit positif, soit négatif : un hyperplan coupe donc l’espace en deux et fournit gratuitement un classifieur. Écrivons

$$f(x) = \beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p$$

et prédisons la classe $+1$ quand $f(x) > 0$ et la classe $-1$ quand $f(x) < 0$. Coder les étiquettes par $\pm 1$ rend « correctement classé » compact : la prédiction est juste exactement quand

$$y_i f(x_i) > 0 .$$

La grandeur de $f(x)$ est elle aussi informative. Un point éloigné de la frontière a un $f(x)$ éloigné de zéro, et l’on peut en être sûr ; un point proche de la frontière tient du pile ou face.

Quel hyperplan séparateur ?

Si les classes peuvent être séparées, elles peuvent généralement l’être d’une infinité de façons : déplacez ou inclinez légèrement une droite séparatrice et elle sépare encore. « Trouver un hyperplan séparateur » n’est donc pas encore un problème bien posé.

Le classifieur à marge maximale le résout. Calculez la distance de chaque observation d’entraînement à un hyperplan candidat ; la plus petite de ces distances est la marge. Choisissez alors l’hyperplan dont la marge est la plus grande. Autrement dit, c’est la ligne médiane de la bande la plus large que l’on puisse glisser entre les deux classes.

Exemple travaillé

Prenons six observations dans le plan :

$$\begin{array}{ll} \text{class } +1: & (3,3),\ (4,4),\ (3,5) \\ \text{class } -1: & (1,1),\ (0,2),\ (2,0) \end{array}$$

L’hyperplan à marge maximale est

$$x_1 + x_2 - 4 = 0 ,$$

et la distance perpendiculaire d’un point à cet hyperplan vaut $|x_1 + x_2 - 4| / \sqrt{2}$. En l’évaluant en chaque observation :

$$\begin{array}{lll} (3,3) & +1 & \sqrt{2} \approx 1.4142 \\ (4,4) & +1 & 2\sqrt{2} \approx 2.8284 \\ (3,5) & +1 & 2\sqrt{2} \approx 2.8284 \\ (1,1) & -1 & \sqrt{2} \approx 1.4142 \\ (0,2) & -1 & \sqrt{2} \approx 1.4142 \\ (2,0) & -1 & \sqrt{2} \approx 1.4142 \end{array}$$

La marge vaut $\sqrt{2}$, et quatre observations l’atteignent : $(3,3)$, $(1,1)$, $(0,2)$ et $(2,0)$. Ce sont les vecteurs de support. Ils se trouvent sur les bords de la bande et la maintiennent en place - déplacez-en un et l’hyperplan bouge.

Les deux autres, $(4,4)$ et $(3,5)$, sont à $2\sqrt{2}$ et sont sans importance. Vous pouvez les déplacer n’importe où de leur côté de la bande sans que le classifieur ajusté change le moins du monde. Notez aussi que les vecteurs de support ne se répartissent pas également entre les classes : un positif, trois négatifs.

L’énoncer comme une optimisation

Le problème s’écrit

$$\max_{\beta_0,\dots,\beta_p,\,M} M \quad\text{subject to}\quad \sum_{j=1}^{p}\beta_j^2 = 1, \qquad y_i\big(\beta_0 + \beta_1 x_{i1} + \cdots + \beta_p x_{ip}\big) \ge M \ \ \forall i .$$

La seconde contrainte dit que chaque observation est du bon côté et à au moins $M$ de distance. La première a l’air d’un détail technique, et n’en est pas un. Multiplier tous les coefficients par un $k \neq 0$ quelconque décrit le même hyperplan : sans convention d’échelle, les paramètres ne sont donc pas déterminés. Fixer le vecteur des coefficients à la norme un les fige, et cela fait de $y_i(\beta_0 + \beta \cdot x_i)$ la véritable distance perpendiculaire - ce qui donne à « maximiser $M$ » le sens de « maximiser la marge ».

La forme canonique. Une convention équivalente met à l’échelle de sorte que les points les plus proches vérifient $y_i f(x_i) = 1$. Notre hyperplan devient $\beta = (0.5, 0.5)$ avec $\beta_0 = -2$, d’où $\lVert\beta\rVert = 0.7071$ et une marge de $1/\lVert\beta\rVert = 1.4142$, le même $\sqrt{2}$. Maximiser la marge revient alors à minimiser $\lVert\beta\rVert$, la forme que résout la plupart des logiciels.

Deux façons d’échouer

Les classes peuvent ne pas être séparables. Aucun hyperplan ne satisfait alors les contraintes avec $M > 0$, et le problème n’a tout simplement pas de solution. Les données réelles sont fréquemment ainsi, et une méthode qui ne renvoie rien du tout n’est pas d’un grand secours.

Même quand elle fonctionne, elle est fragile. La solution est entièrement déterminée par les quelques points les plus proches de la frontière : elle hérite donc de leur instabilité. Ajoutez une seule observation $+1$ en $(1.6, 1.6)$, blottie près du nuage négatif, et la meilleure marge atteignable tombe de $1.4142$ à $0.4243$ - un facteur de plus de trois, à cause d’un seul point. Puisqu’une marge étroite est précisément ce qui généralise mal, exiger une séparation parfaite est contre-productif.

Les deux échecs pointent dans la même direction : il faut autoriser le classifieur à se tromper sur quelques observations. C’est l’objet de la leçon suivante.

Avant le quiz

Sachez classer selon le signe de $f(x)$, définir la marge, repérer les vecteurs de support et dire pourquoi les autres n’importent pas, expliquer à quoi sert la contrainte de normalisation, et nommer les deux modes d’échec.