Support Vector Machine, 30 lignes

Dans cet article, je vais vous montrer comment écrire votre machine vectorielle de support très simple sans scikit-learn ou d'autres bibliothèques avec une implémentation prête à l'emploi en seulement 30 lignes en Python. Si vous vouliez comprendre l'algorithme SMO, mais que cela vous paraissait trop compliqué, alors cet article peut vous être utile.



Il est impossible d'expliquer ce qu'est la machine à vecteurs de support Matrix ... Vous devez le voir vous-même.





Ayant appris que Habré a la capacité d'insérer des éléments multimédias, j'ai créé une petite démo (si ça ne marche pas du coup, vous pouvez encore tenter votre chance avec la version sur github [1] ). Placer sur un plan (espace de deux entités $$$X$ et $$$Y$ ) plusieurs points rouges et bleus (c'est notre jeu de données) et la machine effectuera la classification (chaque point de l'arrière-plan est repeint en fonction de l'endroit où la demande correspondante serait classée). Déplacez les points, changez le noyau (je vous conseille d'essayer les fonctions de base radiale) et la dureté de la bordure (constante $$$C$ ). Mes excuses pour le terrible code de JS - je n'y ai écrit que quelques fois dans ma vie, pour comprendre l'algorithme, utilisez le code Python plus loin dans l'article.

Teneur

• , , , . , — . , — [2] [3], , , .
• « SMO» SMO , , . , , SMO, .
• , «» Python .
• « sklearn.svc.svm» — 2D confusion matrix MNIST.
• «» - .

Support Vector Machine est une méthode d'apprentissage automatique (apprentissage supervisé) pour résoudre des problèmes de classification, de régression, de détection d'anomalies, etc. Nous la considérerons à l'aide de l'exemple d'un problème de classification binaire. Notre exemple de formation est un ensemble de vecteurs de caractéristiques $$$\boldsymbol{x}_i$ classé dans l'une des deux classes $$$y_i = \pm 1$ ... Demande de classification - vecteur $$$\boldsymbol{x}$ auquel nous devons attribuer la classe $$$+1$ ou $$$-1$ ...



Dans le cas le plus simple, les classes de l'échantillon d'apprentissage peuvent être divisées en traçant une seule ligne droite comme sur la figure (pour un plus grand nombre d'entités, ce serait un hyperplan). Maintenant, quand une demande vient classer un point $$$\boldsymbol{x}$ , il est raisonnable de le placer dans la classe de quel côté il sera.



Comment choisir la meilleure ligne droite? Intuitivement, je veux que la ligne droite passe au milieu entre les classes. Pour ce faire, écrivez l'équation de la ligne droite comme $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = 0$ et mettez à l'échelle les paramètres de sorte que les points de l'ensemble de données les plus proches de la ligne droite satisfassent $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = \pm 1$ (plus ou moins, selon la classe) - ces points sont appelés vecteurs de support .



Dans ce cas, la distance entre les points limites des classes est $$$2/|\boldsymbol{w}|$ ... Évidemment, nous voulons maximiser cette valeur afin de séparer au mieux les classes. Ce dernier équivaut à minimiser $$$\frac{1}{2} |\boldsymbol{w}|^2$ , tout le problème d'optimisation est écrit

$$

$$\begin{aligned} &\min \frac{1}{2} |\boldsymbol{w}|^2 \\ \text{subject to: } &y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0. \end{aligned}$$

Si vous le résolvez, alors la classification sur demande $$$\boldsymbol{x}$ produit comme ça

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}\left(\boldsymbol{x} \cdot \boldsymbol{w} + b\right).$$

Il s'agit de la machine vectorielle de support la plus simple.



Et que faire dans le cas où des points de classes différentes se pénètrent mutuellement comme sur la figure?



Nous ne pouvons plus résoudre le problème d'optimisation précédent - aucun paramètre ne remplit ces conditions. Ensuite, il est possible de permettre aux points de violer la limite du montant $$$\xi_i \geq 0$ , mais il est également souhaitable que ces contrevenants soient aussi peu nombreux que possible. Ceci peut être réalisé en modifiant la fonction objectif avec un terme supplémentaire (régularisation $$$L_1$ ):

