Setting up the problem

In order to solve the above problem, we define the following Lagrangian function to be minimized $${\cal L}(\lambda,b,\boldsymbol{w})=\frac{1}{2}\boldsymbol{w}^T\boldsymbol{w}-\sum_{i=1}^n\lambda_i\left[y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1\right],$$ where $\lambda_i$ is a so-called Lagrange multiplier subject to the condition $\lambda_i \geq 0$.

Taking the derivatives with respect to $b$ and $\boldsymbol{w}$ we obtain $$\frac{\partial {\cal L}}{\partial b} = -\sum_{i} \lambda_iy_i=0,$$ and $$\frac{\partial {\cal L}}{\partial \boldsymbol{w}} = 0 = \boldsymbol{w}-\sum_{i} \lambda_iy_i\boldsymbol{x}_i.$$ Inserting these constraints into the equation for ${\cal L}$ we obtain $${\cal L}=\sum_i\lambda_i-\frac{1}{2}\sum_{ij}^n\lambda_i\lambda_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j,$$ subject to the constraints $\lambda_i\geq 0$ and $\sum_i\lambda_iy_i=0$. We must in addition satisfy the Karush-Kuhn-Tucker (KKT) condition $$\lambda_i\left[y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b) -1\right] \hspace{0.1cm}\forall i.$$

1. If $\lambda_i > 0$, then $y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)=1$ and we say that $x_i$ is on the boundary.
2. If $y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)> 1$, we say $x_i$ is not on the boundary and we set $\lambda_i=0$.

When $\lambda_i > 0$, the vectors $\boldsymbol{x}_i$ are called support vectors. They are the vectors closest to the line (or hyperplane) and define the margin $M$.

• «
• 1
• ...
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• ...
• 28
• »