NOISE TOLERANT LEARNING USING EARLY PREDICTORS
Generalization in most PAC learning analysis starts around O (d) examples, where d = V Cdim of the class. Nevertheless, analysis of learning curves using statistical mechanics shows much earlier generalization [7]. Here we introduce a gadget called Early Predictor, which exists if somewhat better than random prediction of the label of an arbitrary instance can be obtained from labels of O (log d) random examples. We were able to show that by taking a majority vote over a committee of Early Predictors, strong and efficient learning is obtained. Moreover, this learning procedure is robust to persistent classification noise. The margin analysis of the vote is used to explain this result. We also compare the suggested method to Bagging [11] and Boosting [5] and connect it to the SQ model [10]. A concrete example of Early Predictor is constructed for learning linear separators under uniform distribution. In this context we should mention the hardness result by Bartlett and