Reducción de dimensionalidad no lineal

Proyección de datos sobre variedades de menor dimensión

Arriba a la izquierda: un conjunto de datos 3D de 1000 puntos en una banda en espiral (también conocida como rollo suizo ) con un agujero rectangular en el medio. Arriba a la derecha: la variedad 2D original utilizada para generar el conjunto de datos 3D. Abajo a la izquierda y a la derecha: recuperaciones 2D de la variedad utilizando respectivamente los algoritmos LLE y Hessian LLE implementados por el kit de herramientas de procesamiento de datos modulares.

La reducción de dimensionalidad no lineal , también conocida como aprendizaje de variedades , es una de varias técnicas relacionadas que tienen como objetivo proyectar datos de alta dimensión, potencialmente existentes en variedades no lineales que no pueden capturarse adecuadamente mediante métodos de descomposición lineal, en variedades latentes de menor dimensión , con el objetivo de visualizar los datos en el espacio de baja dimensión o aprender el mapeo (ya sea del espacio de alta dimensión a la incrustación de baja dimensión o viceversa) en sí. ^{[1] [2]} Las técnicas descritas a continuación pueden entenderse como generalizaciones de los métodos de descomposición lineal utilizados para la reducción de dimensionalidad , como la descomposición en valores singulares y el análisis de componentes principales .

Aplicaciones de NLDR

Los datos de alta dimensión pueden resultar difíciles de manejar para las máquinas, ya que requieren mucho tiempo y espacio para su análisis. También suponen un desafío para los humanos, ya que es difícil visualizar o comprender datos en más de tres dimensiones. Reducir la dimensionalidad de un conjunto de datos, manteniendo sus características esenciales relativamente intactas, puede hacer que los algoritmos sean más eficientes y permitir a los analistas visualizar tendencias y patrones.

Gráfico de puntos bidimensionales que resulta de utilizar un algoritmo NLDR. En este caso, se utiliza Manifold Sculpting para reducir los datos a solo dos dimensiones (rotación y escala).

Las representaciones de datos en dimensiones reducidas suelen denominarse "variables intrínsecas". Esta descripción implica que estos son los valores a partir de los cuales se produjeron los datos. Por ejemplo, considere un conjunto de datos que contiene imágenes de una letra "A", que se ha escalado y rotado en cantidades variables. Cada imagen tiene 32 × 32 píxeles. Cada imagen se puede representar como un vector de 1024 valores de píxeles. Cada fila es una muestra en una variedad bidimensional en un espacio de 1024 dimensiones (un espacio de Hamming ). La dimensionalidad intrínseca es dos, porque se variaron dos variables (rotación y escala) para producir los datos. La información sobre la forma o el aspecto de una letra "A" no forma parte de las variables intrínsecas porque es la misma en todos los casos. La reducción de dimensionalidad no lineal descartará la información correlacionada (la letra "A") y recuperará solo la información variable (rotación y escala). La imagen de la derecha muestra imágenes de muestra de este conjunto de datos (para ahorrar espacio, no se muestran todas las imágenes de entrada) y un gráfico de los puntos bidimensionales que resultan del uso de un algoritmo NLDR (en este caso, se utilizó Manifold Sculpting) para reducir los datos a solo dos dimensiones.

Se utiliza PCA (un algoritmo de reducción de dimensionalidad lineal) para reducir este mismo conjunto de datos a dos dimensiones, los valores resultantes no están tan bien organizados.

En comparación, si se utiliza el análisis de componentes principales , que es un algoritmo de reducción de dimensionalidad lineal, para reducir este mismo conjunto de datos a dos dimensiones, los valores resultantes no están tan bien organizados. Esto demuestra que los vectores de alta dimensión (cada uno de los cuales representa una letra "A") que muestrean esta variedad varían de manera no lineal.

Por lo tanto, debería ser evidente que la NLDR tiene varias aplicaciones en el campo de la visión artificial. Por ejemplo, considere un robot que utiliza una cámara para navegar en un entorno estático cerrado. Las imágenes obtenidas por esa cámara pueden considerarse muestras de una variedad en un espacio de alta dimensión, y las variables intrínsecas de esa variedad representarán la posición y la orientación del robot.

Las variedades invariantes son de interés general para la reducción del orden de modelos en sistemas dinámicos . En particular, si hay una variedad invariante de atracción en el espacio de fases, las trayectorias cercanas convergerán en ella y permanecerán en ella indefinidamente, lo que la convierte en candidata para la reducción de dimensionalidad del sistema dinámico. Si bien no se garantiza la existencia de tales variedades en general, la teoría de subvariedades espectrales (SSM) proporciona condiciones para la existencia de objetos invariantes de atracción únicos en una amplia clase de sistemas dinámicos. ^[3] La investigación activa en NLDR busca desplegar las variedades de observación asociadas con los sistemas dinámicos para desarrollar técnicas de modelado. ^[4]

A continuación se enumeran algunas de las técnicas de reducción de dimensionalidad no lineal más destacadas.

Conceptos importantes

El mapeo de Sammon

El mapeo de Sammon es una de las primeras y más populares técnicas NLDR.

Aproximación de una curva principal mediante un SOM unidimensional (una línea discontinua con cuadrados rojos, 20 nodos). El primer componente principal se representa mediante una línea recta azul. Los puntos de datos son los pequeños círculos grises. Para el PCA, la fracción de varianza no explicada en este ejemplo es del 23,23 %, mientras que para el SOM es del 6,86 %. ^[5]

Mapa autoorganizativo

El mapa autoorganizado (SOM, también llamado mapa de Kohonen ) y su variante probabilística, el mapeo topográfico generativo (GTM), utilizan una representación de puntos en el espacio incrustado para formar un modelo de variable latente basado en un mapeo no lineal del espacio incrustado al espacio de alta dimensión. ^[6] Estas técnicas están relacionadas con el trabajo en redes de densidad, que también se basan en el mismo modelo probabilístico.

