Les limites de décision comme hyperplans
Un classificateur binaire assigne chaque entrée à l'une des deux classes. La limite de décision du classificateur divise l'espace d'entrée en deux régions : une par classe. La géométrie de cette limite détermine les schémas que le classificateur peut apprendre.
Un hyperplan dans ℝ^n : l'ensemble de tous les points x satisfaisant w·x + b = 0, où w est un vecteur de poids dans ℝ^n et b est un biais scalaire. Un hyperplan a n−1 dimensions.
En 2D : un hyperplan est une ligne. En 3D : un plan plat. En n-D : un sous-espace plat de dimension (n−1).
Un perceptron classifie en calculant w·x + b et en retournant la classe 1 si positif, la classe 0 si négatif. Sa limite de décision est un hyperplan.
Séparabilité linéaire
Un ensemble de données est linéairement séparable dans ℝ^n s'il existe un hyperplan qui place tous les points de classe 0 d'un côté et tous les points de classe 1 de l'autre. C'est une propriété purement géométrique de l'ensemble de données.
Tester la séparabilité linéaire
L'ensemble de données de la porte ET en 2D : points de classe 0 en (0,0), (1,0), (0,1) ; point de classe 1 en (1,1). Cet ensemble de données est linéairement séparable.
L'ensemble de données XOR en 2D : points de classe 0 en (0,0) et (1,1) ; points de classe 1 en (1,0) et (0,1). Ces deux classes se situent sur des diagonales opposées.
Lever à des dimensions plus élevées
XOR n'est pas linéairement séparable en 2D. La solution : mapper les données à un espace de dimension plus élevée où elles deviennent linéairement séparables. C'est l'idée centrale de l'astuce du noyau.
Fonction de transformation des caractéristiques : une fonction φ: ℝ^n → ℝ^m (m > n) qui transforme chaque point d'entrée en une représentation de dimension plus élevée.
Pour XOR, une fonction de transformation utile : φ(x₁, x₂) = (x₁, x₂, x₁x₂)
Cela ajoute une troisième dimension z = x₁ × x₂. Les points XOR se transforment en :
- (0,0) → (0, 0, 0), classe 0
- (1,0) → (1, 0, 0), classe 1
- (0,1) → (0, 1, 0), classe 1
- (1,1) → (1, 1, 1), classe 0
En 3D : les points de classe 0 sont en (0,0,0) et (1,1,1) ; les points de classe 1 sont en (1,0,0) et (0,1,0). Trouvez maintenant un plan séparant.
Plan séparant en 3D
Après la transformation de caractéristiques φ(x₁, x₂) = (x₁, x₂, x₁x₂), les données XOR vivent en 3D. Un hyperplan en 3D a l'équation w₁x₁ + w₂x₂ + w₃z + b = 0.
Théorème de Cover : pourquoi les dimensions élevées aident
Théorème de Cover (1965) : un problème de classification complexe projeté dans un espace de dimension élevée est plus susceptible d'être linéairement séparable que dans un espace de faible dimension, pourvu que l'espace ne soit pas densément peuplé.
Énoncé informel : si vous mappez n points de données à un espace de dimension d >> n, la probabilité qu'un marquage aléatoire soit linéairement séparable tend vers 1.
Version formelle : pour n points en position générale dans ℝ^d, le nombre de dichotomies (assignations de classe) linéairement séparables est exactement 2 × Σ_{k=0}^{d} C(n−1, k) pour d < n, et égale 2^n (toutes les dichotomies) pour d ≥ n − 1.
Implication pratique : la transformation de caractéristiques φ qui lève XOR à 3D est un cas spécial de ce principe général. Lever à des dimensions plus élevées augmente la probabilité de séparabilité. Le coût : plus de paramètres à adapter, risque plus élevé de surapprentissage.
Le compromis biais-variance comme géométrie
Limite de décision de faible dimension (peu de paramètres) : biais élevé (ne peut pas capturer les schémas complexes), variance faible (stable d'un échantillon à l'autre). Limite de haute dimension (beaucoup de paramètres) : biais faible, variance élevée (peut surappendre au bruit des données d'entraînement).
Dimension VC : quelle est l'expressivité d'un classificateur ?
La dimension Vapnik-Chervonenkis (VC) d'une classe d'hypothèses H mesure la complexité de la classe : le nombre maximal de points que H peut pulvériser (classifier correctement dans tous les 2^n marquages possibles).
Perceptron dans ℝ^d : dimension VC = d + 1. Un hyperplan de dimension d peut pulvériser d + 1 points (en position générale) mais pas d + 2.
La dimension VC détermine la complexité d'échantillonnage : pour apprendre une hypothèse avec erreur de généralisation ε avec probabilité 1 − δ, vous avez besoin d'environ n ≥ (d × log(1/ε) + log(1/δ)) / ε échantillons d'entraînement, où d est la dimension VC.
Limites de décision & limites de la capacité machine
La géométrie des limites de décision se connecte directement aux limites du raisonnement machine de Hamming.
Un perceptron à une seule couche (classificateur d'hyperplan) ne peut pas résoudre XOR. C'était la critique de Minsky & Papert des premiers perceptrons en 1969. L'argument géométrique : XOR n'est pas linéairement séparable. La machine ne peut pas le résoudre, non pas par manque de puissance de calcul, mais à cause d'une incompatibilité géométrique fondamentale entre la classe d'hypothèses et le problème.
La résolution : les réseaux multi-couches peuvent représenter des limites non-linéaires. Les couches cachées implémentent la transformation de caractéristiques φ — levant les données à des dimensions plus élevées où la séparation linéaire devient possible. Chaque neurone caché calcule un hyperplan ; la combinaison de multiples hyperplans approxime des courbes.
Cette histoire se mappe sur l'observation de Hamming : chaque limitation du raisonnement machine a une structure géométrique dessous. La tâche n'est pas d'argumenter si les machines « peuvent penser » mais d'identifier les contraintes géométriques et de trouver des façons de les contourner.