Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
Mohammed Nechba Mouhajir Mohamed Sedjari Yassine
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.