VC-Dimension von Voronoi-Zellen in R ^ d?

Angenommen, ich habe Punkte in . Diese induzieren ein Voronoi-Diagramm. Wenn ich jedem der Punkte ein Label , induzieren diese eine Binärfunktion auf . Frage: Wie groß ist die VC-Dimension all dieser möglichen Binärfunktionen, die durch einige Punkte und eine gewisse Kennzeichnung dieser Punkte hervorgerufen werden? $k$ $\mathbb{R}^d$ $k$ $\pm$ $\mathbb{R}^d$ $k$

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

Ich sehe, dass in Satz 1 eine Grenze von

ist . Ist das das bekannteste?

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

$O(dk^2\log k)$

Aryeh

Antworten:

Bitte überprüfen Sie Satz 21.5, Abschnitt 21 im Buch "Eine probabilistische Theorie der Mustererkennung (1996)" von Devroye, Gyorfi und Lugosi. Ich denke, die folgende Obergrenze ist gültig: VC . $\leq$ $k + (d+1)k^2\log k$

user2798850
quelle

n

$n$

n

$n$