Polynomial kernel function

Question

Consider SMV with the polynomial kernel $k(x_1,x_2)=(\langle x_1, x_2\rangle + 1)^d,$ where $d > 1.$ Is it true that if the dataset is separated with a hyperplane then the SVM (with the kernel $k$) always separates the dataset with a hyperplane (without any errors in the dataset)?

Answer 1

IT is not completely clear what you mean, but if you are asking "is it true that if the training data is separated with a hyperplane then the SVM will always separate the test data witout error", then the answer is "no".

Consider the case where the true decision boundary is non-linear, but where the training set has fewer samples than input features. In this case it is always possible to separate the training data with zero error with a linear hyperplane, but the classifier will have a non-zero test error (because the true decision boundary is non-linear).

The SVM is an approximate implementation of a bound on generalisation error, but the bound will always be greater than zero for non-trivial problems.

Answer 2

If your question is whether it is possible to separate without errors a linearly separable set of points by using polynomial kernel $k(x, z) = (\langle x, z \rangle + 1)^d$, $d > 1$, then the answer is yes, it is possible to do that. One of the feature spaces $H$ for the polynomial kernel $k(x, z) = (\langle x, z \rangle + 1)^d$ defined for $x, z \in R^n$ contains all monomials of variables $x_1, x_2, ..., x_n$ of degree not higher than $d$. Therefore it contains a subspace of variables $x_1, ..., x_n$. If your dataset is linearly separable in the space of $x_1, ..., x_n$ then it is linearly separable in $H$, which means that there exist an SVM with kernel $k(x, z)$ that separates your dataset in $R^n$ (without errors). It does not mean, however, that your SVM training algorithm of choice will find that hyperplane for a given $d$.