Metode Nystroem untuk Perkiraan Kernel

12

Saya telah membaca tentang metode Nyström untuk aproximation kernel peringkat rendah. Metode ini diimplementasikan dalam scikit-learn [1] sebagai metode untuk memproyeksikan sampel data ke pendekatan peringkat rendah dari pemetaan fitur kernel.

Sepengetahuan saya, diberikan set pelatihan dan fungsi kernel, itu menghasilkan pendekatan peringkat rendah dari matriks kernel dengan menerapkan SVD ke dan .{xi}i=1nn×nKWC

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

Namun, saya tidak mengerti bagaimana pendekatan peringkat rendah dari matriks Kernel dapat digunakan untuk memproyeksikan sampel baru ke ruang fitur kernel yang didekati . Makalah yang saya temukan (misalnya [2]) tidak banyak membantu, karena mereka sedikit bersifat didaktik.

Saya juga ingin tahu tentang kerumitan komputasi dari metode ini, baik dalam fase pelatihan maupun uji.

[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
sumber

Jawaban:

15

Mari kita turunkan perkiraan Nyström dengan cara yang seharusnya membuat jawaban atas pertanyaan Anda lebih jelas.

Asumsi kunci dalam Nyström adalah bahwa fungsi kernel adalah dari peringkat . (Benar-benar kita menganggap bahwa itu kira-kira pangkat , tetapi untuk kesederhanaan membiarkan hanya berpura-pura itu persis peringkat untuk saat ini.) Itu berarti bahwa setiap matriks kernel akan memiliki peringkat paling , dan khususnya adalah peringkat . Oleh karena itu ada nol eigenvalues, dan kita dapat menulis eigendecomposition dari sebagai m m m K = [ k ( x 1 , x 1 ) ... k ( x 1 , x n ) k ( x n , x 1 ) ... k ( x n , x n ) ] , m m K K = U Λ U T U n × m Λ mmmmm

K=[k(x1,x1)k(x1,xn)k(xn,x1)k(xn,xn)],
mmK
K=UΛUT
dengan vektor eigen disimpan di , dengan bentuk , dan nilai eigen disusun dalam , sebuah matriks diagonal .Un×mΛm×m

Jadi, mari kita pilih elemen , biasanya seragam secara acak tetapi mungkin menurut skema lain - semua yang penting dalam versi yang disederhanakan ini adalah K 11 memiliki peringkat penuh. Setelah kita lakukan, cukup beri tanda baru pada titik-titik sehingga kita berakhir dengan matriks kernel dalam blok: K = [ K 11 K T 21 K 21 K 22 ] , di mana kami mengevaluasi setiap entri dalam K 11 (yaitu m × m ) dan K 21 ( ( n - m ) × mmK11

K=[K11K21TK21K22],
K11m×mK21(n-m)×m), tetapi tidak ingin mengevaluasi entri dalam .K22

Sekarang, kita dapat membagi komposisi eigend menurut struktur blok ini juga: manaU1adalahm×mdanU2adalah(n-m)×m. Tetapi perhatikan bahwa sekarang kita memilikiK11=U1ΛU T 1 . Jadi kita bisa menemukannya

K=UΛUT=[U1U2]Λ[U1U2]T=[U1ΛU1TU1ΛU2TU2ΛU1TU2ΛU2T],
U1m×mU2(n-m)×mK11=U1ΛU1T dan Λ oleh eigendecomposing matriks dikenal K 11 .U1ΛK11

Kita juga tahu bahwa . Di sini, kita mengetahui segala sesuatu dalam persamaan ini kecuali U 2 , sehingga kita dapat menyelesaikan untuk apa nilai eigen yang menyiratkan: melipatgandakan kedua belah pihak dengan ( Λ U T 1 ) - 1 = U 1 Λ - 1 untuk mendapatkan U 2 = K 21 U 1 Λ - 1 . Sekarang kami memiliki semua yang kami butuhkan untuk mengevaluasi K 22 : K 22K21=U2ΛU1TU2(ΛU1T)-1=U1Λ-1

U2=K21U1Λ-1.
K22
K22=U2ΛU2T=(K21U1Λ-1)Λ(K21U1Λ-1)T=K21U1(Λ-1Λ)Λ-1U1TK21T=K21U1Λ-1U1TK21T(*)=K21K11-1K21T(**)=(K21K11-12)(K21K11-12)T.

K22

K21K11-12(n-m)×mK1112mm

Φ=[K1112K21K11-12].
Φ
ΦΦT=[K1112K21K11-12][K1112K21K11-12]T=[K1112K1112K1112K11-12K21TK21K11-12K1112K21K11-12K11-12K21T]=[K11K21TK21K21K11-1K21T]=K.

mΦK

xΦ

ϕ(x)=[k(x,x1)...k(x,xm)]K11-12.
x[k(x,x1)...k(x,xm)]K21K21K11-12ϕ(x)K11K11K11-12=K1112Φxbaru
Φuji=Kuji,1K11-12.
m[KmelatihKberlatih, tesKtes, latihKuji]mKujiK22


Di atas, kita mengasumsikan bahwa matriks kernel adalah persis peringkat m . Ini biasanya tidak akan terjadi; untuk Gaussian kernel, misalnya, K adalah selalu rank n , tetapi nilai eigen yang terakhir biasanya drop off cukup cepat, sehingga akan menjadi dekat dengan matriks rank m , dan rekonstruksi kami K 21 atau K tes , 1 akan untuk menjadi dekat dengan nilai sebenarnya tetapi tidak persis sama. Mereka akan rekonstruksi yang lebih baik lebih dekat ruang eigen dari K 11 sampai ke yang dariKmKnmK21Kuji,1K11 keseluruhan, itulah sebabnya mengapa memilihpoin m yang tepatadalah penting dalam praktik.Km

Perhatikan juga bahwa jika memiliki nol nilai eigen, Anda dapat mengganti invers dengan pseudoinverses dan semuanya masih berfungsi; Anda baru saja mengganti K 21 dalam rekonstruksi dengan K 21 K 11 K 11 .K11K21K21K11K11

Kmaks(λsaya,10-12)

Dougal
sumber
1
SEBUAHUΛUTSEBUAHUΣVTSEBUAH-12=VΣ-12VTSEBUAHSEBUAHVΣ-12VT=UΣVTVΣ-12VT=UΣ12VT=SEBUAH12
1
UΣ-12VT=K-12UVK11UΣVTVΣ-12UT=UΣ12UT
1
x-12=1/xVVT
1
xm
1
xxRdxXk:X×XRϕ:XRmk(x,xsaya)m