Description Identification and Retraction with Integrated Instance/Concept-Based Boundary Sets
Evgueni N. Smirnov, Peter J. Braspenning · 1999
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 (Smirnov and Braspenning 1998b). 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.