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 to output a hypotesis with a large error, with high probability. 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{ if } n>N \quad P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon ^{2}) $$ Where $R^*$ is the error of the bayes-optimal decision, and $R_n$ is the true error of the K-NN output (the probability is over the training set of size $n$). $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!


Your Answer

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

Browse other questions tagged or ask your own question.