Support Vector Machine, 30 Zeilen

In diesem Artikel werde ich Ihnen zeigen, wie Sie Ihre sehr einfache Support-Vektor-Maschine ohne Scikit-Learn oder andere Bibliotheken mit einer vorgefertigten Implementierung in nur 30 Zeilen in Python schreiben. Wenn Sie den SMO-Algorithmus verstehen wollten, er aber zu kompliziert schien, kann dieser Artikel für Sie hilfreich sein.



Es ist unmöglich zu erklären, was die Matrix Support Vector Machine ist ... Sie müssen es selbst sehen.





Nachdem ich erfahren habe, dass Habré Medienelemente einfügen kann, habe ich eine kleine Demo erstellt (wenn es plötzlich nicht mehr funktioniert, können Sie Ihr Glück mit der Version auf Github [1] versuchen ). Platzieren Sie es in einer Ebene (Abstand von zwei Merkmalen $$$X$ und $$$Y$ ) mehrere rote und blaue Punkte (dies ist unser Datensatz) und die Maschine führt die Klassifizierung durch (jeder Punkt des Hintergrunds wird übermalt, je nachdem, wo die entsprechende Anforderung klassifiziert werden würde). Verschieben Sie die Punkte, ändern Sie den Kernel (ich empfehle Ihnen, Radial Basis Functions auszuprobieren) und die Härte des Randes (konstant) $$$C$ ). Ich entschuldige mich für den schrecklichen Code in JS - ich habe ihn nur einige Male in meinem Leben geschrieben, um den Algorithmus zu verstehen, verwenden Sie den Python-Code später in diesem Artikel.

Inhalt

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

Support Vector Machine ist eine maschinelle Lernmethode (überwachtes Lernen) zur Lösung von Klassifizierungs-, Regressions-, Anomalieerkennungsproblemen usw. Wir werden es am Beispiel eines binären Klassifizierungsproblems betrachten. Unser Trainingsbeispiel besteht aus einer Reihe von Merkmalsvektoren $$$\boldsymbol{x}_i$ in eine von zwei Klassen eingeteilt $$$y_i = \pm 1$ ... Klassifizierungsanforderung - Vektor $$$\boldsymbol{x}$ dem wir die Klasse zuordnen müssen $$$+1$ oder $$$-1$ ...



Im einfachsten Fall können die Klassen des Trainingsmusters unterteilt werden, indem nur eine gerade Linie wie in der Abbildung gezeichnet wird (für eine größere Anzahl von Merkmalen wäre dies eine Hyperebene). Nun, wenn eine Anfrage kommt, um einen Punkt zu klassifizieren $$$\boldsymbol{x}$ Es ist vernünftig, es in die Klasse einzuteilen, auf welcher Seite es sein wird.



Wie wählt man die beste gerade Linie? Intuitiv möchte ich, dass die gerade Linie in der Mitte zwischen den Klassen verläuft. Schreiben Sie dazu die Gleichung der Geraden als $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = 0$ und skalieren Sie die Parameter so, dass die Datensatzpunkte, die der geraden Linie am nächsten liegen, erfüllt werden $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = \pm 1$ (Plus oder Minus, je nach Klasse) - Diese Punkte werden als Unterstützungsvektoren bezeichnet .



In diesem Fall beträgt der Abstand zwischen den Grenzpunkten der Klassen $$$2/|\boldsymbol{w}|$ ... Natürlich möchten wir diesen Wert maximieren, um die Klassen so gut wie möglich zu trennen. Letzteres entspricht einer Minimierung $$$\frac{1}{2} |\boldsymbol{w}|^2$ wird das gesamte Optimierungsproblem geschrieben

$$

$$\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}$$

Wenn Sie es lösen, dann die Klassifizierung auf Anfrage $$$\boldsymbol{x}$ so produziert

$$

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

Dies ist die einfachste Support-Vektor-Maschine.



Und was tun, wenn sich Punkte verschiedener Klassen wie in der Abbildung gegenseitig durchdringen?



Wir können das vorherige Optimierungsproblem nicht mehr lösen - es gibt keine Parameter, die diese Bedingungen erfüllen. Dann ist es möglich, dass die Punkte die Grenze um den Betrag verletzen $$$\xi_i \geq 0$ Es ist jedoch auch wünschenswert, dass solche Verstöße so gering wie möglich sind. Dies kann erreicht werden, indem die Zielfunktion durch einen zusätzlichen Begriff geändert wird (Regularisierung) $$$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}$$

