Wie kann eine Entwurfsentscheidung bei einer Reihe von Punkten im zweidimensionalen Raum für SVM funktionieren?

Kann mir jemand erklären, wie man eine SVM-Entscheidungsfunktion entwirft? Oder verweisen Sie mich auf eine Ressource, die ein konkretes Beispiel beschreibt.

BEARBEITEN

Für das folgende Beispiel kann ich sehen, dass die Gleichung $X_2 = 1.5$ die Klassen mit maximalem Rand trennt. Aber wie passe ich die Gewichte an und schreibe Gleichungen für Hyperebenen in der folgenden Form.

$$\begin{array}{ll} H_1 : w_0+w_1x_1+w_2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : w_0+w_1x_1+w_2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$$

Ich versuche, die zugrunde liegende Theorie im 2D-Raum richtig zu machen (da sie einfacher zu visualisieren ist), bevor ich über höhere Dimensionen nachdenke.

Ich habe eine Lösung dafür gefunden. Kann jemand bitte bestätigen, ob dies korrekt ist?

Der Gewichtsvektor ist (0, -2) und W_0 ist 3

$$\begin{array}{ll} H_1 : 3+0x_1-2x_2 \ge 1 & \text{for}\; Y_i = +1 \\ H_2 : 3+0x_1 -2x_2 \le -1 & \text{for}\; Y_i = -1.\end{array}$$

Es gibt mindestens zwei Möglichkeiten, SVMs zu motivieren, aber ich werde hier den einfacheren Weg einschlagen.

$\mathcal{D} = \{(x^i_1, x^i_2, y_i)\}$$y_i$$\{1, -1\}$$1$$-1$

$w_0 + w_1x_1 + w_2x_2 = 0$$w_0 + w_1x_1 + w_2x_2 > 0$$w_0 + w_1x_1 + w_2x_2 < 0$

$[w_0, w_1, w_2]$$w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 < 0$$x^i$$y_i = -1$

Nehmen wir an, dass eine solche Zeile tatsächlich existiert, dann kann ich einen Klassifikator folgendermaßen definieren:

$$\min |w_0| + |w_1| + |w_2| \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 0, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 < 0, \forall x^i\text{ with }y_i = -1 \\ $$

Ich habe oben eine beliebige Zielfunktion verwendet, es ist uns im Moment egal, welche Zielfunktion verwendet wird. Wir wollen nur ein , das unsere Anforderungen erfüllt. Da wir angenommen haben, dass eine Linie existiert, so dass wir die beiden Klassen mit dieser Linie trennen können, werden wir eine Lösung für das obige Optimierungsproblem finden.$w$

Das obige ist kein SVM, aber es gibt Ihnen einen Klassifikator :-). Dieser Klassifikator ist jedoch möglicherweise nicht sehr gut. Aber wie definieren Sie einen guten Klassifikator? Ein guter Klassifikator ist normalerweise derjenige, der auf dem Testset gut abschneidet. Im Idealfall würden Sie alle möglichen durchgehen , die Ihre Trainingsdaten trennen, und sehen, welche davon in den Testdaten gut abschneiden. Allerdings gibt es unendlich ‚s, so dass diese ganz hoffnungslos. Stattdessen werden wir einige Heuristiken betrachten, um einen guten Klassifikator zu definieren. Eine Heuristik ist, dass die Linie, die die Daten trennt, ausreichend weit von allen Punkten entfernt ist (dh es gibt immer eine Lücke oder einen Abstand zwischen den Punkten und der Linie). Der beste Klassifikator unter diesen ist der mit der maximalen Marge. Dies wird in SVMs verwendet.$w$$w$

