The Vapnik-Chervonenkis dimension of cubes in $\mathbb{R}^d$
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$.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningSimilar Papers 제목 키워드 기반
On the Vapnik-Chervonenkis dimension of products of intervals in $\mathbb{R}^d$
We study combinatorial complexity of certain classes of products of intervals in $\mathbb{R}^d$, from the point of view of Vapnik-Chervonenkis geometry. As a consequence of the obtained results, we conclude that the Vapn…
The No-Clash Teaching Dimension is Bounded by VC Dimension
In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching. How…
2 Notes on Classes with Vapnik-Chervonenkis Dimension 1
The Vapnik-Chervonenkis dimension is a combinatorial parameter that reflects the "complexity" of a set of sets (a.k.a. concept classes). It has been introduced by Vapnik and Chervonenkis in their seminal 1971 paper and h…
BIG-bench Machine LearningLearning TheoryUse Of Vapnik-Chervonenkis Dimension in Model Selection
In this dissertation, I derive a new method to estimate the Vapnik-Chervonenkis Dimension (VCD) for the class of linear functions. This method is inspired by the technique developed by Vapnik et al. Vapnik et al. (1994).…
modelModel SelectionAn Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory
In this paper, the problem of one-bit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning. It is shown that the Vapnik-Chervonenkis (VC-) dimension of the set of half-spa…
2kcompressed sensingLearning TheoryPAC learning