und das Klassifizierungsverfahren wird wie zuvor fortgesetzt. Hier der Hyperparameter $$$C$ ist verantwortlich für die Stärke der Regularisierung, das heißt, sie bestimmt, wie streng wir Punkte benötigen, um die Grenze zu respektieren: je mehr $$$C$ - je mehr $$$\xi_i$ verschwindet und je weniger Punkte die Grenze verletzen. Unterstützungsvektoren sind in diesem Fall die Punkte, für die $$$\xi_i > 0$ ...



Aber was ist, wenn das Trainingsset dem Logo von The Who ähnelt und die Punkte niemals durch eine gerade Linie getrennt werden können?



Hier wird uns eine geniale Technik helfen - der Kernel-Trick [4] . Um es anzuwenden, muss man jedoch auf das sogenannte duale (oder duale ) Lagrange-Problem übergehen . Eine ausführliche Beschreibung finden Sie in Wikipedia [5] oder in der sechsten Vorlesung des Kurses [3] . Die Variablen, in denen das neue Problem gelöst wird, werden als Dual- oder Lagrange-Multiplikatoren bezeichnet... Das doppelte Problem ist oft einfacher als das ursprüngliche und hat gute zusätzliche Eigenschaften. Beispielsweise ist es konkav, selbst wenn das ursprüngliche Problem nicht konvex ist. Obwohl seine Lösung nicht immer mit der Lösung des ursprünglichen Problems übereinstimmt (Dualitätsbruch), gibt es eine Reihe von Theoremen, die unter bestimmten Bedingungen einen solchen Zufall garantieren (starke Dualität). Und dies ist nur unser Fall, damit Sie sicher zum doppelten Problem gelangen können

$$

$$\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}$$

Wo $$$\lambda_i$ - doppelte Variablen. Nach dem Lösen des Maximierungsproblems muss auch der Parameter berechnet werden $$$b$ , das nicht im dualen Problem enthalten ist, aber für den Klassifikator benötigt wird

$$

$$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].$$

Der Klassifikator kann (und sollte) in Form von dualen Variablen umgeschrieben werden

$$

$$\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.$$

Was ist der Vorteil dieser Aufnahme? Bitte beachten Sie, dass alle Vektoren aus dem Trainingssatz hier ausschließlich in Form von Punktprodukten enthalten sind $$$(\boldsymbol{x}_i \cdot \boldsymbol{x}_j)$ ... Sie können zuerst Punkte auf eine Oberfläche in einem höherdimensionalen Raum abbilden und erst dann das Punktprodukt der Bilder im neuen Raum berechnen. Warum dies so ist, ist aus der Abbildung ersichtlich.



Wenn die Zuordnung erfolgreich ist, werden die Bilder der Punkte durch eine Hyperebene getrennt! In der Tat ist alles noch besser: Es muss nicht angezeigt werden, da wir nur am Punktprodukt interessiert sind und nicht an den spezifischen Koordinaten der Punkte. So kann der gesamte Vorgang emuliert werden, indem das Punktprodukt durch die Funktion ersetzt wird $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)$ , das heißt der Kern . Natürlich kann nicht jede Funktion ein Kernel sein - zumindest hypothetisch muss es eine Zuordnung geben $$$\varphi$ so dass $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)=(\varphi(\boldsymbol{x}_i) \cdot \varphi(\boldsymbol{x}_j))$ ... Die notwendigen Bedingungen werden durch den Satz von Mercer [6] bestimmt . Die Python-Implementierung wird linear darstellen ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j$ ), Polynom ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d$ ) der Kernel und der Kernel der radialen Basisfunktionen ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = e^{-\gamma |\boldsymbol{x}_i - \boldsymbol{x}_j|^2}$ ). Wie Sie den Beispielen entnehmen können, können Kernel ihre spezifischen Hyperparameter in den Algorithmus einführen, was sich auch auf dessen Betrieb auswirkt.



