Quelle fonction pourrait être un noyau?

21

Dans le contexte de l'apprentissage automatique et de la reconnaissance des formes, il existe un concept appelé Kernel Trick . Face à des problèmes où l'on me demande de déterminer si une fonction peut être une fonction noyau ou non, que faire exactement? Dois-je d'abord vérifier si elles ont la forme des trois ou quatre fonctions du noyau telles que polynôme, RBF et gaussien? Alors que suis-je censé faire? Dois-je montrer qu'il est définitivement défini? Quelqu'un pourrait-il résoudre un exemple pour montrer une solution étape par étape pour de tels problèmes? Comme par exemple, est F(X)=eXtX fonction noyau (supposons que nous ne savons pas est un noyau gaussien)?

Gigili
la source

Réponses:

27

Généralement, une fonction k(X,y) est une fonction noyau valide (au sens de l'astuce noyau) si elle satisfait deux propriétés clés:

  • symétrie: k(X,y)=k(y,X)

  • semi-définitif positif.

Référence: page 4 de http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf

La vérification de la symétrie est généralement simple par inspection. La vérification analytique de la semi-définition positive peut parfois être assez velue. Je peux penser à deux stratégies pour vérifier ce fait:

  • (1) Recherche d'une représentation "produit intérieur"

Considérons . Peut - on trouver un φ ( a ) de telle sorte que k ( x , y ) = φ ( x ) T φ ( y ) ? Un peu de calcul montre que e x + y = e x e y , alors laissez ϕ ( a ) = e a et nous avons terminé.k(x,y)=ex+yϕ(a)k(x,y)=ϕ(x)Tϕ(y)ex+y=exeyϕ(a)=ea

Si vous avez de la chance, votre prêtera à cette analyse. Sinon, vous pouvez recourir à l'option (2):k()

  • (2) Vérification de la définition positive par simulation aléatoire.

Considérons la fonction sur les vecteurs -dim k ( x , y ) = D d = 1 min ( x d , y d ) , où chaque vecteur x , y doit être non négatif et somme à un. Est-ce un noyau valide?Dk(x,y)=d=1Dmin(xd,yd)x,y

Nous pouvons vérifier cela par simulation. Dessinez un ensemble de vecteurs aléatoires { x i } N i = 1 et construisez une matrice de Gram KK i j = k ( x i , x j ) . Vérifiez ensuite si K est positif (semi-) défini.N{xi}i=1NKKij=k(xi,xj)K

La meilleure façon de le faire numériquement est de trouver les valeurs propres de la matrice (en utilisant de bonnes bibliothèques numériques existantes comme scipy ou matlab), et de vérifier que la plus petite valeur propre est supérieure ou égale à 0 . Si oui, la matrice est psd Sinon, vous n'avez pas de noyau valide.K

Exemple de code 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) ) );

Il s'agit d'un test très simple, mais soyez prudent . Si le test échoue, vous pouvez être sûr que le noyau n'est pas valide, mais s'il réussit, le noyau pourrait ne pas être valide.

Je trouve que peu importe le nombre de matrices aléatoires que je génère et indépendamment de etND , ce noyau passe le test, il est donc probablement semi-défini positif (en fait, il s'agit du noyau d'intersection d'histogramme bien connu , et il a été prouvé valide).

Cependant, le même test sur k(x,y)=d=1Dmax(xd,yd) échoue à chaque essai que je lui ai donné (au moins 20) . Il est donc très certainement invalide et assez facile à vérifier.

J'aime vraiment cette deuxième option car elle est assez rapide et beaucoup plus facile à déboguer que les preuves formelles compilées. Selon la diapositive 19 de Jitendra Malik , le noyau d'intersection a été introduit en 1991 mais n'a pas été vérifié avant 2005. Les preuves formelles peuvent être très difficiles!

Mike Hughes
la source
Si je comprends bien, la deuxième condition n'est qu'une semi- définition définitive. Et d'après ce qu'on m'a dit, cela n'est nécessaire que si vous voulez prouver la convergence de l'algorithme SVM. En pratique, il existe de nombreux noyaux qui ne sont pas PSD, mais fonctionnent bien dans la pratique.
Peter
@Peter: oui, vous avez raison. Il peut être * semi-* défini, pas seulement défini. Modifié en conséquence.
Mike Hughes
Dans le domaine SVM, l'utilisation d'un noyau PSD garantit que le problème est convexe, de sorte que l'optimisation permet d'obtenir une solution unique et globalement optimale. Sans la propriété PSD, rien ne garantit que la solution trouvée est proche de la meilleure possible. Mais, oui, il existe plusieurs noyaux (comme le Sigmoid) qui ne sont pas PSD mais qui réussissent toujours dans la pratique. Une référence décente pour ce problème est: perso.lcpc.fr/tarel.jean-philippe/publis/jpt-icme05.pdf .
Mike Hughes