Análisis de componentes principales del núcleo

Quizás el algoritmo más utilizado para la reducción dimensional es el PCA del núcleo . ^[7] El PCA comienza calculando la matriz de covarianza de la matriz ${\displaystyle m\times n}$ ${\displaystyle \mathbf {X} }$

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\mathbf {x} _{i}\mathbf {x} _{i}^{\mathsf {T}}}.}$

Luego proyecta los datos sobre los primeros k vectores propios de esa matriz. En comparación, KPCA comienza calculando la matriz de covarianza de los datos después de transformarlos en un espacio de dimensiones superiores.

${\displaystyle C={\frac {1}{m}}\sum _{i=1}^{m}{\Phi (\mathbf {x} _{i})\Phi (\mathbf {x} _{i})^{\mathsf {T}}}.}$

Luego proyecta los datos transformados sobre los primeros k vectores propios de esa matriz, al igual que PCA. Utiliza el truco del kernel para factorizar gran parte del cálculo, de modo que todo el proceso se puede realizar sin realmente calcular . Por supuesto , debe elegirse de manera que tenga un kernel correspondiente conocido. Desafortunadamente, no es trivial encontrar un buen kernel para un problema dado, por lo que KPCA no arroja buenos resultados con algunos problemas cuando se utilizan kernels estándar. Por ejemplo, se sabe que tiene un rendimiento deficiente con estos kernels en la variedad Swiss roll . Sin embargo, se pueden ver otros métodos que funcionan bien en tales configuraciones (por ejemplo, Laplacian Eigenmaps, LLE) como casos especiales de PCA de kernel mediante la construcción de una matriz de kernel dependiente de los datos. ^[8] ${\displaystyle \Phi (\mathbf {x} )}$ ${\displaystyle \Phi }$

KPCA tiene un modelo interno, por lo que se puede utilizar para mapear puntos en su incrustación que no estaban disponibles en el momento del entrenamiento.

Curvas principales y variedades

Aplicación de curvas principales: Índice de calidad de vida no lineal. ^[9] Los puntos representan datos de los 171 países de la ONU en un espacio de 4 dimensiones formado por los valores de 4 indicadores: producto bruto per cápita , esperanza de vida , mortalidad infantil e incidencia de tuberculosis . Diferentes formas y colores corresponden a varias ubicaciones geográficas. La línea roja en negrita representa la curva principal , que aproxima el conjunto de datos. Esta curva principal se produjo mediante el método de mapa elástico . ^[10]

Las curvas principales y las variedades proporcionan el marco geométrico natural para la reducción de dimensionalidad no lineal y extienden la interpretación geométrica del PCA mediante la construcción explícita de una variedad incrustada y la codificación utilizando la proyección geométrica estándar sobre la variedad. Este enfoque fue propuesto originalmente por Trevor Hastie en su tesis de 1984, ^[11] que presentó formalmente en 1989. ^[12] Esta idea ha sido explorada más a fondo por muchos autores. ^[13] La forma de definir la "simplicidad" de la variedad depende del problema, sin embargo, se mide comúnmente por la dimensionalidad intrínseca y/o la suavidad de la variedad. Por lo general, la variedad principal se define como una solución a un problema de optimización. La función objetivo incluye una aproximación de calidad de datos y algunos términos de penalización por la flexión de la variedad. Las aproximaciones iniciales populares se generan mediante PCA lineal y SOM de Kohonen.

Mapas propios laplacianos

Los mapas propios laplacianos utilizan técnicas espectrales para realizar una reducción de dimensionalidad. ^[14] Esta técnica se basa en el supuesto básico de que los datos se encuentran en una variedad de baja dimensión en un espacio de alta dimensión. ^[15] Este algoritmo no puede incorporar puntos fuera de la muestra, pero existen técnicas basadas en la regularización del espacio de Hilbert del núcleo de reproducción para agregar esta capacidad. ^[16] Dichas técnicas también se pueden aplicar a otros algoritmos de reducción de dimensionalidad no lineal.

Las técnicas tradicionales como el análisis de componentes principales no consideran la geometría intrínseca de los datos. Los mapas propios laplacianos construyen un gráfico a partir de la información de vecindad del conjunto de datos. Cada punto de datos sirve como un nodo en el gráfico y la conectividad entre nodos está gobernada por la proximidad de los puntos vecinos (usando, por ejemplo, el algoritmo del vecino más cercano k ). El gráfico así generado puede considerarse como una aproximación discreta de la variedad de baja dimensión en el espacio de alta dimensión. La minimización de una función de costo basada en el gráfico asegura que los puntos cercanos entre sí en la variedad se mapeen cerca uno del otro en el espacio de baja dimensión, preservando las distancias locales. Las funciones propias del operador de Laplace-Beltrami en la variedad sirven como dimensiones de incrustación, ya que en condiciones suaves este operador tiene un espectro contable que es una base para funciones integrables cuadradas en la variedad (compárese con la serie de Fourier en la variedad del círculo unitario). Los intentos de colocar los mapas propios laplacianos sobre una base teórica sólida han tenido cierto éxito, ya que, bajo ciertas suposiciones no restrictivas, se ha demostrado que la matriz laplaciana del gráfico converge al operador de Laplace-Beltrami a medida que el número de puntos tiende a infinito. ^[15]

Isomap

Isomap ^[17] es una combinación del algoritmo Floyd-Warshall con el escalamiento multidimensional clásico (MDS). El MDS clásico toma una matriz de distancias por pares entre todos los puntos y calcula una posición para cada punto. Isomap supone que las distancias por pares solo se conocen entre puntos vecinos y utiliza el algoritmo Floyd-Warshall para calcular las distancias por pares entre todos los demás puntos. Esto estima de manera efectiva la matriz completa de distancias geodésicas por pares entre todos los puntos. Luego, Isomap utiliza el MDS clásico para calcular las posiciones de dimensión reducida de todos los puntos. Landmark-Isomap es una variante de este algoritmo que utiliza puntos de referencia para aumentar la velocidad, a costa de cierta precisión.

