Incrustación semidefinida

El despliegue de máxima varianza (MVU) , también conocido como incrustación semidefinida (SDE), es un algoritmo en informática que utiliza programación semidefinida para realizar una reducción de dimensionalidad no lineal de datos de entrada vectoriales de alta dimensión . ^{[1] [2] [3]}

Está motivado por la observación de que el análisis de componentes principales del kernel (kPCA) no reduce la dimensionalidad de los datos, ^[4] ya que aprovecha el truco del kernel para mapear de manera no lineal los datos originales en un espacio de producto interno .

Algoritmo

MVU crea una asignación de los vectores de entrada de alta dimensión a un espacio vectorial euclidiano de baja dimensión en los siguientes pasos: ^[5]

1. Se crea un gráfico de vecindad . Cada entrada está conectada con sus k vectores de entrada más cercanos (según la métrica de distancia euclidiana) y todos los k vecinos más cercanos están conectados entre sí. Si los datos se muestrean lo suficientemente bien, el gráfico resultante es una aproximación discreta de la variedad subyacente.
2. El gráfico de vecindad se "despliega" con la ayuda de la programación semidefinida. En lugar de aprender los vectores de salida directamente, la programación semidefinida apunta a encontrar una matriz de producto interno que maximice las distancias por pares entre dos entradas cualesquiera que no estén conectadas en el gráfico de vecindad, mientras se preservan las distancias de los vecinos más cercanos.
3. La incrustación de baja dimensión se obtiene finalmente mediante la aplicación de escalamiento multidimensional en la matriz de producto interno aprendida.

Los pasos para aplicar programación semidefinida seguidos de un paso de reducción de dimensionalidad lineal para recuperar una incrustación de baja dimensión en un espacio euclidiano fueron propuestos por primera vez por Linial , London y Rabinovich. ^[6]

Formulación de optimización

Sea la entrada original y la incrustación. Si son dos vecinos, entonces la restricción de isometría local que se debe satisfacer es: ^{[7] [8] [9]} ${\displaystyle X\,\!}$ ${\displaystyle Y\,\!}$ ${\displaystyle i,j\,\!}$

${\displaystyle |X_{i}-X_{j}|^{2}=|Y_{i}-Y_{j}|^{2}\,\!}$

Sean las matrices de Gram de y (es decir: ). Podemos expresar la restricción anterior para cada punto vecino en términos de : ^{[10] [11]} ${\displaystyle G,K\,\!}$ ${\displaystyle X\,\!}$ ${\displaystyle Y\,\!}$ ${\displaystyle G_{ij}=X_{i}\cdot X_{j},K_{ij}=Y_{i}\cdot Y_{j}\,\!}$ ${\displaystyle i,j\,\!}$ ${\displaystyle G,K\,\!}$

${\displaystyle G_{ii}+G_{jj}-G_{ij}-G_{ji}=K_{ii}+K_{jj}-K_{ij}-K_{ji}\,\!}$

Además, también queremos restringir la incrustación al centro en el origen: ^{[12] [13] [14]} ${\displaystyle Y\,\!}$

${\displaystyle 0=|\sum _{i}Y_{i}|^{2}\Leftrightarrow (\sum _{i}Y_{i})\cdot (\sum _{i}Y_{i})\Leftrightarrow \sum _{i,j}Y_{i}\cdot Y_{j}\Leftrightarrow \sum _{i,j}K_{ij}}$

Como se describió anteriormente, excepto que se conservan las distancias de los puntos vecinos, el algoritmo apunta a maximizar la distancia por pares de cada par de puntos. La función objetivo que se debe maximizar es: ^{[15] [16] [17]}

${\displaystyle T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}}$

Intuitivamente, maximizar la función anterior equivale a alejar los puntos lo más posible entre sí y, por lo tanto, "desplegar" la variedad. La restricción de isometría local ^[18]

Deja donde ${\displaystyle \tau =max\{\eta _{ij}|Y_{i}-Y_{j}|^{2}\}\,\!}$ ${\displaystyle \eta _{ij}:={\begin{cases}1&{\mbox{if}}\ i{\mbox{ is a neighbour of }}j\\0&{\mbox{otherwise}}.\end{cases}}}$

evita que la función objetivo diverja (vaya al infinito).

Como el gráfico tiene N puntos, la distancia entre dos puntos cualesquiera es . Podemos entonces acotar la función objetivo de la siguiente manera: ^{[19] [20]} ${\displaystyle |Y_{i}-Y_{j}|^{2}\leq N\tau \,\!}$

${\displaystyle T(Y)={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}\leq {\dfrac {1}{2N}}\sum _{i,j}(N\tau )^{2}={\dfrac {N^{3}\tau ^{2}}{2}}\,\!}$

La función objetivo se puede reescribir puramente en la forma de la matriz de Gram: ^{[21] [22] [23]}

${\displaystyle {\begin{aligned}T(Y)&{}={\dfrac {1}{2N}}\sum _{i,j}|Y_{i}-Y_{j}|^{2}\\&{}={\dfrac {1}{2N}}\sum _{i,j}(Y_{i}^{2}+Y_{j}^{2}-Y_{i}\cdot Y_{j}-Y_{j}\cdot Y_{i})\\&{}={\dfrac {1}{2N}}(\sum _{i,j}Y_{i}^{2}+\sum _{i,j}Y_{j}^{2}-\sum _{i,j}Y_{i}\cdot Y_{j}-\sum _{i,j}Y_{j}\cdot Y_{i})\\&{}={\dfrac {1}{2N}}(\sum _{i,j}Y_{i}^{2}+\sum _{i,j}Y_{j}^{2}-0-0)\\&{}={\dfrac {1}{N}}(\sum _{i}Y_{i}^{2})={\dfrac {1}{N}}(Tr(K))\\\end{aligned}}\,\!}$

