VC размерность клеток Вороного в R ^ d?

Предположим, у меня есть $k$ указывает на $\mathbb{R}^d$ , Они вызывают диаграмму Вороного. Если я назначу каждому из $k$ указывает $\pm$ метка, они вызывают двоичную функцию на $\mathbb{R}^d$ , Вопрос: какова VC-размерность всех таких возможных бинарных функций, вызванных некоторыми $k$ очки и некоторая маркировка этих точек?

cg.comp-geom machine-learning lg.learning convex-geometry high-dimensional-geometry Арье
источник

Я вижу, что граница

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

$O(dk^2\log k)$ дается в теореме 1 . Это самый известный?

Арье

Ответы:

Пожалуйста, проверьте теорему 21.5, раздел 21 в книге «Вероятностная теория распознавания образов (1996)» от Devroye, Gyorfi и Lugosi. Я думаю, что следующая верхняя граница действительна: VC $\leq$ $k + (d+1)k^2\log k$ ,

user2798850
источник

Что такое

n

$n$ Вот?

Сашо Николов

По модулю загадка

n

$n$ похоже, это тот же порядок величины, который я цитировал выше.

Арье