Kernelised k Nearest Neighbor

Jestem nowy w jądrach i wpadłem w kłopoty podczas próby jądra kNN.

Czynności wstępne

Używam wielomianowego jądra:
$K(\mathbf{x},\mathbf{y}) = (1 + \langle \mathbf{x},\mathbf{y} \rangle)^d$

Twój typowy euklidesowy kNN używa następującej miary odległości:
$d(\mathbf{x}, \mathbf{y}) = \vert\vert \mathbf{x} - \mathbf{y} \vert\vert$

Niech $f(\mathbf{x})$ mapa $\mathbf{x}$ do jakiejś wyższej wymiarowej przestrzeni cech. Następnie kwadrat powyższej metryki odległości w przestrzeni Hilberta można wyrazić przez iloczyn wewnętrzny: $d^2(f(x), f(y)) = K(\mathbf{x},\mathbf{x}) - 2K(\mathbf{x}, \mathbf{y}) + K(\mathbf{y} ,\mathbf{y})$

Zauważ, że jeśli pozwolimy $d = 1$ powyższe zdegeneruje się do standardowej odległości euklidesowej.

Pytanie

Główny problem, jaki mam, polega na tym, że nie widzę, w jaki sposób jądro kNN daje lepsze wyniki, co pokazano eksperymentalnie np. W tym dokumencie (ostrzeżenie, bezpośredni link pdf!).

Twierdzenie Covera : Z grubsza powiedziane, mówi, że biorąc pod uwagę dowolny losowy zestaw punktów skończonych (z dowolnymi etykietami), to z dużym prawdopodobieństwem punkty te można uczynić liniowo oddzielnymi [1] poprzez odwzorowanie ich na wyższy wymiar [2].

Znaczenie: Świetnie, to twierdzenie mówi mi, że jeśli wezmę mój zestaw danych i zmapuję te punkty do wyższego wymiaru, wtedy mogę łatwo znaleźć liniowy klasyfikator. Jednak większość klasyfikatorów musi obliczyć pewne podobieństwo, takie jak iloczyn iloczynu, a to oznacza, że ​​złożoność czasowa algorytmu klasyfikacji jest proporcjonalna do wymiaru punktu danych. Zatem wyższy wymiar oznacza większą złożoność czasu (nie wspominając o złożoności przestrzeni do przechowywania tych dużych punktów wymiarowych).

Sztuczka jądra: Niech będzie oryginalnym wymiarem punktów danych, a będzie mapą, która odwzorowuje te punkty na przestrzeń o wymiarze . Teraz, jeżeli jest funkcją która odbywa wejścia i od pierwotnego miejsca i oblicza , wówczas mogę obliczyć iloczyn skalarny w przestrzeni o większych wymiarach, ale w złożoności zamiast .$n$$f$$N (>> n)$$K$$x$$y$$K(x, y) = \langle f(x), f(y) \rangle$$O(n)$$O(N)$

Znaczenie: Jeśli więc algorytm klasyfikacji zależy tylko od iloczynu kropkowego i nie ma zależności od rzeczywistej mapy , mogę użyć sztuczki jądra, aby uruchomić algorytm w przestrzeni o dużych wymiarach bez prawie żadnych dodatkowych kosztów.$f$

Czy liniowa separowalność oznacza, że ​​punkty z tej samej klasy będą się zbliżać niż punkty z różnych klas? Nie, nie ma takiej gwarancji jako takiej. Rozdzielność liniowa tak naprawdę nie oznacza, że ​​punkt z tej samej klasy zbliżył się lub że punkty z dwóch różnych klas poszły jeszcze dalej.

Dlaczego więc miałoby działać kNN? Nie musi! Jeśli jednak tak się dzieje, dzieje się tak wyłącznie z powodu jądra.

Co to znaczy? Rozważ boolowski wektor funkcji . Gdy używasz jądra wielomianowego stopnia drugiego, wektor cech jest mapowany na wektor$x = (x_1, x_2)$$x$$(x_1^2, \sqrt{2} x_1x_2, x_2^2)$. Z wektora cech boolowskich, po prostu stosując wielomian stopnia drugiego, otrzymaliśmy wektor cech „koniunkcji”. Zatem same jądra wytwarzają genialne mapy funkcji. Jeśli Twoje dane mają dobre oryginalne funkcje i jeśli Twoje dane mogłyby skorzystać z map funkcji utworzonych przez te jądra. Przez korzyść rozumiem, że funkcje wytworzone przez te mapy funkcji mogą zbliżyć punkty z tej samej klasy do siebie i odepchnąć punkty z różnych klas, a następnie kNN może skorzystać z jądra. W przeciwnym razie wyniki nie będą się różnić od wyników uzyskanych po uruchomieniu kNN na oryginalnych danych.

Więc po co używać jądra kNN? Pokazaliśmy, że złożoność obliczeniowa korzystania z jądra jest tylko nieco większa niż zwykłego kNN, a jeśli dane korzystają z używania jąder, dlaczego ich nie użyć?

Czy jest jakaś praca, która badała, która klasa danych może korzystać z jąder w kNN? O ile mi wiadomo, nie.

[1] http://en.wikipedia.org/wiki/Linear_separability
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038449&tag=1