I am interested in the question of the Vapnik–Chervonenkis (VC) dimension of Support Vector Machines (SVM). Until now, I have only found partial results related to particular cases of SVM. Some examples:

However, my belief is that we can produce some kind of general result $-$ and very abstract too $-$ on the VC Dimension of any SVM, by using two facts:

  • The first example above, regarding the VC dimension of affine classifiers and hence of linear SVM, and
  • The fact that a kernelized SVM works as a linear SVM applied to a higher-dimensional space $\mathcal{H}$.

In the following lines I explain my reasoning. Data $x_1, ..., x_N$ comes from some space $\mathcal{L}$ that can be thought as $\mathbb{R}^n$.

Let $K$ be some kernel. Let first define: $$\Phi(K) = \{\phi: K(x,y) = \phi(x)\cdot\phi(y), \; (x,y) \in \mathcal{L} \times \mathcal{L}, \; \phi:\mathcal{L} \rightarrow \mathcal{H}\}$$

$\Phi(K)$ is the set of all feature mappings that can be associated to kernel $K$ $-$ i.e. the set of all mappings implicitly defined by $K$; for an example of multiple mappings associated to a single kernel see (Burges, 1998), page 17, where $K(x,y)=(x \cdot y )^2.$

Now, letting $\Phi_K \equiv \Phi(K)$, we define:

$$H(\Phi_K) = \{\mathcal{H}: \phi \in \Phi(K)\}$$

$H(\Phi_K)$ is the set of higher-dimensional spaces $\mathcal{H}$ "generated" by $\Phi(K)$ $-$ each mapping $\phi$ is associated to a space $\mathcal{H}$; $H(\Phi_K)$ is simply the set of all these spaces.

We now define:

$$d_K^{\,\min} = \min_{\mathcal{H} \,\in \, H(\Phi_K)} dim(\mathcal{H})$$

$d_K^{\,\min}$ is simply the dimension of the space $\mathcal{H} \in H(\Phi_K)$ with minimal dimension.

Finally, let $f_K$ be a SVM equipped with a kernel $K$. Given that the underlying mechanism of a kernelized SVM is to classify data in a higher-dimensional space $-$ i.e. $dim(\mathcal{L}) \leq dim(\mathcal{H})$ $-$ where it is linearly separable and using the fact that the VC Dimension of affine classifiers in $n$ dimensions is $n+1$, my claim is:

Claim: The VC Dimension of a SVM $f_K$ equipped with kernel $K$ can be defined as $d_K^{\,\min}+1$.

Of course, I have arbitrarily chosen $d_K^{\,\min}$ $-$ we could for example have defined and chosen $d_K^{\,\max}$ instead $-$ but the minimum choice seems the most sensible one.

As I haven't read anything similar to this claim in SVM related sources, I was wondering what might be wrong with it. Does it make sense? Am I making any mistakes in my reasoning?

  • $\begingroup$ I know this questions hasn't been active in years, but could share any news on this? Thanks! $\endgroup$ Dec 21, 2020 at 14:07


Your Answer

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

Browse other questions tagged or ask your own question.