Método de Nystroem para la aproximación del núcleo

He estado leyendo sobre el método de Nyström para la aproximación de kernel de bajo rango. Este método se implementa en scikit-learn [1] como un método para proyectar muestras de datos a una aproximación de bajo rango del mapeo de características del núcleo.

A lo mejor de mi conocimiento, dado un conjunto de entrenamiento y una función del núcleo, se genera una aproximación de bajo rango de la n × n del núcleo matriz K aplicando SVD a W y C .$\{x_i\}_{i=1}^n$$n \times n$$K$$W$$C$

C = [ W K 21 ] , W ∈ R l × $K = \left [ \begin{array}{cc} W & K_{21}^T \\ K_{21} & K_{22} \end{array} \right ]$ $C = \left [\begin{array}{cc} W \\ K_{21} \end{array}\right ]$$W \in \mathbb{R}^{l\times l}$

Sin embargo, no entiendo cómo la aproximación de bajo rango de la matriz Kernel se puede utilizar para proyectar nuevas muestras en el espacio de características del kernel aproximado . Los documentos que he encontrado (por ejemplo, [2]) no son de gran ayuda, ya que son poco didácticos.

Además, tengo curiosidad acerca de la complejidad computacional de este método, tanto en las fases de entrenamiento como de prueba.

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

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

Derivemos la aproximación de Nyström de una manera que aclare las respuestas a sus preguntas.

La suposición clave en Nyström es que la función del núcleo es de rango . (Realmente suponemos que es aproximadamente de rango m , pero por simplicidad, supongamos que es exactamente rango m por ahora). Eso significa que cualquier matriz del núcleo tendrá rango como máximo m , y en particular K = [ k ( x 1 , x 1 ) … k ( x 1 , x n ) ⋮ ⋱ ⋮ k ( x $m$$m$$m$$m$ es el rangom. Por lo tanto, haymvalores propios distintos de cero, y podemos escribir la descomposición propia deKcomo K=UΛUT con vectores propios almacenados enU, de forman×m, y valores propios dispuestos enΛ, unamatriz diagonalm×m.

$$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} ,$$ $m$$m$$K$ $$K = U \Lambda U^T$$ $U$$n \times m$$\Lambda$$m \times m$

Entonces, escojamos elementos, generalmente de manera uniforme al azar, pero posiblemente de acuerdo con otros esquemas; todo lo que importa en esta versión simplificada es que K 11 sea ​​de rango completo. Una vez que lo hagamos, simplemente vuelva a etiquetar los puntos para que terminemos con la matriz del núcleo en bloques: K = [ K 11 K T 21 K 21 K 22 ] , donde evaluamos cada entrada en K 11 (que es m × m ) y K 21 ( ( n - m ) × $m$$K_{11}$

$$K = \begin{bmatrix} K_{11} & K_{21}^T \\ K_{21} & K_{22} \end{bmatrix} ,$$ $K_{11}$$m \times m$$K_{21}$$(n-m) \times m$), pero no desea evaluar ninguna entrada en .$K_{22}$

Ahora, también podemos dividir la descomposición propia de acuerdo con esta estructura de bloques: dondeU1esm×myT2es(n-m)×m. Pero tenga en cuenta que ahora tenemosK11=U1ΛU T 1 . Para que podamos encontrar

$$\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{align}$$ $U_1$$m \times m$$U_2$$(n-m) \times m$$K_{11} = U_1 \Lambda U_1^T$ y Λ por descomposición de la matriz conocida K 11 .$U_1$$\Lambda$$K_{11}$

También sabemos que . 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 ( Λ U T 1 ) - 1 = U 1 Λ - 1 para obtener U 2 = K 21 U 1 Λ - 1 . Ahora tenemos todo lo que necesitamos para evaluar K 22 : K $K_{21} = U_2 \Lambda U_1^T$$U_2$$(\Lambda U_1^T)^{-1} = U_1 \Lambda^{-1}$

$$U_2 = K_{21} U_1 \Lambda^{-1} .$$ $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 (*), encontramos una versión de la incrustación de Nyström que podría haber visto simplemente como la definición. Esto nos dice los valores efectivos del núcleo que estamos imputando para el bloque .$K_{22}$

En (**), vemos que la matriz de características , que es forma(n-m)×m, corresponde a estos valores de núcleo imputados. Si usamosK$K_{21} K_{11}^{-\frac12}$$(n-m) \times m$para lospuntosm, tenemos un conjunto decaracterísticasm-dimensionales Φ=[K$K_{11}^{\frac12}$$m$$m$ Podemos verificar rápidamente queΦcorresponde a la matriz correcta del núcleo: ΦΦ

$$\Phi = \begin{bmatrix} K_{11}^{\frac12} \\ K_{21} K_{11}^{-\frac12} \end{bmatrix} .$$ $\Phi$ $$\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}$$

$m$$\Phi$$K$

$x$$\Phi$

$$\phi(x) = \begin{bmatrix} k(x, x_1) & \dots & k(x, x_m) \end{bmatrix} K_{11}^{-\frac12} .$$ $x$$\begin{bmatrix} k(x, x_1) & \dots & k(x, x_m) \end{bmatrix}$$K_{21}$$K_{21} K_{11}^{-\frac12}$$\phi(x)$$K_{11}$$K_{11} K_{11}^{-\frac12} = K_{11}^{\frac12}$$\Phi$$x_\text{new}$ $$\Phi_\text{test} = K_{\text{test},1} K_{11}^{-\frac12} .$$ $m$$\begin{bmatrix}K_{\text{train}} & K_{\text{train,test}} \\ K_{\text{test,train}} & K_{\text{test}} \end{bmatrix}$$m$$K_\text{test}$$K_{22}$

---

Arriba, supusimos que la matriz del núcleo tenía exactamente el rango m . Este no suele ser el caso; para un núcleo gaussiano, por ejemplo, K siempre es de rango n , pero los últimos valores propios generalmente disminuyen bastante rápido, por lo que va a estar cerca de una matriz de rango m , y nuestras reconstrucciones de K 21 o K test , 1 van estar cerca de los valores verdaderos pero no exactamente lo mismo. Serán mejores reconstrucciones cuanto más se acerque el espacio propio de K 11 al de$K$$m$$K$$n$$m$$K_{21}$$K_{\text{test},1}$$K_{11}$ general, por lo que elegir lospuntos m correctoses importante en la práctica.$K$$m$

Tenga en cuenta también que si tiene valores propios cero, puede reemplazar los inversos con pseudoinversiones y todo sigue funcionando; simplemente reemplaza K 21 en la reconstrucción con K 21 K † 11 K 11 .$K_{11}$$K_{21}$$K_{21} K_{11}^\dagger K_{11}$

$K$$\max(\lambda_i, 10^{-12})$