Understanding Support Vector Machine Algorithm

Question

I understand the SVM classifying algorithm in my book given the assumptions. My book says, suppose we have these two lines passing through the support vectors of the two classes. They then give the minimizing generalization error argument and proceed to make maximize the margin between the lines passing through the support vectors.

What I do not understand, is how to get the original two lines passing through the support vectors of the two classes? These lines are really defined by the support vectors.

1. When implementing the algorithm, how do you pick the support vectors?
2. What is commonly done in practice or in many libraries?

EDIT: What I meant by 'original two lines' is the decision boundary lines.

Thanks for all the help!

Answer 1

This answer applies to your first question (how to get the line passing through the SVs)

As for your questions on implementations, you may have a look at LibSVM, concretely this paper. Regretfully, there is no easy answer. There are different implementations depending on your application domain. It would be best if you research what implementation people use in the domain of your interest.

Answer 2

I am not sure what you mean by the original two lines passing through the support vectors, so I can't answer that part.

Support vectors arise from the following optimization problem:

$$\begin{align} \min_{\alpha,b,\xi} &\quad \frac{1}{2} \underbrace{\sum_{i\in\mathcal{S}} \sum_{j\in\mathcal{S}} \alpha_i \alpha_j y_i y_j \kappa(\mathbf{x}_i,\mathbf{x}_j)} + C \sum_{i=1}^N \xi_i \\ \text{s.t.} &\quad y_i \big(\sum_{j\in\mathcal{S}} \alpha_j y_j \kappa(\mathbf{x}_j,\mathbf{x}_i) + b\big) \geq 1 - \xi_i, \qquad \forall i \end{align}$$

The dual weights $\alpha$, the bias $b$ and the slack variables $\xi$ form the solution of the optimization problem. $\alpha$, $b$ and the set of support vectors make up the SVM model. The underbraced term in the cost function is the squared norm of the separating hyperplane in feature space, formulated as a function of $\alpha$ and the support vectors.

When implementing the algorithm, how do you pick the support vectors?

The support vectors are those instances for which the associated dual weight $\alpha$ is nonzero in the solution of the optimization problem, e.g. $\mathcal{S} = \{i : \alpha_i \neq 0\}$. In other words, the set of support vectors is a natural part of the solution. This is not something you need to select manually.

What is commonly done in practice or in many libraries?

The optimization problem is typically solved in the dual, particularly for kernel SVM. The most common technique used for this is sequential minimal optimization (SMO).