How to find the initial hyperplane in a Support Vector Machine (SVM)?

Question

As far as I understand Support Vector machines, we are trying to find the optimal hyperplane, out of all hyperplanes that are equidistant from the support vectors. There are an infinite number of these hyperplanes, so we can start with an initial hyperplane, H1, which is not optimal. We can then vary the length of the normal vector w, so that we slightly change H1 into H2, which has a larger margin. We continue this process until we find H_max, the hyperplane with maximum margin.

My question is how do I find the initial formula of the first hyperplane H1? Given a linearly separable data set in the plane, how can I calculate a hyperplane that separates the data into two classes and is equidistant from the support vectors? Additionally, I am perhaps forgetting the significance of the variable b in this process.

Answer 1

Not sure how this is done in the any specific library, but here is what I would try.

Given two sets of points ($K$ points in the first set and $S$ in the second set): $\{\mathbf{a}_i\}_{i=1\dots K}$ and $\{\mathbf{b}_i\}_{i=1\dots S}$, all in $N$-dimensional space ($\mathbb{R}^N$)

I would compute the 'centres of mass' of the two sets:

$$ \begin{align} \mathbf{A}=&\frac{1}{K}\sum_{i=1}^K \mathbf{a}_i \\ \mathbf{B}=&\frac{1}{S}\sum_{i=1}^S \mathbf{b}_i \end{align} $$

I would then use the mid-point between the two centres of mass,

$$\mathbf{M}=\left(\mathbf{A}+\mathbf{B}\right)/2$$ as the point for the hyper-plane.

Then I would use the vector connecting the two centres of mass,

$$\mathbf{C}=\mathbf{A}-\mathbf{B}$$

as the normal for the hyper-plane. Lets define

$$ \mathbf{\hat{n}}=\frac{\mathbf{C}}{\sqrt{\mathbf{C}.\mathbf{C}}} $$

A single point and a normal vector, in $N$-dimensional space, will uniquely define an $N-1$ dimensional hyper-plane. To actually do it you will need to find a set of vectors

$$ \{\mathbf{v}_j\}_{j=1\dots N-1},\quad \mathbf{v}_j.\mathbf{\hat{n}}=0\,\mbox{for all } j $$

This set can be created by Gram-Schmidt type process, starting from your trivial basis and then ensuring that every new vector is orthogonal to all vectors in the set and to $\mathbf{\hat{n}}$.

Once you did that, any point on the hyper-plane will be uniquely described by $N-1$ coordinates $\alpha_{i=1\dots N-1}$, and will correspond to the following point in the original $N$-dimensional space

$$ \mathbf{q}=\sum_{j=1}^{N-1} \alpha_j\mathbf{v}_j+\mathbf{M} $$