En el aprendizaje de variedades, se supone que los datos de entrada se obtienen de una variedad de baja dimensión que está incrustada dentro de un espacio vectorial de mayor dimensión. La intuición principal detrás de MVU es explotar la linealidad local de las variedades y crear una asignación que preserve las vecindades locales en cada punto de la variedad subyacente.

Incrustación lineal local

La incrustación lineal local (LLE) se presentó aproximadamente al mismo tiempo que Isomap. ^[18] Tiene varias ventajas sobre Isomap, incluida una optimización más rápida cuando se implementa para aprovechar los algoritmos de matriz dispersa y mejores resultados con muchos problemas. LLE también comienza por encontrar un conjunto de vecinos más cercanos de cada punto. Luego calcula un conjunto de pesos para cada punto que mejor describe el punto como una combinación lineal de sus vecinos. Finalmente, utiliza una técnica de optimización basada en vectores propios para encontrar la incrustación de puntos de baja dimensión, de modo que cada punto aún se describa con la misma combinación lineal de sus vecinos. LLE tiende a manejar mal las densidades de muestra no uniformes porque no hay una unidad fija para evitar que los pesos se desvíen a medida que varias regiones difieren en densidades de muestra. LLE no tiene un modelo interno.

LLE calcula las coordenadas baricéntricas de un punto X _i en función de sus puntos vecinos X _j . El punto original se reconstruye mediante una combinación lineal, dada por la matriz de pesos W _ij , de sus puntos vecinos. El error de reconstrucción está dado por la función de costo E ( W ).

${\displaystyle E(W)=\sum _{i}\left|\mathbf {X} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {X} _{j}}\right|^{2}}$

Los pesos W _ij se refieren a la cantidad de contribución que tiene el punto X _j al reconstruir el punto X _i . La función de costo se minimiza bajo dos restricciones: (a) cada punto de datos X _i se reconstruye solo a partir de sus vecinos, lo que obliga a que W _ij sea cero si el punto X _j no es vecino del punto X _i y (b) la suma de cada fila de la matriz de pesos es igual a 1.

${\displaystyle \sum _{j}{\mathbf {W} _{ij}}=1}$

Los puntos de datos originales se recopilan en un espacio de dimensión D y el objetivo del algoritmo es reducir la dimensionalidad a d de modo que D >> d . Los mismos pesos W _ij que reconstruyen el i ésimo punto de datos en el espacio de dimensión D se utilizarán para reconstruir el mismo punto en el espacio de dimensión d inferior . Se crea un mapa de conservación de vecindad basado en esta idea. Cada punto X _i en el espacio de dimensión D se asigna a un punto Y _i en el espacio de dimensión d minimizando la función de costo.

${\displaystyle C(Y)=\sum _{i}\left|\mathbf {Y} _{i}-\sum _{j}{\mathbf {W} _{ij}\mathbf {Y} _{j}}\right|^{2}}$

En esta función de costo, a diferencia de la anterior, los pesos W _ij se mantienen fijos y la minimización se realiza en los puntos Y _i para optimizar las coordenadas. Este problema de minimización se puede resolver resolviendo un problema de valores propios dispersos N X N ( N es el número de puntos de datos), cuyos d vectores propios no nulos inferiores proporcionan un conjunto ortogonal de coordenadas. Generalmente, los puntos de datos se reconstruyen a partir de K vecinos más cercanos, medidos por la distancia euclidiana . Para una implementación de este tipo, el algoritmo solo tiene un parámetro libre K, que se puede elegir mediante validación cruzada.

Incrustación local lineal de Hesse (Hessian LLE)

Al igual que LLE, el LLE hessiano también se basa en técnicas de matriz dispersa. ^[19] Tiende a producir resultados de una calidad mucho mayor que el LLE. Desafortunadamente, tiene una complejidad computacional muy costosa, por lo que no es adecuado para variedades con un gran número de muestras. No tiene un modelo interno.

Incrustación lineal local modificada (MLLE)

El LLE modificado (MLLE) ^[20] es otra variante del LLE que utiliza pesos múltiples en cada vecindario para abordar el problema de condicionamiento de la matriz de pesos local que conduce a distorsiones en los mapas LLE. En términos generales, los pesos múltiples son la proyección ortogonal local de los pesos originales producidos por el LLE. Los creadores de esta variante regularizada también son los autores de la alineación del espacio tangente local (LTSA), que está implícita en la formulación MLLE al darse cuenta de que la optimización global de las proyecciones ortogonales de cada vector de pesos, en esencia, alinea los espacios tangentes locales de cada punto de datos. Las implicaciones teóricas y empíricas de la aplicación correcta de este algoritmo son de largo alcance. ^[21]

Alineación del espacio tangente local

LTSA ^[22] se basa en la intuición de que cuando una variedad se desdobla correctamente, todos los hiperplanos tangentes a la variedad se alinearán. Comienza calculando los k vecinos más cercanos de cada punto. Calcula el espacio tangente en cada punto calculando los d primeros componentes principales en cada vecindario local. Luego optimiza para encontrar una incrustación que alinee los espacios tangentes.

Despliegue de varianza máxima

El desdoblamiento de varianza máxima , el isomapa y la incrustación lineal local comparten una intuición común que se basa en la noción de que si una variedad se desdobla correctamente, entonces se maximiza la varianza sobre los puntos. Su paso inicial, como el isomapa y la incrustación lineal local, es encontrar los k vecinos más cercanos de cada punto. Luego busca resolver el problema de maximizar la distancia entre todos los puntos no vecinos, restringidos de tal manera que se preserven las distancias entre los puntos vecinos. La principal contribución de este algoritmo es una técnica para presentar este problema como un problema de programación semidefinida. Desafortunadamente, los solucionadores de programación semidefinida tienen un alto costo computacional. Al igual que la incrustación lineal local, no tiene un modelo interno.

