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 ) / 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.d
Misalnya, beri label (x, y) sebagai positif jika .
cg.comp-geom
vc-dimension
Karan
sumber
sumber
Jawaban:
Metode dasar bekerja seperti ini: Asumsikan ketidaksetaraan Anda berbentuk
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)
sumber
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 }Rd Sebuah1, ... , ahal f D d+ p a ∈ Rhal S( a ) S( a ) = { x ∈ Rd: f( x , a ) ≤ 0 } . Misalnya, lingkaran didefinisikan sebagai .( x1- a1)2+ ( x2- a2)2- 1 ≤ 0
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( a ) } m
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 σ im f1( a ) , ... , fm( a ) σ= ( σ1, ... , σm) ∈ { - , + }m Sebuah saya fsaya( a ) σ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 .m D hal 2O ( p )( D m / p )hal
sumber