www-ai.cs.tu-dortmund.de/LEHRE/VORLESUNGEN/KDD/SS14/FOLIEN/7DMSVM1.slides.2014.pdf
des primalen in das duale Problem
1 2 ||~β||2 −
N∑ i=1
αi
[ yi
(〈 ~xi , ~β
〉 + β0
) − 1 ]
= 1 2 ||~β||2 −
N∑ i=1
αi yi
(〈 ~xi , ~β
〉 + β0
) +
N∑ i=1
αi
= 1 2 ||~β||2 −
N∑ i=1
αiyi
〈 ~xi , ~β
〉 −
N∑ i=1 [...] H1
H2
+
+
+
+
+
−
− −
−
−
−
−
d(H 1 , H 2
)
Nach Konstruktion liegt kein Beispiel zwischen H1 und H2, d.h.
〈~x , ~β〉+ β0 ≥ +1 ∀~x ∈ C+ (5)
〈~x , ~β〉+ β0 ≤ −1 ∀~x ∈ C− (6)
Der Abstand
d(H1,H2) = 2 ||~β|| [...] 〈~x , ~β〉+ β0 = 0
} unter der Bedingung, dass 1
2 ||~β|| 2 minimal ist. Achtung,
Minimieren 1 2 ||~β||
2 ist äquivalent zum Maximieren der Margin || ~β|| 2 .
Das Optimierungsproblem läßt sich in Zeit O(N3) …