Finalmente, la optimización se puede formular como: ^{[24] [25] [26]}

${\displaystyle {\begin{aligned}&{\text{Maximize}}&&Tr(\mathbf {K} )\\&{\text{subject to}}&&\mathbf {K} \succeq 0,\sum _{ij}\mathbf {K} _{ij}=0\\&{\text{and}}&&G_{ii}+G_{jj}-G_{ij}-G_{ji}=K_{ii}+K_{jj}-K_{ij}-K_{ji},\forall i,j{\mbox{ where }}\eta _{ij}=1,\end{aligned}}}$

Una vez que se aprende la matriz de Gram mediante programación semidefinida, la salida se puede obtener mediante la descomposición de Cholesky . ${\displaystyle K\,\!}$ ${\displaystyle Y\,\!}$

En particular, la matriz de Gram se puede escribir como donde es el i-ésimo elemento del vector propio del valor propio . ^{[27] [28]} ${\displaystyle K_{ij}=\sum _{\alpha =1}^{N}(\lambda _{\alpha }V_{\alpha i}V_{\alpha j})\,\!}$ ${\displaystyle V_{\alpha i}\,\!}$ ${\displaystyle V_{\alpha }\,\!}$ ${\displaystyle \lambda _{\alpha }\,\!}$

De ello se deduce que el elemento -ésimo de la salida es . ^{[29] [30]} ${\displaystyle \alpha \,\!}$ ${\displaystyle Y_{i}\,\!}$ ${\displaystyle {\sqrt {\lambda _{\alpha }}}V_{\alpha i}\,\!}$

Véase también

• Incrustación lineal local
• Isometría (desambiguación)
• Alineación del espacio tangente local
• Variedad de Riemann
• Minimización de energía

Notas

1. Weinberger, Sha y Saul 2004a
2. Weinberger y Saul 2004b
3. Weinberger y Saul 2006
4. Lawrence 2012, página 1612
5. Weinberger, Sha y Saul 2004a, página 7.
6. Linial, Londres y Rabinovich 1995
7. Weinberger, Sha y Saul 2004a, página 3, ecuación 8
8. Weinberger y Saul 2004b, página 3, ecuación 2
9. Weinberger y Saul 2006, página 4, ecuación 2
10. Weinberger, Sha y Saul 2004a, página 3, ecuación 9
11. Weinberger y Saul 2004b, página 3, ecuación 3
12. Weinberger, Sha y Saul 2004a, página 3, ecuación 6
13. Weinberger y Saul 2004b, página 3, ecuación 5
14. Weinberger y Saul 2006, página 5, ecuación 8
15. Weinberger, Sha y Saul 2004a, página 4, ecuación 10
16. Weinberger y Saul 2004b, página 4, ecuación 6
17. Weinberger y Saul 2006, página 5, ecuación 4
18. Weinberger y Saul 2004b, página 4, ecuación 7
19. Weinberger y Saul 2004b, página 4, ecuación 8
20. Weinberger y Saul 2006, página 5, ecuación 6
21. Weinberger, Sha y Saul 2004a, página 4, ecuación 11
22. Weinberger y Saul 2004b, página 4, ecuación 9
23. Weinberger y Saul 2006, página 6, ecuaciones 10 a 13
24. Weinberger, Sha y Saul 2004a, página 4, sección 3.3
25. Weinberger y Saul 2004b, página 4, ecuación 9
26. Weinberger y Saul 2006, página 6, ecuaciones 10 a 13
27. Weinberger y Saul 2004b, página 4, ecuación 10
28. Weinberger y Saul 2006, página 7, ecuaciones 14
29. Weinberger y Saul 2004b, página 4, ecuación 11
30. Weinberger y Saul 2006, página 7, ecuaciones 15

Referencias

• Linial, London y Rabinovich, Nathan, Eran y Yuri (1995). "La geometría de grafos y algunas de sus aplicaciones algorítmicas". Combinatorica . 15 (2): 215–245. doi :10.1007/BF01200757. S2CID  5071936.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Weinberger, Sha y Saul, Kilian Q., Fei y Lawrence K. (4 de julio de 2004a). Aprendizaje de una matriz de núcleo para reducción de dimensionalidad no lineal. Actas de la Vigésima Primera Conferencia Internacional sobre Aprendizaje Automático (ICML 2004). Banff, Alberta , Canadá.{{cite conference}}: CS1 maint: multiple names: authors list (link)
• Weinberger y Saul, Kilian Q. y Lawrence K. (27 de junio de 2004b). Aprendizaje no supervisado de variedades de imágenes mediante programación semidefinida. Conferencia de la IEEE Computer Society de 2004 sobre visión artificial y reconocimiento de patrones. Vol. 2.
• Weinberger y Saul, Kilian Q. y Lawrence K. (1 de mayo de 2006). "Aprendizaje no supervisado de variedades de imágenes mediante programación semidefinida" (PDF) . Revista internacional de visión por computadora . 70 : 77–90. doi :10.1007/s11263-005-4939-z. S2CID  291166.
• Lawrence, Neil D (2012). "Una perspectiva probabilística unificadora para la reducción de la dimensionalidad espectral: perspectivas y nuevos modelos". Journal of Machine Learning Research . 13 (mayo): 1612. arXiv : 1010.4830 . Código Bibliográfico :2010arXiv1010.4830L.

Material adicional

• Código Matlab MVU de Kilian Q. Weinberger