Tree-Structured Bias

Abstract

This paper reports on recent progress in the study of autonomous concept learning systems. In such systems, the initial space of hypotheses is considered as a first-order sentence, the declarative bias, and can thus be derived from background knowledge concerning the goal concept. It is easy to show that a simple derivation process generates a concept language corresponding to an unbiased version space defined on a restricted instance description language. However, the structure of a typical derivation corresponds to a stronger restriction still. It is shown that this semantically-motivated, tree-structured bias can in fact reduce the size of the concept language from doubly-exponential to singly-exponential in the number of features. This allows effective learning from a small number of examples.