Dimensión VC de polinomios (en una variable) de grado d

Las funciones lineales en una variable tienen dimensión VC = 3 y recuerdo haber leído en alguna parte que el VC para polinomios de grado es .$d$$(d^2 + 3d + 2)/2$

Estoy buscando ideas que puedan probar la afirmación anterior (y tal vez generalizar a muchas variables también, aunque eso parece demasiado esperar).

Cualquier enfoque, incluso uno incompleto, será apreciado.

Para definir el problema correctamente: Dado un plano (coordenadas 2D, x e y), ¿cuál es el tamaño del conjunto máximo que puede romperse si puede usar funciones de clasificación que son polinomiales ( ) de grado en el modo , y puede elegir qué lado de la curva desea etiquetar como positivo.$y=p(x)$$d$

Por ejemplo, etiquete (x, y) como positivo iff .$y > x^2 +5x +9$

El método básico funciona así: suponga que sus desigualdades son de la forma

$$\sum_{i \le d} a_i x^i \le 0$$

Luego construye un mapa de elevación a un espacio de dimensión superior en el que cada monomio corresponde a una dimensión. Ahora el polinomio se puede expresar como una combinación lineal de las nuevas dimensiones y puede invocar el resultado habitual para medios espacios en el espacio resultante.

No estoy seguro de dónde obtiene su límite: la expresión correcta para la dimensión VC de polinomios en d variables de grado D es , que es el número de monomios de grado como máximo D formado a partir de variables d.$\binom{d + D}{d}$

Lo siguiente está basado en el libro Discrepancia geométrica de Jiri Matousek .

Defina un espacio de rango en parametrizado por un 1 , ... , a p de la siguiente manera. Sea f un polinomio de grado D en las variables d + p . Para cada a ∈ R p , el conjunto S ( a ) se define como S ( a ) = { x ∈ R d : f ( x , a ) ≤ 0 $\mathbb{R}^d$$a_1, \ldots, a_p$$f$$D$$d + p$$a \in \mathbb{R}^p$$S(a)$$S(a) = \{x \in \mathbb{R}^d: f(x, a) \leq 0\}$. Por ejemplo, los círculos se definen como .$(x_1 - a_1)^2 + (x_2 - a_2)^2 - 1 \leq 0$

Podemos obtener un límite en una cantidad que es más delicada que la dimensión VC en este modelo. Defina como el número máximo de conjuntos distintos inducidos por { S ( a ) } en cualquier conjunto de puntos m , es decir, π ( m ) = max X ⊆ R d | { S ( a ) ∩ X } | , donde el máximo se toma sobre conjuntos X de m puntos. Este es el$\pi(m)$$\{S(a)\}$$m$

$$\pi(m) = \max_{X \subseteq \mathbb{R}^d}{|\{S(a) \cap X\}|},$$ $X$$m$función de fragmentación primaria del espacio de rango . Observe que la dimensión VC del espacio de rango es el máximo m tal que π ( m ) = 2 m . Además, si la dimensión VC de un espacio de rango es k , entonces su función de ruptura está limitada por O ( m k ) .$\{S(a)\}$$m$$\pi(m) = 2^m$$k$$O(m^k)$

Para polinomios f 1 ( a ) , ... , f m ( a ) , σ = ( σ 1 , ... , σ m ) ∈ { - , + } m es un patrón de signos si existe algún a tal que para todo i el signo de f i ( a ) es σ $m$$f_1(a), \ldots, f_m(a)$$\sigma = (\sigma_1, \ldots, \sigma_m) \in \{-, +\}^m$$a$$i$$f_i(a)$$\sigma_i$. Un resultado de la geometría algebraica es que el número máximo de patrones de signos distintos de polinomios de grado D en las variables p está limitado por 2 O ( p ) ( D m / p ) p .$m$$D$$p$$2^{O(p)}(Dm/p)^p$

Usemos este teorema. Defina . Lo conseguimos | { S ( a ) ∩ X } | es exactamente el número de patrones de signos distintos de f 1 , ... , f m . Entonces, en particular, si un espacio de rango está dado por una familia de polinomios de grado constante en p parámetros, su función de ruptura está limitada por O ( m p ) .$f_i(a) = f(x^i, a)$$|\{S(a) \cap X\}|$$f_1, \ldots, f_m$$p$$O(m^p)$