How does a quadratic kernel look like?

Question

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?

Answer 1

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):

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.

Answer 2

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

Answer 3

It looks like a conic section, in general. The image in the question is the ellipse case, the accepted answer depicts a parabola, and the one below illustrates the degenerate hyperbola that the two coordinate axis form, which allows for solving the XOR problem through the mapping $(x,y) \rightarrow (x,y,xy)$