Dimensión VC de SVM con núcleo polinómico en $\mathbb{R^{2}}$

Question

¿Cuál es la dimensión VC de SVM con el kernel polinómico $k(x,x')=(1+_{\mathbb{R^{2}}})^{2}$ para clasificación binaria en $\mathbb{R^{2}}$?

Sería igual o mayor que v si existe un conjunto de v puntos tal que, cualquier etiquetado (-1 o +1) de los puntos dados, existe un borde separador correcto.

Sería estrictamente menor que v si para todos los conjuntos de v puntos, existe un etiquetado de los puntos tal que no hay un borde separador correcto.

En este caso, el borde separador es una sección cónica o una línea, así que cualquier idea basada en estas curvas en lugar de SVM es bienvenida.

Por ejemplo, sea $x=(x_{1},x_{2}) \in \mathbb{R^{2}}$. Se mapea a $\mathbb{R^{6}}$ usando cierto $\phi$ y un hiperplano en este nuevo espacio es una sección cónica en el espacio anterior. Así que mi suposición sería la dimensión VC de un clasificador lineal en $\mathbb{R^{6}}$, que es 7.

---

De hecho, la respuesta es 6: la ecuación de un hiperplano en $\mathbb{R^{d}}$ es $$_{\mathbb{R^{d}}}+b=0$$ donde $w \in \mathbb{R^{d}}$ y $b \in \mathbb{R}$. Aquí, tenemos $b=1$ y $w \in \mathbb{R^{5}}$, no en $\mathbb{R^{6}}$.

Answer 1

Si no me equivoco:

$[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$

Por lo tanto, la regla de separación es lineal en $R^6$. En consecuencia, la dimensión de VC es 7.

Answer 2

La respuesta es 6. Consulta las ediciones anteriores para más detalles.

Answer 3

La dimensión VC es igual a la combinatoria enumerativa del número de monomios para un polinomio de grado $k$ y $n$ variables, por lo tanto $\binom{n+k}{k}$. Aquí tenemos $k=2$ y $n=2$ por lo tanto la dimensión VC es $\binom{4}{2}=6$.