Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
In 1984, Valiant [ 7 ] introduced the Probably Approximately Correct (PAC) learning framework for boolean function classes. Blumer et al. [ 2] extended this model in 1989 by introducing the VC dimension as a tool to characterize the learnability of PAC. The VC dimension was based on the work of Vapnik and Chervonenkis in 1971 [8 ], who introduced a tool called the growth function to characterize the shattering property. Researchers have since determined the VC dimension for specific classes, and efforts have been made to develop an algorithm that can calculate the VC dimension for any concept class. In 1991, Linial, Mansour, and Rivest [4] presented an algorithm for computing the VC dimension in the discrete setting, assuming that both the concept class and domain set were finite. However, no attempts had been made to design an algorithm that could compute the VC dimension in the general setting.Therefore, our work focuses on developing a method to approximately compute the VC dimension without constraints on the concept classes or their domain set. Our approach is based on our finding that the Empirical Risk Minimization (ERM) learning paradigm can be used as a new tool to characterize the shattering property of a concept class.
Code (0)
등록된 구현이 없습니다.
Tasks
PAC learningSimilar Papers 제목 키워드 기반
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…
BIG-bench Machine LearningOn 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 Selection