$2$ Support Vector Machine $[30$ pts$]$

Suppose we use suppor vector machines with the kernel:

$K(x,x^{\text{'}})=\{\begin{array}{ccc}1& if& x=x^{\text{'}}\\ 0& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}& \end{array}$

As we discussed in class, this corresponds to mapping each $x$ to a vector $(x)$ in some high

dimensional space $($that need not be specified$)$ so that $K(x,x^{\text{'}})=(x{)}^T(x^{\text{'}})$

As usual, we are given $m$ examples $(x_1,y_1),$cdots,$(x_m,y_m)$ where $y_{i}in\{-1,+1\}.$ Assume for

simplicity that all the $x_i\text{'}$s are distinct$($i$.$e$.,x_i{x}_j$ for $ij).$

$(1)10pts$ Recall that the weight vector $w$ used in SVM$\text{'}$s has the form

$w={\displaystyle \underset{i}{\overset{?}{}}}{}_i{y}_i(x_i).$

Compute the ${}_i\text{'}$s explicitly that would be found using SVM$\text{'}$s with this kernel.

$(2)[10$ pts$]$ Recall that the SVM algorithm outputs a classifier that, on input $x,$ computes the sign of

$w*(x).$ What is the value of this inner product on training example $x_i?$ What is the value of this

inner product on any example $x$ not seen during training? Based on these answers, what kind of

generalization error do you expect will be achieved by SVM$\text{'}$s using this kernel?

$(3)[10$ pts$]$ Recall that the generalization error of SVM$\text{'}$s can be bounded using the margin $($which is

equal to $\frac{1}{|}|w||),$ or using the number of support vectors. What is $$ in this case? How many support

vectors are there in this case? How are these answers consistent with your answer in part $($b$)?$