Iterative versionspaces

摘要

An incremental depth-first algorithm for computing the S- and ς-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 ς-sets, only one element sϵS and 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 ς with a number of coverage tests linear in the number of examples. Consequently the worst-case time complexity to compute S and ς for each example is only a linear factor worse than the Candidate Elimination algorithm's.