Aproximaciones de matrices de bajo rango

Las aproximaciones matriciales de bajo rango son herramientas esenciales en la aplicación de métodos kernel a problemas de aprendizaje a gran escala . ^[1]

Los métodos kernel (por ejemplo, máquinas de vectores de soporte o procesos gaussianos ^[2] ) proyectan puntos de datos en un espacio de características de alta dimensión o de dimensión infinita y encuentran el hiperplano de división óptimo. En el método kernel, los datos se representan en una matriz kernel (o matriz de Gram ). Muchos algoritmos pueden resolver problemas de aprendizaje automático utilizando la matriz kernel . El principal problema del método kernel es su alto costo computacional asociado con las matrices kernel . El costo es al menos cuadrático en el número de puntos de datos de entrenamiento, pero la mayoría de los métodos kernel incluyen el cálculo de la inversión de la matriz o la descomposición de valores propios y el costo se vuelve cúbico en el número de datos de entrenamiento. Los grandes conjuntos de entrenamiento causan grandes costos de almacenamiento y computacionales . Si bien los métodos de descomposición de bajo rango ( descomposición de Cholesky ) reducen este costo, aún requieren el cálculo de la matriz kernel . Uno de los enfoques para abordar este problema son las aproximaciones matriciales de bajo rango. Los ejemplos más populares de ellos son el método de Nyström y las características aleatorias. Ambos se han aplicado con éxito al aprendizaje kernel eficiente.

Aproximación de Nyström

Los métodos del kernel se vuelven inviables cuando el número de puntos es tan grande que la matriz del kernel no se puede almacenar en la memoria. ${\displaystyle n}$ ${\displaystyle {\hat {K}}}$

Si es el número de ejemplos de entrenamiento, el costo de almacenamiento y computacional requerido para encontrar la solución del problema usando el método kernel general es y respectivamente. La aproximación de Nyström puede permitir una aceleración significativa de los cálculos. ^{[2] [3]} Esta aceleración se logra utilizando, en lugar de la matriz kernel, su aproximación de rango . Una ventaja del método es que no es necesario calcular o almacenar toda la matriz kernel, sino solo una submatriz de tamaño . ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle {\tilde {K}}}$ ${\displaystyle q}$ ${\displaystyle q\times n}$

Reduce los requisitos de almacenamiento y complejidad a y respectivamente. ${\displaystyle O(nq)}$ ${\displaystyle O(nq^{2})}$

El método se denomina "aproximación de Nyström" porque puede interpretarse como un caso del método de Nyström de la teoría de ecuaciones integrales . ^[3]

Teorema de aproximación del núcleo

${\displaystyle {\hat {K}}}$es una matriz de kernel para algún método de kernel . Considere los primeros puntos en el conjunto de entrenamiento. Entonces existe una matriz de rango : ${\displaystyle q<n}$ ${\displaystyle {\tilde {K}}}$ ${\displaystyle q}$

${\displaystyle {\tilde {K}}={\hat {K}}_{n,q}{\hat {K}}_{q}^{-1}{\hat {K}}_{n,q}^{\text{T}}}$, dónde

${\displaystyle ({\hat {K}}_{q})_{i,j}=K(x_{i},x_{j}),i,j=1,\dots ,q}$,

${\displaystyle {\hat {K}}_{q}}$es matriz invertible

y

${\displaystyle ({\hat {K}}_{n,q})_{i,j}=K(x_{i},x_{j}),i=1,\dots ,n{\text{ and }}j=1,\dots ,q.}$

Prueba

Aplicación de descomposición en valores singulares

La aplicación de la descomposición en valores singulares (SVD) a una matriz con dimensiones produce un sistema singular que consta de vectores de valores singulares y tales que forman bases ortonormales de y respectivamente: ${\displaystyle A}$ ${\displaystyle p\times m}$ ${\displaystyle \{\sigma _{j}\}_{j=1}^{k},{\text{ }}(\sigma _{j}>0{\text{ }}\forall j=1,\dots ,k),}$ ${\displaystyle \{v_{j}\}_{j=1}^{m}\in \mathbb {C} ^{m}}$ ${\displaystyle \{u_{j}\}_{j=1}^{p}\in \mathbb {C} ^{p}}$ ${\displaystyle \mathbb {C} ^{m}}$ ${\displaystyle \mathbb {C} ^{p}}$

