Dimensi VC sel Voronoi dalam R ^ d?

Misalkan saya memiliki poin dalam . Ini menginduksi diagram Voronoi. Jika saya menetapkan masing-masing menunjuk label , ini menginduksi fungsi biner pada . Pertanyaan: berapakah dimensi VC dari semua fungsi biner yang mungkin diinduksi oleh beberapa titik dan beberapa pelabelan titik-titik ini? $k$ $\mathbb{R}^d$ $k$ $\pm$ $\mathbb{R}^d$ $k$

cg.comp-geom machine-learning lg.learning convex-geometry high-dimensional-geometry Aryeh
sumber

Saya melihat bahwa batas

diberikan dalam Teorema 1 . Apakah itu yang paling dikenal?

O (d k^{2} \log k)

$O(dk^2\log k)$

Aryeh

Jawaban:

Silakan periksa Teorema 21.5, Bagian 21 dalam buku "A probabilistic Theory of Pattern Recognition (1996)" dari Devroye, Gyorfi, dan Lugosi. Saya pikir batas atas berikut ini valid: VC . $\leq$ $k + (d+1)k^2\log k$

pengguna2798850
sumber

n

$n$

n

$n$