4
$\begingroup$

I was going through this Udacity video (part of the ML nano-degree), where the math behind maximizing the length between the data clouds of two classes is done.

So, the line closest to the +1 class cloud would be: $w^T x_1 + b = 1$

And, the line closest to the -1 class cloud would be: $w^T x_2 + b = -1$ ($x_1$ and $x_2$ being points of both the lines respectively.)

So, for getting the distance between both of them (the lines above), the professors subtract both of the equations.

And then, while finding ($x_1-x_2$), they divide both the sides with the norm of w ($||w||$), which starts at 2:24 minutes.

From then, I didn't understand the math in the video.

Why did the professors divide the sides by the norm? What do the norm specify/imply?

Can someone please explain the math from after 2:24?

$\endgroup$
4
$\begingroup$

In my personal opinion the lecturers's attempt to "make things look easy" by showing "magic tricks" ("let us now divide by the norm as if we were dealing with one-dimensional vectors AND VOILA") is rather unhelpful as it does not really explain neither the methodology nor the math nor the intuition.

There are some basic, but important notions hidden behind that "voila" step, let me help you by writing them out explicitly.

One way to find the distance between two parallel lines is to:

  • Pick any point $x_1$ on the first line.
  • Pick any point $x_2$ on the second line.
  • Project the vector $x_1 - x_2$ on the direction, perpendicular to two lines and measure the length of the projection.

    enter image description here

Here's an illustration, just in case: you have two lines, one point taken on each line, the vector $x_2-x_1$ connects the two points. The dotted line is a perpendicular to the two lines. The vector $v$ points in the direction of the perpendicular, and the red segment shows the distance you want to measure.

This red distance is exactly the length of the projection of $x_2 - x_1$ onto the dotted line.

At this point we shall need three facts:

  • (a) For any unit vector $v$ the value $x^T v$ is equal to $|x|\cos \alpha$, where $\alpha$ is the angle between the vectors. Coincidentally, this is exactly the (signed) length of the projection of $x$ on the line with direction defined by $v$.
  • (b) Any vector $v$ can be made a unit vector (i.e. vector of length 1) by dividing it with its actual length: $\frac{v}{|v|}$.
  • (c) The equation $w^T x + b = 0$ defines a line with the normal $w$. I.e. $w$ is a vector, perpendicular to the line.

We know from (c) that $w$ is perpendicular to the line, we know from (b) that $\frac{w}{|w|}$ is a unit vector, so we plug it into (a) to get that the (signed) distance between the lines must be equal to $$\frac{w^T(x_2-x_1)}{|w|}.$$

If we know that $w^T x_2 + b = -1$ and $w^Tx_1 + b = 1$ we can play a bit with the equations to get $w^T(x_2 - x_1) = -2$ and hence the (signed) distance must be $\frac{-2}{|w|}$. We can drop the sign easily. ... and voila!


This is certainly not the only way to solve the problem, so for completeness sake let me show you a similar, yet still useful alternative. Here, you need to know just one fact (which I suggest you memorize just like the facts above):

  • (d) (Signed) distance from point $p$ to a line defined implicitly by the equation $w^T x + b = 0$ (note the zero on the right) is equal to $\frac{w^T p + b}{|w|}$.

Now, we can compute the distance between two lines by taking a point on one of them and substituting it in (d).

Let $x_1$ be a point on the line $w^T x+ b = 1$. The second line has the form $w^T x + b = -1$ which is the same as $w^T x + b + 1 = 0$. The distance between the lines is therefore:

$$\frac{w^T x_1 + b + 1}{|w|} = \frac{1 + 1}{|w|} = \frac{2}{|w|}.$$


Yet another way to derive the necessary distance would be to note that the line $x = sw$ is perpendicular to the two lines of interest. If $x_1$ and $x_2$ are the intersection points of this perpendicular with the first and the second parallel line correspondingly, the necessary distance is just the Euclidean distance between the two points: $$ d = |x_1 - x_2| = \sqrt{(x_1 - x_2)^T(x_1 - x_2)}. $$ I'll leave solving this to you as an exercise.

$\endgroup$
3
$\begingroup$

Without any context, division by the norm of a vector can usually be interpreted as only retaining the direction of a vector while ignoring its magnitude.

As it turns out, retaining only direction is especially important when projecting a vector onto another vector.

Furthermore, it turns out that finding the shortest distance between two lines is also based on projections. In this case, however, the goal is to find a perpendicular line between the two lines, which is actually the original line less its projected part on the other line.

More here: https://en.wikipedia.org/wiki/Vector_projection

$\endgroup$
0
$\begingroup$

I have a question you may help me with…

I know that y(xi), by convention, would be -1 or 1 depending on which class the Xi belongs to.

But I don't fully understand why it's stablished that the hyperplane equation should be: w·xi + b >= 1 or w·xi + b <= -1

Where do those "1" and "-1" come from?

Shouldn't it be that, for any point, depending on its classification, the hyperplane equation would be like this?

w·xi + b >= yi * margin/2 (yi = -1 or 1)

There is no 1 or -1 anywhere…

Thanks in advance

$\endgroup$

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.