Czy KNN jest dyskryminującym algorytmem uczenia się?

17

Wygląda na to, że KNN jest algorytmem uczenia się dyskryminującego, ale nie mogę znaleźć żadnych źródeł online potwierdzających to.

machine-learning classification k-nearest-neighbour

— jpmuc
źródło

19

KNN jest algorytmem dyskryminującym, ponieważ modeluje warunkowe prawdopodobieństwo próby należącej do danej klasy. Aby to zobaczyć, zastanów się, jak przejść do reguły decyzyjnej kNN.

Etykieta klasa odpowiada zbiór punktów, które należą do pewnego obszaru w przestrzeni cech . Jeśli losujesz punkty próbne z rzeczywistego rozkładu prawdopodobieństwa niezależnie, wówczas prawdopodobieństwo wyciągnięcia próbki z tej klasy wynosi $R$ $p(x)$

P. = \int_{R} p (x) re x

$P = \int_{R} p(x) dx$

Co jeśli masz punktów? Prawdopodobieństwo, że punktów tych punktów przypada w obszarze zgodne z rozkładem dwumianowym, $N$ $K$ $N$ $R$

P. r o b (K.) = (\binom{N.}{K.}) {P.}^{K.} (1 - P.)^{N. - K.}

$Prob(K) = {{N} \choose {K}}P^{K}(1-P)^{N-K}$

Ponieważ ten rozkład jest ostro pikowany, więc prawdopodobieństwo można przybliżać za pomocą jego średniej wartości $N \to \infty$ . Dodatkowym przybliżeniem jest to, że rozkład prawdopodobieństwa dlapozostaje w przybliżeniu stały, tak że można przybliżać całkę o, gdziejest całkowitą objętością regionu. Poniżej tych przybliżeń $\frac{K}{N}$ $R$

P. = \int_{R} p (x) re x \approx p (x) V.

$P = \int_{R} p(x) dx \approx p(x)V$

V

$V$

.

p (x) \approx \frac{K}{N V}

$p(x) \approx \frac{K}{NV}$

Gdybyśmy mieli kilka klas, moglibyśmy powtórzyć tę samą analizę dla każdej z nich, co dałoby nam gdziejest liczbą punktów z klasyktóra mieści się w tym regionie, ajest całkowitą liczbą punktów należących do klasy. Wskazówki.

p (x | {do}_{k}) = \frac{{K.}_{k}}{{N.}_{k} V.}

$p(x|C_{k}) = \frac{K_{k}}{N_{k}V}$

K_{k}

$K_{k}$

k

$k$

N_{k}

$N_{k}$

C_{k}

$C_k$

\sum_{k} N_{k} = N

$\sum_{k}N_{k}=N$

Powtarzając analizę z rozkładem dwumianowym, łatwo zauważyć, że możemy oszacować wcześniejsze . $P(C_{k}) = \frac{N_{k}}{N}$

P. ({do}_{k} | x) = \frac{p (x | {do}_{k}) p ({do}_{k})}{p (x)} = \frac{{K.}_{k}}{K.}

$P(C_{k}|x) = \frac{p(x|C_{k})p(C_{k})}{p(x)} = \frac{K_{k}}{K}$

— jpmuc
źródło

2

Odniesienie nie zawiera żadnych informacji na temat KNN. Czy to jest właściwe?

— bayerj

1

Miałem na myśli podkreślenie tego, co rozumie się w przypadku algorytmu dyskryminującego w porównaniu z generatywnym.

— jpmuc

5

Odpowiedź @jpmuc wydaje się nieprawdziwa. Modele generatywne modelują rozkład podstawowy P (x / Ci), a następnie wykorzystują twierdzenie Bayesa do znalezienia prawdopodobieństw późniejszych. To jest dokładnie to, co zostało pokazane w tej odpowiedzi, a następnie konkluduje dokładnie odwrotnie. : O

Aby KNN był modelem generatywnym, powinniśmy mieć możliwość generowania danych syntetycznych. Wydaje się, że jest to możliwe, gdy będziemy mieli pewne dane dotyczące szkolenia początkowego. Ale rozpoczęcie od braku danych treningowych i wygenerowanie danych syntetycznych nie jest możliwe. Dlatego KNN nie pasuje dobrze do modeli generatywnych.

Można argumentować, że KNN jest modelem dyskryminującym, ponieważ możemy narysować granicę dyskryminacyjną dla klasyfikacji lub obliczyć tylną P (Ci / x). Ale wszystko to jest prawdą również w przypadku modeli generatywnych. Prawdziwy model dyskryminujący nie mówi nic o podstawowej dystrybucji. Ale w przypadku KNN wiemy dużo o podstawowej dystrybucji, w rzeczywistości przechowujemy cały zestaw treningowy.

Wygląda więc na to, że KNN znajduje się w połowie drogi między modelami generatywnymi a dyskryminacyjnymi. Prawdopodobnie dlatego KNN nie jest zaliczany do żadnego z generatywnych lub dyskryminujących modeli w renomowanych artykułach. Nazwijmy je modelami nieparametrycznymi.

— Binu Jasim
źródło

Nie zgadzam się. „Klasyfikatory generacyjne uczą się modelu prawdopodobieństwa połączenia, p (x, y), danych wejściowych x i etykiety y, i dokonują ich prognoz, stosując reguły Bayesa do obliczenia p (ylx), a następnie wybierając najbardziej prawdopodobną etykietę y Klasyfikatory dyskryminujące modelują bezpośrednio tylny p (ylx) lub uczą się bezpośredniej mapy z danych wejściowych x do etykiet klas ". Zobacz „O klasyfikatorach dyskryminujących vs. generatywnych: porównanie regresji logistycznej i naiwnych

— Bayesów

3

Natknąłem się na książkę, która mówi coś przeciwnego ( tj. Generatywny nieparametryczny model klasyfikacji)

Oto link online: Machine Learning A Probabilistic Perspective autorstwa Murphy, Kevin P. (2012)

Oto fragment książki:

— Gürol Canbek
źródło

To musi być pomyłka ..

1

Zgadzam się, że kNN jest dyskryminujący. Powodem jest to, że nie przechowuje jawnie lub próbuje nauczyć się (probabilistycznego) modelu, który wyjaśnia dane (w przeciwieństwie do np. Naive Bayes).

Odpowiedź autorstwa juampa myli mnie, ponieważ według mnie klasyfikator generatywny to taki, który próbuje wyjaśnić, w jaki sposób generowane są dane (np. Przy użyciu modelu), a ta odpowiedź mówi, że z tego powodu jest dyskryminujący ...

— Amir
źródło

1

Model generatywny uczy się P (Ck, X), dzięki czemu można wygenerować więcej danych przy użyciu tego wspólnego rozkładu. Natomiast model dyskryminujący nauczyłby się P (Ck | X). Właśnie na to wskazuje @juampa z KNN.

— Zhubarb

1

W czasie klasyfikacji zarówno generatywna, jak i dyskryminacyjna kończy się na wykorzystaniu prawdopodobieństw warunkowych do prognozowania. Jednak klasyfikatory generatywne uczą się wspólnego prawdopodobieństwa i zgodnie z regułą Bayesa oblicza warunek, podczas gdy w dyskryminacji klasyfikator albo oblicza bezpośrednio warunek, albo zapewnia przybliżenie tego tak dobrze, jak to możliwe.

— rapaio