Support vector machine optimization question

Question

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

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.

Answer 1

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

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").

Answer 2

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)}$$