Une Perspective Mathématique Sur Les Machines À Vecteurs De Support (SVM) : Résolution De Problèmes D'Optimisation

Les machines à vecteurs de support (SVM) sont des algorithmes classiques en apprentissage automatique. Cet article se concentre sur la déduction des formules dans les SVM, telles que le raisonnement détaillé de la formule de la distance de marge, ainsi que la formulation du problème primal et du problème dual. Il explore en profondeur les problèmes d’optimisation, y compris la construction de la fonction lagrangienne pour traiter les problèmes d’optimisation sous contrainte, et l’utilisation des conditions KKT pour trouver la solution optimale. Il aborde également les caractéristiques des fonctions noyau polynomial et gaussien.

Raisonnement de la Distance de Marge

Dans les machines à vecteurs de support (SVM), les équations des hyperplans positif et négatif sont respectivement : $$ \vec{w} \cdot \vec{x} + b = 1 \quad \text{(Hyperplan positif)} $$ $$ \vec{w} \cdot \vec{x} + b = -1 \quad \text{(Hyperplan négatif)} $$ où $\vec{w}=(w_1, w_2)$ est le vecteur de poids, $b$ est le biais, et $\vec{x}=(x_1, x_2)$ est le point de données.

Supposons que $\vec{x_m}$ est un point sur l’hyperplan positif et $\vec{x_n}$ un point sur l’hyperplan négatif, alors : $$ w_1 x_{1m} + w_2 x_{2m} + b = 1 \quad \text{(1)} $$ $$ w_1 x_{1n} + w_2 x_{2n} + b = -1 \quad \text{(2)} $$

En soustrayant l’équation (2) de l’équation (1), on obtient : $$ w_1 (x_{1m} - x_{1n}) + w_2 (x_{2m} - x_{2n}) = 2 $$ Sous forme vectorielle : $$ \vec{w} \cdot (\vec{x_m} - \vec{x_n}) = 2 \quad \text{(3)} $$ Considérons deux points $\vec{x_0}$ et $\vec{x_p}$ sur l’hyperplan de décision, satisfaisant l’équation de l’hyperplan de décision $\vec{w} \cdot \vec{x} + b = 0$, c’est-à-dire : $$ w_1 x_{10} + w_2 x_{20} + b = 0 $$ $$ w_1 x_{1p} + w_2 x_{2p} + b = 0 $$ En soustrayant les deux équations, on obtient : $$ w_1 (x_{10} - x_{1p}) + w_2 (x_{20} - x_{2p}) = 0 $$ Sous forme vectorielle : $$ \vec{w} \cdot (\vec{x_0} - \vec{x_p}) = 0 \quad \text{(4)} $$ L’équation (4) montre que $\vec{w}$ est perpendiculaire à la différence vectorielle de deux points quelconques sur l’hyperplan de décision.

D’après les équations (3) et (4), on sait que le produit scalaire de $\vec{w}$ et $(\vec{x_m} - \vec{x_n})$ est égal à 2. Selon la définition du produit scalaire $\vec{a} \cdot \vec{b}=|\vec{a}| \cdot |\vec{b}| \cdot \cos \theta$, où $\theta$ est l’angle entre $\vec{w}$ et $(\vec{x_m} - \vec{x_n})$, nous avons : $$ |\vec{x_m} - \vec{x_n}| \cdot \cos \theta \cdot |\vec{w}| = 2 $$ En posant $L = |\vec{x_m} - \vec{x_n}| \cdot \cos \theta$, on obtient : $$ L \cdot |\vec{w}| = 2 $$ En résolvant, on trouve : $$ L=\frac{2}{|\vec{w}|} $$

Ici, $L$ est la distance de marge du SVM.

Dans la déduction de la distance de marge, nous avons utilisé la signification géométrique du produit scalaire, c’est-à-dire $\vec{a} \cdot \vec{b}=|\vec{a}| \cdot |\vec{b}| \cdot \cos \theta$, où $\theta$ est l’angle entre les deux vecteurs. Grâce à cette relation, nous avons transformé le produit scalaire en une relation entre la norme des vecteurs et l’angle, ce qui nous a permis de dériver l’expression de la distance de marge.

Preuve de l’Équivalence Duale

Dans les machines à vecteurs de support (SVM) linéaires, le problème primal est de trouver le vecteur de poids $w$ et le biais $b$ qui minimisent la fonction objectif :

$$ \min_w f(w) = \frac{1}{2} |w|^2 $$

Ici, $|w|^2$ représente le carré de la norme euclidienne du vecteur $w$, c’est-à-dire la norme $L_2$. L’objectif est de minimiser la largeur de la marge de décision pour obtenir une meilleure capacité de généralisation. Ce problème est soumis à la contrainte suivante :

$$ y_j (w^T x_j + b) - 1 \geq 0 $$

