General formula for the VC Dimension of a SVM

Question

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:

• "The VC Dimension of affine classifiers of the form $f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b$ in $n$ dimensions $-$ i.e. $\mathbf{w} \in \mathbb{R}^n $ $-$ is $n+1$": this corresponds to the case of what is called a linear SVM.
• "The VC Dimension of an SVM equipped with an RBF kernel is infinite."
• Etc.

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?

Answer 1

Your Claim: The VC Dimension of a SVM $f_K$ equipped with kernel $K$ can be defined as $d^{any}_K+1$.

Now, Just consider $K=(x.y)^2$ with transformation $\phi(x) = \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1x_2 \\ x_2^2 \end{pmatrix} $.

Just check that, $\nexists x$ $(=(x_1, x_2))$ s.t $$ \phi(x) = \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1x_2 \\ x_2^2 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} $$

So this alone makes the first case of proof The VC-dimension of the set of linear classifiers is d invalid

Essentially, higher-dimensional space $\mathcal{H}$ generated through any mapping $\phi$ is a "restrictive" space, in the sense that not all points exists in that space. There needs to be a separate proof for VC-dimension in these "restricted" spaces and we may need to proof it for different kernels.

(I hope you got my point, above $K$ and $\phi$ are just examples to get this point across)