Método Nystroem para Aproximação do Kernel

12

Eu tenho lido sobre o método Nyström para aproximação de kernel de baixo escalão. Este método é implementado no scikit-learn [1] como um método para projetar amostras de dados para uma aproximação de baixo escalão do mapeamento de recursos do kernel.

Para o melhor de meu conhecimento, dado um conjunto de treinamento {xi}i=1n e uma função kernel, ele gera um baixo-rank aproximação do n×n núcleo matriz K aplicando SVD para W e C .

K=[WK21TK21K22] C=[WK21] ,WRl×l

No entanto, não entendo como a aproximação de baixo escalão da matriz do Kernel pode ser usada para projetar novos exemplos no espaço aproximado de recursos do kernel . Os documentos que encontrei (por exemplo, [2]) não são de grande ajuda, pois são pouco didáticos.

Além disso, estou curioso sobre a complexidade computacional desse método, tanto nas fases de treinamento quanto de teste.

[1] http://scikit-learn.org/stable/modules/kernel_approximation.html#nystroem-kernel-approx

[2] http://www.jmlr.org/papers/volume13/kumar12a/kumar12a.pdf.

Daniel López
fonte

Respostas:

15

Vamos derivar a aproximação de Nyström de uma maneira que torne as respostas às suas perguntas mais claras.

O principal pressuposto em Nyström é que a função do kernel é da categoria . (Realmente assumimos que é aproximadamente da classificação m , mas, por simplicidade, vamos fingir que é exatamente a classificação m por enquanto.) Isso significa que qualquer matriz do kernel terá classificação no máximo m , e em particular K = [ k ( x 1 , x 1 ) ... k ( x 1 , x n ) k ( x nmmmm é a classificaçãom. Portanto, hámvalores próprios diferentes de zero, e que podemos escrever a eigendecomposition deKcomo K=LΛLT com vectores próprios armazenados emU, de formanxm, e valores próprios dispostos emΛ, umm×mmatriz diagonal.

K=[k(x1,x1)k(x1,xn)k(xn,x1)k(xn,xn)],
mmK
K=UΛUT
Un×mΛm×m

mK11

K=[K11K21TK21K22],
K11m×mK21(nm)×mK22

K=UΛUT=[U1U2]Λ[U1U2]T=[U1ΛU1TU1ΛU2TU2ΛU1TU2ΛU2T],
U1m×mU2(nm)×mK11=U1ΛU1TU1ΛK11

K21=U2ΛU1TU2(ΛU1T)1=U1Λ1

U2=K21U1Λ1.
K22
K22=U2ΛU2T=(K21U1Λ1)Λ(K21U1Λ1)T=K21U1(Λ1Λ)Λ1U1TK21T=K21U1Λ1U1TK21T(*)=K21K111K21T(**)=(K21K1112)(K21K1112)T.

K22

K21K1112(nm)×mK1112mm

Φ=[K1112K21K1112].
Φ
ΦΦT=[K1112K21K1112][K1112K21K1112]T=[K1112K1112K1112K1112K21TK21K1112K1112K21K1112K1112K21T]=[K11K21TK21K21K111K21T]=K.

mΦK

xΦ

ϕ(x)=[k(x,x1)k(x,xm)]K1112.
x[k(x,x1)k(x,xm)]K21K21K1112ϕ(x)K11K11K1112=K1112Φxnew
Φtest=Ktest,1K1112.
m[KtrainKtrain,testKtest,trainKtest]mKtestK22


Acima, assumimos que a matriz do núcleo K era exatamente a classificação m . Isso geralmente não será o caso; para um núcleo Gaussiano, por exemplo, K é sempre posto n , mas os últimos valores próprios tipicamente cair muito rapidamente, por isso vai ser perto de uma matriz de classificação m , e as nossas reconstruções de K 21 ou K teste , 1 vão estar perto dos valores verdadeiros, mas não exatamente o mesmo. Serão melhores reconstruções quanto mais próximo o espaço próprio do K 11 chegar ao deKmKnmK21Ktest,1K11 geral, é por isso que escolher os m pontoscertosé importante na prática.Km

Observe também que se tiver valores próprios zero, você poderá substituir inversos por pseudo-inversos e tudo ainda funcionará; você acabou de substituir K 21 na reconstrução por K 21 K 11 K 11 .K11K21K21K11K11

Kmax(λi,1012)

Dougal
fonte
11
AUΛUTAUΣVTA12=VΣ12VTAAVΣ12VT=UΣVTVΣ12VT=UΣ12VT=A12
11
UΣ12VT=K12UVK11UΣVTVΣ12UT=UΣ12UT
11
x12=1/xVVT
11
xm
11
xxRdxXk:X×XRϕ:XRmk(x,xi)m