$${\displaystyle {\begin{cases}A^{\text{T}}Av_{j}=\sigma _{j}v_{j},{\text{ }}j=1,\dots ,k,\\A^{\text{T}}Av_{j}=0,{\text{ }}j=k+1,\dots ,m,\\AA^{\text{T}}u_{j}=\sigma _{j}u_{j},{\text{ }}j=1,\dots ,k,\\AA^{\text{T}}u_{j}=0,{\text{ }}j=k+1,\dots ,p.\end{cases}}}$$

Si y son matrices con 's y 's en las columnas y es una matriz diagonal que tiene valores singulares en las primeras entradas de la diagonal (todos los demás elementos de la matriz son ceros): ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \Sigma }$ ${\displaystyle p\times m}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle k}$

$${\displaystyle {\begin{cases}Av_{j}={\sqrt {\sigma _{j}}}u_{j},{\text{ }}j=1,\dots ,k,\\Av_{j}=0,{\text{ }}j=k+1,\dots ,m,\\A^{\text{T}}u_{j}={\sqrt {\sigma _{j}}}v_{j},{\text{ }}j=1,\dots ,k,\\A^{\text{T}}u_{j}=0,{\text{ }}j=k+1,\dots ,p,\end{cases}}}$$

Entonces la matriz se puede reescribir como: ^[4] ${\displaystyle A}$

$${\displaystyle A=U\Sigma ^{1/2}V^{\text{T}}.}$$

Más pruebas

• ${\displaystyle {\hat {X}}}$es matriz de datos ${\displaystyle n\times D}$
• ${\displaystyle {\hat {K}}={\hat {X}}{\hat {X}}^{\text{T}}}$
• ${\displaystyle {\hat {C}}={\hat {X}}^{\text{T}}{\hat {X}}}$

Aplicando la descomposición en valores singulares a estas matrices: $${\displaystyle {\hat {X}}={\hat {U}}{\hat {\Sigma }}^{1/2}{\hat {V}}^{\text{T}},{\text{ }}{\hat {K}}={\hat {U}}{\hat {\Sigma }}{\hat {U}}^{T},{\text{ }}{\hat {C}}={\hat {V}}{\hat {\Sigma }}{\hat {V}}^{\text{T}}.}$$

• ${\displaystyle {\hat {X}}_{q}}$es la matriz -dimensional que consta de las primeras filas de la matriz ${\displaystyle q\times D}$ ${\displaystyle q}$ ${\displaystyle {\hat {X}}}$
• ${\displaystyle {\hat {K}}_{q}={\hat {X}}_{q}{\hat {X}}_{q}^{\text{T}}}$
• ${\displaystyle {\hat {C}}_{q}={\hat {X}}_{q}^{\text{T}}{\hat {X}}_{q}}$

Aplicando la descomposición en valores singulares a estas matrices:

${\displaystyle {\hat {X}}_{q}={\hat {U}}_{q}{\hat {\Sigma }}_{q}^{1/2}{\hat {V}}_{q}^{\text{T}},{\text{ }}{\hat {K}}_{q}={\hat {U}}_{q}{\hat {\Sigma }}_{q}{\hat {U}}_{q}^{T},{\text{ }}{\hat {C}}_{q}={\hat {V}}_{q}{\hat {\Sigma }}_{q}{\hat {V}}_{q}^{\text{T}}.}$

Dado que son matrices ortogonales , ${\displaystyle {\hat {U}},{\text{ }}{\hat {V}},{\hat {U}}_{q}{\text{ and }}{\hat {V}}_{q}}$

$${\displaystyle {\hat {U}}={\hat {X}}{\hat {V}}{\hat {\Sigma }}^{-1/2},{\text{ }}{\hat {V}}_{q}={\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1/2}.}$$

