Part of Advances in Neural Information Processing Systems 13 (NIPS 2000)
Shie Mannor, Ron Meir
The problem of constructing weak classifiers for boosting algo(cid:173) rithms is studied. We present an algorithm that produces a linear classifier that is guaranteed to achieve an error better than random guessing for any distribution on the data. While this weak learner is not useful for learning in general, we show that under reasonable conditions on the distribution it yields an effective weak learner for one-dimensional problems. Preliminary simulations suggest that similar behavior can be expected in higher dimensions, a result which is corroborated by some recent theoretical bounds. Addi(cid:173) tionally, we provide improved convergence rate bounds for the gen(cid:173) eralization error in situations where the empirical error can be made small, which is exactly the situation that occurs if weak learners with guaranteed performance that is better than random guessing can be established.