Como provar que a função base radial é um núcleo?

35

Como provar que a função de base radial é um kernel? Tanto quanto eu entendo, para provar isso, temos que provar um dos seguintes:k(x,y)=exp(||xy||2)2σ2)

  1. Para qualquer conjunto de vetores matriz = é semidefinido positivo.x1,x2,...,xnK(x1,x2,...,xn)(k(xi,xj))n×n

  2. Um mapeamento pode ser apresentado como = .Φk(x,y)Φ(x),Φ(y)

Qualquer ajuda?

Leo
fonte
11
Só para ligá-la mais, obviamente: o mapa recurso também é discutida nesta questão , particularmente a resposta de Marc Claesen baseado na série de Taylor e mina que discute tanto os RKHS e a versão geral do L2 incorporação para dado por Douglas abaixo.
Dougal

Respostas:

26

O Zen usou o método 1. Aqui está o método 2: mapeie x para uma distribuição gaussiana esfericamente simétrica, centrada em x no espaço Hilbert L2 . O desvio padrão e um fator constante precisam ser ajustados para que isso funcione exatamente. Por exemplo, em uma dimensão,

exp[(xz)2/(2σ2)]2πσexp[(yz)2/(2σ2)2πσdz=exp[(xy)2/(4σ2)]2πσ.

Portanto, use um desvio padrão de e dimensionar a distribuição de Gauss para obterK(x,y)=Φ(x),Φ(y). Esse último redimensionamento ocorre porque anormaL2de uma distribuição normal não é1em geral.σ/2k(x,y)=Φ(x),Φ(y)L21

Douglas Zare
fonte
2
@ Zen, Douglas Zare: obrigado por suas ótimas respostas. Como devo selecionar a resposta oficial agora?
Leo
23

Usarei o método 1. Verifique a resposta de Douglas Zare para obter uma prova usando o método 2.

I provará o caso quando são números reais, de modo que k ( x , y ) = exp ( - ( x - y ) 2 / 2 σ 2 ) . O caso geral segue mutatis mutandis do mesmo argumento, e vale a pena fazer.x,yk(x,y)=exp((xy)2/2σ2)

Sem perda de generalidade, suponha que .σ2=1

Escreva , onde h ( t ) = exp ( - t 2k(x,y)=h(xy)é a função característica de uma variável aleatóriaZcomdistribuiçãoN(0,1).

h(t)=exp(t22)=E[eitZ]
ZN(0,1)

Para números reais e a 1 , , a n , temos n j , k = 1 a jx1,,xna1,,an que implica que k é uma função semidefinida positiva, também conhecida como kernel.

j,k=1najakh(xjxk)=j,k=1najakE[ei(xjxk)Z]=E[j,k=1najeixjZakeixkZ]=E[|j=1najeixjZ|2]0,
k

Para entender esse resultado em maior generalidade, consulte o Teorema de Bochner: http://en.wikipedia.org/wiki/Positive-definite_function

zen
fonte
2
Este é um bom começo, na direção certa, com duas ressalvas: (a) não é igual à expectativa mostrada (verifique o sinal no expoente) e (b) isso parece restringir a atenção ao caso em que x e y são escalares e não vetores. Enquanto isso, eu voto positivo, porque a exposição é agradável e limpa e tenho certeza de que você rapidamente preencherá essas pequenas lacunas. :-)h(t)xy
cardeal
11
Tks! Estou com pressa aqui. :-)
Zen
11
Com licença, eu realmente não vejo como você gerencia os mutatis mutandis aqui. Se você desenvolver a norma antes de passar para o formulário , terá produtos e não poderá trocar produtos e somas. E simplesmente não vejo como desenvolver a norma depois de passar para a forma h para obter uma expressão agradável. Você pode me levar um pouco até lá? :)h
Alburkerk
23

Vou adicionar um terceiro método, apenas para variar: construir o kernel a partir de uma sequência de etapas gerais conhecidas por criar kernels pd. Deixe- denotar o domínio dos grãos abaixo e & Phi; os mapas de características.Xφ

  • Escalonamentos: Se é um kernel pd, também é γ κ para qualquer constante γ > 0 .κγκγ>0

    Prova: se é o mapa de características de κ , φκé um mapa de recursos válido paraγκ.γφγκ

  • Soma: Se e κ 2 são pd kernels, também é κ 1 + κ 2 .κ1κ2κ1+κ2

    Prova: concatene os mapas de recursos e φ 2 , para obter x [ φ 1 ( x ) φ 2 ( x ) ] .φ1φ2x[φ1(x)φ2(x)]

  • Limites: Se são pd kernels e κ ( x , y ) : = lim n κ n ( x , y ) existe para todos x , y , então k é pd.κ1,κ2,κ(x,y):=limnκn(x,y)x,yκ

    Prova: Para cada e cada { ( x i , c i ) } m i = 1X × R temos que Σ m i = 1 c i κ n ( x i , x j ) c j0 . Tomar o limite como n fornece a mesma propriedade para κ .m,n1{(xi,ci)}i=1mX×Ri=1mciκn(xi,xj)cj0nκ

  • Produtos: Se e κ 2 são pd kernels, o mesmo acontece com g ( x , y ) = κ 1 ( x , y )κ1κ2 .g(x,y)=κ1(x,y)κ2(x,y)

    Prova: Segue-se imediatamente a partir do teorema do produto Schur , mas Schölkopf e Smola (2002) fornecem a seguinte prova agradável e elementar. Seja seja independente. Assim, C o v ( V i W i , V j W j ) = C o v ( V i , V j )

    (V1,,Vm)N(0,[κ1(xi,xj)]ij)(W1,,Wm)N(0,[κ2(xi,xj)]ij)
    As matrizes de covariância devem ser psd, portanto, considerando a matriz de covariância de ( V 1 W 1 , , V n W n ) prova isso.
    Cov(ViWi,VjWj)=Cov(Vi,Vj)Cov(Wi,Wj)=κ1(xi,xj)κ2(xi,xj).
    (V1W1,,VnWn)
  • κκn(x,y):=κ(x,y)nn

    Prova: imediata da propriedade "produtos".

  • κeκ(x,y):=exp(κ(x,y))

    eκ(x,y)=limNn=0N1n!κ(x,y)n

  • κf:XRg(x,y):=f(x)κ(x,y)f(y)

    xf(x)φ(x)

k(x,y)=exp(12σ2xy2)=exp(12σ2x2)exp(1σ2xTy)exp(12σ2y2).
κ(x,y)=xTy1σ2xexp(12σ2x2)
Dougal
fonte