/vault

Definition - Duales Optimierungsproblem der Support Vector Machine

May 06, 202413 min read

⠀

Definition: Duales Optimierungsproblem der Support Vector Machine

Sei ein Datensatz mit und .

Das duale Optimierungsproblem der SVM erhalten wir durch:

Ist die (eindeutige) Lösung des Optimierungsproblems, so erhalten wir die Lösung des primalen Problems, und durch:

  • und
  • ,

wobei der kleinste Index sei, so dass .

Herleitung des dualen Optimierungsproblems

Sei das Primales Optimierungsproblem der SVM gegeben durch

Durch den Zusammenhang von Vektornorm und Skalarprodukt wissen wir, dass

außerdem haben wir verschiedene Beispiele . Wir haben also nicht nur eine, sondern Nebenbedingungen mit:

Die Lagrangefunktion erhalten wir nach Definition also durch:

Die Duale Funktion erhalten wir nun durch

Da ein konvexes Minimierungsproblem ohne Nebenbedingungen - und außerdem differenzierbar ist, erhalten wir die beiden optimalen Werte für und , indem wir den Gradienten von gleich null setzen. (Siehe hierzu auch Konvexe Funktion hat ihr globales Minimum an der Stelle an der der Gradient null ist).

Nullstellen der Lagrange-Funktion

An dieser Stelle noch eine kurze Memo, die wir gleich brauchen:

Memo - Dimension von und

Da , ist auch .

Also:

und nun nacheinander:

1. Term:

Wenn wir den Ausdruck jetzt noch nullstellen, erhalten wir:

Und das erhalten wir zum Beispiel durch

2. Term:

Jetzt zur zweiten partiellen Ableitung:

Wenn wir nun noch nullstellen, erhalten wir:

Nullgestellte Langrange-Funktion und resultierende duale Funktion

Die Lagrange-Funktion

wird also Minimal, wenn

  1. und
  2. (das ist auch Nebenbedingung des dualen Optimierungsproblems)

Setzen wir dies in die duale Funktion ein, erhalten wir

Da mit der 1. Folgerung gilt, dass , gilt

Das nutzen wir jetzt aus und erhalten:

und das entspricht genau der dualen Funktion des dualen Optimierungsproblems der SVM, was zu zeigen war.

Graph View

Mentioned in