7
$\begingroup$

What is the VC dimension of SVM with the polynomial kernel $k(x,x')=(1+<x,x'>_{\mathbb{R^{2}}})^{2}$ for binary classification in $\mathbb{R^{2}}$?

It would be equal or more than v iff there exists a set of v points such that, any labeling (-1 or +1) of the points given, there exists a correct separating border.

It would be strictly less than v iff for all sets of v points, there exists a labeling of the points such that there is no correct separating border.

In this case, the separating border is a conic section or a line, so any idea based on these curves rather than SVM is welcome.

For instance, let $x=(x_{1},x_{2}) \in \mathbb{R^{2}}$. It is mapped to $\mathbb{R^{6}}$ using a certain $\phi$ and an hyperplane in this new space is a conic section in the former space. So my guess would be the VC dimension of a linear classifier in $\mathbb{R^{6}}$, which is 7.


Actually, the answer is 6: the equation of an hyperplane in $\mathbb{R^{d}}$ is $$<w,x>_{\mathbb{R^{d}}}+b=0$$ where $w \in \mathbb{R^{d}}$ and $b \in \mathbb{R}$. Here, we have $b=1$ and $w \in \mathbb{R^{5}}$, not $\mathbb{R^{6}}$.

$\endgroup$

3 Answers 3

4
$\begingroup$

If I'm not mistaken:

$[1 + \langle x,y\rangle]^2$ = $\langle[1, \sqrt{2}y_1, y_1^2, \sqrt{2}y_2, y_2^2, \sqrt{2}y_1y_2], [1, \sqrt{2}x_1, x_1^2, \sqrt{2}x_2, x_2^2, \sqrt{2}x_1x_2]^T\rangle$

So the separating rule is linear in $R^6$. Consequently, VC-dim is 7.

$\endgroup$
2
  • $\begingroup$ @wok: oops, I haven't seen your last paragraph! $\endgroup$
    – bijey
    Nov 24, 2010 at 20:30
  • $\begingroup$ I was mistaken by the term 1. This is a linear separating rule in $\mathbb{R^{5}}$. :'( $\endgroup$
    – Wok
    Nov 30, 2010 at 22:11
1
$\begingroup$

The answer is 6. See the edits above for details.

$\endgroup$
1
  • $\begingroup$ How do you generalize this for $w\in \mathbb{R}^d$-dimensions? Is the VC dimension then $2(d+1)$? $\endgroup$ Nov 23, 2015 at 0:10
1
$\begingroup$

The VC dimension is the equal to the enumerative combinatorics of the number of monomials for a polynomial of degree $k$ and $n$ variables, thus $\binom{n+k}{k}$. Here we have $k=2$ and $n=2$ thus the VC dimension is $\binom{4}{2}=6$.

$\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.