Reemplazando por y , se puede obtener una aproximación para : ${\displaystyle {\hat {V}},{\hat {\Sigma }}}$ ${\displaystyle {\hat {V}}_{q}}$ ${\displaystyle {\hat {\Sigma }}_{q}}$ ${\displaystyle {\hat {U}}}$

${\displaystyle {\tilde {U}}={\hat {X}}{\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1}}$( no es necesariamente una matriz ortogonal ). ${\displaystyle {\tilde {U}}}$

Sin embargo, al definirlo , se puede calcular de la siguiente manera: ${\displaystyle {\tilde {K}}={\tilde {U}}{\hat {\Sigma }}_{q}{\tilde {U}}^{\text{T}}}$

$${\displaystyle {\begin{aligned}{\tilde {K}}={\tilde {U}}{\hat {\Sigma }}_{q}{\tilde {U}}^{\text{T}}={\hat {X}}{\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1}{\hat {\Sigma }}_{q}({\hat {X}}{\hat {X}}_{q}^{\text{T}}{\hat {U}}_{q}{\hat {\Sigma }}_{q}^{-1})^{\text{T}}\\={\hat {X}}{\hat {X}}_{q}^{\text{T}}{\big \{}{\hat {U}}_{q}({\hat {\Sigma }}_{q}^{-1})^{\text{T}}{\hat {U}}_{q}^{\text{T}}{\big \}}({\hat {X}}{\hat {X}}_{q}^{\text{T}})^{\text{T}}\\\end{aligned}}}$$

Por la caracterización de la matriz ortogonal : se cumple la igualdad. Luego, utilizando la fórmula para la inversa de la multiplicación de matrices para matrices invertibles y , la expresión entre llaves se puede reescribir como: ${\displaystyle {\hat {U}}_{q}}$ ${\displaystyle ({\hat {U}}_{q})^{\text{T}}=({\hat {U}}_{q})^{-1}}$ ${\displaystyle (AB)^{-1}=B^{-1}A^{-1}}$ ${\displaystyle A}$ ${\displaystyle B}$

$${\displaystyle {\hat {U}}_{q}({\hat {\Sigma }}_{q}^{-1})^{\text{T}}{\hat {U}}_{q}^{\text{T}}=({\hat {U}}_{q}{\hat {\Sigma }}_{q}^{\text{T}}{\hat {U}}_{q}^{\text{T}})^{-1}=({\hat {K}}_{q})^{-1}.}$$

Entonces la expresión para : ${\displaystyle {\tilde {K}}}$ $${\displaystyle {\tilde {K}}=({\hat {X}}{\hat {X}}_{q}^{\text{T}}){\hat {K}}_{q}^{-1}({\hat {X}}{\hat {X}}_{q}^{\text{T}})^{\text{T}}.}$$

Definiendo , la prueba está terminada. ${\displaystyle {\hat {K}}_{n,q}={\hat {X}}{\hat {X}}_{q}^{\text{T}}}$

Teorema general para la aproximación del núcleo para un mapa de características

Para un mapa de características con kernel asociado : la igualdad también se obtiene reemplazando por el operador tal que , , , y por el operador tal que , , . Una vez más, una inspección simple muestra que el mapa de características solo es necesario en la prueba, mientras que el resultado final solo depende del cálculo de la función kernel. ${\displaystyle \Phi :{\mathcal {X}}\to {\mathcal {F}}}$ ${\displaystyle K(x,x')=\langle \Phi (x),\Phi (x')\rangle _{\mathcal {F}}}$ ${\displaystyle {\hat {K}}={\hat {K}}_{n,q}{\hat {K}}_{q}^{-1}{\hat {K}}_{n,q}^{\text{T}}}$ ${\displaystyle {\hat {X}}}$ ${\displaystyle {\hat {\Phi }}:{\mathcal {F}}\to \mathbb {R} ^{n}}$ ${\displaystyle \langle {\hat {\Phi }}w\rangle _{i}=\langle \Phi (x_{i}),w\rangle _{\mathcal {F}}}$ ${\displaystyle {\text{ }}i=1,\dots ,n}$ ${\displaystyle w\in {\mathcal {F}}}$ ${\displaystyle {\hat {X}}_{q}}$ ${\displaystyle {\hat {\Phi }}_{q}:{\mathcal {F}}\to \mathbb {R} ^{q}}$ ${\displaystyle \langle {\hat {\Phi }}_{q}w\rangle _{i}=\langle \Phi (x_{i}),w\rangle _{\mathcal {F}}}$ ${\displaystyle {\text{ }}i=1,\dots ,q}$ ${\displaystyle w\in {\mathcal {F}}}$

