Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
- URL: http://arxiv.org/abs/2308.10041v1
- Date: Sat, 19 Aug 2023 14:57:24 GMT
- Title: Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
- Authors: Mohammed Nechba, Mouhajir Mohamed, Sedjari Yassine
- Abstract summary: We develop 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- On the Computability of Multiclass PAC Learning [9.507869508188266]
In the recently introduced computable PAC (CPAC) learning framework, both learners and the functions they output are required to be computable.
We show that the corresponding computable dimensions for distinguishers characterize CPAC learning.
arXiv Detail & Related papers (2025-02-10T01:07:23Z) - On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
Many practical prediction algorithms represent inputs in Euclidean space and replace the discrete 0/1 classification loss with a real-trivial surrogate loss.
We develop a generalization of the Borsuk-Ulam Theorem that combines the classical topological approach with convexity considerations.
We also present natural classification tasks that can be represented in much smaller dimensions by leveraging randomness.
arXiv Detail & Related papers (2024-11-16T12:09:37Z) - Mathematical Algorithm Design for Deep Learning under Societal and
Judicial Constraints: The Algorithmic Transparency Requirement [65.26723285209853]
We derive a framework to analyze whether a transparent implementation in a computing model is feasible.
Based on previous results, we find that Blum-Shub-Smale Machines have the potential to establish trustworthy solvers for inverse problems.
arXiv Detail & Related papers (2024-01-18T15:32:38Z) - Human as Points: Explicit Point-based 3D Human Reconstruction from Single-view RGB Images [71.91424164693422]
We introduce an explicit point-based human reconstruction framework called HaP.
Our approach is featured by fully-explicit point cloud estimation, manipulation, generation, and refinement in the 3D geometric space.
Our results may indicate a paradigm rollback to the fully-explicit and geometry-centric algorithm design.
arXiv Detail & Related papers (2023-11-06T05:52:29Z) - A Geometric Notion of Causal Probing [91.14470073637236]
In a language model's representation space, all information about a concept such as verbal number is encoded in a linear subspace.
We give a set of intrinsic criteria which characterize an ideal linear concept subspace.
We find that LEACE returns a one-dimensional subspace containing roughly half of total concept information.
arXiv Detail & Related papers (2023-07-27T17:57:57Z) - Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
We aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting.
We first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable.
In the context of online learning we provide a dimension that characterizes the minimax optimal instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression.
arXiv Detail & Related papers (2023-07-07T21:39:25Z) - A Characterization of List Learnability [15.368858716555888]
We consider list PAC learning where the goal is to output a list of $k$ predictions.
Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.
arXiv Detail & Related papers (2022-11-07T21:28:05Z) - On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI)
Contrary to other CMI bounds, our loo-CMI bounds can be computed easily and can be interpreted in connection to other notions such as classical leave-one-out cross-validation.
We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning.
arXiv Detail & Related papers (2022-07-01T17:58:29Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation.
We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
arXiv Detail & Related papers (2022-06-01T23:26:51Z) - A Characterization of Multiclass Learnability [18.38631912121182]
We characterize multiclass PAC learnability through the DS dimension, a dimension defined by Daniely and Shalev-Shwartz 2014.
In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions.
Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability.
arXiv Detail & Related papers (2022-03-03T07:41:54Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.