Learning Boolean Functions in an Infinite Attribute SpaceLearning Boolean Functions in an Infinite Attribute SpaceBlum, Avrim1992

Paper summarycdmurray80This paper develops algorithms and mistake bounds for learning non-noisy boolean functions. It considers the case when there is a very large number of possible attributes, but each example (and the concept) depends on only a few attributes, so we want ot avoid having to ever explicitly list or consider all possible attributes. The concept classes it deals with learning are boolean formulas. The paper is a good cite but (for my work) probably not directly applicable.

This paper develops algorithms and mistake bounds for learning non-noisy boolean functions. It considers the case when there is a very large number of possible attributes, but each example (and the concept) depends on only a few attributes, so we want ot avoid having to ever explicitly list or consider all possible attributes. The concept classes it deals with learning are boolean formulas. The paper is a good cite but (for my work) probably not directly applicable.