Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
We show that the notion of inductive bias in concept learning can be quantified in a way that directly relates to learning performance in the framework recently introduced by Valiant. Our measure of bias is based on the growth function introduced by Vapnik and Chervonenkis, and on the Vapnik-Chervonenkis dimension. We measure some common language biases, including restriction to conjunctive concepts, conjunctive concepts with internal disjunction, k-DNF and k-CNF concepts. We also measure certain types of bias that result from a preference for simpler hypotheses. Using these bias measurements we analyze the performance of the classical learning algorithm for conjunctive concepts from the perspective of Valiant's learning framework. We then augment this algorithm with a hypothesis simplification routine that uses a greedy heuristic and show how this improves learning performance on simpler target concepts. Improved learning algorithms are also developed for conjunctive concepts with internal disjunction, k-DNF and k-CNF concepts. We show that all our algorithms are within a logarithmic factor of optimal in terms of the number of examples they require to achieve a given level of leaning performance in the Valiant framework. Our results hold for arbitrary attribute-based instance spaces defined by either tree-structured or linear attributes.
- scientific article; zbMATH DE number 1448976
- Inductive Biases in Machine Learning for Robotics and Control
- A Survey of Bias in Machine Learning Through the Prism of Statistical Parity
- scientific article; zbMATH DE number 1351087
- scientific article; zbMATH DE number 1301801
- On data and algorithms: Understanding inductive performance
- scientific article; zbMATH DE number 615131
- Statistical learning from biased training samples
- -nets and simplex range queries
- A general lower bound on the number of examples needed for learning
- A Greedy Heuristic for the Set-Covering Problem
- A theory of the learnable
- An analytical comparison of some rule-learning programs
- Approximation algorithms for combinatorial problems
- Computational limitations on learning from examples
- Enumeration of Seven-Argument Threshold Functions
- Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1149430 (Why is no real title available?)
- Learnability and the Vapnik-Chervonenkis dimension
- Learning decision trees from random examples
- Learning structural shape descriptions from examples
- Modeling by shortest data description
- Occam's razor
- On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
- ON THE CONNECTION BETWEEN THE COMPLEXITY AND CREDIBILITY OF INFERRED MODELS
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Queries and concept learning
- Some special Vapnik-Chervonenkis classes
- Sharpening Occam's razor
- Parameterized learnability of juntas
- Partial Occam's Razor and its applications
- System design and evaluation using discrete event simulation with AI
- Embedding decision-analytic control in a learning architecture
- Principles of metareasoning
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Reasoning about model accuracy
- Bounding sample size with the Vapnik-Chervonenkis dimension
- Specification and simulation of statistical query algorithms for efficiency and noise tolerance
- Combinatorics and connectionism
- A result of Vapnik with applications
- Theory refinement combining analytical and empirical methods
- Iterative versionspaces
- The minimum feature set problem
- A sufficient condition for polynomial distribution-dependent learnability
- Solving the multiple instance problem with axis-parallel rectangles.
- A computational study on the performance of artificial neural networks under changing structural design and data distribution
- The complexity of theory revision
- Learning decision trees from random examples
- A general lower bound on the number of examples needed for learning
- Scaling, machine learning, and genetic neural nets
- A reduction algorithm meeting users' requirements.
- Autonomous theory building systems
- Shifting vocabulary bias in speedup learning
- An approach to guided learning of Boolean functions
- Learning the set covering machine by bound minimization and margin-sparsity trade-off
- Finite electro-elasticity with physics-augmented neural networks
- PALO: a probabilistic hill-climbing algorithm
- On the fusion of threshold classifiers for categorization and dimensionality reduction
- Noise modelling and evaluating learning from examples
- DNA sequencing and string learning
- Parameterized Learnability of k-Juntas and Related Problems
- The gap between abstract and concrete results in machine learning
- Precise induction from statistical data
- Learning nested concept classes with limited storage
- Constraint acquisition
- An alternative method of concept learning
- Inductive logic programming
- Computational sample complexity and attribute-efficient learning
- Robust logics
- Improved learning of \(k\)-parities
- Inductive constraint logic
- Advanced discretization techniques for hyperelastic physics-augmented neural networks
- Nonlinear electro-elastic finite element analysis with neural network constitutive models
- Statistical computational learning
- Hyperrelations in version space
- Prediction-preserving reducibility
- Version spaces and the consistency problem
- Learning decision trees with taxonomy of propositionalized attributes
This page was built for publication: Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106669)
