Jaką funkcją może być jądro?

21

W kontekście uczenia maszynowego i rozpoznawania wzorców istnieje koncepcja o nazwie Kernel Trick . W obliczu problemów, w których jestem proszony o ustalenie, czy funkcja może być funkcją jądra, czy nie, co dokładnie należy zrobić? Czy powinienem najpierw sprawdzić, czy mają one postać trzech lub czterech funkcji jądra, takich jak wielomian, RBF i Gaussa? Więc co mam zrobić? Czy powinienem wykazać, że jest to zdecydowanie określony? Czy ktoś mógłby rozwiązać przykład pokazujący krok po kroku rozwiązanie takich problemów? Na przykład, czy jest funkcją jądraf(x)=extx (przypuśćmy, że nie wiemy, że jest to jądro Gaussa)?

Gigili
źródło

Odpowiedzi:

27

Zasadniczo funkcja jest prawidłową funkcją jądra (w sensie sztuczki jądra), jeśli spełnia dwie kluczowe właściwości:k(x,y)

  • symetria: k(x,y)=k(y,x)

  • pozytywna półokreśloność.

Odniesienie: Strona 4 z http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf

Sprawdzanie symetrii jest zwykle proste dzięki inspekcji. Weryfikacja analityczna pozytywnej półokreśloności może czasami być dość owłosiona. Mogę wymyślić dwie strategie sprawdzania tego faktu:

  • (1) Sprawdzanie reprezentacji „produktu wewnętrznego”

Rozważmy k(x,y)=ex+y . Czy możemy znaleźć takie ϕ(a) , że k(x,y)=ϕ(x)Tϕ(y) ? Mała matematyka pokazuje, że ex+y=exey , więc niech ϕ(a)=ea i gotowe.

Jeśli ci się poszczęści, twoja k() będzie podlegać tej analizie. Jeśli nie, możesz skorzystać z opcji (2):

  • (2) Sprawdzanie pozytywnej definitywności za pomocą symulacji losowej.

Rozważ funkcję w wektorach -dim , gdzie każdy wektor musi być nieujemny i sumować się do jednego. Czy to jest prawidłowe jądro?k ( x , y ) = D d = 1 min ( x d , y d ) x , yDk(x,y)=d=1Dmin(xd,yd)x,y

Możemy to sprawdzić za pomocą symulacji. Narysuj zestaw losowych wektorów i zbuduj macierz Gram gdzie . Następnie sprawdź, czy jest dodatnie (pół-) określone.{ x i } N i = 1 K K i j = k ( x i , x j ) KN{xi}i=1NKKij=k(xi,xj)K

Najlepszym sposobem na zrobienie tego numerycznie jest znalezienie wartości własnych macierzy (przy użyciu dobrych istniejących bibliotek numerycznych, takich jak scipy lub matlab), i sprawdzenie, czy najmniejsza wartość własna jest większa lub równa 0 . Jeśli tak, macierz to psd. W przeciwnym razie nie masz prawidłowego jądra.K

Przykładowy kod MATLAB / Octave:

D=5;
N=100;

X = zeros(N,D);
for n = 1:N
   xcur = rand(1,D);
   X(n,:) = xcur/sum(xcur);
end

K = zeros(N,N);
for n = 1:N;  for m = 1:N
    K(n,m) = sum( min( X(n,:), X(m,:) ) );
end;  end;

disp( min( eig(K) ) );

To bardzo prosty test, ale bądź ostrożny . Jeśli test nie powiedzie się, można mieć pewność, jądro jest nie ważny, ale jeśli przechodzi jądro nadal może nie być aktualne.

Uważam, że bez względu na to, ile losowych macierzy generuję i niezależnie od i , jądro to przechodzi test, więc prawdopodobnie jest półdefiniowane pozytywnie (w rzeczywistości jest to dobrze znane jądro przecięcia histogramu i zostało udowodnione ważny).DND

Jednak ten sam test na kończy się niepowodzeniem przy każdej próbie, którą mu (co najmniej 20) . Jest to więc zdecydowanie nieważne i dość łatwe do zweryfikowania.k(x,y)=d=1Dmax(xd,yd)

Naprawdę podoba mi się ta druga opcja, ponieważ jest dość szybka i znacznie łatwiejsza do debugowania niż skompilowane formalne dowody. Według slajdu 19 Jitendry Malik jądro przecięcia zostało wprowadzone w 1991 r., Ale udowodniono, że jest poprawne do 2005 r. Formalne dowody mogą być bardzo trudne!

Mike Hughes
źródło
Jak rozumiem drugi warunek jest tylko pozytywne pół -definiteness. I z tego, co mi powiedziano, jest to konieczne tylko wtedy, gdy chcesz udowodnić zbieżność algorytmu SVM. W praktyce istnieje wiele jąder, które nie są PSD, ale działają dobrze w praktyce.
Peter
@Peter: tak, masz rację. Może być * częściowo * określony, a nie tylko określony. Odpowiednio zredagowane.
Mike Hughes,
W domenie SVM użycie jądra PSD zapewnia wypukłość problemu, dzięki czemu optymalizacja osiąga unikalne, globalnie optymalne rozwiązanie. Bez właściwości PSD nie ma gwarancji, że znalezione rozwiązanie znajdzie się w pobliżu najlepszego możliwego rozwiązania. Ale tak, istnieje kilka jąder (takich jak Sigmoid), które nie są PSD, ale wciąż odnoszą sukcesy w praktyce. Godne odniesienia do tego problemu to: perso.lcpc.fr/tarel.jean-philippe/publis/jpt-icme05.pdf .
Mike Hughes,