Gerade Abstand von Punkten / Support Vector Machine

31.07.2017, 18:27	fakename90	Auf diesen Beitrag antworten »
Gerade Abstand von Punkten / Support Vector Machine Hallo zusammen, die Aufgabe an der ich knobel hängt eigentlich mit dem "Maximum Margin Classifier", einer Vorversion der Support Vector Machine zusammen. Letztendlich dreht es sich aber nur noch um ein Gleichungssystem, und ob dieses Sinn ergibt: Ich habe 5 Punkte in 2D gegeben, 3 von einer Klasse und 2 von einer anderen Klasse (siehe Bild) [attach]45009[/attach] Die Aufgabe ist nun eine Hyperplane so zu bestimmen, dass die Datensets geteilt werden und die minimale Distanz der Punkte von der Hyperplane maximiert wird. Durch Anschauung kann man 3 Punkte identifizieren, die "support vectors" sind und somit die Hyperplane (hier: Gerade) festlegen. Jetzt gibt es zur Lösung des Problems ein allgemeines Optimierungsproblem: $\begin{eqnarray} $$ max M $$ \end{eqnarray}$ $\begin{eqnarray} $$ y_i (\beta_0 + \beta_1 \cdot x_{i1} + \beta_2 \cdot x_{i2} ....) \geq M $$ \end{eqnarray}$ $\begin{eqnarray} $$\sum\limits_{i=1}^n \beta_i^2 = 1$$ \end{eqnarray}$ Hierbei ist $\begin{eqnarray} $$y_i$$ \end{eqnarray}$ die Klassenzugehörigkeit, welche mit +1 oder -1 gegeben ist. Mein Ansatz war nun, für die drei Support Vectors (c, d, e) die Ungleichung durch eine Gleichung zu ersetzen, da die Margin M für diese ja gleich sein muss im Optimalfall: $\begin{eqnarray} $$ +1 (\beta_0 + 3 \beta_1+ 2 \beta_2 ) = M $$ \end{eqnarray}$ für den Punkt (3,2) $\begin{eqnarray} $$ -1 (\beta_0 + 2 \beta_1+ 4 \beta_2 ) = M $$ \end{eqnarray}$ für den Punkt (2,4) $\begin{eqnarray} $$ -1 (\beta_0 + 4 \beta_1+ 3 \beta_2 ) = M $$ \end{eqnarray}$ für den Punkt (4,3) Danach erhält man Werte für die Betas(M) und habe dann versucht über $\begin{eqnarray} $$\sum\limits_{i=1}^n \beta_i^2 = 1$$ \end{eqnarray}$ M zu bestimmen. Das Ergebnis kann aber nicht stimmen, die Rechnung habe ich 100x nachgerechnet. Wo liegt der Denkfehler? Vielen Dank
31.07.2017, 18:49	HAL 9000	Auf diesen Beitrag antworten »
Von welchem Ergebnis reden wir? Man sieht ja in deinem einfachen 2D-Beispiel sofort, dass die Trennungsgerade parallel zur Strecke $\begin{eqnarray} de \end{eqnarray}$ verläuft, d.h. die Darstellung $\begin{align} x+2y=t \end{align}$ hat, und wenig später bekommt man auch $\begin{align} t=8.5 \end{align}$ heraus. Normierung ergibt dann $\begin{align} \beta_0 = \frac{17}{2\sqrt{5}} \end{align}$ , $\begin{align} \beta_1 = -\frac{1}{\sqrt{5}} \end{align}$ und $\begin{align} \beta_2 = -\frac{2}{\sqrt{5}} \end{align}$ sowie dann Abstand $\begin{align} M = \frac{3}{2\sqrt{5}} \end{align}$ Eine allgemeine Anmerkung, was dein Optimierungsproblem betrifft: Du musst natürlich fordern, dass beide Klassen nichtleer sind, ansonsten gibt es keine Lösung: Die Trennungsgerade bzw. -hyperebene kann ja sonst ins unendliche verschoben werden. EDIT: Wieder einer, der sehr schnell das Interesse verloren hat. Oder woanders fündig geworden ist.
01.08.2017, 11:12	fakename90	Auf diesen Beitrag antworten »
Hallo, zu deinem Edit: Ich habe nur drüber nachgedacht Also nicht zu deiner Antwort, die ist super und nachvollziehbar. Allerdings habe ich mein Problem noch gesucht und auch mittlerweile gefunden. Wie so oft ein enorm dämlicher Fehler, der doch bei den 100x rechnen aufgetreten ist. $\begin{eqnarray} $$\sum\limits_{i=1}^n \beta_i^2 = 1$$ \end{eqnarray}$ Bei dieser Formel habe ich betta0 noch betrachtet. Trotzdem vielen Dank für den anderen Gedanken mit der Parallele!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »