Description Identification and Retraction with Integrated Instance Concept-Based Boundary Sets

Evgueni N. Smirnov and Peter J. Braspenning

This paper presents incremental version space algorithms for description identification and retracting training data. The correctness of the algorithms is proven for the class of admissible description languages when version spaces to be learned are represented with integrated instance/concept-based boundary sets. It is shown that the exponential complexity of description identification and retracting data is avoided when generation of version spaces with respect to particular training descriptions is polynomial in the relevant properties of admissible languages.