$($SVM formulation $[10$pt$])[$Context: During lectures, we studied how to formulate the SVM problem by generating buffer lines. Here, we will take a more direct approach.$]$ Work out the following steps to formulate a hard$-$margin SVM problem.

$($a$)[2$pt$]$ Consider a fixed hyperplane prescribed by ${}^{TT}x+b=0$ as plotted $($green line$)$ in the below figure. For an arbitrary point hat$(x)$ that lies on the positive halfspace, let hat$(x{)}_P$ be the projection of hat$(x)$ onto the hyperplane. The distance from hat$(x)$ to the hyperplane is $r.$ Write hat$(x)$ as a function of hat$(x{)}_P,$ and $r.[$Note that $$ may not be of unit length$]$

Answer:

$($b$)[2$pt$]$ Using the result in $($a$),$ expand ${}^{TT}$hat$(x)+b,$ then write $r$ as a function that depends on $,b$ and hat$(x).$

Hint: hat$(x{)}_P$ is on the hyperplane, so which condition does it satisfy?

Answer:

$($c$)[2$pt$]$ Consider a point hat$(x{)}^{\text{'}}$ that lies on the negative halfspace. Its distance to the hyperplane is $r^{\text{'}}.$ Write $r^{\text{'}}$ as a function that depends on $,b$ and hat$(x{)}^{\text{'}}.$

Answer:

$($d$)[2$pt$]$ Given a training dataset $(hat(x{)}_i,$hat$(y{)}_i)$ for $i=1,$dots,$N$ and hat$(y{)}_{i}in\{-1,+1\}.$ What is the distance from hat$(x{)}_i$ to the hyperplane ${}^{TT}x+b=0?$

Answer:

$2$

$($e$)[2$pt$]$ The training dataset is linearly separable. Define the margin as the minimum distance from the training samples to the hyperplane. Formulate an optimization problem over $$ and $b$ to find a separating hyperplane with maximum margin. $[$Note that here we are talking about the hyperplane ${}^{TT}x+b=0,$ and thus the separating constraint should be modeling the requirement that $"{}^{TT}$hat$(x{)}_i+b$ and hat$(y{)}_i$ have the same sign".$]$

Answer: