On Boosting Sparse Parities

Abstract

While boosting has been extensively studied, considerablyless attention has been devoted to the task of designing good weaklearning algorithms. In this paper we consider the problem of designing weak learners thatare especially adept to the boosting procedure and specifically the AdaBoost algorithm. First we describe conditions desirable for a weak learning algorithm. We then propose using sparse parity functions as weak learners, which have many of our desired properties, as weak learners in boosting. Our experimental tests show the proposed weak learners tobe competitive with the most widely used ones: decisionstumps and pruned decision trees.