Que função poderia ser um kernel?

No contexto do aprendizado de máquina e reconhecimento de padrões, existe um conceito chamado Kernel Trick . Enfrentando problemas em que me pedem para determinar se uma função pode ser uma função do kernel ou não, o que exatamente deve ser feito? Devo primeiro verificar se eles têm a forma de três ou quatro funções do kernel, como polinomial, RBF e Gaussian? Então o que eu devo fazer? Devo mostrar que é positivo definitivo? Alguém poderia resolver um exemplo para mostrar uma solução passo a passo para esses problemas? Como por exemplo, é uma função de kernel$f(x)=e^{x^tx'}$ (suponha que nós não sabemos é um kernel Gaussian)?

Geralmente, uma função é uma função válida do kernel (no sentido do truque do kernel) se ela satisfizer duas propriedades principais:$k(x,y)$

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

• semi-definição positiva.

Referência: página 4 de http://www.cs.berkeley.edu/~jordan/courses/281B-spring04/lectures/lec3.pdf

A verificação da simetria é geralmente direta por inspeção. Verificar a semi-definição positiva analiticamente pode ser bastante complicado às vezes. Eu posso pensar em duas estratégias para verificar esse fato:

• (1) Inspeção de uma representação de "produto interno"

Considere . Podemos encontrar alguns tais que ? Um pouco de matemática mostra que e ^ {x + y} = e ^ xe ^ y , então vamos \ phi (a) = e ^ a e nós terminamos. ϕ ( a ) k ( x , y ) = ϕ ( x ) T ϕ ( y ) e x + y = e x e y ϕ ( a ) = e $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$

Se você tiver sorte, seu $k()$ será passível de análise. Caso contrário, você pode recorrer à opção (2):

• (2) Verificação da definição positiva por simulação aleatória.

Considere a função nos vetores dim , em que cada vetor deve ser não negativo e soma a um. Este é um kernel válido?$D$$k(\vec{x},\vec{y}) = \sum_{d=1}^D \min( x_d, y_d)$$\vec{x}, \vec{y}$

Podemos verificar isso por simulação. Desenhe um conjunto de vetores aleatórios e construa uma matriz Gram onde . Depois verifique se é positivo (semi-) definido.$N$$\{\vec{x}_i\}_{i=1}^N$$K$$K_{ij} = k( \vec{x}_i , \vec{x}_j )$$K$

A melhor maneira de fazer isso numericamente é encontrar os valores próprios da matriz (usando boas bibliotecas numéricas existentes, como scipy ou matlab) e verifique se o menor valor próprio é maior que ou igual a 0 . Se sim, a matriz é psd Caso contrário, você não possui um kernel válido.$K$

Exemplo de código 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) ) );

Este é um teste muito simples, mas tenha cuidado . Se o teste falhar, você pode ter certeza de que o kernel não é válido, mas se for aprovado, o kernel ainda pode não ser válido.

Acho que não importa quantas matrizes aleatórias eu gere e, independentemente de e , esse kernel passa no teste, portanto é provavelmente semi-definido positivo (na verdade, esse é o conhecido kernel de interseção do histograma e foi comprovado válido).$N$$D$

No entanto, o mesmo teste em falha em todas as tentativas realizadas (pelo menos 20) . Portanto, é definitivamente inválido e fácil de verificar.$k(\vec{x},\vec{y}) = \sum_{d=1}^D max( x_d, y_d)$

Eu realmente gosto dessa segunda opção porque é muito rápida e muito mais fácil de depurar do que provas formais compiladas. De acordo com o slide 19 de Jitendra Malik , o núcleo de interseção foi introduzido em 1991, mas não se provou correto até 2005. Provas formais podem ser muito desafiadoras!