Incremental Non-Backtracking Focusing: A Polynomially Bounded Generalization Algorithm for Version Spaces

The candidate elimination algorithm for inductive learning with version spaces can require both exponential time and space. This article describes the Incremental Non-Backtracking Focusing (INBF) algorithm which learns strictly tree-structured concepts in polynomial space and time. Specifically, it learns in time O(pnrC) and space 0( nk) where p is the number of positives, n the number of negatives, and k the number of features. INBF is an extension of an existing batch algorithm, Avoidance Focusing (AF). Although AF also learns in polynomial time, it assumes a convergent set of positive examples, and handles additional examples inefficiently; INBF has neither of these restrictions. Both the AF and INBF algorithms assume that the positive examples plus the near misses will be sufficient for convergence if the initial set of examples is convergent. This article formally proves that for treestructured concepts this assumption does in fact hold.

Authors

• Benjamin D. Smith Paul S. Rosenbloom

Keywords

No keywords are indexed for this paper.