support vector - Aller au boulot

Suppose dataset $x_{i} \in R^{n}$ related to label $y_{i} \in {+ 1, - 1}$ , find $w \in R^{n}$ and bias $b \in R$ such that

${x_{i} \cdot w + b \geq + 1, y_{i} x_{i} \cdot w + b \leq - 1, y_{i} = + 1 = - 1$

which leads to

$y_{i} (x_{i} \cdot w + b) \geq + 1 .$

The distance between optimal hyperplanes is $2 / ∣ ∣ w ∣ ∣$ , so maximizing the margin equals to minimizing $∣ ∣ w ∣ ∣$ .

Primary problem : min $L_{p} (w, α_{i})$ ,

$L_{p} (w, α_{i}) = \frac{1}{2} ∣ ∣ w ∣ ∣^{2} - i \sum n α_{i} y_{i} (x_{i} \cdot w + b) + i \sum n α_{i}$

$\frac{\partial L _{p} ( w , α _{i} )}{\partial w} = 0$

leads to

$w = i \sum n α_{i} y_{i} x_{i}$

and $\forall i, α_{i} \geq 0$ ,

$\frac{\partial L _{p} ( w , α _{i} )}{\partial b} = 0$

leads to

$i \sum n α_{i} y_{i} = 0 .$

Dual problem : max $L_{d} (α_{i})$ ,

$L_{d} (α_{i}) = i \sum n α_{i} - \frac{1}{2} i, j \sum n α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j})$

s.t. $\forall i, α_{i} \geq 0$ ,

$i \sum n α_{i} y_{i} = 0 .$

Only support vectors have nonzero coefficients $α_{i}$ .

Approaches : sub-gradient descent and coordinate descent.