zbMATH — the first resource for mathematics

The strength of weak learnability. (English) Zbl 0747.68058
Computational learning theory, Proc. 2nd Annu. Workshop, Santa Cruz, CA/USA 1989, 383 (1989).
Summary: [For the entire collection see Zbl 0741.00077.]
The hypothesis boosting question is answered in the affirmative. The main result is a proof of the perhaps surprising equivalence of strong and weak learnability.
The proof is constructive, an explicit method is described for directly converting a weak learning algorithm into one that achieves arbitrary accuracy. The construction uses filtering to modify the distribution of examples and so forces the weak learning algorithm to focus on the harder to learn parts of distribution. Thus, the distribution-free nature of the learning model is fully exploited.

68T05 Learning and adaptive systems in artificial intelligence