Polynomial-Time Learning with Version Spaces

Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Learning: Inductive

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.