Twierdzenie o braku obiadu i zgodność K-NN

10

W uczeniu obliczeniowym twierdzenie NFL stwierdza, że ​​nie ma uniwersalnego ucznia. Dla każdego algorytmu uczenia się istnieje rozkład, który powoduje, że uczeń wysyła hipotezę z dużym błędem, z dużym prawdopodobieństwem (choć istnieje hipoteza o niskim błędzie). Wniosek jest taki, że aby się uczyć, klasa hipotez lub dystrybucje muszą być ograniczone. W swojej książce „Probabilistyczna teoria rozpoznawania wzorów” Devroye i wsp. Udowodnili następującą tezę dla ucznia z najbliższych sąsiadów: Gdzie

Assume μ has a density. if k and k/n0 then for every ϵ>0, there's N, s.t. for all n>N:P(RnR>ϵ)<2exp(Cdnϵ2)
Rjest błędem reguły optymalnej Rn , R_n jest prawdziwym błędem wyjścia K-NN (prawdopodobieństwo przekracza zbiór treningowy wielkości n ), μ jest miarą prawdopodobieństwa w przestrzeni instancji Rd i Cd to pewna stała zależna tylko od wymiaru euklidesowego. Dlatego możemy zbliżyć się do najlepszej hipotezy (nie najlepszej w niektórych ograniczonych klasach), nie przyjmując żadnych założeń dotyczących podziału. Więc staram się zrozumieć, w jaki sposób ten wynik nie jest sprzeczny z koncepcją NFL? dzięki!

Michał J
źródło

Odpowiedzi:

6

Rozumiem twierdzenie NFL, że nie ma algorytmu uczenia się, który byłby lepszy od pozostałych w każdym zadaniu. Nie jest to jednak twierdzenie w czystym matematycznym sensie, że ma dowód, a raczej obserwację empiryczną.

Podobnie do tego, co powiedziałeś dla kNN, istnieje również uniwersalne twierdzenie aproksymacyjne dla sieci neuronowych, które stwierdza, że ​​biorąc pod uwagę 2-warstwową sieć neuronową, możemy aproksymować dowolną funkcję dowolnym błędem.

Jak to nie przełamuje NFL? Zasadniczo stwierdza, że ​​można rozwiązać każdy możliwy problem za pomocą prostej 2-warstwowej NN. Powodem jest to, że chociaż teoretycznie NN mogą aproksymować wszystko, w praktyce bardzo trudno jest nauczyć ich przybliżania czegokolwiek. Dlatego w przypadku niektórych zadań preferowane są inne algorytmy.

Bardziej praktycznym sposobem interpretacji NFL jest:

Nie ma możliwości ustalenia a priori, który algorytm najlepiej wykona dla danego zadania.

CaucM
źródło
3
Dzięki za odpowiedź, ale są pewne nieścisłości. Po pierwsze, twierdzenie NFL ma dowód (na przykład shalev-shwartz & ben-david, rozumienie uczenia maszynowego, rozdział 5). Dla uniwersalnego twierdzenia aproksymacyjnego - to twierdzenie dotyczy ekspresyjności, podczas gdy twierdzenie NFL dotyczy uogólnienia.
Michael J