Dimensi VC polinomial di atas semir tropis?

Seperti dalam hal ini pertanyaan, saya tertarik dengan $\mathbf{BPP}$ vs / masalah untuk tropis dan sirkuit. Pertanyaan ini mengurangi untuk menunjukkan batas atas untuk dimensi VC polinomial di atas semir tropis (lihat Teorema 2 di bawah). $\mathbf{P}$ $\mathrm{poly}$ $(\max,+)$ $(\min,+)$

Biarkan $R$ menjadi semiring. Pola nol urutan $(f_1,\ldots,f_m)$ dari $m$ polinomial dalam $R[x_1,\ldots,x_n]$ adalah himpunan bagian $S\subseteq \{1,\ldots,m\}$ untuk yang ada $x\in R^n$ dan $y\in R$ sehingga untuk semua $i=1,\ldots,m$ , $f_i(x)= y$ jika dan hanya jika $i\in S$ . Yaitu, grafik polinomial persis $f_i$ dengan $i\in S$ harus mencapai titik $(x,y)\in R^{n+1}$ . ("Pola-nol" karena kondisi $f_i(x)=y$ dapat digantikan oleh $f_i(x)-y=0$ ) Biarkan $Z(m)$ = jumlah maksimum pola nol dari urutan $m$ polinomial derajat paling banyak $d$ . Karenanya, $0\leq Z(m)\leq 2^m$ . The Vapnik-Chervonenkis dimensi derajat $d$ polinomial adalah $VC(n,d) := \max\{m\colon Z(m)=2^m\}$ .

Catatan: Biasanya, dimensi VC didefinisikan untuk keluarga ${\cal F}$ set sebagai kardinalitas terbesar $|S|$ dari set $S$ sehingga $\{F\cap S\colon F\in{\cal F}\}=2^S$ . Untuk masuk ke dalam bingkai ini, kita dapat mengasosiasikan dengan setiap pasangan $(x,y)\in R^{n+1}$ himpunan $F_{x,y}$ dari semua polinomial derajat yang mana memegang. Maka dimensi VC dari keluarga dari semua set persis . $f$ $\leq d$ $f(x)=y$ ${\cal F}$ $F_{x,y}$ $VC(n,d)$

Batas atas sepele pada $m=VC(n,d)$ adalah $m\leq n\log |R|$ (kita membutuhkan setidaknya $2^m$ vektor yang berbeda $x\in R^n$ untuk memiliki semua pola yang mungkin $2^m$ ), tetapi tidak berguna dalam semiring tak terbatas. Untuk memiliki batas atas yang baik pada dimensi VC, kita perlu batas atas yang baik pada $Z(m)$ . Di atas bidang , batas seperti itu diketahui.

Teorema 1: Di atas bidang apa pun $R$ , kami memiliki $Z(m)\leq \binom{md+n}{n}$ .

Batas atas yang serupa sebelumnya dibuktikan oleh Milnor , Heintz dan Warren ; bukti mereka menggunakan teknik-teknik berat dari geometri aljabar nyata. Sebaliknya, bukti setengah halaman dari Teorema 1 oleh Ronyai, Babai dan Ganapathy (yang kami berikan di bawah) adalah aplikasi sederhana dari aljabar linier.

Dengan mencari kecil $m$ 's memuaskan $\binom{md+n}{n} < 2^m$ , kita memperoleh bahwa $VC(n,d)=O(n\log d)$ memegang lebih dari setiap bidang . Mengingat $\mathbf{BPP}$ vs. $\mathbf{P}$ / $\mathrm{poly}$ , penting di sini adalah bahwa dimensi hanya logaritmik dalam derajat $d$ . Ini penting karena sirkuit dengan ukuran polinom dapat menghitung polinom dengan derajat eksponensial, dan karena hasil Haussler dalam pembelajaran PAC (Corollary 2 pada halaman 114 makalah ini ) menghasilkan yang berikut (di mana kami mengasumsikan bahwa sirkuit deterministik diizinkan untuk menggunakan suara mayoritas) untuk menampilkan nilai-nilai mereka).

Teorema 2: $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ berlaku untuk sirkuit di atas semiring $R$ , di mana $VC(n,d)$ hanya polinomial dalam $n$ dan $\log d$ .

Lihat di sini tentang bagaimana hasil Haussler mengimplikasikan Teorema 2.

Secara khusus, menurut Teorema 1, $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ berlaku di semua bidang. (Yang menarik di sini hanya kasus bidang tak terhingga : untuk bidang terbatas, argumen yang jauh lebih sederhana bekerja: Chernoff terikat kemudian bekerja.) Tetapi bagaimana dengan semir (tak terbatas) yang bukan bidang, atau bahkan tidak berdering? Termotivasi oleh pemrograman dinamis, saya terutama tertarik pada semir tropis $(\max,+)$ dan $(\min,+)$ , tetapi semir "non-lapangan" (tak terbatas) lainnya juga menarik. Perhatikan bahwa, pada semiring $(\max,+)$ , polinomial $f(x)=\sum_{a\in A} c_a\prod_{i=1}^n x_i^{a_i}$ dengan $A\subseteq\mathbb{N}$ dan $c_a\in \mathbb{R}$ , berubah menjadi masalah maksimalisasi $f(x)=\max_{a\in A}\ \{c_a+a_1x_1+a_2x_2+\cdots+a_nx_n\}$ ; derajat $f$ adalah (seperti adat) yang maksimal $a_1+\cdots+a_n$ atas semua $a\in A$ .

Pertanyaan: Apakah dimensi VC derajat polinomial $\leq d$ atas polinomial semiring tropis di $n\log d$ ?

Saya akui, ini bisa menjadi pertanyaan yang agak sulit untuk mengharapkan jawaban cepat: aljabar tropis agak "gila". Tetapi mungkin seseorang memiliki beberapa gagasan tentang mengapa (jika ada) polinomial tropis dapat menghasilkan lebih banyak pola nol daripada polinomial nyata? Atau mengapa mereka "tidak seharusnya"? Atau beberapa referensi terkait.

Atau, mungkin, bukti Babai, Ronyai, dan Ganapathy (di bawah) entah bagaimana bisa "diputarbalikkan" untuk bekerja di semir tropis? Atau lebih dari semiring tak terbatas lainnya (yang bukan bidang)?

Bukti Teorema 1: Asumsikan bahwa urutan memiliki pola nol yang berbeda, dan biarkan menjadi saksi dari pola nol ini. Mari menjadi-pola nol disaksikan oleh th vektor , dan mempertimbangkan polinomial . Kami mengklaim bahwa polinomial ini bebas linear terhadap bidang kami. Klaim ini melengkapi bukti teorema karena setiap memiliki derajat paling banyak , dan dimensi ruang polinomial derajat paling banyak adalah $(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$ $g_i:=\prod_{k\in S_i}f_k$ $g_i$ $D:=md$ $D$ $\binom{n+D}{D}$ . Untuk membuktikan klaim, cukup untuk mencatat bahwa jika dan hanya jika . Misalkan sebaliknya bahwa relasi linear nontrivial ada. Biarkan menjadi subskrip sehinggaminimal di antara dengan . Pengganti dalam hubungan tersebut. Sementara , kita memiliki untuk semua , sebuah kontradiksi. $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$ $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
sumber

Dimensi VC polinomial di atas semir tropis?

Jawaban: