3
$\begingroup$

I know how support vector machines work, but for some reason I always get confused by what exactly the support vectors are.

In the case of linearly separable data, the support vectors are those data points that lie (exactly) on the borders of the margins. These are the only points that are necessary to compute the margin (through the bias term $b$).

For C-SVMs, however, I always get confused as to what exactly the support vectors are. Obviously, the data points on the border of the margin are still support vectors, but I always get confused whether or not the points that are in the margin are support vectors or not. After all, only the exact borders are used to compute the bias term $b$ (in the same way as for the linearly separable case) and thus it could be argued that the margin is only supported by these points.

I do have this feeling that this is incorrect, however, because I have found multiple questions here where they mention 1000+ support vectors, which would be impossible if only those on the border count. My question is thus what exactly the support vectors are for an SVM and how I can remember this.

$\endgroup$
2
$\begingroup$

Short answer

The support vectors are those points for which the Lagrange multiplier is not zero (There is more than just $b$ in a Support Vector Machine).

Long answer

For a simple hard-margin SVM, we have to solve the following minimisation problem:

$$\min_{\boldsymbol{w}, b} \frac{1}{2} \|\boldsymbol{w}\|^2$$ subject to $$\forall i : y_i (\boldsymbol{w} \cdot \boldsymbol{x}_i + b) - 1 \geq 0$$

The solution can be found with help of Lagrange multipliers $\alpha_i$ and through the Karush-Kuhn-Tucker conditions, we find that the solution satisfies $$\alpha_i (y_i (\boldsymbol{w} \cdot \boldsymbol{x}_i + b) - 1) = 0$$ and thus either $\alpha_i = 0$ or the constraint for sample $i$ in the data is tight, i.e. $y_i (\boldsymbol{w} \cdot \boldsymbol{x}_i + b) - 1 = 0$. Therefore, those samples for which $\alpha_i \neq 0$ make up the points that are on the border and affect the solution.

For the C-SVM, which seems to be known as soft-margin SVM, the minimisation problem is given by:

$$\min_{\boldsymbol{w}, b} \frac{1}{2} \|\boldsymbol{w}\|^2 + C \sum_i \xi_i$$ subject to $$\forall i : \begin{aligned}y_i (\boldsymbol{w} \cdot \boldsymbol{x}_i + b) - 1 + \xi_i & \geq 0 \\ \xi_i &\geq 0\end{aligned}$$

Using Lagrange multipliers $\alpha_i$ and $\lambda_i = (C - \alpha_i)$, the Karush-Kuhn-Tucker conditions tell us that

$$\begin{align} \alpha_i (y_i (\boldsymbol{w} \cdot \boldsymbol{x}_i + b) - 1 + \xi_i) & = 0 \\ (C - \alpha_i) \xi_i & = 0 \end{align}$$

and thus those points for which $\alpha \neq 0$, and thus $y_i (\boldsymbol{w} \cdot \boldsymbol{x}_i + b) - 1 + \xi_i = 0$ directly affect the solution and make up the set of support vectors. In order to compute $b$, we can only use those points for which $\alpha_i = C$, and thus $\xi_i = 0$, because then we get $y_i (\boldsymbol{w} \cdot \boldsymbol{x}_i + b) - 1 = 0$ again. However, the entire solution also depends on those points for which $\alpha_i < C$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.