Learnability and the Vapnik-Chervonenkis dimension

DOI10.1145/76359.76371zbMath0697.68079OpenAlexW2154952480WikidataQ56214749 ScholiaQ56214749MaRDI QIDQ3474905

David Haussler, Anselm Blumer, Andrzej Ehrenfeucht, Manfred K. Warmuth

Publication date: 1989

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/76359.76371

zbMATH Keywords

probabilistic algorithmsinductionPAC learningconcept learningVapnik-Chervonenkis dimensionOccam's razorsample complexityVapnik-Chervonenkis classeslearning from examplesgeometrical problems and computationslearnability theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10)

Related Items (only showing first 100 items - show all)

A linear lower bound on the unbounded error probabilistic communication complexity. ⋮ Learning from rounded-off data. ⋮ Advanced elementary formal systems. ⋮ Intrinsic complexity of learning geometrical concepts from positive data ⋮ A Sauer-Shelah-Perles lemma for sumsets ⋮ On data classification by iterative linear partitioning ⋮ Some connections between learning and optimization ⋮ Efficient algorithms for learning functions with bounded variation ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ Concentration inequalities for non-causal random fields ⋮ RotEqNet: rotation-equivariant network for fluid systems with symmetric high-order tensors ⋮ VC-saturated set systems ⋮ Can PAC learning algorithms tolerate random attribute noise? ⋮ On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations ⋮ New bounds on the minimal dispersion ⋮ Minimal dispersion of large volume boxes in the cube ⋮ Testing nonlinear operators ⋮ A counterexample concerning uniform ergodic theorems for a class of functions ⋮ Classification by polynomial surfaces ⋮ On specifying Boolean functions by labelled examples ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Large width nearest prototype classification on general distance spaces ⋮ Fusion methods for multiple sensor systems with unknown error densities ⋮ A generalization of Sauer's lemma ⋮ A new PAC bound for intersection-closed concept classes ⋮ VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states ⋮ Learning an intersection of a constant number of halfspaces over a uniform distribution ⋮ Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers ⋮ Inductive inference in the limit of empirically adequate theories ⋮ On fixed-parameter tractability and approximability of NP optimization problems ⋮ Almost optimal set covers in finite VC-dimension ⋮ The VC-dimension of set systems defined by graphs ⋮ A sufficient condition for polynomial distribution-dependent learnability ⋮ Improved upper bounds for probabilities of uniform deviations ⋮ On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions ⋮ An approach to guided learning of Boolean functions ⋮ Approximation and learning of convex superpositions ⋮ Learning distributions by their density levels: A paradigm for learning without a teacher ⋮ Learning recursive functions from approximations ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ On the complexity of learning from drifting distributions ⋮ The bounded injury priority method and the learnability of unions of rectangles ⋮ Classification based on prototypes with spheres of influence ⋮ A theory of formal synthesis via inductive learning ⋮ On the value of partial information for learning from examples ⋮ Efficient learning with virtual threshold gates ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ Approximate testing and its relationship to learning ⋮ A framework for incremental learning of logic programs ⋮ PAC-learning from general examples ⋮ PAC learning of concept classes through the boundaries of their items ⋮ Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location ⋮ Permissive planning: Extending classical planning to uncertain task domains. ⋮ On the difficulty of approximately maximizing agreements. ⋮ An improved lower bound on query complexity for quantum PAC learning ⋮ Learning figures with the Hausdorff metric by fractals -- towards computable binary classification ⋮ Learning under \(p\)-tampering poisoning attacks ⋮ Bounds on the minimax rate for estimating a prior over a VC class from independent learning tasks ⋮ On the dispersion of sparse grids ⋮ A Sauer-Shelah-Perles lemma for lattices ⋮ The true sample complexity of active learning ⋮ Accuracy of techniques for the logical analysis of data ⋮ The monotone theory for the PAC-model. ⋮ Queries revisited. ⋮ On learning multicategory classification with sample queries. ⋮ On weak \(\epsilon\)-nets and the Radon number ⋮ Learning privately with labeled and unlabeled examples ⋮ The minimal \(k\)-dispersion of point sets in high dimensions ⋮ \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration ⋮ Large-width bounds for learning half-spaces on distance spaces ⋮ Optimization approaches to supervised classification ⋮ Meta-interpretive learning: application to grammatical inference ⋮ Bounds on the sample complexity for private learning and private data release ⋮ PAC-learning in the presence of one-sided classification~noise ⋮ (Machine) learning parameter regions ⋮ Testing piecewise functions ⋮ The complexity of exact learning of acyclic conditional preference networks from swap examples ⋮ The power of random counterexamples ⋮ The learnability of unions of two rectangles in the two-dimensional discretized space ⋮ Practical issues in temporal difference learning ⋮ New applications of random sampling in computational geometry ⋮ Learning decision trees from random examples ⋮ A general lower bound on the number of examples needed for learning ⋮ An average-case optimal one-variable pattern language learner ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ Convexity and logical analysis of data ⋮ Mean estimation and regression under heavy-tailed distributions: A survey ⋮ The Vapnik-Chervonenkis dimension of a random graph ⋮ Exact VC-dimension of Boolean monomials ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ On computing the diameter of a point set in high dimensional Euclidean space. ⋮ PAC learning with nasty noise. ⋮ On the complexity of learning for spiking neurons with temporal coding. ⋮ Improved lower bounds for learning from noisy examples: An information-theoretic approach ⋮ Learning fixed-dimension linear thresholds from fragmented data ⋮ Quantum learning of concentrated Boolean functions ⋮ Statistical active learning algorithms for noise tolerance and differential privacy ⋮ Transfer theorems via sign conditions ⋮ A new abstract combinatorial dimension for exact learning via queries ⋮ The complexity of theory revision

This page was built for publication: Learnability and the Vapnik-Chervonenkis dimension