Delaying the Choice of Bias: A Disjunctive Version Space Approach

Abstract

This paper is concerned with alleviating the choice of learning biases via a two-step process: \\Gamma The set of all hypotheses that are consistent with the data and cover at least one training example, is given an implicit characterization of polynomial complexity. The only bias governing this induction phase is that of the language of hypotheses. \\Gamma Classification of further examples is done via interpreting this implicit theory; the interpretation mechanism allows one to relax the consistency requirement and tune the specificity of the theory at no extra induction cost. Experimental validations demonstrate very good results on both nominal and numerical datasets. 1 INTRODUCTION In a seminal paper, Mitchell (1980) introduced the term of bias to refer to any basis for choosing one generalization over another, other than strict consistency with the training instances. Learning biases proceed from at least two motivations: improve the predictive power of the induced theory (Mit...