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

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ądra$f(x)=e^{x^tx'}$ (przypuśćmy, że nie wiemy, że jest to jądro Gaussa)?

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) = e^{x+y}$ . Czy możemy znaleźć takie $\phi(a)$ , że $k(x,y) = \phi(x)^T \phi(y)$ ? Mała matematyka pokazuje, że $e^{x+y} = e^x e^y$ , więc niech $\phi(a)=e^a$ 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 , → $D$$k(\vec{x},\vec{y}) = \sum_{d=1}^D \min( x_d, y_d)$$\vec{x}, \vec{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 ) $N$$\{\vec{x}_i\}_{i=1}^N$$K$$K_{ij} = k( \vec{x}_i , \vec{x}_j )$$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).$N$$D$

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(\vec{x},\vec{y}) = \sum_{d=1}^D max( x_d, y_d)$

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!