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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @wok: oops, I haven't seen your last paragraph! $\endgroup$ – bijey Nov 24 '10 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 '10 at 22:11
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do you generalize this for $w\in \mathbb{R}^d$-dimensions? Is the VC dimension then $2(d+1)$? $\endgroup$ – user2205916 Nov 23 '15 at 0:10
0
$\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$.

| cite | improve this answer | |
$\endgroup$

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.