Dimensión VC de polinomios sobre semirremolques tropicales?

$\mathbf{BPP}$ $\mathbf{P}$ $\mathrm{poly}$ $(\max,+)$ $(\min,+)$

Deje ser un semired. Un patrón cero de una secuencia de polinomios en es un subconjunto para el que existen y tal que para todo , si y sólo si . Es decir, las gráficas de exactamente esos polinomios con deben alcanzar el punto . ("Patrón cero" porque la condición se puede reemplazar por ) Sea $R$ $(f_1,\ldots,f_m)$ $m$ $R[x_1,\ldots,x_n]$ $S\subseteq \{1,\ldots,m\}$ $x\in R^n$ $y\in R$ $i=1,\ldots,m$ $f_i(x)= y$ $i\in S$ $f_i$ $i\in S$ $(x,y)\in R^{n+1}$ $f_i(x)=y$ $f_i(x)-y=0$ $Z(m)$ = el número máximo posible de patrones cero de una secuencia de polinomios de grado como máximo . Por lo tanto, . La dimensión Vapnik-Chervonenkis de los polinomios de grado es . $m$ $d$ $0\leq Z(m)\leq 2^m$ $d$ $VC(n,d) := \max\{m\colon Z(m)=2^m\}$

Observación: por lo general, la dimensión VC se define para una familia ${\cal F}$ de conjuntos como la mayor cardinalidad $|S|$ de un conjunto $S$ de tal manera que $\{F\cap S\colon F\in{\cal F}\}=2^S$ . Para encajar en este marco, podemos asociar con cada par $(x,y)\in R^{n+1}$ el conjunto $F_{x,y}$ de todos los polinomios de $f$ grado $\leq d$ para los cuales mantiene. Entonces, la dimensión VC de la familia de todos estos conjuntos es exactamente . $f(x)=y$ ${\cal F}$ $F_{x,y}$ $VC(n,d)$

Un límite superior trivial en es (necesitamos al menos vectores distintos para tener los patrones posibles), pero es inútil en infinitas semirrelaciones. Para tener buenos límites superiores en la dimensión VC, necesitamos buenos límites superiores en . Sobre los campos , tales límites son conocidos. $m=VC(n,d)$ $m\leq n\log |R|$ $2^m$ $x\in R^n$ $2^m$ $Z(m)$

Teorema 1: sobre cualquier campo , tenemos $R$ . $Z(m)\leq \binom{md+n}{n}$

Milnor , Heintz y Warren probaron límites superiores similares ; Sus pruebas utilizan técnicas pesadas de geometría algebraica real. En contraste, una prueba de media página del Teorema 1 de Ronyai, Babai y Ganapathy (que damos a continuación) es una aplicación simple de álgebra lineal.

Al buscar pequeños 's satisfactorios $m$ , obtenemos que mantiene sobre cualquiercampo. En vista devs./, lo importante aquí es que la dimensión solo eslogarítmicaen el grado. Esto es importante porque los circuitos de tamaño polinómico pueden calcular polinomios de grado exponencial, y porque el resultado de Haussler en el aprendizaje PAC (Corolario 2 en la página 114 de $\binom{md+n}{n} < 2^m$ $VC(n,d)=O(n\log d)$ $\mathbf{BPP}$ $\mathbf{P}$ $\mathrm{poly}$ $d$ este artículo ) produce lo siguiente (donde suponemos que los circuitos deterministas pueden usar el voto mayoritario para emitir sus valores).

Teorema 2: se mantiene para los circuitos a través de cualquier semiring , donde sólo está polinomio en y . $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ $R$ $VC(n,d)$ $n$ $\log d$

Vea aquí cómo el resultado de Haussler implica el Teorema 2.

En particular, según el Teorema 1, mantiene sobre cualquier campo. (Lo interesante es aquí solo el caso de los campos infinitos : para los finitos, los argumentos mucho más simples funcionan: Chernoff encuadernado entonces funciona). Pero, ¿qué pasa con los semirrelaciones (infinitos) que no son campos, o incluso no son anillos? Motivado por la programación dinámica, me interesan principalmente los semirrelaciones tropicales y , pero también son interesantes otras semirrelaciones "no de campo" (infinitas). Tenga en cuenta que, sobre el $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ $(\max,+)$ $(\min,+)$ semiring, un polinomio con y , se convierte en el problema de maximización $(\max,+)$ $f(x)=\sum_{a\in A} c_a\prod_{i=1}^n x_i^{a_i}$ $A\subseteq\mathbb{N}$ $c_a\in \mathbb{R}$ ; el grado de es (como es habitual) el máximo de sobre toda . $f(x)=\max_{a\in A}\ \{c_a+a_1x_1+a_2x_2+\cdots+a_nx_n\}$ $f$ $a_1+\cdots+a_n$ $a\in A$

Pregunta: ¿Es la dimensión VC de los polinomios de grado sobre polinomios de semirremolques tropicales en ? $\leq d$ $n\log d$

Lo admito, esta puede ser una pregunta bastante difícil de esperar una respuesta rápida: el álgebra tropical es bastante "loco". Pero tal vez alguien tiene algunas ideas sobre por qué (si los hay) los polinomios tropicales podrían producir más patrones cero que los polinomios reales. ¿O por qué "no deberían"? O algunas referencias relacionadas.

¿O, tal vez, la prueba de Babai, Ronyai y Ganapathy (abajo) puede ser de alguna manera "retorcida" para trabajar en semirremolques tropicales? ¿O sobre cualquier otra semirenida infinita (que no son campos)?

Prueba del teorema 1: suponga que una secuencia tiene patrones de cero diferentes, y que sean testigos de estos patrones de cero. Sea un patrón cero atestiguado por el -ésimo vector , y considere los polinomios $(f_1,\ldots,f_m)$ $p$ $v_1,\ldots,v_p\in R^n$ $S_i=\{k\colon f_k(v_i)\neq 0\}$ $i$ $v_i$ . Afirmamos que estos polinomios son linealmente independientes sobre nuestro campo. Esta afirmación completa la prueba del teorema ya que cada tiene un grado como máximo , y la dimensión del espacio de polinomios de grado como máximo es $g_i:=\prod_{k\in S_i}f_k$ $g_i$ $D:=md$ $D$ . Para probar la afirmación, es suficiente tener en cuenta quesi y solo si. Supongamos, por el contrario, que existe una relación lineal no trivial . Seaun subíndice tal quees mínimo entre loscon $\binom{n+D}{D}$ $g_i(v_j)\neq 0$ $S_i\subseteq S_j$ $\lambda_1 g_i(x)+\cdots+\lambda_p g_p(x)=0$ $j$ $|S_j|$ $S_i$ . Sustituye en la relación. Mientras que , tenemos para todo , una contradicción. $\lambda_i\neq 0$ $v_j$ $\lambda_jg_j(v_j)\neq 0$ $\lambda_ig_i(v_j)=0$ $i\neq j$ $\Box$

co.combinatorics circuit-complexity algebraic-complexity arithmetic-circuits vc-dimension Stasys
fuente

Dimensión VC de polinomios sobre semirremolques tropicales?

Respuestas: