Dimensi VC polinomial (dalam satu variabel) derajat d

8

Fungsi linear dalam satu variabel memiliki dimensi VC = 3 dan saya ingat pernah membaca bahwa VC untuk polinomial derajat adalah .( d 2 + 3 d + 2 ) / 2d(d2+3d+2)/2

Saya mencari ide yang dapat membuktikan klaim di atas (dan mungkin menggeneralisasi ke banyak variabel juga, meskipun itu tampaknya terlalu banyak harapan).

Setiap pendekatan, bahkan yang tidak lengkap, akan dihargai.

Untuk mendefinisikan masalah dengan benar: Diberikan bidang (koordinat 2D, x dan y) berapa ukuran set maksimum yang dapat dihancurkan jika Anda dapat menggunakan fungsi klasifikasi yang polinomial ( ) derajat pada mode , dan Anda bebas memilih sisi kurva mana yang ingin Anda beri label positif.dy=p(x)d

Misalnya, beri label (x, y) sebagai positif jika .y>x2+5x+9

Karan
sumber
1
Saya tidak bekerja di daerah itu, tetapi saya ingin memahami pertanyaannya. Apa domain dan rentang fungsi-fungsi ini? Bisakah Anda menjelaskan sedikit bagaimana fungsi linear dalam satu variabel memiliki VC dimensi 3?
Robin Kothari
2
Pernyataan lebih baik diulang sebagai: ruang rentang didefinisikan oleh rentang yang dapat dinyatakan sebagai ketidaksetaraan mana f (x) adalah fungsi linier memiliki VC dimensi 3 (ini karena ruang rentang ini adalah ruang rentang setengah spasi dalam 2D)f(x)0
Suresh Venkat
1
@ Suresh: Terima kasih atas klarifikasi. Dari jawaban Anda, saya kira pertanyaan umum yang diajukan adalah apa dimensi VC dari ruang rentang yang didefinisikan oleh fungsi derajat-d (bukan linier) mana x R n , bukan R 2 . f(x)0xRnR2
Robin Kothari

Jawaban:

8

Metode dasar bekerja seperti ini: Asumsikan ketidaksetaraan Anda berbentuk

sayadSebuahsayaxsaya0

Kemudian Anda membangun peta pengangkat ke ruang dimensi yang lebih tinggi di mana masing-masing monomial sesuai dengan satu dimensi. Sekarang polinomial dapat dinyatakan sebagai kombinasi linear dari dimensi baru dan Anda dapat meminta hasil yang biasa untuk setengah ruang di ruang yang dihasilkan.

Saya tidak yakin dari mana Anda mendapatkan ikatan: ekspresi yang benar untuk dimensi VC polinomial dalam variabel d derajat D adalah , yang merupakan jumlah monomial derajat paling banyak D dibentuk dari variabel d.(d+Dd)

Suresh Venkat
sumber
Baik. Tetapi OP tidak mengatakan berapa banyak variabel yang ada.
Suresh Venkat
Ketidaksetaraan saya melibatkan y dan polinomial dalam x. Saya telah membuat beberapa perubahan dalam masalah, berharap untuk mendefinisikan masalah dengan lebih tepat.
Karan
Dan mnrt. untuk masalah yang telah saya nyatakan, kuadrat di x harus menghancurkan setidaknya 4 poin (yang bisa saya lihat) dan mnrt. ke formula yang saya berikan, itu harus menghancurkan 6 poin! (tidak yakin apakah itu berlaku)
Karan
Rumusnya adalah batas atas.
Suresh Venkat
1
Dalam masalah Anda yang dimodifikasi, jawabannya adalah D + 1
Suresh Venkat
5

Berikut ini didasarkan pada buku Geometric Discrepancy Jiri Matousek .

Mendefinisikan ruang kisaran di parametrized oleh seorang 1 , ... , a p sebagai berikut. Biarkan f menjadi derajat D polinomial dalam variabel d + p . Untuk setiap satu R p , set S ( a ) didefinisikan sebagai S ( a ) = { x R d : f ( x , a ) 0 }Rda1,,apfDd+pSebuahRhalS(Sebuah)S(Sebuah)={xRd:f(x,Sebuah)0}. Misalnya, lingkaran didefinisikan sebagai .(x1-Sebuah1)2+(x2-Sebuah2)2-10

Kita bisa mendapatkan batasan pada kuantitas yang lebih halus daripada dimensi VC dalam model ini. Tentukan sebagai jumlah maksimum dari set berbeda yang diinduksi oleh { S ( a ) } pada setiap set poin m , yaitu π ( m ) = maks X R d | { S ( a ) X } | , Di mana max diambil alih set X dari m poin. Ini adalahπ(m){S(Sebuah)}m

π(m)=maksXRd|{S(Sebuah)X}|,
Xmfungsi penghancur primal dari ruang rentang . Perhatikan bahwa dimensi VC dari ruang jangkauan adalah maksimum m sedemikian rupa sehingga π ( m ) = 2 m . Juga, jika VC-dimensi ruang rentang k , maka fungsi pecah nya dibatasi oleh O ( m k ) .{S(Sebuah)}mπ(m)=2mkHAI(mk)

Untuk polinomial f 1 ( a ) , ... , f m ( a ) , σ = ( σ 1 , ... , σ m ) { - , + } m adalah pola tanda jika ada beberapa yang sehingga untuk semua i yang tanda f i ( a ) adalah σ imf1(Sebuah),...,fm(Sebuah)σ=(σ1,...,σm){-,+}mSebuahsayafsaya(Sebuah)σsaya. Hasil dari aljabar geometri adalah bahwa jumlah maksimum pola tanda yang berbeda dari gelar D polinomial di p variabel dibatasi oleh 2 O ( p ) ( D m / p ) p .mDhal2HAI(hal)(Dm/hal)hal

fsaya(Sebuah)=f(xsaya,Sebuah)|{S(Sebuah)X}|f1,...,fmhalHAI(mhal)

Sasho Nikolov
sumber