3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I know this questions hasn't been active in years, but could share any news on this? Thanks! $\endgroup$ Commented Dec 21, 2020 at 14:07
  • $\begingroup$ @nullgeppetto Does my answer make sense? $\endgroup$ Commented Oct 5, 2022 at 10:23

1 Answer 1

0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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