TDIS : An Algebraic Formalization

Abstract

In the light of the success of Top-Down Induction Systems (TDIS), the problems to be addressed concern the structure of descriptions and the exploration of strategies. This paper introduces a formal model to describe TDIS, based on the use of lattice theory and, more precisely, on the use of a Galois connection. One of the advantages of this formalization is that it justifies the extensive use of attribute-value representation in the case of classical TDIS and generalizes this representation to products of hierarchical posets. In addition, given that there are many different learning strategies for TDIS, this formal model shows the limitations of classical strategies and offers a general framework in which many other strategies can be expressed. 1- Introduction During the last decade, many top-down induction systems --- TDIS --- have been developed --- ID3 [Quinlan 83], ID5 [Utgoff 88], CN2 [Clark & Al. 89], etc. They have been compared with other learning techniques such as back pro...