Dimensão VC de polinômios (em uma variável) de grau d

Funções lineares em uma variável têm dimensão VC = 3 e eu lembro de ler em algum lugar que o VC para polinômios de grau é . $d$ $(d^2 + 3d + 2)/2$

Estou procurando idéias que possam provar a afirmação acima (e talvez generalize também para muitas variáveis, embora isso pareça esperar demais).

Qualquer abordagem, mesmo incompleta, será apreciada.

Para definir o problema corretamente: Dado um plano (coordenadas 2D, x e y), qual é o tamanho do conjunto máximo que pode ser quebrado se você puder usar funções de classificação polinomiais ( ) de grau no modo , e você pode escolher qual lado da curva deseja rotular positivo. $y=p(x)$ $d$

Por exemplo, rotule (x, y) como positivo se . $y > x^2 +5x +9$

cg.comp-geom vc-dimension Karan
fonte

Não trabalho na área, mas gostaria de entender a pergunta. Qual é o domínio e o alcance dessas funções? Você poderia explicar um pouco como as funções lineares em uma variável têm a dimensão 3 do VC?

22612 Robin Bottai

A declaração é melhor reformulada como: espaços de intervalo definidos por intervalos que podem ser expressos como desigualdades

f (x) \leq 0

$f(x) \le 0$ que f (x) é uma função linear têm a dimensão 3 de VC (isso ocorre porque esse espaço de intervalo é o espaço de intervalo de espaços meia em 2D)

Suresh Venkat

@ Suresh: Obrigado pelo esclarecimento. Da sua resposta que eu acho que a pergunta geral feita é qual a dimensão VC de espaços intervalo definido pelo grau-d (em vez de linear) funções

, onde

, em vez de

f (x) \leq 0

$f(x) \leq 0$

x \in R^{n}

$x \in \mathbb{R}^n$

R^{2}

$\mathbb{R}^2$

22612 Robin Kothari

Respostas:

O método básico funciona assim: Suponha que suas desigualdades sejam da forma

\sum_{i \leq d} a_{i} x^{i} \leq 0

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

Em seguida, você constrói um mapa de elevação para um espaço de maior dimensão, em que cada monômio corresponde a uma dimensão. Agora, o polinômio pode ser expresso como uma combinação linear das novas dimensões e você pode chamar o resultado usual para meios espaços no espaço resultante.

Não tenho certeza de onde você se identifica: a expressão correta para a dimensão VC de polinômios em d variáveis de grau D é , que é o número de monômios de grau no máximo D formado a partir de d variáveis. $\binom{d + D}{d}$

Suresh Venkat
fonte

Direita. Mas o OP não disse quantas variáveis havia.

Suresh Venkat

Minhas desigualdades envolvem y e um polinômio em x. Fiz algumas alterações no problema, esperando definir o problema com mais precisão.

22412 Karan

E acc. para o problema que afirmei, as quadráticas em x devem quebrar pelo menos 4 pontos (que eu posso ver) e acc. para a fórmula que dei, deve quebrar 6 pontos! (não sei se ele mantém embora)

Karan

A fórmula é um limite superior.

Suresh Venkat

No seu problema modificado, a resposta é D + 1

Suresh Venkat

O seguinte é baseado no livro de Discrepância Geométrica de Jiri Matousek .

Definir um espaço de intervalo em parametrizada por como se segue. Seja um polinômio grau em variáveis . Para cada , o conjunto é definido como $\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 exemplo, os círculos são definidos como . $(x_1 - a_1)^2 + (x_2 - a_2)^2 - 1 \leq 0$

Podemos vincular uma quantidade que é mais delicada que a dimensão VC neste modelo. Defina como o número máximo de conjuntos distintos induzidos por em qualquer conjunto de pontos, ou seja, onde o máximo é assumido define de pontos. Isto é o $\pi(m)$ $\{S(a)\}$ $m$

π (m) = max_{X \subseteq R^{d}} | {S (a) \cap X} |,

$\pi(m) = \max_{X \subseteq \mathbb{R}^d}{|\{S(a) \cap X\}|},$

X

$X$

m

$m$ função primária de quebra do espaço do intervalo

. Observe que a dimensão VC do espaço do intervalo é aquele máximo

tal que

. Além disso, se a dimensão VC de um espaço de intervalo for

, sua função de quebra será limitada por

{S (a)}

$\{S(a)\}$

m

$m$

π (m) = 2^{m}

$\pi(m) = 2^m$

k

$k$

O (m^{k})

$O(m^k)$

$m$ $f_1(a), \ldots, f_m(a)$ $\sigma = (\sigma_1, \ldots, \sigma_m) \in \{-, +\}^m$ $a$ $i$ $f_i(a)$ $\sigma_i$ $m$ $D$ $p$ $2^{O(p)}(Dm/p)^p$

$f_i(a) = f(x^i, a)$ $|\{S(a) \cap X\}|$ $f_1, \ldots, f_m$ $p$ $O(m^p)$

Sasho Nikolov
fonte