Polynomial-Time Learning with Version Spaces

Although version spaces provide a useful conceptual tool for inductive concept learning, they often face severe computational difficulties when implemented. For example, the G set of traditional boundary-set implementations of version spaces can have size exponential in the amount of data for even the most simple conjunctive description languages [Haussler, 1988]. This paper presents a new representation for version spaces that is more general than the traditional boundary-set representation, yet has worst-case time complexity that is polynomial in the amount of data when used for learning from attribute-value data with tree-structured feature hierarchies (which includes languages like Haussler’s). The central idea underlying this new representation is to maintain the traditional S boundary set as usual, but use a list N of negative data rather than keeping a G set as is typically done.

Authors

• Haym Hirsh Daniel Kudenko

Keywords

No keywords are indexed for this paper.