Author:

Keywords:

concept learning, versionspaces, example generation, search, Science & Technology, Technology, Computer Science, Artificial Intelligence, Computer Science, CONCEPT LEARNING, VERSIONSPACES, EXAMPLE GENERATION, SEARCH, 0801 Artificial Intelligence and Image Processing, 0802 Computation Theory and Mathematics, 1702 Cognitive Sciences, Artificial Intelligence & Image Processing, 4602 Artificial intelligence, 4603 Computer vision and multimedia computation, 4611 Machine learning

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.