$$

$$\begin{aligned} &\min\left( \frac{1}{2} |\boldsymbol{w}|^2 + C \sum_i \xi_i \right)\\ \text{subject to: }&\xi_i + y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0,\\ &\xi_i \geq 0, \end{aligned}$$

et la procédure de classement se poursuivra comme avant. Ici l'hyperparamètre $$$C$ est responsable de la force de la régularisation, c'est-à-dire qu'il détermine à quel point nous avons besoin de points pour respecter la frontière: plus $$$C$ - Le plus $$$\xi_i$ disparaîtra et moins de points violeront la limite. Les vecteurs de support dans ce cas sont les points pour lesquels $$$\xi_i > 0$ ...



Mais que se passe-t-il si l'ensemble d'entraînement ressemble au logo de The Who et que les points ne peuvent jamais être séparés par une ligne droite?



Ici, nous serons aidés par une technique ingénieuse - l' astuce du noyau [4] . Cependant, pour l'appliquer, il faut passer au problème de Lagrange dit dual (ou dual ). Une description détaillée de celui-ci peut être trouvée dans Wikipedia [5] ou dans la sixième conférence du cours [3] . Les variables dans lesquelles le nouveau problème est résolu sont appelées multiplicateurs doubles ou de Lagrange... Le problème double est souvent plus simple que le problème d'origine et présente de bonnes propriétés supplémentaires, par exemple, il est concave même si le problème d'origine n'est pas convexe. Bien que sa solution ne coïncide pas toujours avec la solution du problème d'origine (rupture de dualité), il existe un certain nombre de théorèmes qui, sous certaines conditions, garantissent une telle coïncidence (forte dualité). Et ce n'est que notre cas, vous pouvez donc vous attaquer au double problème en toute sécurité

$$

$$\begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j (\boldsymbol{x}_i \cdot \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

Où $$$\lambda_i$ - deux variables. Après avoir résolu le problème de maximisation, il est également nécessaire de calculer le paramètre $$$b$ , qui n'est pas inclus dans le problème double, mais est nécessaire pour le classificateur

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}\left[y_k - \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}_k)\right].$$

Le classificateur peut (et devrait) être réécrit en termes de variables doubles

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}) + b.$$

Quel est l'avantage de cet enregistrement? Veuillez noter que tous les vecteurs de l'ensemble de formation sont inclus ici exclusivement sous forme de produits scalaires $$$(\boldsymbol{x}_i \cdot \boldsymbol{x}_j)$ ... Vous pouvez d'abord mapper des points sur une surface dans un espace de plus grande dimension, puis seulement calculer le produit scalaire des images dans le nouvel espace. Pourquoi cela peut être vu sur la figure.



Si le mapping est réussi, les images des points sont séparées par un hyperplan! En fait, tout est encore mieux: il n'y a pas besoin d'afficher, car on ne s'intéresse qu'au produit scalaire, et non aux coordonnées spécifiques des points. Ainsi, toute la procédure peut être émulée en remplaçant le produit scalaire par la fonction $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)$ , qui s'appelle le noyau . Bien sûr, toutes les fonctions ne peuvent pas être un noyau - au moins hypothétiquement, il doit y avoir un mappage $$$\varphi$ tel que $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)=(\varphi(\boldsymbol{x}_i) \cdot \varphi(\boldsymbol{x}_j))$ ... Les conditions nécessaires sont déterminées par le théorème de Mercer [6] . L'implémentation Python représentera linéaire ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j$ ), polynôme ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d$ ) le noyau et le noyau des fonctions de base radiale ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = e^{-\gamma |\boldsymbol{x}_i - \boldsymbol{x}_j|^2}$ ). Comme vous pouvez le voir dans les exemples, les noyaux peuvent introduire leurs hyperparamètres spécifiques dans l'algorithme, ce qui affectera également son fonctionnement.



