6
$\begingroup$

I came across this question on coursera's machine learning course. Could anyone explain me how do you solve the following questions?

enter image description here

enter image description here

EDIT:

According to my understanding(maybe I am wrong), theta is always orthogonal to the decision boundary. By looking at the data it seems that decision boundary should be Y-axis. As Y-axis will separate the positive and negatives. Moreover, it will have the maximum margin.

But I don't understand how to calculate norm of theta. As the theta vector is unknown.

Note: This is not a homework question. I already know the correct answer to the question. But I don't know how to solve this question. I just want to know how to solve this question.

$\endgroup$
  • $\begingroup$ Please follow the instructions displayed above. For more information, see self-study or our help center. $\endgroup$ – whuber Feb 5 '17 at 21:42
  • 1
    $\begingroup$ You have to give us at least some hint concerning the help you need. Otherwise all we can tell is you're asking for some kind of introduction to SVMs at some kind of generality at some kind of level of sophistication; and that just keeps us guessing. $\endgroup$ – whuber Feb 5 '17 at 21:51
  • 2
    $\begingroup$ @whuber I edited the question. Added the things that I know. $\endgroup$ – John Rambo Feb 5 '17 at 22:00
  • $\begingroup$ This is helpful, but please add the [self-study] tag. It doesn't matter that it isn't actually homework. $\endgroup$ – gung Feb 5 '17 at 22:10
  • $\begingroup$ @gung added the tag. $\endgroup$ – John Rambo Feb 5 '17 at 22:27
7
$\begingroup$

The simplification in this problem is that the intercept term $\theta_0=0$. This condition allows to draw the decision boundary through the origin. The goal is then to maximize the signed length of the projection vectors, so as to minimize the norm of $\lVert\theta\rVert$, which is our optimization goal: $\underset{\theta}{\arg \min} \frac{1}{2}\displaystyle \sum_{j=1}^n \theta_j^2.$

enter image description here

If you pivot the green vector $\theta$ around the origin, the optimization falls on the most intuitive position. Here is the simulation on Geogebra with a slider.

So just read the x-coordinate, and think about the reciprocal relationship of $p$ and $\lVert \theta \rVert$ (smaller projection values necessitate higher $\lVert\theta\rVert$ to compensate), under the $\pm 1$ constraint.

If the projection happened to be symmetrically $\pm 2$, your constraints that $p^{I=1}\lVert\theta\rVert\geq 1$, and $p^{I=0}\lVert\theta\rVert\leq -1$ would dictate for the norm, $\lVert \theta \rVert$ to be at least $1/2$.

The norm of theta is its length $\lVert \theta \rVert=\sqrt{\theta_1^2 + \theta_2^2}$ in the case of two features (as in the case illustrated - without intercept or "bias term").

$\endgroup$
0
$\begingroup$

I suggest that you study Andrew Ng's lecture note on SVM here. The short answer is, first you need to solve $\alpha_i$ in dual optimization problem. Then, solve for $\theta$, or $w$ in the lecture note using the following eq: $$w=\sum_{i=1}^{m}\alpha_iy^{(i)}x^{(i)}$$

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