Support Vector Machines

We have seen that in $p=2$ dimensions, a linear decision boundary takes the form ${}_0+{}_1{x}_1+{}_2{x}_2=0.$ We now investigate a non$-$linear decision boundary.

$($a$)(0\mathrm{.}5$ Point$)$ Sketch the curve $(1+x_1{)}^2+(2-x_2{)}^2=4.$

$($b$)(0\mathrm{.}5$ Point$)$ On your sketch, indicate the set of points for which $(1+x_1{)}^2+(2-x_2{)}^2>4$ and the set of points for which $(1+x_1{)}^2+(2-x_2{)}^{2}4$

$($c$)(1$ Point$)$ Suppose that a classifier assigns an observation to the blue class if $(1+x_1{)}^2+(2-x_2{)}^2>4,$ and to the red class otherwise. To what class are the following observations classified? $(0,0),(-1,1),(2,2),(3,8).$

$($d$)(1$ Point$)$ Argue that while the decision boundary in $($c$)$ is not linear in terms of $x_1$ and $x_2,$ it is linear in terms of $x_1,x_2,x_1^2,$ and $x_2^2.$

$2.$ Provide and explain one case where you would prefer One versus One approach to One vs All for multi$-$class classification. Provide one example and explain where you would prefer One vs All.

Consider the following optimization problem for Support Vector Classifier given in ISLP book Section $9\mathrm{.}2\mathrm{.}2.$ This classifier can be used to learn a linear decision boundary between two classes.

$mamiz{e}_{{}_0,{}_1\text{d}\text{o}\text{t}\text{s}\text{,}{}_p,lo{n}_0,lo{n}_1,\text{d}\text{o}\text{t}\text{s}\text{,}lo{n}_p,M}M$

subject $to{\displaystyle \underset{j=1}{\overset{p}{}}}{}_j^2=1,$

$y_i({}_0+{}_1{x}_{i1}+{}_2{x}_{i2}+$dots$+{}_p{x}_{ip})M(1-lo{n}_i)$

$lo{n}_{i}0,{\displaystyle \underset{i=1}{\overset{n}{}}}lo{n}_{i}C.$

$($a$)$ Explain how the variables $lo{n}_i$ and $C$ are related.

$($b$)$ Explain why the following sentence is true or false: $"$As the value of $C$ increases, the bias of the classifier decreases and the variance increases"

$($c$)$ Write down the optimization problem if we want to change the linear decision boundary to a quadratic decision boundary.

$($d$)$ How would you change the support vector classifier such that it can fit arbitrary non$-$linear decision boundary? $($Hint: Read Section $9\mathrm{.}3$ ISLP$)$