Dimensión VC de las células Voronoi en R ^ d?

Supongamos que tengo puntos en . Estos inducen un diagrama de Voronoi. Si asigno a cada uno de los puntos una etiqueta , estos inducen una función binaria en . Pregunta: ¿cuál es la dimensión VC de todas esas funciones binarias posibles inducidas por algunos puntos y algún etiquetado de estos puntos? $k$ $\mathbb{R}^d$ $k$ $\pm$ $\mathbb{R}^d$ $k$

cg.comp-geom machine-learning lg.learning convex-geometry high-dimensional-geometry Aria
fuente

Veo que un límite de

se da en el Teorema 1 . ¿Es eso el más conocido?

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

$O(dk^2\log k)$

Aryeh

Respuestas:

Consulte el Teorema 21.5, Sección 21 del libro "Una teoría probabilística del reconocimiento de patrones (1996)" de Devroye, Gyorfi y Lugosi. Creo que el siguiente límite superior es válido: VC . $\leq$ $k + (d+1)k^2\log k$

usuario2798850
fuente

¿Qué es

aquí?

n

$n$

Sasho Nikolov

Módulo el misterio

, este parece ser el mismo orden de magnitud que cité anteriormente.

n

$n$

Aryeh