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

Tenth Midwest Artificial intelligence and Cognitive Science Conference

Volume

Tenth Midwest Artificial intelligence and Cognitive Science Conference

Contents

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.