Abstract
Learning from hints is a generalization of learning from examples that allows for a variety of information about the unknown function to be used in the learning process. In this paper, we use the VC dimension, an established tool for analyzing learning from examples, to analyze learning from hints. In particular, we show how the VC dimension is affected by the introduction of a hint. We also derive a new quantity that defines a VC dimension for the hint itself. This quantity is used to estimate the number of examples needed to "absorb" the hint. We carry out the analysis for two types of hints, invariances and catalysts. We also describe how the same method can be applied to other types of hints.
Keywords
Dimension (graph theory)GeneralizationVC dimensionVariety (cybernetics)Computer scienceFunction (biology)Carry (investment)Process (computing)Theoretical computer scienceMachine learningArtificial intelligenceMathematicsCombinatoricsProgramming language
Affiliated Institutions
Related Publications
A training algorithm for optimal margin classifiers
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented. The technique is applicable to a wide variety of the classif...
Distributed Learning, Communication Complexity and Privacy
We consider the problem of PAC-learning from distributed data and analyze fundamental communication complexity questions involved. We provide general upper and lower bounds on t...
Statistical Learning Theory
A comprehensive look at learning and generalization theory. The statistical theory of learning and generalization concerns the problem of choosing desired functions on the basis...
Inserting rules into recurrent neural networks
The authors present a method that incorporates a priori knowledge in the training of recurrent neural networks. This a priori knowledge can be interpreted as hints about the pro...
Structural risk minimization over data-dependent hierarchies
The paper introduces some generalizations of Vapnik's (1982) method of structural risk minimization (SRM). As well as making explicit some of the details on SRM, it provides a r...
Publication Info
- Year
- 1993
- Type
- article
- Volume
- 5
- Issue
- 2
- Pages
- 278-288
- Citations
- 81
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
81
OpenAlex
Cite This
Yaser S. Abu‐Mostafa
(1993).
Hints and the VC Dimension.
Neural Computation
, 5
(2)
, 278-288.
https://doi.org/10.1162/neco.1993.5.2.278
Identifiers
- DOI
- 10.1162/neco.1993.5.2.278