Codificadores automáticos

Un autocodificador es una red neuronal de propagación hacia adelante que se entrena para aproximarse a la función de identidad. Es decir, se entrena para mapear desde un vector de valores al mismo vector. Cuando se utiliza para fines de reducción de dimensionalidad, una de las capas ocultas en la red se limita a contener solo una pequeña cantidad de unidades de red. Por lo tanto, la red debe aprender a codificar el vector en una pequeña cantidad de dimensiones y luego decodificarlo nuevamente en el espacio original. Por lo tanto, la primera mitad de la red es un modelo que mapea desde el espacio de alta dimensión al espacio de baja dimensión, y la segunda mitad mapea desde el espacio de baja dimensión al espacio de alta dimensión. Aunque la idea de los autocodificadores es bastante antigua, ^[23] el entrenamiento de autocodificadores profundos solo se ha vuelto posible recientemente mediante el uso de máquinas de Boltzmann restringidas y autocodificadores de eliminación de ruido apilados. Relacionado con los autocodificadores está el algoritmo NeuroScale, que usa funciones de estrés inspiradas en el escalamiento multidimensional y mapeos Sammon (ver arriba) para aprender un mapeo no lineal desde el espacio de alta dimensión al espacio incrustado. Las asignaciones en NeuroScale se basan en redes de funciones de base radial .

Modelos de variables latentes de procesos gaussianos

Los modelos de variables latentes de proceso gaussiano (GPLVM) ^[24] son ​​métodos de reducción de dimensionalidad probabilística que utilizan procesos gaussianos (GP) para encontrar una incrustación no lineal de menor dimensión de datos de alta dimensionalidad. Son una extensión de la formulación probabilística de PCA. El modelo se define de forma probabilística y luego se marginan las variables latentes y se obtienen los parámetros maximizando la probabilidad. Al igual que el PCA kernel, utilizan una función kernel para formar un mapeo no lineal (en forma de un proceso gaussiano ). Sin embargo, en el GPLVM el mapeo es del espacio incrustado (latente) al espacio de datos (como las redes de densidad y GTM), mientras que en el PCA kernel es en la dirección opuesta. Originalmente se propuso para la visualización de datos de alta dimensionalidad, pero se ha ampliado para construir un modelo de variedad compartida entre dos espacios de observación. El GPLVM y sus numerosas variantes se han propuesto especialmente para el modelado del movimiento humano, por ejemplo, el GPLVM con restricción de la espalda, el modelo dinámico GP (GPDM), el GPDM equilibrado (B-GPDM) y el GPDM con restricción topológica. Para capturar el efecto de acoplamiento de las variedades de postura y marcha en el análisis de la marcha, se propuso una variedad de posturas de marcha conjuntas de múltiples capas. ^[25]

Incrustación vecinal estocástica distribuida en t

La incrustación vecinal estocástica con distribución t (t-SNE) ^[26] se utiliza ampliamente. Es uno de los métodos de incrustación vecinal estocástica. El algoritmo calcula la probabilidad de que pares de puntos de datos en el espacio de alta dimensión estén relacionados y luego elige incrustaciones de baja dimensión que produzcan una distribución similar.

Otros algoritmos

Mapa de perspectiva relacional

El mapa de perspectiva relacional es un algoritmo de escalamiento multidimensional . El algoritmo encuentra una configuración de puntos de datos en una variedad simulando un sistema dinámico de múltiples partículas en una variedad cerrada, donde los puntos de datos se asignan a partículas y las distancias (o disimilitudes) entre los puntos de datos representan una fuerza repulsiva. A medida que la variedad aumenta gradualmente de tamaño, el sistema de múltiples partículas se enfría gradualmente y converge a una configuración que refleja la información de distancia de los puntos de datos.

El mapa de perspectiva relacional se inspiró en un modelo físico en el que partículas con carga positiva se mueven libremente sobre la superficie de una pelota. Guiada por la fuerza de Coulomb entre partículas, la configuración de energía mínima de las partículas reflejará la intensidad de las fuerzas repulsivas entre ellas.

El mapa de perspectiva relacional se introdujo en ^[27] . El algoritmo utilizó primero el toro plano como variedad de imagen, luego se extendió (en el software VisuMap) para utilizar otros tipos de variedades cerradas, como la esfera , el espacio proyectivo y la botella de Klein , como variedades de imagen.

Mapas de contagio

Los mapas de contagio utilizan múltiples contagios en una red para mapear los nodos como una nube de puntos. ^[28] En el caso del modelo de cascadas globales, la velocidad de propagación se puede ajustar con el parámetro de umbral . Para el mapa de contagio es equivalente al algoritmo Isomap . ${\displaystyle t\in [0,1]}$ ${\displaystyle t=0}$

Análisis de componentes curvilíneos

El análisis de componentes curvilíneos (CCA) busca la configuración de puntos en el espacio de salida que preserve las distancias originales tanto como sea posible mientras se enfoca en distancias pequeñas en el espacio de salida (a la inversa del mapeo de Sammon que se enfoca en distancias pequeñas en el espacio original). ^[29]

Cabe señalar que el CCA, como algoritmo de aprendizaje iterativo, comienza centrándose en grandes distancias (como el algoritmo Sammon) y luego cambia gradualmente el enfoque a distancias pequeñas. La información de distancias pequeñas sobrescribirá la información de distancias grandes, si es necesario llegar a un acuerdo entre ambas.

La función de estrés del CCA está relacionada con una suma de divergencias de Bregman hacia la derecha. ^[30]

Análisis de distancia curvilínea

