3
$\begingroup$

I am working on implementing the kernel SVM using cvxopt quadratic programming, this is for a class so that why I'm not using something like SKLearn. Assume here no slack variable, only SMV but with the "kernel trick".

Starting with linear SMV, once the model is trained, we calculate the $w$ and $b$, and have a linear decision boundary defined by:

$$x^Tw+b=0$$

When using a new (test) data point, I can directly interpret the class of the new by checking if it is above or below this line.

My question is how to interpret the class of a test point when I am using a non-linear kernel for the SVM. So I have trained the SVM using the polynomial kernel, where the kernel function can be seen as a feature map:

$$K=\langle \phi(x_i),\phi(x_j) \rangle=(x_i^Tx_j+1)^2$$

But again from the optimization I calculate a $w$ and $b$, which just defines a linear separation hyperplane, so I can't use the decision boundary directly to interpret a new (test) data point. This is where I am unsure what to do. It seems I need to first transform a new data point and then use the linear boundary, like this:

$$\phi(x)^Tw+b=0$$

Is this correct? If so, how can I calculate $\phi(x_i)$ for a single data point since I only used the kernel function and didn't transform the input data? I don't have an explicit function $\phi$ to use in this case.

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No. For any kernel, feature space never has to be specified, even if it can be, sometimes, for comprehension purpuses. Still, it is not univocal, whatever space satisfies kernel dot product equation can be considered the feature space of your kernel. Also, considering that some kernel spaces have infinite dimensions, computing $\phi(x)$ is often downright impossible.

Everithing can be made dependent on dot products, so that kernel function can be used on data. $$f(x)= sgn\left(\sum_i y_i\alpha_i k(x, x_i) + b\right)$$

Here the sum goes over support vectors $x_i$, $\alpha$ are the lagrangian multiplier and $y$ is 1 for one class and -1 for the other.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So inside the parentheses for the kernel function k, you have d, $x_i$. So how does this correspond to classifying a new point, I assume $x_i$ is the new point, so what is x? This is what I’m unsure about, how can I have a dot product when I just have 1 vector, the new x point to classify? Since in the example I gave we compute the dot product of the new x_i with w. $\endgroup$
    – jeffery_the_wind
    Nov 2, 2019 at 18:13
  • $\begingroup$ $w$ is not used, it may be infinite in dimension, and is not really estimated. $x_i$ are the support vectors, and $x$ is the new point. $\endgroup$
    – carlo
    Nov 2, 2019 at 18:15
  • $\begingroup$ Oh sorry right x_i are support vectors, alright I got it. Do you have any link to a reference on this? I Know there’s tons of material online but haven’t found something I really like yet, just lots of bits and pieces. $\endgroup$
    – jeffery_the_wind
    Nov 2, 2019 at 18:21
  • 1
    $\begingroup$ Well, my reference was Learning with Kernels by Scholkopf and Smola, so no. But consider this is just a rework of linear SVM to make it work without estimating $w$, and only using dot products instead. This way you can make the kernel magic happen. $\endgroup$
    – carlo
    Nov 2, 2019 at 18:26
  • 1
    $\begingroup$ This is chapter 1, which has the derivation you referred to: cs.utah.edu/~piyush/teaching/learning-with-kernels.pdf $\endgroup$
    – jeffery_the_wind
    Nov 3, 2019 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.