Vous avez peut-être vu une vidéo où l'action de la gravité est expliquée à l'aide de l'exemple d'un film de caoutchouc étiré sous la forme d'un entonnoir [7] . Cela fonctionne, car le mouvement d'un point sur une surface courbe dans un espace de grande dimension équivaut au mouvement de son image dans un espace de dimension inférieure, si vous lui fournissez une métrique non triviale. En fait, le noyau plie l'espace.

Algorithme SMO

Donc, on est au but, il reste à résoudre le double problème posé dans la section précédente

$$

$$\def\M{{\color{red}M}} \def\L{{\color{blue}L}} \begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(\boldsymbol{x}_i; \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

puis trouvez le paramètre

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}[y_k - \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}_k)], \tag{1}$$

et le classificateur prendra la forme suivante

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}) + b. \tag{2}$$

L'algorithme SMO (Sequential Minimal Optimization, [8] ) pour résoudre le problème dual est le suivant. Dans la boucle, en utilisant une heuristique complexe ( [9] ), une paire de variables doubles est sélectionnée $$$\lambda_\M$ et $$$\lambda_\L$ , puis la fonction objectif est minimisée sur eux, avec la condition de la constance de la somme $\$\; en\; ligne\; \$\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; \$\; en\; ligne\; \$$$y_\M\lambda_\M + y_\L\lambda_\L$ et restrictions $$$0 \leq \lambda_\M \leq C$ , $$$0 \leq \lambda_\L \leq C$ (réglage de la dureté de la bordure). La condition de somme stocke la somme de tous $$$y_i\lambda_i$ inchangé (après tout, nous n'avons pas touché au reste des lambdas). L'algorithme s'arrête lorsqu'il détecte une observance suffisamment bonne des conditions dites KKT (Karush-Kuna-Tucker [10] ).



Je vais faire quelques simplifications.

• Je rejetterai l'heuristique complexe de la sélection d'index (ceci est fait dans le cours de l'Université de Stanford [11] ) et j'irai sur un index, et je sélectionnerai l'autre au hasard.
• Je refuserai de vérifier le CCP et effectuerai un nombre prédéterminé d'itérations à l'avance.
• Dans la procédure d'optimisation elle-même, contrairement au travail classique [9] ou à l'approche de Stanford [11] , j'utiliserai l'équation vectorielle d'une droite. Cela simplifiera grandement les calculs (comparez le volume de [12] et [13] ).

Maintenant pour les détails. Les informations de l'échantillon de formation peuvent être écrites sous la forme d'une matrice

$$

$$\boldsymbol{K} = \begin{pmatrix} y_1 y_1 K(\boldsymbol{x}_1; \boldsymbol{x}_1) & y_1 y_2 K(\boldsymbol{x}_1; \boldsymbol{x}_2) & \dots & y_1 y_N K(\boldsymbol{x}_1; \boldsymbol{x}_N) \\ y_2 y_1 K(\boldsymbol{x}_2; \boldsymbol{x}_1) & y_2 y_2 K(\boldsymbol{x}_2; \boldsymbol{x}_2) & \dots & y_2 y_N K(\boldsymbol{x}_2; \boldsymbol{x}_N) \\ \cdots & \cdots & \cdots & \cdots \\ y_N y_1 K(\boldsymbol{x}_N; \boldsymbol{x}_1) & y_N y_2 K(\boldsymbol{x}_N; \boldsymbol{x}_2) & \dots & y_N y_N K(\boldsymbol{x}_N; \boldsymbol{x}_N) \\ \end{pmatrix}. \tag{3}$$

Dans ce qui suit, j'utiliserai la notation avec deux indices ( $$$\boldsymbol{K}_{i,j}$ ) pour faire référence à un élément de la matrice et avec un index ( $$$\boldsymbol{K}_{k}$ ) pour désigner le vecteur colonne de la matrice. Collectez les variables doubles dans un vecteur colonne $$$\boldsymbol{\lambda}$ ... Nous sommes intéressés par

$$

$$\max_{\boldsymbol{\lambda}} \underbrace{ \sum_{i=1}^n \lambda_i - \frac12 \boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda} }_{\mathscr{L}}.$$