Aplicación de mínimos cuadrados regularizados

En notación vectorial y kernel, el problema de mínimos cuadrados regularizados se puede reescribir como: Calculando el gradiente y estableciendo en 0, se puede obtener el mínimo: La matriz inversa se puede calcular utilizando la identidad matricial de Woodbury : $${\displaystyle \min _{c\in \mathbb {R} ^{n}}{\frac {1}{n}}\|{\hat {Y}}-{\hat {K}}c\|_{\mathbb {R} ^{n}}^{2}+\lambda \langle c,{\hat {K}}c\rangle _{\mathbb {R} ^{n}}.}$$ $${\displaystyle {\begin{aligned}&-{\frac {1}{n}}{\hat {K}}({\hat {Y}}-{\hat {K}}c)+\lambda {\hat {K}}c=0\\\Rightarrow {}&{\hat {K}}({\hat {K}}+\lambda nI)c={\hat {K}}{\hat {Y}}\\\Rightarrow {}&c=({\hat {K}}+\lambda nI)^{-1}{\hat {Y}},{\text{ where }}c\in \mathbb {R} ^{n}\end{aligned}}}$$ ${\displaystyle ({\hat {K}}+\lambda nI)^{-1}}$ $${\displaystyle {\begin{aligned}({\hat {K}}+\lambda nI)^{-1}&={\frac {1}{\lambda n}}\left({\frac {1}{\lambda n}}{\hat {K}}+I\right)^{-1}\\&={\frac {1}{\lambda n}}\left(I+{\hat {K}}_{n,q}({\lambda n}{\hat {K}}_{q})^{-1}{\hat {K}}_{n,q}^{\text{T}}\right)^{-1}\\&={\frac {1}{\lambda n}}\left(I-{\hat {K}}_{n,q}(\lambda n{\hat {K}}_{q}+{\hat {K}}_{n,q}^{\text{T}}{\hat {K}}_{n,q})^{-1}{\hat {K}}_{n,q}^{\text{T}}\right)\end{aligned}}}$$

Tiene los requisitos de almacenamiento y complejidad deseados.

Aproximación de mapas de características aleatorias

