Quantifying the Inductive Bias in Concept Learning

We show that the notion of bias in inductive concept learning can be quantified in a way that directly relates to learning performance, and that this quantitative theory of bias can provide guidance in the design of effective learning algorithms. We apply this idea by measuring some common language biases, including restriction to conjunctive concepts and conjunctive concepts with internal disjunction, and, uided by these measurements, develop learning algorithms P or these classes of concepts that have provably good convergence properties. Introduction The theme of this pa er is that the notion of bias in inductive concept learning Ip U86] [R86/ can be quantified in a way that enables us to rove meaningful convergence properties for learning algorit i ms. We measure bias with a combinatorial parameter defined on classes of concepts known as the Vapnik-Chervonenkis dimension (or simply d ensiorr) [VC71/, [P78j', JBEHW86/. The lower the dlmenslon of the class of concepts considered by the learning algorithm, the stronger the bias.