Anstatt darauf zu bestehen, dass für alle Punkte mit und für alle Punkte mit , wenn wir darauf bestehen, dass für alle Punkte mit und für alle Punkte mit , dann bestehen wir tatsächlich darauf, dass Punkte weit von der Linie entfernt sind. Der dieser Anforderung entsprechende geometrische Rand lautet .$w_0 + w_1x^i_1 + w_2x^i_2 \geq 0$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 < 0$$x^i$$y_i = -1$$w_0 + w_1x^i_1 + w_2x^i_2 \geq 1$$x^i$$y_i = 1$$w_0 + w_1x^i_1 + w_2x^i_2 \leq -1$$x^i$$y_i = -1$$\frac{1}{\|w\|_2}$

Wir erhalten also das folgende Optimierungsproblem: Eine leicht prägnante Form des Schreibens ist: Dies ist im Grunde die grundlegende SVM-Formulierung. Der Kürze halber habe ich viele Diskussionen übersprungen. Hoffentlich habe ich den größten Teil der Idee noch durchgebracht.

$$\max \frac{1}{\|w\|_2} \\ \text{subject to} : w_0 + w_1x^i_1 + w_2x^i_2 \geq 1, \forall x^i\text{ with }y_i = 1 \\ w_0 + w_1x^i_1 + w_2x^i_2 \leq -1, \forall x^i\text{ with }y_i = -1 \\ $$ $$\min \|w\|_2 \\ \text{subject to} : y_i(w_0 + w_1x^i_1 + w_2x^i_2) \geq 1, \forall i$$

---

CVX-Skript zur Lösung des Beispielproblems:

A = [1 2 1; 3 2 1; 2 3 1; 3 3 1; 1 1 1; 2 0 1; 2 1 1; 3 1 1];
b = ones(8, 1);
y = [-1; -1; -1; -1; 1; 1; 1; 1];
Y = repmat(y, 1, 3);
cvx_begin
variable w(3)
minimize norm(w)
subject to
(Y.*A)*w >= b
cvx_end

---

Nachtrag - Geometrischer Rand

Oben haben wir bereits darum gebeten, nach suchen, so dass oder allgemein . Die LHS, die Sie hier sehen, wird als funktionale Marge bezeichnet. Wir haben hier also angefordert, dass die funktionale Marge . Nun werden wir versuchen, den geometrischen Rand unter Berücksichtigung dieser funktionalen Randanforderung zu berechnen.$w$$y_i(w_0 + w_1x_1 + w_2x_2) \geq 1$$y_i(w_0 + w^Tx) \geq 1$$\geq 1$

Was ist ein geometrischer Rand? Der geometrische Rand ist der kürzeste Abstand zwischen Punkten in den positiven Beispielen und Punkten in den negativen Beispielen. Nun können die Punkte mit dem kürzesten Abstand, wie oben gefordert, einen Funktionsspielraum von mehr als 1 haben. Betrachten wir jedoch den Extremfall, wenn sie der Hyperebene am nächsten liegen, dh der Funktionsspielraum für die kürzesten Punkte ist genau gleich zu 1. Sei der Punkt auf dem positiven Beispiel ein Punkt, so dass und der Punkt auf dem negativen Beispiel ein Punkt ist, so dass . Nun ist der Abstand zwischen und der kürzeste, wenn$x_+$$w^Tx_+ + w_0 = 1$$x_-$$w^Tx_- + w_0 = -1$$x_+$$x_-$$x_+ - x_-$ ist senkrecht zur Hyperebene.

Mit all den obigen Informationen werden wir nun versuchen, welches der geometrische Rand ist. $\|x_+ - x_-\|_2$

$$w^Tx_+ + w_0 = 1$$ $$w^Tx_- + w_0 = -1$$ $$w^T(x_+ - x_-) = 2$$ $$|w^T(x_+ - x_-)| = 2$$ $$\|w\|_2\|x_+ - x_-\|_2 = 2$$ $$\|x_+ - x_-\|_2 = \frac{2}{\|w\|_2}$$

---

[1] Es spielt eigentlich keine Rolle, welche Seite du für und wählst . Sie müssen nur konsequent bleiben, was auch immer Sie wählen.$1$$-1$