# Definition of weak and strong learners

1. What is the exact definition, or at least the main idea, of weak and strong learners? For instance, these terms are used in propositions such as "Boosting is based on weak learners".

2. Regarding the viewpoint that weak learners are of the type (high bias, low variance) and strong learners are (low bias,high variance). How are these terms defined without respect to specific datasets or data distributions?

For instance, is it possible to find specific datasets for which a so-called weak learner (low bias) is actually a strong learner (low variance)?

More simply, can the learning method X be a weak learner on data distribution A but a strong learner for data distribution B?

Intuitively, a weak learner is one that is somewhat better than random guessing, but not particularly good. More precisely, a weak learning algorithm is an algorithm to produce some classifier which has a high chance of being better than random guessing, depending on your training data.

There is a more formal definition given in [1]; one of the authors is Leslie Valiant, who developed the PAC learning framework. The definition given is cast in this framework – if you're unfamiliar, a good reference is chapter 2 of Mohri's Foundations of Machine Learning. If the formalism is difficult to follow, hopefully the more intuitive definition will help – in effect, the formal definition says the same thing, but in more precise terms.

It's easiest to think about binary classification. We can certainly produce a classifier that is correct with probability $$1/2$$, no matter what the distribution is: just always pick the more common class!

The idea of a weak learning algorithm is to ask for a bit more: can we find an algorithm $$\mathcal A$$ that will give us a classifier that has accuracy at least $$1/2 + \varepsilon$$ with high probability? Note that the classifier depends on the randomly drawn training data, so we must speak in terms of probabilities here. We might be unlucky and draw training data which makes it hard for the algorithm, for example.

I prefer the presentation of weak learning in [2], so I will paraphrase it here.

A weak learning algorithm $$\mathcal A$$ is an algorithm where there exist $$\varepsilon > 0$$, $$\delta \in (0, 1)$$ and $$N \in \mathbb{N}$$ such that given a randomly drawn training set $$\{(X_i, Y_i)\}_{i = 1}^N$$ from any distribution, the corresponding classifier $$h_{\mathcal A}$$ constructed by the algorithm satisfies $$\mathbb{P} \left [ h_\mathcal{A}(X) \neq Y\right ] \leq 1/2 - \varepsilon$$ with probability greater than $$1 - \delta$$ for randomly drawn $$(X, Y)$$ from the distribution.

In other words, for a weak learner as defined, given $$N$$ samples, the algorithm will perform strictly better than random guessing with probability at least $$1 - \delta$$ on any distribution. But, it might not be much better: $$\varepsilon$$ might be small, so we are only a little better than random guessing.

Every strong learner is also a weak learner under the formal definitions in [1] and [2], so indeed, if a strong learner exists, a weak learner could actually be a strong learner. It is certainly possible that an algorithm could produce a strong learner on one distribution while satisfying the weak learning algorithm property.

## References

[1] Michael Kearns and Leslie Valiant. 1994. Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM 41.1 (Jan. 1994), pp. 67–95.

[2] Leo Breiman. 1998. Arcing classifier (with discussion and a rejoinder by the author). Ann. Statist. 26.3, pp. 801–849. Open Access.