Based on visualized decision boundaries, we have to decide what kind of classifier has generated it. One example is shown in the image below - this is from a quadratic kernel Support Vector Machine (SVM), i.e. $K(x,y) = (x^T*y+c)^2$. I know what a quadratic function looks like in two dimensions, but want to understand how to determine what kind of functions have led to the boundaries in three dimensions - is this basically a "cut" through for instance a parabola in three dimensions, which leads to this ellipsoid boundary?

enter image description here

up vote 5 down vote accepted

There are (at least) two ways to think about this.

One is as you mentioned: imagine the points being lifted into the shape of a quadratic function, and then being cut by a plane, producing an ellipse. This is kind of like this picture (stolen from this paper): illustration of kernel mapping features

Another way to think about it is: the decision boundary for an SVM will always be of the form $\{ y \mid \sum_i \alpha_i k(x_i, y) = b \}$. For the kernel $k(x, y) = (x^T y + c)^2$, we have: \begin{align} \sum_i \alpha_i (x_i^T y + c)^2 &= \sum_i \left[ \alpha_i (x_i^T y)^2 + 2 \alpha_i x_i^T y + \alpha_i c^2 \right] \\&= \sum_i \alpha_i y^T x_i x_i^T y + \left( \sum_i 2 \alpha_i x_i \right)^T y + c^2 \sum_i \alpha_i \\&= y^T \left( \sum_i \alpha_i x_i x_i^T \right) y + \left( \sum_i 2 \alpha_i x_i \right)^T y + c^2 \sum_i \alpha_i \\&= y^T Q y + r^T y + s ,\end{align} which is itself a quadratic function. So the decision boundary is always going to be the level set of some quadratic function on the input space.

  • Thank you:) Though does it not follow simply from the kernel being quadratic that the decision boundary is so, too? I can follow your derivation, but what additional information does it give me in this context? – Pegah Jul 31 '17 at 19:31
  • 3
    The kernel being quadratic implies that the decision boundary is a level set of a mixture of quadratics. It's true for quadratics specifically that a mixture of quadratics is itself quadratic (as I showed here), but that's not necessarily true for other classes of kernels. For example, a Gaussian RBF kernel is itself a Gaussian bump, but $\sum_i \alpha_i k(x_i, y)$ is not necessarily shaped like a Gaussian bump – it can have a very complicated form. – Dougal Jul 31 '17 at 22:35

Suppose we have two features $(x_1, x_2)$, and we expand it into five features $(x_1^2, x_2^2, x_1, x_2, x_1x_2)$

The decision boundary is

$$ \beta_0+\beta_1x_1^2+\beta_2x_2^2+\beta_3x_1+\beta_4x_2+\beta_5x_1x_2=0 $$

The intersection with a plane is ellipsoid boundary, Which looks like this

enter image description here

  • How does a quadratic kernel lead from two features to five? – Pegah Jul 31 '17 at 19:35
  • 1
    @Pegah check slide 4 and 5 here feature mapping – hxd1011 Jul 31 '17 at 19:37
  • 2
    (+1) This is the equation form of the first way of thinking about it from my answer. – Dougal Jul 31 '17 at 22:36

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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