www-ai.cs.tu-dortmund.de/LEHRE/VORLESUNGEN/NOPT/WS16/lectures/lecture-00_intro.pdf
Untitled
yi ∈ {+1,−1}, i = 1, 2, . . . ,m
min w∈Rn,b∈R,ξ∈Rm
1
2 ‖w‖2 + C
m∑
i=1
ξi
s.t. ξi ≥ 1− yi (〈w , xi 〉+ b), i = 1, 2, . . . ,m
ξi ≥ 0, i = 1, 2, . . . ,m.
Primal form of the soft-margin SVM
• n+m+1 variables [...] Sangkyun Lee 14
min w∈Rn,b∈R,ξ∈Rm
1
2 ‖w‖2 + C
m∑
i=1
ξi
s.t. ξi ≥ 1− yi (〈w , xi 〉+ b), i = 1, 2, . . . ,m
ξi ≥ 0, i = 1, 2, . . . ,m.
Primal:
Dual:
Primal form à dual form
• n+m+1 variables à m variables
• [...] • 2m constraints à 2m (simple) + 1 constrains
• Can we solve the dual, instead of the primal ?
min α∈Rm
1
2 α TDyKDyα− eTα
s.t. yT α = 0
0 ≤ αi ≤ C , i = 1, 2, . . . ,m.
Kij = 〈xi , xj〉
Sparse Coding …
