Twierdzenie o braku obiadu i zgodność K-NN

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 \to \infty and k / n \to 0 then for every ϵ > 0, there's N, s.t. for all n > N : P (R_{n} - R^{*} > ϵ) < 2 e x p (- C_{d} n ϵ^{2})

$\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})$

R^{*}

$R^*$ jest błędem reguły optymalnej

R_{n}

$R_n$ ,

jest prawdziwym błędem wyjścia K-NN (prawdopodobieństwo przekracza zbiór treningowy wielkości

n

$n$ ),

μ

$\mu$ jest miarą prawdopodobieństwa w przestrzeni instancji

R^{d}

$\mathbb{R}^d$ i

C_{d}

$C_d$ 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!

k-nearest-neighbour consistency Michał J
źródło

Odpowiedzi:

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

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