1
$\begingroup$

SVM with gaussian kernel (RBF kernel) have infinite VC-dimension and the VC-dimension for SVM with polynomial kernels is very big too. Thus, I wonder how is possible that SVM have good generalization performances. In SRM (structural risk minimization) as larger is the VC dimension as larger is the risk. I know that SVM algorithm selects the hyperplane with minimum VC dimension (namely with minimum margin) however if the VC-dimension is infinite (like in gaussian kernels) this minimum is infinite and the risk will be likely high. How is it possible?

(the question is more specific than an other already existing)

$\endgroup$
  • $\begingroup$ You mean maximum margin not minimum margin $\endgroup$ – MotiNK May 11 '17 at 11:42
1
$\begingroup$

Note that the VC dimension for the SVM is at most the dimension of the data in kernel space.

The generalization capabilities of SVM arise through the margin, see for example herehttps://www.cs.utah.edu/~piyush/teaching/27-9-print.pdf on page 13 where they use Vapnik's bound on classifiers having a specific margin $\gamma$ (these are actually for classifiers which don't make mistakes on the training data but the point is illustrative). Specifically: $$ VC(H_\gamma) \leq \min\left\{D, \left\lceil\frac{4R^2}{\gamma^2}\right\rceil\right\} $$ where $D$ is the dimension of the data, and $||x_i|| \leq R$ for all data (so for RBF, $D=\infty$ and $R=1$)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, the VC-dimension of a SVM with a kernel that encounter Mercer's condition is VC(H)+1 where H is the dimension of minimum space where the training samples are mapped from that kernel(and this minimum space is infinite for RBF kernel).Thus SVM gaussian kernels have infinite VC-dimension. I knew the result that you posted but D is the dimension of data (the number of features) not the VC-dimension. However this last result tells that VC-Dimension is limited, but the other result tells us that VC-dimension should be infinite for RBF kernels.The two seem to be opposed.How is it possible? $\endgroup$ – Umbert May 11 '17 at 16:32
  • $\begingroup$ You're right about the dimension of data vs VC-dimension (and I've updated the answer to reflect that). $\endgroup$ – MotiNK May 12 '17 at 7:26
  • $\begingroup$ Your statement is inaccurate. The VC-dimension for SVM is upper-bounded by the value you give - it is not equal to it for all margins. Yes, with RBF kernel if we have a margin $\gamma \rightarrow 0$ then indeed our bound does become infinite, but if it is lower-bounded for the data, then we have a limit to the VC-dimension. In other words, SVM with RBF kernel CAN have infinite VC-dimension, but by maximizing the margin we choose a classifier belonging to a class of limited VC-dimension (and given the kernel it is indeed the minimizer of the above bound). $\endgroup$ – MotiNK May 12 '17 at 7:31
  • $\begingroup$ Thanks. Ok the statement "CAN HAVE" for me was "HAVE", instead maximizing the margin the VC-dimension is limited. Now it's all clear $\endgroup$ – Umbert May 15 '17 at 13:55

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.