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 .nfN(>>n)KxyK(x,y)=⟨f(x),f(y)⟩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 wektorx=(x1,x2)x(x21,2–√x1x2,x22). 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