Title: Iterative versionspaces
Authors: Sablon, Gunther ×
De Raedt, Luc
Bruynooghe, Maurice #
Issue Date: Sep-1994
Publisher: Elsevier science bv
Series Title: Artificial intelligence vol:69 issue:1-2 pages:393-409
Abstract: An incremental depth-first algorithm for computing the S- and G-set of Mitchell's Candidate Elimination and Mellish's Description Identification algorithm is presented. As in Mellish's approach, lowerbounds (examples) as well as upperbounds can be handled. Instead of storing the complete S- and G-sets, only one element s is an element of S and g is an element of G is stored, together with backtrack information. The worst-case space complexity of our algorithm is linear in the number of lower- and upperbounds. For the Candidate Elimination algorithm this can be exponential. We introduce a test for membership of S and G with a number of coverage tests linear in the number of examples. Consequently the worst-case time complexity to compute S and G for each example is only a linear factor worse than the Candidate Elimination algorithm's.
ISSN: 0004-3702
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
94_IterativeVersionspaces.pdf Published 5450KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science