Ici, $x_j$ est le $j$-ième échantillon d’entraînement, et $y_j$ est l’étiquette correspondante, prenant les valeurs +1 ou -1, ce qui garantit que tous les points de données sont correctement classifiés et sont à au moins une unité de distance de la marge de décision.

Pour traiter ce problème d’optimisation sous contrainte, nous construisons la fonction lagrangienne :

$$ L(w, b, \alpha) = f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) $$

Ici, $\alpha_j \geq 0$ sont les multiplicateurs de Lagrange, utilisés pour introduire les conditions de contrainte du problème primal $g_j(w, b) = y_j (w^T x_j + b) - 1 \geq 0$.

Ensuite, nous définissons la fonction duale $q(\alpha)$ comme suit :

$$ q(\alpha) = \min_{w, b} L(w, b, \alpha) = \min_{w, b} \left( f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) \right) $$

Puisque $\alpha_j \geq 0$ et $g_j(w^{*}, b^{*}) \geq 0$, nous pouvons en déduire :

$$ q(\alpha) = \min_{w, b} \left( f(w) - \sum_{j = 1}^n \alpha_j g_j(w, b) \right) \leq f(w^*) - \sum_{j = 1}^n \alpha_j g_j(w^*, b^*) \leq f(w^*) \leq f(w) $$

Cela signifie que la fonction duale fournit une borne inférieure du problème primal. Ensuite, nous devons trouver un $\alpha^*$ tel que :

$$ q(\alpha) \leq q(\alpha^*) \leq f(w^*) \leq f(w) $$

Le problème primal et le problème dual des SVM peuvent être formulés comme suit :

$$ \max_{\alpha} q(\alpha) = \max_{\alpha} \min_{w, b} L(w, b, \alpha) $$

Avec la contrainte : $ \alpha_i \geq 0 $

Et lorsque la dualité faible est satisfaite, nous avons $q(\alpha^*) \leq f(w^*)$ ; tandis que lorsque la dualité forte est satisfaite, c’est-à-dire lorsque la condition de Slater est remplie, nous avons $q(\alpha^*) = f(w^*)$. La condition de Slater exige qu’il existe une solution faisable telle que toutes les contraintes d’inégalité soient strictement satisfaites, et le SVM linéairement séparable satisfait automatiquement la condition de Slater.

Ainsi, nous avons :

$$ f(w) \geq q(\alpha^*) = f(w^*) \geq q(\alpha_i) $$

D’après cette équation, nous pouvons obtenir :

$$ q(\alpha^*) \geq q(\alpha_i) $$ $$ f(w^*) \leq f(w) $$

$f(w)$ a trouvé sa valeur minimale (problème primal), $q(\alpha)$ a trouvé sa valeur maximale (problème dual), et les solutions optimales du problème primal et du problème dual sont égales, c’est-à-dire :

$ w^*, b^* $ est la solution du problème primal, $\alpha^*$ est la solution du problème dual, et $f(w^*) = q(\alpha^*)$.

Nous pouvons voir que dans les SVM linéaires, lorsque certaines conditions (conditions de Slater) sont satisfaites, les solutions du problème primal et du problème dual sont cohérentes. Cela constitue une méthode efficace pour résoudre des problèmes d’optimisation complexes, en particulier lorsque le problème primal est difficile à résoudre directement, on peut résoudre le problème dual pour le résoudre indirectement.

Exemple Simple

Pour comprendre plus intuitivement que les solutions du problème primal et du problème dual sont les mêmes, considérons un problème d’optimisation simple, défini comme suit :

Problème primal : $$ \min_x f(x) = x^2 $$ Avec la contrainte : $$ x - 1 \geq 0 $$

L’objectif de ce problème est de minimiser la fonction $f(x) = x^2$, tout en satisfaisant $x \geq 1$. Intuitivement, nous savons que lorsque $x = 1$, $f(x) = 1$, c’est la valeur minimale sous la contrainte donnée.

Pour vérifier la dualité, nous construisons la fonction lagrangienne :

$$ q(\alpha) = \min_x L(x, \alpha) = \min_x (x^2 - \alpha(x - 1)) $$

Ici, $\alpha \geq 0$ est le multiplicateur de Lagrange, utilisé pour introduire la contrainte du problème primal $x - 1 \geq 0$. En construisant la fonction lagrangienne, nous avons transformé le problème d’optimisation sous contrainte en un problème sans contrainte.

Ensuite, nous dérivons $L(x, \alpha)$ par rapport à $x$ et nous l’égalons à zéro :

$$ \frac{\partial L}{\partial x} = 0 2x - \alpha = 0 $$

En résolvant, on trouve :

$$ x = \frac{\alpha}{2} $$

En substituant $x = \frac{\alpha}{2}$ dans $q(\alpha)$ :

