0
$\begingroup$

I am reading this paper about Support Vector Machines and need clarification on the method used to maximize the distance between two supporting hyperplanes.

First, some definitions:

Let:

$A$: an $m$ by $n$ matrix for each row represents a point in $\mathbb{R}^{n}$

$B$: another $m$ by $n$ matrix where the rows represent another set of points in $\mathbb{R}^{n}$

$x,\,w$: a column vector in $\mathbb{R}^{n}$

$x'$: the transpose of $x$

$\epsilon$: a vector of $1\textit{s}$ in $\mathbb{R}^{n}$

$\alpha\:\beta$: a real constant

Now, let's define two supporting hyperplanes:

$x'w=\beta$ and $x'w=\alpha$.

From page 3 of the paper:

The distance between the two parallel supporting hyperplanes is $\frac{\alpha-\beta}{\left\Vert w\right\Vert }$. Therefore, the distance between the two planes can be maximized by minimizing $\left\Vert w\right\Vert $ and maximizing $\left(\alpha-\beta\right)$.

The problem of maximizing the distance between the two supporting hyperplanes can be written as the following optimization problem (C-Margin): \begin{aligned}\underset{w,\alpha,\beta}{\min} & & \frac{1}{2}\left\Vert w\right\Vert ^{2}-\left(\alpha-\beta\right)\\ \text{s.t. } & &Aw-\alpha\epsilon\ge0,\, -Bw+\beta\epsilon\ge0 \end{aligned}

I don't understand how maximizing the numerator and minimizing the denominator of $\frac{\alpha-\beta}{\left\Vert w\right\Vert }$ is equivalent to minimizing the given objective function for $w,\alpha,\beta$

$\endgroup$
1
$\begingroup$

Here is one way of looking at it:

Minimizing $f(x,y)=\frac{x}{y}$ is like minimizing $\ln\frac{x}{y}$, as $\ln:t\rightarrow \ln t$ is an increasing function.

But since $\ln\frac{x}{y}=\ln x-\ln y$, minimizing $\frac{x}{y}$ is like minimizing $\ln x-\ln y$.

Now, although minimizing $x-y$ is not exactly equivalent to minimizing $\ln x-\ln y$, it should give you an intuition on why it works.

This being said, there are alternatives. In fact, the author of your paper minimizes $x^2 -y$, so he decided to give more importance to the numerator. You could very well choose to minimize $\alpha x -\beta y$, where $\alpha$ and $\beta$ are weights that give more less importance to your terms.

$\endgroup$
  • $\begingroup$ I'm sorry, I don't get the intuition of why it should work. Since the transformation to $x-y$ from $\ln x-\ln y$ did not involve the application of an increasing or decreasing function, how can we be sure that the point at which the former obtains an optima corresponds to the same point at which the latter obtains an optima too? Also, since the goal is to maximize the distance between the two planes, I thought your answer should have begun with maximizing $f(x,y)=\frac{x}{y}$. $\endgroup$ – mauna Jan 30 '16 at 3:30
  • $\begingroup$ If you want to maximize $f(x,y)=\frac{x}{y}$, then $x$ has to be as large as possible, and $y$ as small as possible. In other words you want to minimize $y$ and maximize $x$, or equivalently, minimize $-x$. As a result, you want to minimize $y-x$. $\endgroup$ – Kuifje Jan 30 '16 at 4:18

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.