Supposons, à l'itération courante, que l'on veuille maximiser la fonction objectif par des indices $$$\L$ et $$$\M$ ... Nous prendrons des dérivés, il est donc pratique de sélectionner les termes contenant les indices $$$\L$ et $$$\M$ ... C'est facile à faire dans la partie avec le montant $$$\lambda_i$ , mais la forme quadratique nécessitera plusieurs transformations.



Lors du calcul $$$\boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda}$ la sommation est effectuée sur deux indices, soit $$$i$ et $$$j$ ... Mettez en évidence les paires d'indices contenant $$$\L$ ou $$$\M$ ...





Réécrivons le problème en combinant tout ce qui ne contient pas $$$\lambda_\L$ ou $$$\lambda_\M$ ... Pour faciliter le suivi des indices, faites attention à $$$\boldsymbol{K}$ dans l'image.

$$\begin{aligned} \mathscr{L} &= \lambda_\M + \lambda_\L - \sum_{j} \lambda_\M \lambda_j K_{\M,j} - \sum_{i} \lambda_\L \lambda_i K_{\L,i} + \text{const} + \\ {\text{}\atop\text{ }} \rightarrow\qquad &+ \frac{1}{2}\lambda_\M^2 K_{\M,\M} + \lambda_\M \lambda_\L K_{\M,\L} + \frac{1}{2}\lambda_\L^2 K_{\L,\L} = \\ &= \lambda_\M \left(1-\sum_{j} \lambda_j K_{\M,j}\right) + \lambda_\L \left(1-\sum_{i} \lambda_i K_{\L,i}\right)+\\ &+\frac{1}{2}\left(\lambda_\M^2 K_{\M,\M} + 2 \lambda_\M \lambda_\L K_{\M,\L}+\lambda_\L^2 K_{\L,\L} \right) + \text{const} = \\ &=\boldsymbol{k}^T_0 \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}, \end{aligned}$$

Où $$$\text{const}$ désigne des termes indépendants de $$$\lambda_\L$ ou $$$\lambda_\M$ ... Dans la dernière ligne, j'ai utilisé la notation

$$\begin{align} \boldsymbol{v}_0 &= (\lambda_\M, \lambda_\L)^T, \tag{4a}\\ \boldsymbol{k}_0 &= \left(1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\M}, 1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\L}\right)^T, \tag{4b}\\ \boldsymbol{Q} &= \begin{pmatrix} K_{\M,\M} & K_{\M,\L} \\ K_{\L,\M} & K_{\L,\L} \\ \end{pmatrix},\tag{4c}\\ \boldsymbol{u} &= (-y_\L, y_\M)^T. \tag{4d} \end{align}$$

Notez que $$$\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0$ ne dépend pas de $$$\lambda_\L$ ni de $$$\lambda_\M$

$\$\$\; display\; \$\$\; \backslash \; boldsymbol\; \{k\}\; \_0\; =\; \backslash \; begin\; \{pmatrix\}\; 1\; -\; \backslash \; lambda\_\; \backslash \; M\; K\; \_\; \{\backslash \; M,\; \backslash \; M\}\; -\; \backslash \; lambda\_\; \backslash \; L\; K\; \_\; \{\backslash \; M,\; \backslash \; L\}\; -\; \backslash \; sum\_\; \{i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; M,\; i\}\; \backslash \backslash \; 1\; -\; \backslash \; lambda\_\; \backslash \; MK\; \_\; \{\backslash \; L,\; \backslash \; M\}\; -\; \backslash \; lambda\_\; \backslash \; LK\; \_\; \{\backslash \; L,\; \backslash \; L\}\; -\; \backslash \; sum\_\; \{\; i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; L,\; i\}\; \backslash \backslash \; \backslash \; end\; \{pmatrix\}\; =\; \backslash \; begin\; \{pmatrix\}\; 1\; -\; \backslash \; sum\_\; \{i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; M,\; i\}\; \backslash \backslash \; 1\; -\; \backslash \; sum\_\; \{i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; L,\; i\}\; \backslash \backslash \; \backslash \; end\; \{pmatrix\}\; -\; \backslash \; boldsymbol\; \{Q\}\; \backslash \; boldsymbol\; \{v\}\; \_0.\$\$\; afficher\; \$\$$

$$\boldsymbol{k}_0 = \begin{pmatrix} 1 - \lambda_\M K_{\M,\M} - \lambda_\L K_{\M,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \lambda_\M K_{\L,\M} - \lambda_\L K_{\L,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} = \begin{pmatrix} 1 - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} - \boldsymbol{Q} \boldsymbol{v}_0.$$

Le noyau est symétrique, donc $$$\boldsymbol{Q}^T = \boldsymbol{Q}$ et tu peux écrire

$$

$$\mathscr{L} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0 - \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 - \frac{1}{2} \boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}$$

Nous voulons effectuer la maximisation pour que $\$\; en\; ligne\; \$\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; +\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; \$\; en\; ligne\; \$$$y_\L\lambda_\L + y_\M\lambda_\M$ resté constant. Pour cela, les nouvelles valeurs doivent se trouver sur la ligne droite

$\$\$\; display\; \$\$\; (\backslash \; lambda\_\; \backslash \; M\; ^\; \backslash \; text\; \{nouveau\},\; \backslash \; lambda\_\; \backslash \; L\; ^\; \backslash \; text\; \{nouveau\})\; ^\; T\; =\; \backslash \; boldsymbol\; \{v\}\; (t)\; =\; \backslash \; boldsymbol\; \{v\}\; \_0\; +\; t\; \backslash \; boldsymbol\; \{u\}.\$\$\; afficher\; \$\$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new})^T = \boldsymbol{v}(t) = \boldsymbol{v}_0 + t \boldsymbol{u}.$$

Il est facile de s'assurer que pour tout $$$t$

$\$\$\; afficher\; \$\$\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; ^\; \backslash \; text\; \{nouveau\}\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; ^\; \backslash \; text\; \{nouveau\}\; =\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; +\; t\; (-y\_\; \backslash \; M\; y\_\; \backslash \; L\; +\; y\_\; \backslash \; L\; y\_\; \backslash \; M)\; =\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L.\$\$\; afficher\; \$\$$

$$y_\M\lambda_\M^\text{new} + y_\L\lambda_\L^\text{new} = y_\M \lambda_\M + y_\L \lambda_\L + t (-y_\M y_\L + y_\L y_\M) = y_\M\lambda_\M + y_\L\lambda_\L.$$

Dans ce cas, il faut maximiser

$$

$$\mathscr{L}(t) = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}(t) - \frac12 \boldsymbol{v}^{\,T}(t) \, \boldsymbol{Q} \, \boldsymbol{v}(t) + \text{const},$$

ce qui est facile à faire en prenant le dérivé

$$

$$\begin{align} \frac{d \mathscr{L}(t)}{d t} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \frac{d \boldsymbol{v}}{dt} &- \frac12 \left(\frac{d(\boldsymbol{v}^{\,T} \, \boldsymbol{Q} \, \boldsymbol{v})}{d \boldsymbol{v}}\right)^T \frac{d\boldsymbol{v}}{d t} =\\ &= \boldsymbol{k}_0^T \boldsymbol{u} + \underbrace{\boldsymbol{v}_0^T \boldsymbol{Q}^T \boldsymbol{u} - \boldsymbol{v}^T \boldsymbol{Q}^T \boldsymbol{u}}_{(\boldsymbol{v}_0^T - \boldsymbol{v}^T)\boldsymbol{Q} \boldsymbol{u}} = \boldsymbol{k}_0^T \boldsymbol{u} - t \boldsymbol{u}^T \boldsymbol{Q} \boldsymbol{u}. \end{align}$$

En égalant la dérivée à zéro, nous obtenons

$$

$$t_* = \frac{\boldsymbol{k}^T_0 \boldsymbol{u}}{\boldsymbol{u}^{\,T} \boldsymbol{Q} \boldsymbol{u}}. \tag{5}$$

Et encore une chose: peut-être allons-nous monter plus loin que nécessaire et nous retrouver en dehors de la place comme sur la photo. Ensuite, vous devez prendre du recul et revenir à sa frontière

