Hypercuboid-Formation Behaviour of Two Learning Algorithms

Abstract

Bundy. Silver and Plummet (1985) provide an analysis of the Focussing algorithm and the Classification algorithm in the case where the description space consists of a set of relation trees. This paper discusses an extension to their analysis in which the description space is construed as a geometric space. Under this construal the behaviour of both the Focussing algorithm and the Classification algorithm is analysed in terms of the construction of hypercuboids. This analysis leads to a number of observations: (i) that a distinction can be made between a strong and a weak version of the disjunctive-concept problem; (ii) that certain solutions to the disjunctive-concept problem can be shown to exploit what are, in effect, distance functions over the description space and (iii). that the Classification algorithm is only capable of learning a subset of the possible disjunctive concepts in any given domain.