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 ( xn, x1)...⋱...k ( x1, xn)⋮k ( xn, xn)⎤⎦⎥⎥,
mmKK= 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= [ K11K21KT21K22] ,
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Λ UT1U2Λ UT1U1Λ UT2U2Λ UT2] ,
U1m × mU2( n - m ) × mK11= U1Λ UT1 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Λ UT1U2( Λ UT1)- 1= U1Λ- 1
U2= K21U1Λ- 1.
K22K22= U2Λ UT2= ( K21U1Λ- 1) Λ ( K21U1Λ- 1)T= K21U1( Λ- 1Λ ) Λ- 1UT1KT21= K21U1Λ- 1UT1KT21= K21K- 111KT21= ( K21K- 1211) ( K21K- 1211)T.(*)(**)
K22
K21K- 1211( n - m ) × mK1211mm
Φ = ⎡⎣⎢K1211K21K- 1211⎤⎦⎥.
ΦΦ ΦT= ⎡⎣⎢K1211K21K- 1211⎤⎦⎥⎡⎣⎢K1211K21K- 1211⎤⎦⎥T= ⎡⎣⎢K1211K1211K21K- 1211K1211K1211K- 1211KT21K21K- 1211K- 1211KT21⎤⎦⎥= [ K11K21KT21K21K- 111KT21]= K.
mΦK
xΦ
ϕ ( x ) = [ k ( x , x1)...k ( x , xm)] K- 1211.
x[ k ( x , x1)...k ( x , xm)]K21K21K- 1211ϕ ( x )K11K11K- 1211= K1211ΦxbaruΦuji= Ktes , 1K- 1211.
m[ KmelatihKtes, latihKberlatih, tesKuji]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 dari
KmKnmK21Ktes , 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 .K11K21K21K†11K11
Kmaks ( λsaya, 10- 12)