Dlaczego KNN nie jest „oparty na modelach”?

10

ESL rozdział 2.4 wydaje się klasyfikować regresję liniową jako „opartą na modelu”, ponieważ zakłada , podczas gdy nie podano podobnego przybliżenia dla najbliższych sąsiadów. Ale czy obie metody nie przyjmują założeń dotyczących ? $f(x) \approx x\cdot\beta$ $f(x)$

Później w 2.4 mówi nawet:

Najmniejsze kwadraty zakładają, że jest dobrze przybliżone przez globalnie liniową funkcję. $f(x)$

k-najbliżsi sąsiedzi zakładają, że jest dobrze aproksymowane lokalnie stałą funkcją. $f(x)$

Wydaje się, że założenie KNN można również sformalizować (choć nie jestem pewien, czy takie postępowanie doprowadziłoby do algorytmu KNN w sposób, w jaki założenie, że jest liniowe, prowadzi do regresji liniowej). $f$

Jeśli więc KNN nie jest oparty na modelach, dlaczego? A może źle czytam ESL?

machine-learning model k-nearest-neighbour

— Alec
źródło

8

Trudno jest bezpośrednio porównać kNN i regresję liniową, ponieważ są to bardzo różne rzeczy, jednak myślę, że kluczową kwestią jest tutaj różnica między „modelowaniem ” a „posiadaniem założeń dotyczących ”. $f(x)$ $f(x)$

Podczas regresji liniowej konkretnie modeluje się , często coś między liniami gdzie jest terminem szumu Gaussa. Można ustalić, że model maksymalnego prawdopodobieństwa jest równoważny modelowi błędu minimalnej sumy kwadratów. $f(x)$ $f(x) = \mathbf{wx} + \epsilon$ $\epsilon$

KNN, z drugiej strony, jak sugeruje twój drugi punkt, zakłada, że możesz aproksymować tę funkcję lokalnie stałą funkcją - pewną miarą odległości między -sesami, bez konkretnego modelowania całego rozkładu. $x$

Innymi słowy, regresja liniowa często ma dobry pomysł na wartość dla niektórych niewidzialnych z samej wartości , podczas gdy kNN potrzebuje innych informacji (tj. Sąsiadów k), aby przewidzieć , ponieważ wartość i sama wartość nie podadzą żadnych informacji, ponieważ nie ma modelu dla . $f(x)$ $x$ $x$ $f(x)$ $x$ $f(x)$

EDYCJA: powtórzenie tego poniżej, aby ponownie wyrazić to jaśniej (patrz komentarze)

Oczywiste jest, że zarówno regresja liniowa, jak i metody najbliższego sąsiedztwa mają na celu przewidzenie wartości dla nowego . Teraz są dwa podejścia. Regresja liniowa przebiega dalej, zakładając, że dane spadają na linię prostą (plus minus pewien szum), a zatem wartość y jest równa wartości razy nachylenie linii. Innymi słowy, wyrażenie liniowe modeluje dane jako linię prostą. $y=f(x)$ $x$ $f(x)$

Teraz metody najbliższego sąsiada nie dbają o to, jak wyglądają dane (nie modelują danych), tzn. Nie dbają o to, czy jest to linia, parabola, koło itp. Wszystko, co zakłada, to to, że i będą podobne, jeśli i są podobne. Zauważ, że to założenie jest w przybliżeniu prawdziwe dla niemal każdego modelu, włączając wszystkie te, o których wspomniałem powyżej. Jednak metoda NN nie może stwierdzić, w jaki sposób wartość jest powiązana z (czy jest to linia, parabola itp.), Ponieważ nie ma modelu tej zależności, po prostu zakłada, że można ją aproksymować przez patrząc na bliskie punkty. $f(x_1)$ $f(x_2)$ $x_1$ $x_2$ $f(x)$ $x$

— Saulius Lukauskas
źródło

„jeden konkretnie modeluje f (x)” Co to znaczy? Wydaje się, że można sformalizować założenie, że f jest lokalnie stałe. Czy to po prostu, że KNN nie może być wyprowadzony przez taką formalizację?

— Alec

„regresja liniowa często ma dobry pomysł na wartość f (x) dla niektórych niewidzialnych x z samej wartości x” nie jestem pewien, co przez to rozumiesz… nadal potrzebujesz parametrów modelu liniowego, po prostu ponieważ potrzebujesz parametrów dla KNN (choć jego parametry są bardziej zaangażowane)

— Alec

Dobre punkty, próbowałem zredagować swoją odpowiedź, aby była jaśniejsza i mam nadzieję, że odpowiedzą na twoje punkty (limit znaków na komentarze jest niski).

— Saulius Lukauskas

+1, to jest dobrze wyjaśnione. „różnica między„ modelowaniem f (x) ”a„ posiadaniem założeń dotyczących f (x) ”” bardzo dobrze oddaje ten pomysł, IMO. Być może innym sposobem przedstawienia tego jest wzięcie pod uwagę, że modelowanie f (x) sprowadza się do przyjęcia założeń dotyczących procesu generowania danych , podczas gdy knn tego nie robi, a jedynie pokazuje, że wartość danego punktu odniesienia może być podobna do wartości w pobliżu dane.

— gung - Przywróć Monikę

Hmm, okej. Twoja edycja z pewnością sprawia, że jest to trochę jaśniejsze, ale nadal mam problemy z dostrzeżeniem formalnego rozróżnienia. Wydaje się, że przez „modelowanie” masz na myśli „uzyskanie dobrego pomysłu na kształt litery f na całym świecie”, podczas gdy KNN dba tylko o zachowanie lokalne. Więc to ta różnica w globalnym vs lokalnym sprawia, że modelowanie regresji liniowej nie jest znane z KNN?

— Alec

5

Regresja liniowa jest oparta na modelu, ponieważ zakłada się strukturę danych w celu wygenerowania modelu. Podczas ładowania zestawu danych do programu statystycznego i użyć go do uruchomienia regresji liniowej wyjście jest w rzeczywistości model: . Możesz wprowadzić nowe dane do tego modelu i uzyskać prognozowane dane wyjściowe, ponieważ przyjęto założenia dotyczące sposobu generowania zmiennej wyjściowej. $\hat{f}(X)=\hat{\beta} X$

W KNN tak naprawdę nie ma modelu - istnieje tylko założenie, że obserwacje, które znajdują się blisko siebie w przestrzeni prawdopodobnie będą zachowywać się podobnie pod względem zmiennej wyjściowej. Nie wprowadzasz nowej obserwacji do „modelu KNN”, po prostu określasz, które istniejące obserwacje są najbardziej podobne do nowej obserwacji i przewidujesz zmienną wyjściową dla nowej obserwacji na podstawie danych treningowych. $X$

— tjnel
źródło

Chociaż intuicyjnie rozumiem, co masz na myśli, rozróżnienie wciąż jest dla mnie niepewne ... czy nie możesz postrzegać KNN jako sparametryzowanego przez partycję R ^ d i wagi przypisane do partycji?

— Alec

1

Jeśli ktoś poprosił cię o uzasadnienie twoich przewidywań, możesz to zrobić, jeśli zastosujesz regresję liniową, wyjaśniając związki między danymi wejściowymi i wyjściowymi zakładanymi przez model. Model próbuje wyjaśnić związek między wejściami i wyjściami czarno-białych. KNN nie próbuje wyjaśnić związku czarno-białych danych wejściowych i wyjściowych, dlatego nie ma modelu.

— tjnel

4

Termin „oparty na modelu” jest synonimem „oparty na dystrybucji” przy omawianiu metod grupowania. Regresja liniowa przyjmuje założenia dystrybucyjne (że błędy są gaussowskie). KNN nie przyjmuje żadnych założeń dystrybucyjnych. To jest rozróżnienie.

— DL Dahly
źródło

1

Jest to dla mnie jak dotąd najbardziej sensowne pod względem formalnego rozróżnienia, chociaż ESL tak naprawdę nie przedstawił regresji liniowej w ten sposób. Najpierw wprowadzili funkcję kosztu błędu kwadratu, niejako arbitralnie (zamiast zrobić MLE dla Gaussa), wykorzystali ją do stwierdzenia, że powinniśmy przewidzieć f (x) = E (Y | X = x), wyjaśnili, w jaki sposób przybliża KNN przy pewnych założeniach, a następnie założył, że f jest liniowy, aby uzyskać regresję liniową.

— Alec

Ciekawa propozycja, ale byłoby znacznie lepiej, gdybyśmy mieli jakieś referencje na ten temat.

— ivanmp

0

kNN jest oparty na instancji

Aby dokonać prognozy dla nowej obserwacji, musisz zachować cały zbiór danych szkoleniowych, ponieważ nie ma modelu o tym zestawie danych.

Tak działa kNN: biorąc pod uwagę nową obserwację, obliczymy odległość między tą nową obserwacją a wszystkimi innymi obserwacjami w zbiorze danych szkoleniowych. Następnie dostajesz sąsiadów (najbliższych nowej obserwacji).

Jeśli , to patrzymy na 5 najbliższych obserwacji. „lokalnie stała funkcja” oznacza, że po wybraniu tych 5 obserwacji nie dbamy o odległości. Są takie same, mają takie samo znaczenie dla prognozy. $k=5$

Jak znaleźć model?

Teraz, jeśli spróbujemy znaleźć funkcję, która nie jest „lokalnie stała”, byłby to rozkład normalny. W takim przypadku otrzymasz algorytm o nazwie Linear Discriminant Analysis lub Naive Bayes (w zależności od innych założeń).

— Xiaoshi
źródło