$\$\$\; display\; \$\$\; (\backslash \; lambda\_\; \backslash \; M\; ^\; \backslash \; text\; \{nouveau\},\; \backslash \; lambda\_\; \backslash \; L\; ^\; \backslash \; text\; \{nouveau\})\; =\; \backslash \; boldsymbol\; \{v\}\; \_0\; +\; t\; \_\; *\; ^\; \{\backslash \; text\; \{restr\}\}\; \backslash \; boldsymbol\; \{\; u\}.\$\$\; afficher\; \$\$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new}) = \boldsymbol{v}_0 + t_*^{\text{restr}} \boldsymbol{u}.$$

Ceci termine l'itération et sélectionne de nouveaux index.

Mise en œuvre

Le diagramme schématique de la formation d'une machine à vecteurs de support simplifiée peut être écrit comme







Jetons un œil au code dans un vrai langage de programmation. Si vous n'aimez pas le code des articles, vous pouvez l'étudier sur le github [14] .







Lors de la création d'un objet de la classe SVM, vous pouvez spécifier des hyperparamètres. L'entraînement se fait en appelant la fonction fit, les classes doivent être spécifiées comme $$$0$ et $$$1$ (converti en interne en $$$-1$ et $$$+1$ , conçu pour une plus grande compatibilité avec sklearn), la dimension du vecteur d'entités est autorisée de manière arbitraire. La fonction de prédiction est utilisée pour la classification.

Comparaison avec sklearn.svm.SVC

Non pas que cette comparaison ait beaucoup de sens, car nous parlons d'un algorithme extrêmement simplifié, développé uniquement dans le but d'enseigner aux étudiants, mais quand même. Pour tester (et pour voir comment tout utiliser), vous pouvez faire ce qui suit (ce code est également disponible sur le github [14] ).





Après le lancement, des images seront générées, mais comme l'algorithme est aléatoire, elles seront légèrement différentes à chaque lancement. Voici un exemple du fonctionnement de l'algorithme simplifié (de gauche à droite: noyaux linéaires, polynomiaux et rbf)



Et c'est le résultat de la version industrielle de la machine à vecteurs de support.



Si la dimension $$$2$ semble trop petit, vous pouvez toujours tester sur MNIST





Pour MNIST, j'ai essayé plusieurs paires aléatoires de classes (l'algorithme simplifié ne prend en charge que la classification binaire), mais je n'ai trouvé aucune différence dans le travail de l'algorithme simplifié et de sklearn. La matrice de confusion suivante donne une idée de la qualité.

Conclusion

Merci à tous ceux qui ont lu jusqu'au bout. Dans cet article, nous avons examiné une implémentation de tutoriel simplifiée d'une machine à vecteurs de support. Bien sûr, il ne peut pas rivaliser avec un design industriel, mais en raison de l'extrême simplicité et du code compact en Python, ainsi que du fait que toutes les idées de base de SMO ont été préservées, cette version de SVM pourrait bien prendre sa place dans le salle de cours. Il convient de noter que l'algorithme est plus simple non seulement qu'un algorithme très délicat [9] , mais même sa version simplifiée de l'Université de Stanford [11] . Après tout, une machine à vecteurs de support en 30 lignes est magnifique.

Liste de références

1. https://fbeilstein.github.io/simplest_smo_ever/
2. page sur http://www.machinelearning.ru
3. "Les débuts de l'apprentissage automatique", KAU
4. https://en.wikipedia.org/wiki/Kernel_method
5. https://en.wikipedia.org/wiki/Duality_(optimization)
6. http://www.machinelearning.ru
7. https://www.youtube.com/watch?v=MTY1Kje0yLg
8. https://en.wikipedia.org/wiki/Sequential_minimal_optimization
9. Platt, John. Fast Training of Support Vector Machines using Sequential Minimal Optimization, in Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. Burges, A. Smola, eds., MIT Press (1998).
10. https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
11. http://cs229.stanford.edu/materials/smo.pdf
12. https://www.researchgate.net/publication/344460740_Yet_more_simple_SMO_algorithm
13. http://fourier.eng.hmc.edu/e176/lectures/ch9/node9.html
14. https://github.com/fbeilstein/simplest_smo_ever