We decide to run the kernel perceptron algorithm over this dataset using the quadratic kernel. The number of

mistakes made on each point is displayed in the table below. $($These points correspond to those in the plot

above.$)$

Define the feature map of our quadratic kernel to be:

$(x)=[x_1^2,\sqrt[\phantom{2}]{2}{x}_1{x}_2,x_2^2{]}^T.$

Assume all parameters are set to zero before running the algorithm.

Based on the table, what is the output of $$ and ${}_0?$

$($Enter ${}_0$ accurate to at least $2$ decimal places.$)$

${}_0=$

$($Enter $$ as a vector, enclosed in square brackets, and components separated by commas, e$.$g$.$ type $0,1$ for

${\left[\begin{array}{cc}0& 1\end{array}\right]}^T.$ Note that this sample vector input may not be of the same dimension of the answer. Enter each

component accurate to at least $2$ decimal places.$)$

$=$

$2\mathrm{.}3$

Based on the calculation of $$ and ${}_0,$ does the decision boundary ${}^T(x)+{}_0=0$ correctly classify all the

points in the training dataset?

Yes

No $2\mathrm{.}4$

Recall for $x={\left[\begin{array}{cc}{x}_1& x_2\end{array}\right]}^T$

$(x)=[x_1^2,\sqrt[\phantom{2}]{2}{x}_1{x}_2,x_2^2{]}^T$

Define the kernel function

$K(x,x^{\text{'}})=(x{)}^T(x^{\text{'}})$

Write $K(x,x^{\text{'}})$ as a function of the dot product $x*x^{\text{'}}.$ To answer, let $z=x*x^{\text{'}},$ and enter $K(x,x^{\text{'}})$ in terms

of $z.$

$K(x,x^{\text{'}})=$Problem $2.$ Kernel Methods

In this problem, we want to do classification over a different training dataset, as shown in plot below:

$2\mathrm{.}1$

If we again use the linear perceptron algorithm to train the classifier, what will happen?

Note: In the choices below "converge" means given a certain input, the algorithm will terminate with a fixed

output within finite steps $($assume $T$ is very large: the output of the algorithm will not change as we increase $T$

$.$ Otherwise we say the algorithm diverges $($even for an extremely large $T,$ the output of the algorithm will

change as we increase $T$ further$).$

The algorithm always converges and we get a classifier that perfectly classifies the training dataset.

The algorithm always converges and we get a classifier that does not perfectly classifies the training

dataset.

The algorithm will never converge.

The algorithm might converge for some initial input of $,{}_0$ and certain sequence of the data, but will

diverge otherwise. When it converges, we always get a classifier that does not perfectly classifies the

training dataset.

The algorithm might converge for some initial input of $,{}_0$ and certain sequence of the data, but will

diverge otherwise. When it converges, we always get a classifier that perfectly classifies the training

dataset.