The Vapnik-Chervonenkis dimension of cubes in ℝ^d

2014/12/20 by Despres, Christian J. J.
#03E05 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1412.6612

Abstract

The Vapnik-Chervonenkis (VC) dimension of a collection of subsets of a set is an important combinatorial concept in settings such as discrete geometry and machine learning. In this paper we prove that the VC dimension of the family of d-dimensional cubes in \mathbb R^d is \lfloor(3d+1)/2\rfloor.

Related

• On the Vapnik-Chervonenkis dimension of products of intervals in ℝ^d
• Vapnik-Chervonenkis Dimension of Axis-Parallel Cuts
• 2 Notes on Classes with Vapnik-Chervonenkis Dimension 1
• The VC-dimension of k-vertex d-polytopes
• On density of subgraphs of halved cubes