$$ q(\alpha) = - \frac{\alpha^2}{4} + \alpha $$

Nous avons maintenant obtenu la forme de la fonction duale $q(\alpha)$. Ensuite, nous devons résoudre le problème dual pour trouver le maximum $\max_{\alpha} q(\alpha) $

Pour cela, nous dérivons $q(\alpha)$ par rapport à $\alpha$ et nous l’égalons à zéro :

$$ \frac{dq}{d\alpha} = - \frac{\alpha}{2} + 1 = 0 $$

En résolvant, on trouve $$ \alpha = 2 $$

En substituant $\alpha = 2$ dans $x = \frac{\alpha}{2}$, on obtient : $$ x = 1 $$

À ce moment-là, en substituant $\alpha = 2$ dans $q(\alpha)$, on calcule :

$$ q(\alpha) = - \frac{2^2}{4} + 2 = 1 $$

À travers cet exemple simple, nous pouvons voir que la solution du problème primal $x = 1$, $f(x) = 1$, est équivalente à la solution du problème dual $\alpha = 2$, $q(\alpha) = 1$. Cela vérifie que, sous certaines conditions, les solutions du problème dual et du problème primal sont cohérentes.

En appliquant la théorie de la dualité, nous avons non seulement trouvé la solution du problème primal, mais aussi obtenu le même résultat en résolvant le problème dual, vérifiant ainsi l’équivalence des solutions du problème dual.

Résolution avec les Conditions KKT

SVM Satisfait les Conditions KKT

Le problème d’optimisation original des SVM est un problème d’optimisation convexe. La fonction objectif des SVM $\frac{1}{2}|w|^2$ est une fonction quadratique, qui est une fonction convexe par rapport à $w$. En même temps, la contrainte $y_i(w \cdot x_i + b) \geq 1$ est linéaire (contrainte affine), donc elle est également convexe. Dans un problème d’optimisation convexe, une solution localement optimale est également globalement optimale, et les conditions KKT sont des conditions nécessaires et suffisantes. Cela signifie que si un point satisfait les conditions KKT, alors il est globalement optimal.

La fonction objectif $\frac{1}{2}|w|^2$ est continue et différentiable, et la contrainte $y_i(w \cdot x_i + b) \geq 1$ est également continue et différentiable. Cette régularité garantit l’existence et l’unicité du gradient, permettant ainsi l’application efficace des conditions KKT dans lesquelles on dérive par rapport à $w$ et $b$ et on égalise à zéro.

Dans un problème d’optimisation convexe, les conditions KKT ne sont pas seulement nécessaires, mais aussi suffisantes. Cela signifie que si un point satisfait les conditions KKT, alors il est nécessairement une solution globalement optimale. Pour les SVM, en résolvant les conditions KKT, nous pouvons trouver les valeurs optimales de $w^*$ et $b^*$, déterminant ainsi le meilleur hyperplan séparateur.

Utilisation des Conditions KKT pour Résoudre les SVM Linéaires

Le problème d’optimisation original des SVM est de minimiser $\frac{1}{2}|w|^{2}$ tout en satisfaisant la contrainte $y_{i}(w\cdot x_{i}+b)\geqslant1$, où $i = 1,2,\cdots,N$.

Tout d’abord, construisons la fonction lagrangienne $L(w,b,\alpha)=\frac{1}{2}|w|^{2}-\sum_{i = 1}^{N}\alpha_{i}(y_{i}(w\cdot x_{i}+b)-1)$, où $\alpha_{i}\geqslant0$ sont les multiplicateurs de Lagrange. Selon les conditions KKT, nous avons :

$$ \nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0 $$

$$ \nabla_{b}L(w^*,b^*,\alpha^*)=-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}=0 $$

$$ \alpha_{i}^*(y_{i}(w^*\cdot x_{i}+b^*)-1)=0 $$

$$ y_{i}(w^*\cdot x_{i}+b^*)-1\geqslant0 $$

$$ \alpha_{i}^*\geqslant0 $$

Ces conditions s’appliquent pour tous les $i = 1,2,\cdots,N$.

De $\nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0$, nous pouvons déduire

$$ w^*=\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i} \quad \text{(5)} $$ Étant donné qu’il existe au moins un $\alpha_{j}^*>0$ (si nous supposons que $\alpha_{i}^*=0$, cela conduirait à une contradiction avec la solution donnée par l’équation $\nabla_{w}L(w^*,b^*,\alpha^*) = w^*-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}=0$).

Pour résoudre $b^*$, nous pouvons substituer $w^*=\sum_{i = 1}^{N}\alpha_{i}^*y_{i}x_{i}$ dans $y_{j}(w^*\cdot x_{j}+b^*)-1 = 0$ (considérant l’existence de $\alpha_{j}^*>0$), et en notant que $y_{j}^{2}=1$, nous obtenons :

