Аннотация:
Известный результат Хаусслера говорит о том, что если подмножество $V$ куба $\{0, 1\}^n$ имеет размерность Вапника-Червоненкиса $d$, то число упаковки $V$ по метрике Хэмминга ограничено сверху $(сn/k)^d$, где $с$ – абсолютная константа, а $k$ – наименьшее Хэммингово расстояние между элементами максимальной упаковки. Эта верхняя оценка используется в теории эмпирических процессов, математической статистике и вычислительной геометрии. В докладе речь пойдет о простом доказательстве, возникающем как следствие минимаксного анализа классификаторов.
|
