1
$\begingroup$

I am trying to get a grasp of hard margin SVMs. In the lecture I am watching the professor talks about a classification equation which when a positive sample is input, returns a value of $1$ or more; and when a negative sample is input, returns a value of $-1$ or less. The graph below shows the vector $\overrightarrow{w}$ which is perpendicular to the separating hyperplane and an arbitrary point with unknown class $\overrightarrow{u}$.

enter image description here

In the lecture it says that:

$$\overrightarrow{w} \cdot \overrightarrow{u_+} + b \geq 1 \textrm{ , for positive class samples}$$

$$\overrightarrow{w} \cdot \overrightarrow{u_-} + b \leq -1 \textrm{ , for negative class samples} $$

To me it seems that we should take the projection of $\overrightarrow{u}$ on $\frac{\overrightarrow{w}}{|\overrightarrow{w}|}$, since this would give the component of $\overrightarrow{u}$ in the direction of $\overrightarrow{w}$. If this component is greater than the distance to the decision boundary/hyperplane, $b$, then $\overrightarrow{u}$ is a positive sample, if it is less then it is a negative sample. In math terms

$$\frac{\overrightarrow{w}}{|\overrightarrow{w}|} \cdot \overrightarrow{u_+} - b > 0$$

$$\frac{\overrightarrow{w}}{|\overrightarrow{w}|} \cdot \overrightarrow{u_-} - b < 0$$

If $\overrightarrow{u}$ lies on the decision boundary then the above expressions will be equal to 0.

If $\overrightarrow{u}$ lies on a support vector hyperplane, then the above expressions will be equal to $m$ or $-m$ for positive and negative samples respectively, where $m$ is the margin from the decision boundary to any support vector.

I don't understand the lecturer's equations. Why is the value for positive sample classification $\geq 1$? Why is the value for negative sample classification $\leq -1$? Furthermore, what does $b$ represent in the lecturer's equations?

Basically, I have trouble understanding the proposed equations, but they should be doing the same thing as mine.

$\endgroup$
0
$\begingroup$

when a positive sample is input, returns a value of $1$ or more; and when a negative sample is input, returns a value of $-1$ or less. The graph below shows the vector $\overrightarrow{w}$ which is perpendicular to the separating hyperplane and an arbitrary point with unknown class $\overrightarrow{u}$.

I don't understand the lecturer's equations. Why is the value for positive sample classification $\geq 1$? Why is the value for negative sample classification $\leq -1$? Furthermore, what does $b$ represent in the lecturer's equations?

The plane in the middle is $w \cdot u + b = 0$ where w is the vector of weights and u is the vector of inputs, the plane above that is $w \cdot u + b = 1$ and the plane below that is $w \cdot u + b = -1$. Consider that this -1 or +1 is the threshold we have chosen. It might be anything else. So, when input comes with a positive (+1) label that should be classified in the top of the $w \cdot u + b = +1$ plane, this equation is $+1$ if it is exactly on this plane and $ > 1$ if it is above this plane.

Moreover, as I mentioned this w is the weights vector and u is the input that is not classified in the beginning and then by calculating this expression $w \cdot u + b$ it is labeled as positive or negative.

To me it seems that we should take the projection of $\overrightarrow{u}$ on $\frac{\overrightarrow{w}}{|\overrightarrow{w}|}$, since this would give the component of $\overrightarrow{u}$ in the direction of $\overrightarrow{w}$. If this component is greater than the distance to the decision boundary/hyperplane, $b$, then $\overrightarrow{u}$ is a positive sample, if it is less then it is a negative sample. In math terms

$$\frac{\overrightarrow{w}}{|\overrightarrow{w}|} \cdot \overrightarrow{u_+} - b > 0$$

$$\frac{\overrightarrow{w}}{|\overrightarrow{w}|} \cdot \overrightarrow{u_-} - b < 0$$

b is not the distance from the vectors to the decision boundary. b is a constant of the line where the input is a vector 0. In the equation, you have substituted w for its unique vector, but this expression relies on b as well as w and input u, hence, this might turn out to be wrong in classifying inputs.

For instance, consider the plot I'm gonna describe, you have a middle plane $w \cdot u + b = 0$ where $w = (1, 1)$ and $b = -3$, so the plane is $1 \cdot u_1 + 1 \cdot u_2 -3 = 0$, thereby the above plane is $u_1 + u_2 -3 = 1$ and the bellow one equals $u_1 + u_2 -3 = -1$ Now for classifying the point $(4, 0)$ that is on plane $u_1 + u_2 -3 = 1$, if we follow your expression we would have $\frac{u_1}{\sqrt 2} + \frac{u_2}{\sqrt 2} -3$ that gives $\frac{4}{\sqrt 2} + \frac{0}{\sqrt 2} -3$ which is a negative value, though the point is in the + area.

More important than that, with your formula, you are ignoring the hard margin SVM because your expression is based on the middle line only.

If $\overrightarrow{u}$ lies on the decision boundary then the above expressions will be equal to 0.

No, then the dot product would be equal to 0 and the expression you have written would be equal to $-b$

If $\overrightarrow{u}$ lies on a support vector hyperplane, then the above expressions will be equal to $m$ or $-m$ for positive and negative samples respectively, where $m$ is the margin from the decision boundary to any support vector.

I have written a counterexample and the logic behind above.

$\endgroup$
  • $\begingroup$ So we could use $\overrightarrow{w} \cdot \overrightarrow{u} + b \geq c$ for any constant $c$ instead of using $1$? The choice of $c$ is arbitrary. $\endgroup$ – Tom Finet Jul 24 at 7:48
  • $\begingroup$ this expression defines your planes over and beneath the middle plane, if c is a bigger value than these planes are much farther from the middle one. It totally depends on the data points but consider an example in which the points are uniformly distributed. here if we set c as 1, for instance 30% of the data are above the upper line and if we set it as 2, then the upper line is farther and 10% of the points might be above this plane. But in general, we don't usually consider c as an arbitrary parameter. It usually gets some certain values. $\endgroup$ – Fatemeh Asgarinejad Jul 24 at 21:17
  • 1
    $\begingroup$ We only consider those $w$ and $b$ that are scaled so that the support vectors lie on the planes with $c=\pm1$. (This is why we can end up optimizing something about $\|w\|$.) $\endgroup$ – Ben Reiniger Jul 25 at 16:21
0
$\begingroup$

Very good question. Its worth understanding following concepts about SVM to understand about your point

  • SVM get trained from the training dataset in such a way that for every instance Xi in dataset
    W.Xi + b <= -1 if Xi belongs to -ve class
    W.Xi + b >=1 if Xi belongs to +ve class
  • This also means that for edge instances of +ve and -ve classes the value will be 1 and -1 respectively. This is what it means by making the street as wide as possible.
  • Above condition is not necessarily true with new unseen instance 'U' because it hasn't been seen by SVM algorithm yet so it can also be inside the street separating the classes
  • Above equation also implies that the edge instances are separated by 2 units (whatever the unit is). To make the street gap 2 unit, W not give projection of Xi perpendicular to the street but it also scales it to make the gap 2 units. This means W is not necessarily a unit vector.
  • In other word we are not comparing the component of U in direction perpendicular to the street but scaled version of it so that the street is always 2 units wide

This is intuition based explanation of SVM but mathematically also above equation is the constrain of the optimization problem needed to solved for SVM

$\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.