Vamos a derivar la aproximación de Nyström de forma que las respuestas a tus preguntas queden más claras.
El supuesto clave de Nyström es que la función de núcleo es de rango $m$ . (Realmente suponemos que es aproximadamente de rango $m$ pero para simplificar vamos a fingir que es exactamente rango $m$ por ahora). Esto significa que cualquier matriz del núcleo va a tener rango como máximo $m$ , y en particular $$ K = \begin{bmatrix} k(x_1, x_1) & \dots & k(x_1, x_n) \\ \vdots & \ddots & \vdots \\ k(x_n, x_1) & \dots & k(x_n, x_n) \end{bmatrix} ,$$ es el rango $m$ . Por lo tanto, hay $m$ valores propios no nulos, y podemos escribir la eigendecomposición de $K$ como $$K = U \Lambda U^T$$ con los vectores propios almacenados en $U$ de forma $n \times m$ , y los valores propios dispuestos en $\Lambda$ , an $m \times m$ matriz diagonal.
Así que, elijamos $m$ elementos, normalmente de manera uniforme al azar pero posiblemente según otros esquemas - todo lo que importa en esta versión simplificada es que $K_{11}$ ser de rango completo. Una vez que lo hagamos, basta con reetiquetar los puntos para que acabemos con la matriz del núcleo en bloques: $$ K = \begin{bmatrix} K_{11} & K_{21}^T \\ K_{21} & K_{22} \end{bmatrix} ,$$ donde evaluamos cada entrada en $K_{11}$ (que es $m \times m$ ) y $K_{21}$ ( $(n-m) \times m$ ), pero no desea evaluar ninguna entrada en $K_{22}$ .
Ahora, también podemos dividir la eigendecomposición según esta estructura de bloques: \begin{align} K &= U \Lambda U^T \\&= \begin{bmatrix}U_1 \\ U_2\end{bmatrix} \Lambda \begin{bmatrix}U_1 \\ U_2\end{bmatrix} ^T \\&= \begin{bmatrix} U_1 \Lambda U_1^T & U_1 \Lambda U_2^T \\ U_2 \Lambda U_1^T & U_2 \Lambda U_2^T \end{bmatrix} end donde $U_1$ es $m \times m$ y $U_2$ es $(n-m) \times m$ . Pero tenga en cuenta que ahora tenemos $K_{11} = U_1 \Lambda U_1^T$ . Así que podemos encontrar $U_1$ y $\Lambda$ eigendecomponiendo la matriz conocida $K_{11}$ .
También sabemos que $K_{21} = U_2 \Lambda U_1^T$ . Aquí, sabemos todo en esta ecuación excepto $U_2$ por lo que podemos resolver qué valores propios implica: multiplicar a la derecha ambos lados por $(\Lambda U_1^T)^{-1} = U_1 \Lambda^{-1}$ para obtener $$ U_2 = K_{21} U_1 \Lambda^{-1} .$$ Ahora tenemos todo lo que necesitamos para evaluar $K_{22}$ : \begin{align} K_{22} &= U_2 \Lambda U_2^T \\&= \left(K_{21} U_1 \Lambda^{-1}\right) \Lambda \left(K_{21} U_1 \Lambda^{-1}\right)^T \\&= K_{21} U_1 (\Lambda^{-1} \Lambda) \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} U_1 \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} K_{11}^{-1} K_{21}^T \tag{*} \\&= \left( K_{21} K_{11}^{-\frac12} \right) \left( K_{21} K_{11}^{-\frac12} \right)^T \tag{**} .\end{align}
En (*), hemos encontrado una versión de la incrustación de Nyström que podría haber visto simplemente como la definición. Esto nos indica los valores efectivos del núcleo que estamos imputando para el bloque $K_{22}$ .
En (**), vemos que el matriz de características $K_{21} K_{11}^{-\frac12}$ que es la forma $(n-m) \times m$ corresponde a estos valores de núcleo imputados. Si utilizamos $K_{11}^{\frac12}$ para la $m$ puntos, tenemos un conjunto de $m$ -características dimensionales $$ \Phi = \begin{bmatrix} K_{11}^{\frac12} \\ K_{21} K_{11}^{-\frac12} \end{bmatrix} .$$ Podemos verificar rápidamente que $\Phi$ corresponde a la matriz correcta del núcleo: \begin{align} \Phi \Phi^T &= \begin{bmatrix} K_{11}^{\frac12} \\ K_{21} K_{11}^{-\frac12} \end{bmatrix} \begin{bmatrix} K_{11}^{\frac12} \\ K_{21} K_{11}^{-\frac12} \end{bmatrix} ^T \\&= \begin{bmatrix} K_{11}^{\frac12} K_{11}^{\frac12} & K_{11}^{\frac12} K_{11}^{-\frac12} K_{21}^T \\ K_{21} K_{11}^{-\frac12} K_{11}^{\frac12} & K_{21} K_{11}^{-\frac12} K_{11}^{-\frac12} K_{21}^T \end{bmatrix} \\&= \begin{bmatrix} K_{11} & K_{21}^T \\ K_{21} & K_{21} K_{11}^{-1} K_{21}^T \end{bmatrix} \\&= K .\end{align}
Por lo tanto, todo lo que tenemos que hacer es entrenar nuestro modelo de aprendizaje regular con el $m$ -características dimensionales $\Phi$ . Esto será exactamente el mismo (bajo las suposiciones que hemos hecho) que la versión kernelizada del problema de aprendizaje con $K$ .
Ahora, para un punto de datos individual $x$ las características de $\Phi$ corresponden a $$ \phi(x) = \begin{bmatrix} k(x, x_1) & \dots & k(x, x_m) \end{bmatrix} K_{11}^{-\frac12} .$$ Para un punto $x$ en la partición 2, el vector $\begin{bmatrix} k(x, x_1) & \dots & k(x, x_m) \end{bmatrix}$ es sólo la fila correspondiente de $K_{21}$ de modo que apilándolos nos da $K_{21} K_{11}^{-\frac12}$ - así $\phi(x)$ coincide para los puntos de la partición 2. También funciona en la partición 1: allí, el vector es una fila de $K_{11}$ por lo que apilarlos $K_{11} K_{11}^{-\frac12} = K_{11}^{\frac12}$ , de nuevo de acuerdo con $\Phi$ . Así que ... sigue siendo cierto para un punto de prueba no visto en el momento de la formación $x_\text{new}$ . Tú haz lo mismo: $$ \Phi_\text{test} = K_{\text{test},1} K_{11}^{-\frac12} .$$ Porque asumimos que el núcleo es de rango $m$ la matriz $\begin{bmatrix}K_{\text{train}} & K_{\text{train,test}} \\ K_{\text{test,train}} & K_{\text{test}} \end{bmatrix}$ también es de rango $m$ y la reconstrucción de $K_\text{test}$ sigue siendo exacta por exactamente la misma lógica que para $K_{22}$ .
Anteriormente, asumimos que la matriz del núcleo $K$ fue exactamente rango $m$ . Esto no suele ser así; por ejemplo, para un núcleo gaussiano, $K$ es siempre rango $n$ pero los últimos valores propios caen bastante rápido, así que va a ser cerca de una matriz de rango $m$ y nuestras reconstrucciones de $K_{21}$ o $K_{\text{test},1}$ van a ser cerca de los valores verdaderos pero no exactamente iguales. Serán mejores reconstrucciones cuanto más se acerque el eigespacio de $K_{11}$ llega a la de $K$ en general, por lo que elegir el $m$ puntos es importante en la práctica.
Tenga en cuenta también que si $K_{11}$ tiene cualquier valor propio cero, se pueden sustituir los inversos por pseudoinversos y todo sigue funcionando; basta con sustituir $K_{21}$ en la reconstrucción con $K_{21} K_{11}^\dagger K_{11}$ .
Si lo desea, puede utilizar la SVD en lugar de la eigendecomposición, ya que $K$ es psd, son la misma cosa, pero el SVD podría ser un poco más robusto a un ligero error numérico en la matriz del núcleo y tal, así que eso es lo que hace scikit-learn. scikit-learn's aplicación real lo hace, aunque utiliza $\max(\lambda_i, 10^{-12})$ en el inverso en lugar del pseudoinverso.
