# What are the support vectors in a support vector machine?

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.

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).

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$.