You are given the $16$ training data points on the figure, denoted by $+$ and $-$ symbols, along

with $3$ test data points, denoted by squares $($for which you have no labels$).$ The axes intention$-$

ally have no tick marks, but you can assume that the scale of the $x_1$ and $x_2$ axes are the same.

$($a$)$ The closest average classifier has a high training

error rate. Explain why this is the case.

$($b$)$ Is there a linear classifier of the form $D_{\text{l}\text{i}\text{n}\text{e}\text{a}\text{r}}(x_1,x_2)=\{\begin{array}{cc}+1,& a_1{x}_1+a_2{x}_{2}0\\ -1,& a_1{x}_1+a_2{x}_2<mn\; id="EditorElement\_1059019">0</mn>\end{array}$

that can attain training error rate less than $\frac{1}{4}?$ Justify your answer.

$($c$)$ Consider a non$-$linear classifier of the form $D_{\text{n}\text{o}\text{n}-\text{l}\text{i}\text{n}\text{e}\text{a}\text{r}}(x_1,x_2)=\{\begin{array}{ccc}+1,& g(x_1,& x_2)\\ -1,& g(x_1,& x_2)>\end{array}$

where the function $g(x_1,x_2)$ depends only on $x_1,x_2$ while the threshold $$ can depend on

the training data. Select a good function $g(x_1,x_2)$ for this scenario. Justify your answer.

$($d$)$ Write a detailed procedure for selecting the threshold $$ from part $($c$)$ using the training

data. Your answer should be written explicitly in terms of $(\{$:$x_{\text{t}\text{r}\text{a}\text{i}\text{n},1,1},x_{\text{t}\text{r}\text{a}\text{i}\text{n},1,2},Y_{\text{t}\text{r}\text{a}\text{i}\text{n},1})$ for

$i=1,$dots,$n_{\text{t}\text{r}\text{a}\text{i}\text{n}}($but it does not need to be MATLAB$/$Python code or pseudo$-$code$).$

$($e$)$ Sketch the decision boundary for your trained non$-$linear classifier from parts $($c$)$ and $($d$)$

on the figure above. In each test data square, write the label selected by your classifier.