Möglicherweise haben Sie ein Video gesehen, in dem die Wirkung der Schwerkraft am Beispiel eines gedehnten Gummifilms in Form eines Trichters erklärt wird [7] . Dies funktioniert, da die Bewegung eines Punkts auf einer gekrümmten Oberfläche in einem hochdimensionalen Raum der Bewegung seines Bildes in einem niedrigerdimensionalen Raum entspricht, wenn Sie ihm eine nichttriviale Metrik zur Verfügung stellen. Tatsächlich verbiegt der Kern den Raum.

SMO-Algorithmus

Wir sind also am Ziel, das im vorherigen Abschnitt aufgeworfene Doppelproblem zu lösen

$$

$$\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}$$

dann finden Sie den Parameter

$$

$$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}$$

und der Klassifikator nimmt die folgende Form an

$$

$$\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}$$

Der SMO-Algorithmus (Sequential Minimal Optimization, [8] ) zur Lösung des Doppelproblems lautet wie folgt. In der Schleife wird unter Verwendung einer komplexen Heuristik ( [9] ) ein Paar von Doppelvariablen ausgewählt $$$\lambda_\M$ und $$$\lambda_\L$ und dann wird die Zielfunktion über ihnen unter der Bedingung der Konstanz der Summe minimiert $$$y_\M\lambda_\M + y_\L\lambda_\L$ und Einschränkungen $$$0 \leq \lambda_\M \leq C$ , $$$0 \leq \lambda_\L \leq C$ (Einstellen der Härte der Grenze). Die Summenbedingung speichert die Summe aller $$$y_i\lambda_i$ unverändert (schließlich haben wir den Rest der Lambdas nicht berührt). Der Algorithmus stoppt, wenn er eine ausreichend gute Einhaltung der sogenannten KKT-Bedingungen feststellt (Karush-Kuna-Tucker [10] ).



Ich werde einige Vereinfachungen vornehmen.

• Ich werde die komplexen Heuristiken der Indexauswahl verwerfen (dies wird im Kurs der Stanford University [11] durchgeführt ) und über einen Index iterieren und den anderen zufällig auswählen.
• Ich werde mich weigern, die KPCh zu überprüfen, und im Voraus eine vorgegebene Anzahl von Iterationen durchführen.
• Im Optimierungsverfahren selbst werde ich im Gegensatz zur klassischen Arbeit [9] oder zum Stanford-Ansatz [11] die Vektorgleichung einer geraden Linie verwenden. Dies vereinfacht die Berechnungen erheblich (vergleiche das Volumen von [12] und [13] ).

Nun zu den Details. Informationen aus dem Trainingsmuster können in Form einer Matrix geschrieben werden

$$

$$\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}$$

Im Folgenden werde ich die Notation mit zwei Indizes verwenden ( $$$\boldsymbol{K}_{i,j}$ ), um sich auf ein Element der Matrix und mit einem Index zu beziehen ( $$$\boldsymbol{K}_{k}$ ), um den Spaltenvektor der Matrix zu bezeichnen. Sammeln Sie die beiden Variablen in einem Spaltenvektor $$$\boldsymbol{\lambda}$ ... Wir sind interessiert an

$$

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

Angenommen, wir möchten bei der aktuellen Iteration die Zielfunktion durch Indizes maximieren $$$\L$ und $$$\M$ ... Wir werden Derivate nehmen, daher ist es zweckmäßig, die Begriffe auszuwählen, die die Indizes enthalten $$$\L$ und $$$\M$ ... Es ist einfach, in dem Teil mit der Menge zu tun $$$\lambda_i$ Die quadratische Form erfordert jedoch mehrere Transformationen.



Bei der Berechnung $$$\boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda}$ Die Summierung erfolgt über zwei Indizes $$$i$ und $$$j$ ... Markieren Sie Indexpaare mit $$$\L$ oder $$$\M$ ...





Schreiben wir das Problem neu, indem wir alles kombinieren, was nicht enthalten ist $$$\lambda_\L$ oder $$$\lambda_\M$ ... Beachten Sie Folgendes, um die Übersicht über die Indizes zu erleichtern $$$\boldsymbol{K}$ im Bild.

$$

$$\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}$$

Wo $$$\text{const}$ bezeichnet Begriffe unabhängig von $$$\lambda_\L$ oder $$$\lambda_\M$ ... In der letzten Zeile habe ich die Notation verwendet

$$

$$\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}$$

beachten Sie, dass $$$\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0$ hängt nicht ab von $$$\lambda_\L$ noch von $$$\lambda_\M$

$$

$$\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.$$

Der Kernel ist daher symmetrisch $$$\boldsymbol{Q}^T = \boldsymbol{Q}$ und du kannst schreiben

$$

$$\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}$$

Wir wollen die Maximierung so durchführen $$$y_\L\lambda_\L + y_\M\lambda_\M$ konstant geblieben. Dazu müssen die neuen Werte auf der Geraden liegen

$$

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

Es ist einfach, das für jeden sicherzustellen $$$t$

$$

$$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.$$

In diesem Fall müssen wir maximieren

$$

$$\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},$$

Das ist einfach, wenn man das Derivat nimmt

$$

$$\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}$$

Wenn wir die Ableitung mit Null gleichsetzen, erhalten wir

$$

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

Und noch etwas: Vielleicht klettern wir weiter als nötig und befinden uns wie auf dem Bild außerhalb des Platzes. Dann müssen Sie einen Schritt zurücktreten und an die Grenze zurückkehren

$$

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

Damit ist die Iteration abgeschlossen und es werden neue Indizes ausgewählt.

Implementierung

Das schematische Diagramm des Trainings einer vereinfachten Unterstützungsvektormaschine kann wie folgt geschrieben werden







Schauen wir uns den Code in einer echten Programmiersprache an. Wenn Ihnen der Code in den Artikeln nicht gefällt, können Sie ihn auf dem Github [14] studieren .







Beim Erstellen eines Objekts der SVM-Klasse können Sie Hyperparameter angeben. Das Training erfolgt durch Aufrufen der Fit-Funktion. Die Klassen müssen als angegeben werden $$$0$ und $$$1$ (intern konvertiert zu $$$-1$ und $$$+1$ Aus Gründen der besseren Kompatibilität mit sklearn) ist die Dimension des Merkmalsvektors beliebig zulässig. Die Vorhersagefunktion wird zur Klassifizierung verwendet.

Vergleich mit sklearn.svm.SVC

Nicht, dass dieser Vergleich viel Sinn macht, denn es handelt sich um einen extrem vereinfachten Algorithmus, der ausschließlich zum Unterrichten von Schülern entwickelt wurde, aber dennoch. Zum Testen (und um zu sehen, wie man alles benutzt) können Sie Folgendes tun (dieser Code ist auch auf dem Github verfügbar [14] ).





Nach dem Start werden Bilder generiert. Da der Algorithmus jedoch zufällig ausgewählt wird, unterscheiden sie sich bei jedem Start geringfügig. Hier ist ein Beispiel für die Funktionsweise des vereinfachten Algorithmus (von links nach rechts: lineare, polynomiale und rbf-Kernel)



Und dies ist das Ergebnis der industriellen Version der Support-Vektor-Maschine.



Wenn die Dimension $$$2$ scheint zu klein, können Sie immer noch auf MNIST testen





Für MNIST habe ich mehrere zufällige Klassenpaare ausprobiert (der vereinfachte Algorithmus unterstützt nur die binäre Klassifizierung), aber ich habe keinen Unterschied in der Arbeit des vereinfachten Algorithmus und von sklearn festgestellt. Die folgende Verwirrungsmatrix gibt eine Vorstellung von der Qualität.

Fazit

Vielen Dank an alle, die bis zum Ende gelesen haben. In diesem Artikel haben wir uns eine vereinfachte Tutorial-Implementierung einer Support-Vektor-Maschine angesehen. Natürlich kann es nicht mit einem Industriedesign mithalten, aber aufgrund der extremen Einfachheit und des kompakten Codes in Python sowie der Tatsache, dass alle Grundideen von SMO erhalten geblieben sind, kann diese Version von SVM durchaus ihren Platz in der Klassenzimmer. Es sollte beachtet werden, dass der Algorithmus nicht nur einfacher ist als ein sehr kniffliger Algorithmus [9] , sondern auch seine vereinfachte Version von der Stanford University [11] . Immerhin ist eine Support-Vektor-Maschine in 30 Zeilen wunderschön.

Referenzliste

1. https://fbeilstein.github.io/simplest_smo_ever/
2. Seite unter http://www.machinelearning.ru
3. "Anfänge des maschinellen Lernens", 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