Incrustaciones semidefinidas

El despliegue de varianza máxima (MVU) , también conocido como incrustación semidefinida (SDE), es un algoritmo en ciencias de la computación 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 de 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 .

MVU crea un mapeo desde 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 grafo de vecindad . Cada entrada se conecta 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 se conectan entre sí. Si los datos se muestrean con suficiente precisión, el grafo resultante es una aproximación discreta de la variedad subyacente.
2. El grafo de vecindad se "despliega" con la ayuda de la programación semidefinida. En lugar de aprender directamente los vectores de salida, la programación semidefinida busca una matriz de producto interno que maximice las distancias entre pares cualesquiera de entradas que no estén conectadas en el grafo de vecindad, preservando al mismo tiempo las distancias entre vecinos más cercanos.
3. Finalmente, la incrustación de baja dimensión se obtiene mediante la aplicación de un escalamiento multidimensional a la matriz de producto interno aprendida.

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 ]}

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

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

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

${\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.${\displaystyle Y\,\!}$centrar en el origen: ^{[ 12 ] [ 13 ] [ 14 ]}

${\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 es equivalente 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 ]}

Dejar${\displaystyle \tau =max\{\eta _{ij}|Y_{i}-Y_{j}|^{2}\}\,\!}$dónde ${\displaystyle \eta _{ij}:={\begin{cases}1&{\mbox{si}}\ i{\mbox{ es vecino de }}j\\0&{\mbox{en otro caso}}.\end{cases}}}$

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

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

${\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 puede reescribirse 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{Maximizar}}&&Tr(\mathbf {K} )\\&{\text{sujeto a}}&&\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{ donde }}\eta _{ij}=1,\end{aligned}}}$

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

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

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

• Incrustaciones lineales locales
• Isometría (desambiguación)
• Alineación del espacio tangente local
• variedad riemanniana
• minimización de energía

• Linial, London y Rabinovich, Nathan, Eran y Yuri (1995). "La geometría de los grafos y algunas de sus aplicaciones algorítmicas" . Combinatorica . 15 (2): 215– 245. doi : 10.1007/BF01200757 . S2CID 5071936 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
• Weinberger, Sha y Saul, Kilian Q., Fei y Lawrence K. (4 de julio de 2004a). Aprendizaje de una matriz kernel para la reducción de dimensionalidad no lineal . Actas de la Vigésimo Primera Conferencia Internacional sobre Aprendizaje Automático (ICML 2004). Banff, Alberta , Canadá.{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace )
• 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) . International Journal of Computer Vision . 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 . Bibcode : 2010arXiv1010.4830L .

• Código Matlab de Kilian Q. Weinberger para la unidad móvil de vídeo (MVU).