Vapnik-Chervonenkis Dimension of Axis-Parallel Cuts

2012/03/01 by Servane Gey, Gey, Servane · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Face and Expression Recognition #Medical Image Segmentation Techniques #Morphological variations and asymmetry #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1203.0193

openalex publication_date 2012/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Vapnik-Chervonenkis (VC) dimension of the set of half-spaces of R^d with frontiers parallel to the axes is computed exactly. It is shown that it is much smaller than the intuitive value of d. A good approximation based on the Stirling's formula proves that it is more likely of the order log_2(d). This result may be used to evaluate the performance of classifiers or regressors based on dyadic partitioning of R^d for instance. Algorithms using axis-parallel cuts to partition R^d are often used to reduce the computational time of such estimators when d is large.

Cited by

• Stable coresets: Unleashing the power of uniform sampling

Related

• The Vapnik-Chervonenkis dimension of cubes in ℝ^d
• 2 Notes on Classes with Vapnik-Chervonenkis Dimension 1
• VC-Dimension and Distance Chains in \mathbbF_q^d
• Use Of Vapnik-Chervonenkis Dimension in Model Selection
• On the Vapnik-Chervonenkis dimension of products of intervals in ℝ^d