Sea – muestras de datos, – un mapa de características aleatorio (mapea un solo vector a un vector de mayor dimensionalidad) de modo que el producto interno entre un par de puntos transformados se aproxime a su evaluación de kernel : ${\displaystyle \mathbf {x} ,\mathbf {x'} \in \mathbb {R} ^{d}}$ ${\displaystyle z:\mathbb {R} ^{d}\to \mathbb {R} ^{D}}$

$${\displaystyle K(\mathbf {x} ,\mathbf {x'} )=\langle \Phi (\mathbf {x} ),\Phi (\mathbf {x'} )\rangle \approx z(\mathbf {x} )^{\text{T}}z(\mathbf {x'} ),}$$¿Dónde está el mapeo incrustado en el kernel RBF ? ${\displaystyle \Phi }$

Dado que es de baja dimensión, la entrada se puede transformar fácilmente con , después de eso se pueden aplicar diferentes métodos de aprendizaje lineal para aproximar la respuesta del núcleo no lineal correspondiente. Existen diferentes mapas de características aleatorizados para calcular las aproximaciones a los núcleos RBF. Por ejemplo, características aleatorias de Fourier y características de binning aleatorio . ${\displaystyle z}$ ${\displaystyle z}$

Características aleatorias de Fourier

El mapa de características aleatorias de Fourier produce una aproximación de Monte Carlo al mapa de características. El método de Monte Carlo se considera aleatorio. Estas características aleatorias consisten en sinusoides extraídas aleatoriamente de la transformada de Fourier del núcleo que se va a aproximar, donde y son variables aleatorias . La línea se elige aleatoriamente y luego los puntos de datos se proyectan sobre ella mediante las asignaciones. El escalar resultante pasa por una sinusoide. El producto de los puntos transformados se aproximará a un núcleo invariante al desplazamiento. Dado que el mapa es suave, las características aleatorias de Fourier funcionan bien en tareas de interpolación. ${\displaystyle \cos(w^{\text{T}}\mathbf {x} +b)}$ ${\displaystyle w\in \mathbb {R} ^{d}}$ ${\displaystyle b\in \mathbb {R} }$

Funciones de clasificación aleatoria

Un mapa de características de binning aleatorio divide el espacio de entrada utilizando cuadrículas desplazadas aleatoriamente con resoluciones elegidas aleatoriamente y asigna a un punto de entrada una cadena de bits binarios que corresponde a los bins en los que cae. Las cuadrículas se construyen de modo que la probabilidad de que dos puntos se asignen al mismo bin sea proporcional a . El producto interno entre un par de puntos transformados es proporcional a la cantidad de veces que los dos puntos se agrupan juntos y, por lo tanto, es una estimación imparcial de . Dado que este mapeo no es uniforme y utiliza la proximidad entre los puntos de entrada, las características de binning aleatorio funcionan bien para aproximar núcleos que dependen solo de la distancia entre los puntos de datos. ${\displaystyle \mathbf {x} ,\mathbf {x'} \in \mathbb {R} ^{d}}$ ${\displaystyle K(\mathbf {x} ,\mathbf {x'} )}$ ${\displaystyle K(\mathbf {x} ,\mathbf {x'} )}$ ${\displaystyle L_{1}}$

Comparación de métodos de aproximación

Los enfoques para el aprendizaje de kernel a gran escala ( método Nyström y características aleatorias) difieren en el hecho de que el método Nyström utiliza funciones de base dependientes de los datos, mientras que en el enfoque de características aleatorias las funciones de base se muestrean a partir de una distribución independiente de los datos de entrenamiento. Esta diferencia conduce a un análisis mejorado para los enfoques de aprendizaje de kernel basados ​​en el método Nyström. Cuando hay una gran brecha en el espectro propio de la matriz kernel , los enfoques basados ​​en el método Nyström pueden lograr mejores resultados que el enfoque basado en características aleatorias . ^[5]

Véase también

• Método de Nyström
• Máquina de vectores de soporte
• Núcleo de función de base radial
• Mínimos cuadrados regularizados

Enlaces externos

• Andreas Müller (2012). Aproximaciones de kernel para SVM eficientes (y otros métodos de extracción de características).

Referencias

1. Francis R. Bach y Michael I. Jordan (2005). "Descomposición predictiva de bajo rango para métodos de kernel". ICML .
2. Williams, CKI; Seeger, M. (2001). "Uso del método Nyström para acelerar las máquinas de núcleo". Avances en sistemas de procesamiento de información neuronal . 13 .
3. Petros Drineas y Michael W. Mahoney (2005). "Sobre el método Nyström para aproximar una matriz de Gram para mejorar el aprendizaje basado en kernel". Journal of Machine Learning Research 6 , págs. 2153–2175.
4. C. Eckart, G. Young, La aproximación de una matriz por otra de rango inferior. Psychometrika, Volumen 1, 1936, Páginas 211–8. doi :10.1007/BF02288367
5. Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin y Zhi-Hua Zhou (2012). "Método Nyström vs. características aleatorias de Fourier: una comparación teórica y empírica". Advances in Neural Information Processing Systems 25 (NIPS) .