El análisis de componentes curvilíneos ^[29] entrena una red neuronal autoorganizada para que se ajuste a la variedad y busca preservar las distancias geodésicas en su incrustación. Se basa en el análisis de componentes curvilíneos (que amplió el mapeo de Sammon), pero utiliza distancias geodésicas en su lugar.

Reducción de dimensionalidad difeomórfica

La reducción de dimensionalidad difeomórfica o Diffeomap ^[31] aprende una aplicación difeomórfica suave que transporta los datos a un subespacio lineal de menor dimensión. Los métodos resuelven un campo vectorial indexado en el tiempo suave de modo que los flujos a lo largo del campo que comienzan en los puntos de datos terminarán en un subespacio lineal de menor dimensión, intentando así preservar las diferencias por pares tanto en la aplicación directa como en la inversa.

Alineación del colector

La alineación de variedades aprovecha la suposición de que conjuntos de datos dispares producidos por procesos de generación similares compartirán una representación de variedad subyacente similar. Al aprender proyecciones de cada espacio original a la variedad compartida, se recuperan las correspondencias y el conocimiento de un dominio se puede transferir a otro. La mayoría de las técnicas de alineación de variedades consideran solo dos conjuntos de datos, pero el concepto se extiende a una cantidad arbitraria de conjuntos de datos iniciales. ^[32]

Mapas de difusión

Los mapas de difusión aprovechan la relación entre la difusión de calor y un paseo aleatorio ( cadena de Markov ); se establece una analogía entre el operador de difusión en una variedad y una matriz de transición de Markov que opera sobre funciones definidas en el gráfico cuyos nodos fueron muestreados de la variedad. ^[33] En particular, supongamos que un conjunto de datos se representa por . La suposición subyacente del mapa de difusión es que los datos de alta dimensión se encuentran en una variedad de baja dimensión de dimensión . Sea X el conjunto de datos y la distribución de los puntos de datos en X . Además, defina un núcleo que represente alguna noción de afinidad de los puntos en X . El núcleo tiene las siguientes propiedades ^[34] ${\displaystyle \mathbf {X} =[x_{1},x_{2},\ldots ,x_{n}]\in \Omega \subset \mathbf {R^{D}} }$ ${\displaystyle \mathbf {d} }$ ${\displaystyle \mu }$ ${\displaystyle {\mathit {k}}}$

${\displaystyle k(x,y)=k(y,x),}$

k es simétrico

${\displaystyle k(x,y)\geq 0\qquad \forall x,y,k}$

k es preservación de positividad

Por lo tanto, se puede pensar en los puntos de datos individuales como los nodos de un gráfico y en el núcleo k como la definición de algún tipo de afinidad en ese gráfico. El gráfico es simétrico por construcción, ya que el núcleo es simétrico. Es fácil ver aquí que a partir de la tupla ( X , k ) se puede construir una cadena de Markov reversible . Esta técnica es común a una variedad de campos y se conoce como el laplaciano del gráfico.

Por ejemplo, el gráfico K = ( X , E ) se puede construir utilizando un núcleo gaussiano.

${\displaystyle K_{ij}={\begin{cases}e^{-\|x_{i}-x_{j}\|_{2}^{2}/\sigma ^{2}}&{\text{if }}x_{i}\sim x_{j}\\0&{\text{otherwise}}\end{cases}}}$

En la ecuación anterior, denota que es un vecino más cercano de . Correctamente, la distancia geodésica debería usarse para medir realmente distancias en la variedad . Dado que no se dispone de la estructura exacta de la variedad, para los vecinos más cercanos la distancia geodésica se aproxima mediante la distancia euclidiana. La elección modula nuestra noción de proximidad en el sentido de que si entonces y si entonces . El primero significa que ha tenido lugar muy poca difusión mientras que el segundo implica que el proceso de difusión está casi completo. Se pueden encontrar diferentes estrategias para elegir en. ^[35] ${\displaystyle x_{i}\sim x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle \sigma }$ ${\displaystyle \|x_{i}-x_{j}\|_{2}\gg \sigma }$ ${\displaystyle K_{ij}=0}$ ${\displaystyle \|x_{i}-x_{j}\|_{2}\ll \sigma }$ ${\displaystyle K_{ij}=1}$ ${\displaystyle \sigma }$

Para representar fielmente una matriz de Markov, se debe normalizar mediante la matriz de grados correspondiente : ${\displaystyle K}$ ${\displaystyle D}$

${\displaystyle P=D^{-1}K.}$

${\displaystyle P}$Ahora representa una cadena de Markov. es la probabilidad de transición de a en un paso de tiempo. De manera similar, la probabilidad de transición de a en t pasos de tiempo está dada por . Aquí está la matriz multiplicada por sí misma t veces. ${\displaystyle P(x_{i},x_{j})}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle P^{t}(x_{i},x_{j})}$ ${\displaystyle P^{t}}$ ${\displaystyle P}$

La matriz de Markov constituye una noción de geometría local del conjunto de datos X. La principal diferencia entre los mapas de difusión y el análisis de componentes principales es que en los mapas de difusión solo se consideran las características locales de los datos, en lugar de tomar correlaciones de todo el conjunto de datos. ${\displaystyle P}$

${\displaystyle K}$define un recorrido aleatorio en el conjunto de datos, lo que significa que el núcleo captura cierta geometría local del conjunto de datos. La cadena de Markov define direcciones de propagación rápidas y lentas a través de los valores del núcleo. A medida que el recorrido se propaga hacia adelante en el tiempo, la información de la geometría local se agrega de la misma manera que las transiciones locales (definidas por ecuaciones diferenciales) del sistema dinámico. ^[34] La metáfora de la difusión surge de la definición de una distancia de difusión familiar. ${\displaystyle \{D_{t}\}_{t\in N}}$

${\displaystyle D_{t}^{2}(x,y)=\|p_{t}(x,\cdot )-p_{t}(y,\cdot )\|^{2}}$

