Que função poderia ser um kernel?

21

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 kernelf(x)=extx (suponha que nós não sabemos é um kernel Gaussian)?

Gigili
fonte

Respostas:

27

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 ak(x,y)=ex+yϕ(a)k(x,y)=ϕ(x)Tϕ(y)ex+y=exeyϕ(a)=ea

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?Dk(x,y)=d=1Dmin(xd,yd)x,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{xi}i=1NKKij=k(xi,xj)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).ND

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(x,y)=d=1Dmax(xd,yd)

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!

Mike Hughes
fonte
Pelo que entendi, a segunda condição é apenas semi- indefinição positiva . E pelo que me disseram, só é necessário se você quiser provar a convergência do algoritmo SVM. Na prática, existem muitos kernels que não são PSD, mas funcionam bem na prática.
Peter
@ Peter: sim, você está certo. Pode ser * semi- * definido, não apenas definido. Editado de acordo.
Mike Hughes
No domínio SVM, o uso de um kernel PSD garante que o problema seja convexo, de modo que a otimização alcança uma solução global ideal ideal. Sem a propriedade PSD, não há garantia de que a solução encontrada esteja próxima do melhor possível. Mas, sim, existem vários kernels (como o Sigmoid) que não são PSD, mas ainda são bem-sucedidos na prática. Uma referência decente para esse problema é: perso.lcpc.fr/tarel.jean-philippe/publis/jpt-icme05.pdf .
Mike Hughes