Beim rechnerischen Lernen besagt das NFL-Theorem, dass es keinen universellen Lernenden gibt. Für jeden Lernalgorithmus gibt es eine Verteilung, die bewirkt, dass der Lernende mit hoher Wahrscheinlichkeit eine Hypotese mit einem großen Fehler ausgibt (obwohl es eine Hypotese mit geringem Fehler gibt). Die Schlussfolgerung ist, dass zum Lernen die Hypotese-Klasse oder die Verteilungen eingeschränkt werden müssen. In ihrem Buch "Eine probabilistische Theorie der Mustererkennung" beweisen Devroye et al. Den folgenden Satz für den Lernenden der K-nächsten Nachbarn:
Assume μ has a density. if k→∞ and k/n→0 then for every ϵ>0, there's N, s.t. for all n>N:P(Rn−R∗>ϵ)<2exp(−Cdnϵ2)
WobeiR∗ der Fehler der Bayes-optimalen Regel ist, ist Rn der wahre Fehler des K-NN-Ausgangs (der Die Wahrscheinlichkeit liegt über dem Trainingssatz der Größen ),μ ist das Wahrscheinlichkeitsmaß für den InstanzraumRd undCdDiese Konstante hängt nur von der euklidischen Dimension ab. Daher können wir der besten Hypothese, die es gibt, so nahe kommen, wie wir wollen (nicht die beste in einer eingeschränkten Klasse), ohne eine Annahme über die Verteilung zu treffen. Also versuche ich zu verstehen, wie dieses Ergebnis dem NFL-Theroem nicht widerspricht? Vielen Dank!