10
$\begingroup$

In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner output a hypotesis with a large error, with high probability (although there is a low error hypotesis). The conclusion is that in order to learn, the hypotesis class or the distributions must be restricted. In their book "A probabilistic theory of pattern recognition", Devroye et al prove the following theroem for the K-nearest neighbors learner: $$\text{Assume } \mu \text{ has a density. if } k\to \infty \text{ and } k/n\to0 \\ \text{ then for every } \epsilon>0, \text{ there's } N, \text{ s.t.} \text{ for all } n>N : \\ P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon ^{2}) $$ Where $R^*$ is the error of the bayes-optimal rule, $R_n$ is the true error of the K-NN output (the probability is over the training set of size $n$), $\mu$ is the probability measure on the instance space $\mathbb{R}^d$ and $C_d$ is some constant depends only on the euclidean dimension. Therefore, we can get as close as we want to the best hypothesis there is (not the best in some restricted class), without making any assumption on the ditribution. So I'm trying to understand how this result does not contradict the NFL theroem? thanks!

$\endgroup$
6
$\begingroup$

The way I understand the NFL theorem is that there is no learning algorithm that's better than the rest in every task. This isn't however a theorem in the clear mathematical sense that it has a proof, rather an empirical observation.

Similar to what you said for the kNN, there is also the Universal Approximation Theorem for Neural Networks, which states that given a 2-layer neural network, we can approximate any function with any arbitrary error.

Now, how does this not break the NFL? It basically states that you can solve any conceivable problem with a simple 2-layer NN. The reason is that while, theoretically NNs can approximate anything, in practice its very hard to teach them to approximate anything. That's why for some tasks, other algorithms are preferable.

A more practical way to interpret NFL is the following:

There is no way of determine a-priori which algorithm will do best for a given task.

$\endgroup$
  • 3
    $\begingroup$ Thanks for the answer, but there are some inaccuracies.. First, the NFL theorem has a proof (for example, shalev-shwartz & ben-david, understanding machine learning, chapter 5). For the Universal Approximation Theorem - this theorem deals with expresivness, while the NFL theorem deals with generaliztion. $\endgroup$ – michael J Aug 25 '19 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.