Para un valor t fijo, define una distancia entre dos puntos cualesquiera del conjunto de datos en función de la conectividad de rutas: el valor de será menor cuanto más rutas conecten x con y y viceversa. Debido a que la cantidad implica una suma de todas las rutas de longitud t, es mucho más resistente al ruido en los datos que la distancia geodésica. tiene en cuenta toda la relación entre los puntos x e y al calcular la distancia y sirve como una mejor noción de proximidad que la distancia euclidiana o incluso la distancia geodésica. ${\displaystyle D_{t}}$ ${\displaystyle D_{t}(x,y)}$ ${\displaystyle D_{t}(x,y)}$ ${\displaystyle D_{t}}$ ${\displaystyle D_{t}}$

Escalamiento multidimensional local

El escalamiento multidimensional local realiza un escalamiento multidimensional en regiones locales y luego utiliza la optimización convexa para ajustar todas las piezas. ^[36]

PCA no lineal

El PCA no lineal (NLPCA) utiliza retropropagación para entrenar un perceptrón multicapa (MLP) para que se ajuste a una variedad. ^[37] A diferencia del entrenamiento MLP típico, que solo actualiza los pesos, NLPCA actualiza tanto los pesos como las entradas. Es decir, tanto los pesos como las entradas se tratan como valores latentes. Después del entrenamiento, las entradas latentes son una representación de baja dimensión de los vectores observados, y el MLP mapea desde esa representación de baja dimensión al espacio de observación de alta dimensión.

Escalamiento de alta dimensión basado en datos

El escalamiento de alta dimensión basado en datos (DD-HDS) ^[38] está estrechamente relacionado con el mapeo de Sammon y el análisis de componentes curvilíneos, excepto que (1) penaliza simultáneamente los vecindarios falsos y los desgarros al enfocarse en distancias pequeñas tanto en el espacio original como en el de salida, y que (2) tiene en cuenta la concentración del fenómeno de medida al adaptar la función de ponderación a la distribución de distancias.

Escultura múltiple

Manifold Sculpting ^[39] utiliza optimización graduada para encontrar una incrustación. Al igual que otros algoritmos, calcula los k vecinos más cercanos e intenta buscar una incrustación que preserve las relaciones en los vecindarios locales. Escala lentamente la varianza de dimensiones superiores, mientras que simultáneamente ajusta los puntos en dimensiones inferiores para preservar esas relaciones. Si la tasa de escalamiento es pequeña, puede encontrar incrustaciones muy precisas. Cuenta con una precisión empírica mayor que otros algoritmos con varios problemas. También se puede utilizar para refinar los resultados de otros algoritmos de aprendizaje de variedades. Sin embargo, tiene dificultades para desplegar algunas variedades, a menos que se utilice una tasa de escalamiento muy lenta. No tiene modelo.

RankVisu

RankVisu ^[40] está diseñado para preservar el rango de vecindad en lugar de la distancia. RankVisu es especialmente útil en tareas difíciles (cuando no se puede lograr la preservación de la distancia de manera satisfactoria). De hecho, el rango de vecindad es menos informativo que la distancia (los rangos se pueden deducir a partir de las distancias, pero las distancias no se pueden deducir a partir de los rangos) y, por lo tanto, su preservación es más fácil.

Incrustaciones isométricas topológicamente restringidas

La incrustación isométrica restringida topológicamente (TCIE) ^[41] es un algoritmo basado en la aproximación de distancias geodésicas después de filtrar las geodésicas incompatibles con la métrica euclidiana. Con el objetivo de corregir las distorsiones causadas cuando se utiliza Isomap para mapear datos intrínsecamente no convexos, TCIE utiliza MDS de mínimos cuadrados ponderados para obtener un mapeo más preciso. El algoritmo TCIE primero detecta posibles puntos límite en los datos y, durante el cálculo de la longitud geodésica, marca las geodésicas incompatibles, para que se les asigne un peso pequeño en la mayorización de la tensión ponderada que sigue.

Aproximación y proyección de variedades uniformes

La aproximación y proyección de variedades uniformes (UMAP) es una técnica de reducción de dimensionalidad no lineal. ^[42] Es similar a t-SNE. ^[43]

Métodos basados ​​en matrices de proximidad

Un método basado en matrices de proximidad es aquel en el que los datos se presentan al algoritmo en forma de una matriz de similitud o una matriz de distancia . Todos estos métodos se incluyen en la clase más amplia de escalamiento multidimensional métrico . Las variaciones tienden a ser diferencias en cómo se calculan los datos de proximidad; por ejemplo, isomapa , incrustaciones lineales locales , despliegue de varianza máxima y mapeo Sammon (que en realidad no es un mapeo) son ejemplos de métodos de escalamiento multidimensional métrico.

Software

• Waffles es una biblioteca C++ de código abierto que contiene implementaciones de LLE, Manifold Sculpting y algunos otros algoritmos de aprendizaje de variedades.
• UMAP.jl implementa el método para el lenguaje de programación Julia .
• El método también se ha implementado en Python (código disponible en GitHub )

Véase también

• Hipótesis de colectores
• Subvariedad espectral
• Teorema de Taken
• Teorema de incrustación de Whitney
• Análisis discriminante
• Mapa elástico
• Aprendizaje de características
• Mapa autoorganizado en crecimiento (GSOM)
• Mapa autoorganizativo (SOM)

Referencias