$$ b^*=y_{j}-\sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x_{i}\cdot x_{j}) \quad \text{(6)} $$

Basé sur la théorie ci-dessus, l’hyperplan séparateur peut être exprimé comme :

$$ \sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x\cdot x_{i})+b^*=0 $$

Ainsi, la fonction de décision de classification peut être écrite comme :

$$ f(x)=\text{sign}(\sum_{i = 1}^{N}\alpha_{i}^*y_{i}(x\cdot x_{i})+b^*) $$

Dans les SVM, la condition de complémentarité $\alpha_i (y_i(w \cdot x_i + b) - 1) = 0$ indique que si un point d’échantillon $x_i$ n’est pas un vecteur de support (c’est-à-dire $y_i(w \cdot x_i + b) > 1$), alors le multiplicateur de Lagrange correspondant $\alpha_i$ doit être nul. Inversement, si un point d’échantillon est un vecteur de support (c’est-à-dire $y_i(w \cdot x_i + b) = 1$), alors $\alpha_i$ peut être non nul. Cette condition garantit que seuls les vecteurs de support contribuent à la solution du problème d’optimisation, simplifiant ainsi le processus de résolution du problème.

Fonction Noyau Polynomial et Noyau Gaussien

Si le problème actuel n’est pas linéairement séparable, nous pouvons mapper les données existantes dans un espace de haute dimension, de sorte qu’elles deviennent un problème linéairement séparable dans cet espace de haute dimension. Mais effectuer des calculs directement dans l’espace de caractéristiques de haute dimension peut être très complexe. D’après les équations (5) et (6), nous savons que nous n’avons pas vraiment besoin de mapper les données dans un espace de haute dimension, tant que nous connaissons le produit scalaire entre les points de données. Le rôle de la fonction noyau est d’éviter de réaliser explicitement le mappage vers un espace de haute dimension, en calculant la valeur de la fonction noyau dans l’espace de caractéristiques d’origine pour réaliser indirectement le calcul du produit scalaire dans l’espace de caractéristiques de haute dimension.

La fonction noyau gaussienne est une fonction noyau courante, de la forme : $$ K(x, y) = \exp\left(-\gamma |x - y|^2\right) $$

où $\gamma$ est un paramètre positif, contrôlant la largeur de la fonction noyau.

Nous pouvons développer la fonction exponentielle en série de Taylor :

$$ \exp(z) = \sum_{k=0}^{\infty} \frac{z^k}{k!} $$

En substituant $ z = -\gamma |x - y|^2 $ dans la formule ci-dessus, on obtient :

$$ K(x, y) = \exp\left(-\gamma |x - y|^2\right) = \sum_{k=0}^{\infty} \frac{(-\gamma |x - y|^2)^k}{k!} $$

La fonction noyau polynomial est de la forme :

$$ K_{\text{poly}}(x, y) = (x \cdot y + c)^d $$

où $ c $ est la constante et $ d $ est le degré du polynôme.

$|x - y|^2$ peut être développé comme suit :

$$ |x - y|^2 = (x - y) \cdot (x - y) = x \cdot x + y \cdot y - 2 x \cdot y $$

En substituant cette expression dans la série de Taylor de la fonction noyau gaussienne :

$$ K(x, y) = \sum_{k=0}^{\infty} \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!} $$

On peut voir que chaque terme $ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!} $ est en fait un terme polynomial, c’est-à-dire que chaque terme peut être exprimé comme une combinaison de puissances différentes de $ x $ et $ y $.

Si nous examinons attentivement chaque terme, nous pouvons constater que la fonction noyau gaussienne est en réalité obtenue en harmonisant les fonctions noyau polynomiales de différents ordres. Chaque terme $ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^k}{k!} $ peut être considéré comme une forme pondérée d’une fonction noyau polynomiale d’ordre $ k $.

Par exemple, lorsque $ k = 1 $ :

$$ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^1}{1!} = -\gamma (x \cdot x + y \cdot y - 2 x \cdot y) $$

Lorsque $ k = 2 $ :

$$ \frac{(-\gamma (x \cdot x + y \cdot y - 2 x \cdot y))^2}{2!} = \frac{\gamma^2 (x \cdot x + y \cdot y - 2 x \cdot y)^2}{2} $$

Ces termes sont tous sous forme polynomiale de $ x $ et $ y $, et sont pondérés par la factorielle $ k! $.

La fonction noyau gaussienne peut être considérée comme étant obtenue en harmonisant les fonctions noyau polynomiales de différents ordres dans un espace de dimensions infinies. Cette harmonisation permet à la fonction noyau gaussienne de capturer des relations non linéaires plus complexes dans l’espace de caractéristiques de haute dimension. Par conséquent, dans la plupart des scénarios de tâches non linéaires, la fonction noyau gaussienne est un très bon choix.