2
$\begingroup$

I am currently trying to understand the derivation of the optimization problem for support vector machines. This is my derivation so far:

Suppose the optimal separating hyperplane determined by a SVM is given by: $$\vec{w} \cdot \vec{x} = b$$ Where $\vec{w}\in \mathbb{R}^n$ is the normal vector of the hyperplane, $\vec{x} \in \mathbb{R}^n$ is just some arbitrary vector and b is essentially the offset of the plane from the origin

Since this is the optimal separating hyperplane it must be that the shortest distance between it and the nearest data-point of the +class ($x_{+}$) and nearest data-point of the -class ($x_{-}$) must be equal, that is,

$$\tag{1} \frac{|\vec{x_{+}} \cdot \vec{w} - b|}{||\vec{w}||} = \frac{|\vec{x_{-}} \cdot \vec{w} - b|}{||\vec{w}||}$$

Now since $\vec{w}$ is the normal defining the hyperplane we can scale its magnitude without violating the hyperplane equation ($\vec{w}$ will still define the same hyperplane found by the SVM). Combine this with the fact:

$$\tag{2} \vec{w} \cdot \vec{x} = ||\vec{w}||\Bigl(\frac{\vec{w}}{||\vec{w}||} \cdot \vec{x} \Bigl)$$

And it becomes apparent that we can scale $||\vec{w}||$ in order to simplify (1) and obtain a simpler optimization problem.

Now this is where my derivation breaks down, I know that I am supposed to end up with part of the optimization problem being (and I am ignoring the additional constraints for now):

$$\tag{3} \min \frac{2}{||\vec{w}||}$$

which I can easily get from the LHS of equation (1) by scaling $||\vec{w}||$ such that $\vec{x_{+}} \cdot \vec{w} = b+1$

The issue is that I can't see how equality (1) is maintained if I do this. If I scale the mag. of $\vec{w}$ so that $\vec{x_{+}} \cdot \vec{w} = b+1$ then doesn't this mean that $\vec{x_{-}} \cdot \vec{w} = -(b+1)$? which when we plug into (1) we get the contradiction:

$$\frac{|\vec{x_{+}} \cdot \vec{w} - b|}{||\vec{w}||} = \frac{|\vec{x_{-}} \cdot \vec{w} - b|}{||\vec{w}||} \Rightarrow \frac{|(b+1)-b|}{||\vec{w}||} = \frac{|-(b-1)-b|}{||\vec{w}||} \Rightarrow \frac{1}{||\vec{w}||} = \frac{2b+1}{||\vec{w}||}$$

$\endgroup$

1 Answer 1

1
$\begingroup$

We scale not only $\vec w$, but also parameter $b$. One can do this, because if you multiply hyperplane by some parameter, you get the same hyperplane.

So $3 x_{1} - 5 x_{2} + 2 = 0 \ $ is the same as $-9x_{1} + 15 x_{2} - 6 = 0$. One can use such flexibility to set parameters ($\vec w, \ b$) such, that in optimal value the constrained $\min\limits_{X} |<\vec w, x> - b| = 1$ is met.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .