Incrustación semidefinida

El despliegue de varianza máxima (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 forma no lineal los datos originales en un espacio de producto interno .

Algoritmo

MVU crea un mapeo de los vectores de entrada de alta dimensión a algún 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 programación semidefinida. En lugar de aprender los vectores de salida directamente, la programación semidefinida tiene como objetivo encontrar una matriz de producto interna que maximice las distancias por pares entre dos entradas cualesquiera que no estén conectadas en el gráfico de vecindad y al mismo tiempo preserve las distancias de los vecinos más cercanos.
3. La incrustación de baja dimensión se obtiene finalmente mediante la aplicación de un escalado multidimensional en la matriz del producto interno aprendido.

Los pasos de 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 debe satisfacerse 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 para que se centre 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 tiene como objetivo maximizar la distancia por pares de cada par de puntos. La función objetivo a 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 (llegue al infinito).

Dado que la gráfica tiene N puntos, la distancia entre dos puntos cualesquiera . Luego podemos limitar 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 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, el resultado se puede obtener mediante descomposición de Cholesky . ${\displaystyle K\,\!}$ ${\displaystyle Y\,\!}$

En particular, la matriz de Gram se puede escribir como dónde está 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 -ésimo elemento de la salida es . ^{[29] [30]} ${\displaystyle \alpha \,\!}$ ${\displaystyle Y_{i}\,\!}$ ${\displaystyle {\sqrt {\lambda _{\alpha }}}V_{\alpha i}\,\!}$

Ver también

• Incrustación localmente lineal
• 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 Saúl 2004b
3. Weinberger y Saúl 2006
4. Lorenzo 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 los gráficos y algunas de sus aplicaciones algorítmicas". Combinatoria . 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). Aprender una matriz central para la reducción de dimensionalidad no lineal. Actas de la XXI 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 por computadora 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: conocimientos y nuevos modelos". Revista de investigación sobre aprendizaje automático . 13 (mayo): 1612. arXiv : 1010.4830 . Código Bib : 2010arXiv1010.4830L.

Material adicional

• Código MVU Matlab de Kilian Q. Weinberger