Learning Disjunctions of Features

Abstract

Littlestone's WINNOW algorithm for learning disjunctions of Boolean attributes where most attributes are irrelevant is one of the most fundamental results in learning theory. Because of the importance of WINNOW, it is natural to try extending WINNOW to learn disjunctions of features (i.e., concepts). In doing so, we may generalize some earlier applications of WINNow. In this paper, we extend WiNNow to learn k -disjunctions of indicator-feature pairs where each pair is a conjunction of a Boolean attribute and a feature (concept) from a certain type of feature (concept) class. (When all the Boolean attributes are always set to 1, then the concept class is the class of disjunctions of features.) Our algorithm inherits Winnow's . capability of discounting irrelevant attributes quickly. As an application of our algorithm, we generalize an earlier Winnow -based result of Maass and Warmuth on learning boxes to learn a concave lower halfspace in the discretized domain by approximating it using a union of special boxes. We believe that some of the other earlier Winnow -based results maybe extendable using our algorithm. Other applications include efficient learning of lower-dimensional boxes embedded in a much higher dimensional space and learning disjunctions of features where the attributes maybe from different domains and the features maybe from different feature classes.