1. 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): 1609–38. arXiv : 1010.4830 . Código Bibliográfico :2010arXiv1010.4830L.
2. Lee, John A.; Verleysen, Michel (2007). Reducción de dimensionalidad no lineal . Springer. ISBN 978-0-387-39350-6.
3. Haller, George; Ponsioen, Sten (2016). "Modos normales no lineales y subvariedades espectrales: Existencia, unicidad y uso en la reducción de modelos". Dinámica no lineal . 86 (3): 1493–1534. arXiv : 1602.00560 . doi :10.1007/s11071-016-2974-z. S2CID  44074026.
4. Gashler, M.; Martínez, T. (2011). Reducción de dimensionalidad no lineal temporal (PDF) . Actas de la Conferencia conjunta internacional sobre redes neuronales IJCNN'11. págs. 1959–66.
5. La ilustración se preparó utilizando software libre: Mirkes, EM (2011). "Análisis de componentes principales y mapas autoorganizados: subprograma". Universidad de Leicester.
6. Yin, Hujun (2007). "3. Aprendizaje de variedades principales no lineales mediante mapas autoorganizados". En Gorban, AN; Kégl, B.; Wunsch, DC; Zinovyev, A. (eds.). Variedades principales para visualización de datos y reducción de dimensión . Apuntes de clase en informática e ingeniería. Vol. 58. Springer. págs. 68–95. ISBN. 978-3-540-73749-0.
7. Schölkopf, B.; Smola, A.; Müller, K.-R. (1998). "Análisis de componentes no lineales como un problema de valores propios del kernel". Computación neuronal . 10 (5). Prensa del MIT : 1299–1319. doi :10.1162/089976698300017467. S2CID  6674407.
8. Ham, Jihun; Lee, Daniel D.; Mika, Sebastian; Schölkopf, Bernhard. "Una visión de núcleo de la reducción de dimensionalidad de variedades". Actas de la 21.ª Conferencia Internacional sobre Aprendizaje Automático, Banff, Canadá, 2004. doi : 10.1145/1015330.1015417.
9. Gorban, AN; Zinovyev, A. (2010). "Variedades principales y grafos en la práctica: de la biología molecular a los sistemas dinámicos". Revista internacional de sistemas neuronales . 20 (3): 219–232. arXiv : 1001.1122 . doi :10.1142/S0129065710002383. PMID  20556849. S2CID  2170982.
10. A. Zinovyev, ViDaExpert - Herramienta de visualización de datos multidimensionales Institut Curie , París.
11. Hastie, T. (noviembre de 1984). Principal Curves and Surfaces (PDF) (PhD). Stanford Linear Accelerator Center, Universidad de Stanford. Archivado (PDF) del original el 2 de agosto de 2019.
12. Hastie, T. ; Stuetzle, W. (junio de 1989). "Curvas principales" (PDF) . Revista de la Asociación Estadounidense de Estadística . 84 (406): 502–6. doi :10.1080/01621459.1989.10478797.
13. Gorban, AN ; Kégl, B.; Wunsch, DC; Zinovyev, A., eds. (2007). Variedades principales para visualización de datos y reducción de dimensión. Apuntes de clase en informática e ingeniería (LNCSE). Vol. 58. Springer. ISBN 978-3-540-73749-0.
14. Belkin, Mikhail; Niyogi, Partha (2001). "Mapas propios laplacianos y técnicas espectrales para incrustación y agrupamiento" (PDF) . Avances en sistemas de procesamiento de información neuronal . 14. MIT Press: 586–691. ISBN. 0-262-27173-7.OCLC 52710683  .
15. Belkin, Mikhail (agosto de 2003). Problemas de aprendizaje en variedades (PhD). Departamento de Matemáticas, Universidad de Chicago.El código Matlab para mapas propios laplacianos se puede encontrar en algoritmos en Ohio-state.edu
16. Bengio, Yoshua; Paiement, Jean-Francois; Vincent, Pascal; Delalleau, Olivier; Le Roux, Nicolas; Ouimet, Marie (2004). "Extensiones fuera de muestra para LLE, Isomap, MDS, Eigenmaps y agrupamiento espectral" (PDF) . Avances en sistemas de procesamiento de información neuronal . Vol. 16. MIT Press. ISBN. 0-262-20152-6.
17. Tenenbaum, J B.; de Silva, V.; Langford, JC (2000). "Un marco geométrico global para la reducción de la dimensionalidad no lineal" (PDF) . Science . 290 (5500): 2319–23. Bibcode :2000Sci...290.2319T. doi :10.1126/science.290.5500.2319. PMID  11125149. S2CID  221338160.
18. Roweis, ST; Saul, LK (2000). "Reducción de dimensionalidad no lineal mediante incrustación lineal local". Science . 290 (5500): 2323–6. Bibcode :2000Sci...290.2323R. doi :10.1126/science.290.5500.2323. PMID  11125150. S2CID  5987139.
19. Donoho, D.; Grimes, C. (2003). "Mapas propios de Hesse: técnicas de incrustación lineal local para datos de alta dimensión". Proc Natl Acad Sci USA . 100 (10): 5591–6. Bibcode :2003PNAS..100.5591D. doi : 10.1073/pnas.1031596100 . PMC 156245 . PMID  16576753. 
20. Zhang, Z.; Wang, J. (2006). "MLLE: Incorporación lineal local modificada utilizando pesos múltiples". NIPS'06: Actas de la 19.ª Conferencia internacional sobre sistemas de procesamiento de información neuronal : 1593-1600.
21. Sidhu, Gagan (2019). "Incorporación lineal local y selección de características fMRI en la clasificación psiquiátrica". Revista IEEE de Ingeniería Traslacional en Salud y Medicina . 7 : 1–11. arXiv : 1908.06319 . doi :10.1109/JTEHM.2019.2936348. PMC 6726465 . PMID  31497410. S2CID  201832756. 
22. Zhang, Zhenyue; Hongyuan Zha (2005). "Variedades principales y reducción de dimensión no lineal mediante alineación del espacio tangente local". Revista SIAM de informática científica . 26 (1): 313–338. CiteSeerX 10.1.1.211.9957 . doi :10.1137/s1064827502419154. 
23. DeMers, D.; Cottrell, GW (1993). "Reducción de la dimensionalidad no lineal". Avances en sistemas de procesamiento de información neuronal . Vol. 5. págs. 580–7. ISBN 1558600159.OCLC 928936290  .
24. Lawrence, N. (2005). "Análisis probabilístico no lineal de componentes principales con modelos de variables latentes de procesos gaussianos". Journal of Machine Learning Research . 6 : 1783–1816.
25. Ding, M.; Fan, G. (2015). "Variedades de posturas de marcha articuladas multicapa para modelado del movimiento de la marcha humana". IEEE Transactions on Cybernetics . 45 (11): 2413–24. doi :10.1109/TCYB.2014.2373393. PMID  25532201. S2CID  15591304.
26. van der Maaten, LJP; Hinton, GE (2008). "Visualización de datos de alta dimensión mediante t-SNE" (PDF) . Revista de investigación en aprendizaje automático . 9 : 2579–2605.
27. Li, James X. (2004). "Visualización de datos de alta dimensión con un mapa de perspectiva relacional" (PDF) . Visualización de la información . 3 : 49–59. doi :10.1057/palgrave.ivs.9500051. S2CID  7566939.
28. Taylor, D.; Klimm, F.; Harrington, HA; Kramár, M.; Mischaikow, K.; Porter, MA; Mucha, PJ (2015). "Análisis de datos topológicos de mapas de contagio para examinar procesos de propagación en redes". Nature Communications . 6 : 7723. arXiv : 1408.1168 . Bibcode :2015NatCo...6.7723T. doi :10.1038/ncomms8723. PMC 4566922 . PMID  26194875. 
29. Demartines, P.; Hérault, J. (1997). "Análisis de componentes curvilíneos: una red neuronal autoorganizada para el mapeo no lineal de conjuntos de datos" (PDF) . IEEE Transactions on Neural Networks . 8 (1): 148–154. doi :10.1109/72.554199. PMID  18255618.
30. Sun, Jigang; Crowe, Malcolm; Fyfe, Colin (2010). "Análisis de componentes curvilíneos y divergencias de Bregman" (PDF) . Simposio Europeo sobre Redes Neuronales Artificiales (Esann) . Publicaciones de d-side. págs. 81–86.
31. Walder, Christian; Schölkopf, Bernhard (2009). "Reducción de la dimensionalidad difeomórfica" (PDF) . Avances en sistemas de procesamiento de información neuronal . Vol. 22. MIT Press. págs. 1713–20.
32. Wang, Chang; Mahadevan, Sridhar (julio de 2008). Alineación de variedades mediante análisis de Procrustes (PDF) . 25.ª Conferencia internacional sobre aprendizaje automático. pp. 1120–7.
33. Lafon, Stephane (mayo de 2004). Mapas de difusión y armónicos geométricos (PhD). Universidad de Yale .
34. Coifman, Ronald R.; Lafon, Stephane (julio de 2006). "Mapas de difusión" (PDF) . Análisis armónico computacional y aplicado . 21 (1): 5–30. doi :10.1016/j.acha.2006.04.006. S2CID  17160669.
35. Bah, B. (2008). Mapas de difusión: aplicaciones y análisis (Maestría). Universidad de Oxford.
36. Venna, J.; Kaski, S. (2006). "Escalamiento multidimensional local". Redes neuronales . 19 (6–7): 889–899. doi :10.1016/j.neunet.2006.05.014. PMID  16787737.
37. Scholz, M.; Kaplan, F.; Guy, CL; Kopka, J.; Selbig, J. (2005). "PCA no lineal: un enfoque de datos faltantes". Bioinformática . 21 (20). Oxford University Press: 3887–95. doi : 10.1093/bioinformatics/bti634 . hdl : 11858/00-001M-0000-0014-2B1F-2 . PMID  16109748.
38. S. Lespinats, M. Verleysen, A. Giron, B. Fertil, DD-HDS: una herramienta para la visualización y exploración de datos de alta dimensión, IEEE Transactions on Neural Networks 18 (5) (2007) 1265–1279.
39. Gashler, M. y Ventura, D. y Martinez, T., Reducción iterativa de la dimensionalidad no lineal con modelado de variedades , en Platt, JC y Koller, D. y Singer, Y. y Roweis, S., editor, Advances in Neural Information Processing Systems 20, págs. 513–520, MIT Press, Cambridge, MA, 2008
40. Lespinats S., Fertil B., Villemain P. y Herault J., Rankvisu: Mapeo de la red de vecindad, Neurocomputing, vol. 72 (13–15), págs. 2964–2978, 2009.
41. Rosman, G.; Bronstein, MM; Bronstein, AM; Kimmel, R. (2010). "Reducción de dimensionalidad no lineal mediante incrustación isométrica topológicamente restringida" (PDF) . Revista internacional de visión por computadora . 89 (1): 56–68. doi :10.1007/s11263-010-0322-1. S2CID  1365750.
42. McInnes, Leland; Healy, John; Melville, James (7 de diciembre de 2018). "Aproximación y proyección de variedades uniformes para reducción de dimensión". arXiv : 1802.03426 .
43. "UMAP: Aproximación y proyección de variedades uniformes para reducción de dimensión — documentación de umap 0.3". umap-learn.readthedocs.io . Consultado el 4 de mayo de 2019 .

Lectura adicional

• Murphy, Kevin P. (2022). "Aprendizaje múltiple". Aprendizaje automático probabilístico . MIT Press. págs. 682–699. ISBN 978-0-262-04682-4.

Enlaces externos

• Isomap
• Mapeo topográfico generativo
• La tesis de Mike Tipping
• Modelo de variable latente del proceso gaussiano
• Incrustación lineal local
• Mapa de perspectiva relacional
• Página de inicio de DD-HDS
• Página de inicio de RankVisu
• Breve reseña de los mapas de difusión
• PCA no lineal mediante redes neuronales de codificador automático.