Dimension VC des cellules Voronoi dans R ^ d?

Supposons que j'ai points dans . Ceux-ci induisent un diagramme de Voronoi. Si j'attribue à chacun des points une étiquette , ceux-ci induisent une fonction binaire sur . Question: quelle est la dimension VC de toutes ces fonctions binaires possibles induites par certains points et un étiquetage de ces points? $k$ $\mathbb{R}^d$ $k$ $\pm$ $\mathbb{R}^d$ $k$

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

Je vois qu'une limite de

est donnée dans le théorème 1 . Est-ce le plus connu?

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

$O(dk^2\log k)$

Aryeh

Réponses:

Veuillez consulter le théorème 21.5, section 21 du livre "Une théorie probabiliste de la reconnaissance des formes (1996)" de Devroye, Gyorfi et Lugosi. Je pense que la borne supérieure suivante est valide: VC . $\leq$ $k + (d+1)k^2\log k$

user2798850
la source

n

$n$

n

$n$