Welche Funktion könnte ein Kernel haben?

Im Kontext von maschinellem Lernen und Mustererkennung gibt es ein Konzept namens Kernel Trick . Bei Problemen, bei denen ich gefragt werde, ob eine Funktion eine Kernelfunktion sein kann oder nicht, was genau soll ich tun? Sollte ich zuerst prüfen, ob sie die Form der drei oder vier Kernfunktionen wie Polynom, RBF und Gauß haben? Was soll ich dann tun? Sollte ich zeigen, dass es definitiv positiv ist? Könnte jemand ein Beispiel lösen, um eine schrittweise Lösung für solche Probleme aufzuzeigen? Wie zum Beispiel, ist $f(x)=e^{x^tx'}$ eine Kernfunktion (Angenommen , wir wissen nicht , es ist ein Gauß - Kern ist)?

Im Allgemeinen ist eine Funktion $k(x,y)$ eine gültige Kernelfunktion (im Sinne des Kernel-Tricks), wenn sie zwei Schlüsseleigenschaften erfüllt:

• Symmetrie: $k(x,y) = k(y,x)$

• positive Halbbestimmtheit.

Hinweis: Seite 4 von http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf

Die Überprüfung der Symmetrie ist in der Regel einfach durch Inspektion. Das analytische Überprüfen der positiven Halbwertszeit kann manchmal ziemlich haarig sein. Ich kann mir zwei Strategien vorstellen, um diese Tatsache zu überprüfen:

• (1) Überprüfung auf eine "innere Produkt" -Darstellung

Betrachte . Können wir einige ϕ ( a ) so finden, dass k ( x , y ) = ϕ ( x ) T ϕ ( y ) ist ? Eine kleine Rechnung zeigt, dass e x + y = e x e y , also sei ϕ ( a ) = e a und wir sind fertig.$k(x,y) = e^{x+y}$$\phi(a)$$k(x,y) = \phi(x)^T \phi(y)$$e^{x+y} = e^x e^y$$\phi(a)=e^a$

Wenn Sie Glück haben, ist Ihr für diese Analyse zugänglich. Wenn nicht, können Sie auf Option (2) zurückgreifen:$k()$

• (2) Überprüfung der positiven Bestimmtheit durch zufällige Simulation.

Betrachten Sie die Funktion auf dim Vektoren k ( → x , → y ) = ∑ D d = 1 min ( x d , y d ) , wobei jeder Vektor → x , → $D$$k(\vec{x},\vec{y}) = \sum_{d=1}^D \min( x_d, y_d)$$\vec{x}, \vec{y}$ nicht negativ sein und zu eins summieren muss. Ist das ein gültiger Kernel?

Wir können dies durch Simulation überprüfen. Zeichnen Sie eine Menge von Zufallsvektoren { → x i } N i = 1 und bauen Sie eine Gram-Matrix K auf, wobei K i j = k ( → x i , → x j ) . Überprüfen Sie dann, ob K positiv (semi-) definit ist.$N$$\{\vec{x}_i\}_{i=1}^N$$K$$K_{ij} = k( \vec{x}_i , \vec{x}_j )$$K$

Der beste Weg, dies numerisch zu tun, besteht darin, die Eigenwerte der Matrix zu ermitteln (unter Verwendung guter vorhandener numerischer Bibliotheken wie scipy oder matlab) und zu überprüfen, ob der kleinste Eigenwert größer oder gleich 0 ist . Wenn ja, ist die Matrix psd. Andernfalls ist dies nicht der Fall$K$ über einen gültigen Kernel.

Beispiel MATLAB / Octave-Code:

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) ) );

Dies ist ein sehr einfacher Test, aber seien Sie vorsichtig . Wenn der Test fehlschlägt, können Sie sicher sein, dass der Kernel nicht gültig ist. Wenn er jedoch erfolgreich ist, ist der Kernel möglicherweise immer noch nicht gültig.

Unabhängig davon, wie viele zufällige Matrizen ich generiere und unabhängig von und D , besteht dieser Kernel den Test. Daher ist er wahrscheinlich positiv semidefinit (tatsächlich ist dies der bekannte Histogramm-Schnittpunkt-Kernel)$N$$D$ , der sich bewährt hat) gültig).

$k(\vec{x},\vec{y}) = \sum_{d=1}^D max( x_d, y_d)$

Ich mag diese zweite Option wirklich, weil sie ziemlich schnell und viel einfacher zu debuggen ist als kompilierte formale Beweise. Laut Jitendra Maliks Folie 19 wurde der Kreuzungskern 1991 eingeführt, aber erst 2005 als richtig erwiesen. Formale Beweise können sehr schwierig sein!