Dérivons l'approximation de Nyström d'une manière qui devrait rendre les réponses à vos questions plus claires.
L'hypothèse clé dans Nyström est que la fonction du noyau est de rang . (Vraiment, nous supposons qu'il est approximativement de rang , mais pour simplifier, supposons que c'est exactement le rang pour l'instant.) Cela signifie que toute matrice de noyau va avoir un rang au plus , et en particulier
est le rang . Il y a donc valeurs propres non nulles, et nous pouvons écrire la composition propre de comme
m m m K = [ k ( x 1mmmmmmKK=UΛUTUn×mΛm
K=⎡⎣⎢⎢k(x1,x1)⋮k(xn,x1)…⋱…k(x1,xn)⋮k(xn,xn)⎤⎦⎥⎥,
mmKK=UΛUT
avec des vecteurs propres stockés dans , de forme , et des valeurs propres disposées dans , une matrice diagonale .
Un×mΛm×m
Alors, choisissons éléments, généralement uniformément au hasard mais éventuellement selon d'autres schémas - tout ce qui compte dans cette version simplifiée est que soit de rang complet. Une fois que nous le faisons, il suffit de réétiqueter les points afin de nous retrouver avec la matrice du noyau en blocs:
où nous évaluons chaque entrée dans (qui est ) et ( ), mais nous ne voulons pas évaluer les entrées dans .K 11 K = [ K 11 K T 21 K 21 K 22 ] , K 11 m × m K 21 ( n - m ) × m K 22mK11
K=[K11K21KT21K22],
K11m×mK21(n−m)×mK22
Maintenant, nous pouvons également diviser la composition d'origine en fonction de cette structure de bloc:
où est et est . Mais notez que nous avons maintenant . On peut donc trouver et en composant par eigendecomposant la matrice connue .
K=UΛUT=[U1U2]Λ[U1U2]T=[U1ΛUT1U2ΛUT1U1ΛUT2U2ΛUT2],
U1m×mU2(n−m)×mK11=U1ΛUT1U1ΛK11
Nous savons aussi que . Ici, nous savons tout dans cette équation sauf , donc nous pouvons résoudre pour quelles valeurs propres cela implique: multiplier à droite des deux côtés par pour obtenir
Nous avons maintenant tout ce dont nous avons besoin pour évaluer :
K21=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.(*)(**)
Dans (*), nous avons trouvé une version de l'incorporation de Nyström que vous auriez pu voir simplement comme la définition. Cela nous indique les valeurs effectives du noyau que nous imputons pour le bloc .K22
Dans (**), nous voyons que la matrice d' , qui est la forme , correspond à ces valeurs de noyau imputées. Si nous utilisons pour les points, nous avons un ensemble de caractéristiques à dimensions
Nous pouvons simplement vérifier rapidement que correspond à la matrice de noyau correcte:
K21K−1211(n−m)×mK1211mm
Φ=⎡⎣⎢K1211K21K−1211⎤⎦⎥.
ΦΦΦT=⎡⎣⎢K1211K21K−1211⎤⎦⎥⎡⎣⎢K1211K21K−1211⎤⎦⎥T=⎡⎣⎢K1211K1211K21K−1211K1211K1211K−1211KT21K21K−1211K−1211KT21⎤⎦⎥=[K11K21KT21K21K−111KT21]=K.
Donc, tout ce que nous devons faire est de former notre modèle d'apprentissage régulier avec les fonctionnalités dimensionnelles . Ce sera exactement le même (sous les hypothèses que nous avons fait) que la version kernelized du problème d'apprentissage avec .mΦK
Maintenant, pour un point de données individuel , les fonctionnalités de correspondent à
Pour un point dans la partition 2, le vecteur n'est que la ligne appropriée de , de sorte que l'empilement cela nous donne - donc est d'accord pour les points de la partition 2. Cela fonctionne aussi dans la partition 1: là, le vecteur est une rangée de , donc les empiler devient , encore une fois d'accord avecxΦ
ϕ(x)=[k(x,x1)…k(x,xm)]K−1211.
x[k(x,x1)…k(x,xm)]K21K21K−1211ϕ(x)K11K11K−1211=K1211Φ. Donc ... c'est toujours vrai pour un point de test invisible au moment de la formation . Vous faites juste la même chose:
Parce que nous avons supposé que le noyau était de rang , la matrice est également de rang , et la reconstruction de est toujours exacte avec exactement la même logique que pour .
xnewΦtest=Ktest,1K−1211.
m[KtrainKtest,trainKtrain,testKtest]mKtestK22
Ci-dessus, nous avons supposé que la matrice du noyau était
exactement de rang . Ce ne sera généralement pas le cas; pour un noyau gaussien, par exemple, est
toujours de rang , mais ces dernières valeurs propres chutent assez rapidement, donc ça va être
proche d' une matrice de rang , et nos reconstructions de ou vont être
proches des vraies valeurs mais pas exactement les mêmes. Ce seront de meilleures reconstructions à mesure que l'espace propre de se rapprochera de celui de
KmKnmK21Ktest,1K11Kdans l'ensemble, c'est pourquoi le choix des bons points est important dans la pratique.
m
Notez également que si a des valeurs propres nulles, vous pouvez remplacer les inverses par des pseudoinverses et tout fonctionne toujours; vous venez de remplacer dans la reconstruction par .K11K21K21K†11K11
Vous pouvez utiliser le SVD au lieu de la composition eigend si vous le souhaitez; puisque est psd, c'est la même chose, mais le SVD pourrait être un peu plus robuste à une légère erreur numérique dans la matrice du noyau et ainsi, c'est ce que fait scikit-learn. L' implémentation réelle de scikit-learn fait cela, bien qu'elle utilise à l'inverse de la pseudoinverse.max ( λ i , 10 - 12 )Kmax(λi,10−12)