Combinations of weak predictors can be very effective.

From Boosting Algorithms: Regularization, Prediction and Model Fitting:

Kearns and Valiant [52] proved that if individual classifiers perform at least slightly better than guessing at random, their predictions can be combined and averaged, yielding much better predictions.

The reference is to Cryptographic limitations on learning Boolean formulae and finite automata.