SVM optimization problem

$$\underset{w,b}{min}\frac{1}{2}||w|{|}^2$$$$subjectto{y}_i(w^T{X}_i+b)\ge 1,i=1,\dots ,m$$$$y_i(w^T{x}_i+b)\ge 1,i=1,2,\dots ,m$$

• We can write the constraints as

  $$g_i(w)=1-y_i(w^T{x}_i+b)\le 0$$

• When we construct the Lagrangian for our optimization problem, we have:

  $$\mathcal{L}(w,b,\alpha )=\frac{1}{2}\parallel w{\parallel }^2+\sum _{i=1}^m{\alpha }_i[1-y_i(w^T{x}_i+b)]$$

• Let’s find the dual form of the problem.

  • First minimize $\mathcal{L}(w,b,\alpha )$ with respect to $w$ and $b$ (for fixed $\alpha$), to get ${\theta }_{\mathcal{D}}(\alpha )$.

• We’ll do this by setting the derivatives of $\mathcal{L}$ with respect to $w$ and $b$ to zero:

  $$\frac{\partial }{\partial w}\mathcal{L}(w,b,\alpha )=w-\sum _{i=1}^m{\alpha }_i{y}_i{x}_i=0$$$$\frac{\partial }{\partial b}\mathcal{L}(w,b,\alpha )=\sum _{i=1}^m-{\alpha }_i{y}_i=0$$

• We have: $$w = \sum_{i=1}^m \alpha_i y_i x_i$$ and $$\sum_{i=1}^m \alpha_i y_i = 0$$. Plugging back into the Lagrangian equation:

  $$\mathcal{L}(w,b,\alpha )=\frac{1}{2}\parallel w{\parallel }^2+\sum _{i=1}^m{\alpha }_i[1-y_i(w^T{x}_i+b)]$$$$=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j-b\sum _{i=1}^m{\alpha }_i{y}_i$$$$=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

Hard SVM

Hyperplane: $H=\{w|w^{T}x+b=0\}$Constraint: $y_i(w^T{x}_i+b)\ge 1$ $\mathrm{\forall }i$Goal: $min\frac{1}{2}||w|{|}^2$ s.t. $y_i(w^t{x}_i+b)\ge 1$Lagrangian:$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _i{\alpha }_i(y_i(w^T{x}_i+b)-1),{\alpha }_i\ge 0$Partial derivative: $\frac{\partial L}{\partial w}=w-\sum _i{\alpha }_i{y}_i{x}_i=0$ $\frac{\partial L}{\partial b}=-\sum _i{\alpha }_i{y}_i=0$Solution: $||w|{|}^2=(\sum _i{\alpha }_i{y}_i{x}_i{)}^T(\sum _i{\alpha }_i{y}_i{x}_i)=\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$Lagrangian becomes: $L=\sum _i{\alpha }_i-\frac{1}{2}\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$s.t. $\sum _i{\alpha }_i{y}_i=0$ and ${\alpha }_i\ge 0\mathrm{\forall }i$Weight vector: $w^{\ast }=\sum _i{\alpha }_i{y}_i{x}_i$Bias: $b^{\ast }=y_i-\sum _i{\alpha }_i{y}_i{x}_i^T{x}_j$

Soft SVM

Hyperplane: $H=\{w|w^{T}x+b=0\}$Constraint: $y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,\mathrm{\forall }i$Goal: $min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i,s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$
Lagrangian: $L(w,b,\alpha ,\xi )=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1+{\xi }_i)-\sum _{i=1}^n{\mu }_i{\xi }_i,{\alpha }_i,{\mu }_i\ge 0$Partial Derivative: $\frac{\partial L}{\partial w}=w-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0,\frac{\partial L}{\partial b}=-\sum _{i=1}^n{\alpha }_i{y}_i=0,\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0$Solution: $||w|{|}^2=\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$Dual Problem: $L=\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$s.t. $\sum _{i=1}^n{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C$

Weight vector: $w^{\ast }=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$Bias: $b^{\ast }=y_k-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i^T{x}_k\text{for any }0<{\alpha }_k<C$

The reason that ξ disappears: The slack variables ${\xi }_i$ disappear in the dual problem because they are implicitly handled through the Lagrange multipliers ${\alpha }_i$. By taking the derivative of the Lagrangian with respect to ${\xi }_i$, we obtain:$\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0$ This relationship ensures that ${\alpha }_i$ is bounded by $0\le {\alpha }_i\le C$. Consequently, the slack variables ${\alpha }_i$ do not explicitly appear in the dual formulation. Instead, the dual problem balances maximizing the margin and allowing for misclassification through the constraint on ${\alpha }_i$.

Kernel SVM

Hyperplane: $H=\{w|w^T\varphi (x)+b=0\}$Constraint: $y_i(w^T\varphi (x_i)+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,\mathrm{\forall }i$Goal: $min\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i,s.t.y_i(w^T\varphi (x_i)+b)\ge 1-{\xi }_i$Lagrangian (Dual): $L(\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)$s.t. $\sum _{i=1}^n{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C,\mathrm{\forall }i$Weight vector: $w=\sum _{i=1}^n{\alpha }_i{y}_i\varphi (x_i)$Decision Function: $f(x)=\text{sign}(\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b)$Bias: $b=y_k-\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x_k)\mathrm{\forall }supvec0<{\alpha }_k<C$Kernel Functions:
Linear: $K(x_i,x_j)=x_i^T{x}_j$
Polynomial: $K(x_i,x_j)=(x_i^T{x}_j+c{)}^d$
Gaussian (RBF): $K(x_i,x_j)=\exp (-\frac{||x_i-x_j|{|}^2}{2{\sigma }^2})$
Sigmoid: $K(x_i,x_j)=\tanh (\kappa x_i^T{x}_j+c)$