Wymiar VC wielomianów nad tropikalnymi półksiężycami?

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

Niech będzie na pół wieku. Zerowej wzorzec sekwencji z wielomianów jest podzbiorem , dla których istnieją , a taki sposób, aby dla wszystkich , IFF . Oznacza to, że wykresy dokładnie tych wielomianów z muszą trafić w punkt $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}$ . („Wzór zerowy”, ponieważ warunek $f_i(x)=y$ można zastąpić $f_i(x)-y=0$ ). Niech $Z(m)$ = maksymalna możliwa liczba wzorów zerowych sekwencji $m$ wielomiany stopnia co najwyżej $d$ . Stąd $0\leq Z(m)\leq 2^m$ . Wymiar Vapnik-Chervonenkiswielomianów stopnia $d$ wynosi $VC(n,d) := \max\{m\colon Z(m)=2^m\}$ .

Uwaga: Zazwyczaj wymiar VC jest definiowany dla rodziny ${\cal F}$ zestawów jako największa liczność $|S|$ z szeregu $S$ w taki sposób, $\{F\cap S\colon F\in{\cal F}\}=2^S$ . Aby dopasować się do tej ramki, możemy skojarzyć z każdą parą $(x,y)\in R^{n+1}$ zbiór $F_{x,y}$ wszystkich wielomianów stopnia dla których $f$ $\leq d$ $f(x)=y$ trzyma. Zatem wymiar VC rodziny ${\cal F}$ wszystkich takich zbiorów $F_{x,y}$ jest dokładnie $VC(n,d)$ .

Trywialna górna granica na wynosi (potrzebujemy co najmniej różnych wektorów aby mieć wszystkie możliwych wzorów), ale jest to bezużyteczne w nieskończonych półporównaniach. Aby mieć dobre górne granice wymiaru VC, potrzebujemy dobrych górnych granic na . Ponad polami takie granice są znane. $m=VC(n,d)$ $m\leq n\log |R|$ $2^m$ $x\in R^n$ $2^m$ $Z(m)$

Twierdzenie 1: Na dowolnym polu mamy $R$ . $Z(m)\leq \binom{md+n}{n}$

Podobne górne granice wcześniej udowodnili Milnor , Heintz i Warren ; ich dowody wykorzystują ciężkie techniki z prawdziwej geometrii algebraicznej. Natomiast półstronicowy dowód twierdzenia 1 Ronyai, Babai i Ganapathy (który podajemy poniżej) jest prostym zastosowaniem algebry liniowej.

Szukając małych spełniających $m$ , otrzymujemy, że utrzymuje się na dowolnympolu. Biorąc pod uwagęvs./, ważne jest tutaj, że wymiar jestlogarytmicznytylkow stopniu. Jest to ważne, ponieważ obwody wielomianowe mogą obliczać wielomiany o wykładniczym stopniu oraz ponieważ wynik Hausslera w uczeniu się PAC (wniosek 2 na stronie 114 $\binom{md+n}{n} < 2^m$ $VC(n,d)=O(n\log d)$ $\mathbf{BPP}$ $\mathbf{P}$ $\mathrm{poly}$ $d$ ten artykuł ) daje następujące wyniki (przy założeniu, że obwody deterministyczne mogą wykorzystywać większość głosów do wyprowadzania swoich wartości).

Twierdzenie 2: dotyczy obwodów w dowolnym półprzewodniku , gdzie jest tylko wielomianem w i . $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ $R$ $VC(n,d)$ $n$ $\log d$

Zobacz tutaj, jak wynik Hausslera implikuje Twierdzenie 2.

W szczególności, zgodnie z twierdzeniem 1 posiada na dowolną dziedzinie. (Interesujące jest tutaj tylko pole nieskończone : w przypadku skończonych działają znacznie prostsze argumenty: Chernoff związany jest wtedy.) Ale co z (nieskończonymi) półpierścieniami, które nie są polami, a nawet nie dzwonią? Zmotywowani programowaniem dynamicznym, interesują mnie głównie tropikalne i semirings, ale interesujące są również inne semirings „non-field” (nieskończone). Pamiętaj, że ponad $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ $(\max,+)$ $(\min,+)$ semiring, wielomian z i , zamienia się w problem maksymalizacji $(\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}$ ; stopień jest (jak zwykle) maksimum na całej . $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$

Pytanie: Czy wymiar VC stopnia wielomianów stopnia wielomianów tropikalnych półwymiarów w ? $\leq d$ $n\log d$

Przyznaję, że odpowiedź na szybką odpowiedź może być trudna: algebra tropikalna jest raczej „szalona”. Ale może ktoś ma jakieś pomysły, dlaczego (jeśli w ogóle) tropikalne wielomiany mogą wytwarzać więcej zerowych wzorów niż prawdziwe wielomiany? Lub dlaczego „nie powinni”? Lub niektóre powiązane odniesienia.

A może dowód na to, że Babai, Ronyai i Ganapathy (poniżej) można w jakiś sposób „przekręcić” do pracy nad tropikalnymi półksiężycami? Lub nad jakimkolwiek innym nieskończonym półkolem (które nie są polami)?

Dowód twierdzenia 1: Załóżmy, że sekwencja ma różnych wzorów zerowych i niech będą świadkami tych wzorów zerowych. Niech będzie wzorem zerowym obserwowanym przez -ty wektor , i rozważmy wielomiany $(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$ . Twierdzimy, że te wielomiany są liniowo niezależne od naszego pola. Twierdzenie to uzupełnia dowód twierdzenia, ponieważ każdy ma stopień co najwyżej , a wymiar przestrzeni wielomianów stopnia co najwyżej wynosi $g_i:=\prod_{k\in S_i}f_k$ $g_i$ $D:=md$ $D$ . Aby udowodnić twierdzenie, wystarczy zauważyć, żewtedy i tylko wtedy, gdy. Załóżmy, że przeciwnie, istnieje nietrywialna zależność liniowa . Niechbędzie indeksem takim, żeminimalna wśródz $\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$ $\lambda_i\neq 0$ . Substitute $v_j$ in the relation. While $\lambda_jg_j(v_j)\neq 0$ , we have $\lambda_ig_i(v_j)=0$ for all $i\neq j$ , a contradiction. $\Box$

co.combinatorics circuit-complexity algebraic-complexity arithmetic-circuits vc-dimension Stasys
źródło

Wymiar VC wielomianów nad tropikalnymi półksiężycami?

Odpowiedzi: