3
$\begingroup$

Gaussian is well known because its corresponding feature mapping is to infinite dimension. So with finite number of training data, is that the case that we can achieve zero training error with some proper combination of parameters?

If not, how we explain the reason behind it? Why data (no exact same here) can't be linear separable even if we map it into infinite dimension?

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes, it is always possible – as long as there are no duplicate data points, and assuming exact arithmetic – for a Gaussian kernel to perfectly separate any dataset:

Recall that SVMs, due to the representer theorem, find functions of the form $$f(x) = \sum_i \alpha_i k(X_i, x).$$

We want to show that there exist $\alpha_i$ such that $\operatorname{sign}(f(X_i)) = y_i$ for all $i$ in the training set, using the notation that $y_i \in \{-1, 1\}$. It's enough that $f(X_i) = y_i$ for each $i$.

Note that $f(X_j) = \sum_i \alpha_i k(X_i, X_j) = e_j^T K \alpha$, where $e_j$ is the $j$th standard basis vector (a 1 in the $j$th dimension, zero otherwise). Stacking these together, the vector of predictions on the training set is just $K \alpha$. So we need $$ K \alpha = y .$$

As long as $K$ is invertible, we just set $\alpha = K^{-1} y$.

But a Gaussian kernel matrix is always strictly positive definite: see here for example. So $K$ is always invertible, and we can always do this.

This of course isn't the actual SVM optimization problem, but if you do an unregularized SVM ($\lambda \to 0$ or, in the more typical SVM formulation, $C \to \infty$), $K^{-1} y$ (or any positive scalar multiple of it) will be the global optimizer of the SVM loss. A regularized SVM won't pick exactly this, and often this solution will overfit.

Note that this holds for any value of the Gaussian kernel bandwidth, at least theoretically; numerical error will often be an issue, especially with inappropriate bandwidths.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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