Learning boolean functions in an infinite attribute space
Avrim L. Blum · 1990
This paper presents a model for learning Boolean functions in domains described by a potentially infinite number of attributes.The model allows an algorithm to employ a rich vocabulary with which to describe the objects it encounters in the world without necessarily incurring time and space penalties so long as each individual object is relatively simple.We show that many of the basic Boolean functions learnable in the standard models, such as conjunctions, disjunctions, K-CNF, and K-DNF, are still learnable in the new model, though by algorithms no longer quite so trivial as before.We feel that this new model better captures the way objects and their attributes relate and are presented to us in the real world.