Los datos de alta dimensión , es decir, los datos que requieren más de dos o tres dimensiones para representarse, pueden ser difíciles de interpretar . Un enfoque de simplificación es asumir que los datos de interés se encuentran dentro del espacio de dimensiones inferiores. Si los datos de interés tienen una dimensión lo suficientemente baja, los datos se pueden visualizar en el espacio de baja dimensión.
A continuación se muestra un resumen de algunos métodos notables para la reducción de dimensionalidad no lineal . [1] [2] Muchos de estos métodos de reducción de dimensionalidad no lineal están relacionados con los métodos lineales que se enumeran a continuación . Los métodos no lineales pueden clasificarse ampliamente en dos grupos: los que proporcionan un mapeo (ya sea desde el espacio de alta dimensión a la incrustación de baja dimensión o viceversa) y los que solo brindan una visualización.
Métodos de descomposición lineal relacionados
- Análisis de componentes independientes (ICA)
- Análisis de componentes principales (PCA) - también llamado teorema de Karhunen-Loève - KLT
- Descomposición de valores singulares (SVD)
- Análisis factorial
Aplicaciones de NLDR
Considere un conjunto de datos representado como una matriz (o una tabla de base de datos), de modo que cada fila representa un conjunto de atributos (o características o dimensiones) que describen una instancia particular de algo. Si el número de atributos es grande, entonces el espacio de filas posibles únicas es exponencialmente grande. Por lo tanto, cuanto mayor sea la dimensionalidad, más difícil será muestrear el espacio. Esto causa muchos problemas. Los algoritmos que operan con datos de alta dimensión tienden a tener una complejidad de tiempo muy alta. Muchos algoritmos de aprendizaje automático, por ejemplo, luchan con datos de alta dimensión. Reducir los datos a menos dimensiones a menudo hace que los algoritmos de análisis sean más eficientes y puede ayudar a los algoritmos de aprendizaje automático a realizar predicciones más precisas.
Los humanos a menudo tienen dificultades para comprender datos en grandes dimensiones. Por lo tanto, reducir los datos a un pequeño número de dimensiones es útil para fines de visualización.
Las representaciones de datos de dimensiones reducidas se denominan a menudo "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 32x32 píxeles. Cada imagen se puede representar como un vector de valores de 1024 píxeles. Cada fila es una muestra de 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 una gráfica de los puntos bidimensionales que resultan del uso de un algoritmo NLDR (en este caso, se usó Manifold Sculpting) para reducir los datos a solo dos dimensiones.
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 en dos dimensiones, los valores resultantes no están tan bien organizados. Esto demuestra que los vectores de alta dimensión (cada uno representa una letra 'A') que muestran esta variedad varían de manera no lineal.
Por lo tanto, debería ser evidente que NLDR tiene varias aplicaciones en el campo de la visión por computadora. Por ejemplo, considere un robot que usa una cámara para navegar en un entorno estático cerrado. Las imágenes obtenidas por esa cámara pueden considerarse muestras en un colector en un espacio de alta dimensión, y las variables intrínsecas de ese colector representarán la posición y orientación del robot. Esta utilidad no se limita a los robots. Los sistemas dinámicos , una clase más general de sistemas, que incluye a los robots, se definen en términos de una variedad. La investigación activa en NLDR busca desplegar las variedades de observación asociadas con los sistemas dinámicos para desarrollar técnicas para modelar dichos sistemas y permitirles operar de manera autónoma. [3]
Algunas de las técnicas de reducción de dimensionalidad no lineal más destacadas se enumeran a continuación.
Conceptos importantes
Mapeo de Sammon
El mapeo de Sammon es una de las primeras y más populares técnicas de NLDR.
Mapa autoorganizado
El mapa autoorganizado (SOM, también llamado mapa de Kohonen ) y su mapeo topográfico generativo variante probabilístico (GTM) utilizan una representación de puntos en el espacio incrustado para formar un modelo de variable latente basado en un mapeo no lineal desde el espacio incrustado hasta el espacio de alta dimensión. [5] 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 kernel
Quizás el algoritmo más utilizado para la reducción dimensional sea el kernel PCA . [6] PCA comienza calculando la matriz de covarianza de la matriz
Luego proyecta los datos sobre los primeros k autovectores de esa matriz. En comparación, KPCA comienza calculando la matriz de covarianza de los datos después de transformarse en un espacio de dimensiones superiores,
Luego proyecta los datos transformados en los primeros k autovectores 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 pueda realizar sin calcular realmente. Por supuestodebe 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 da buenos resultados con algunos problemas cuando se utilizan kernels estándar. Por ejemplo, se sabe que funciona mal con estos granos en el colector de rodillos suizo . Sin embargo, se pueden ver algunos otros métodos que funcionan bien en tales entornos (por ejemplo, mapas propios de Laplacia, LLE) como casos especiales de PCA del núcleo mediante la construcción de una matriz del núcleo dependiente de los datos. [7]
KPCA tiene un modelo interno, por lo que puede usarse para mapear puntos en su incrustación que no estaban disponibles en el momento del entrenamiento.
Colectores y curvas principales
Las curvas principales y las variedades proporcionan el marco geométrico natural para la reducción de dimensionalidad no lineal y amplían la interpretación geométrica de PCA mediante la construcción explícita de una variedad incrustada y mediante la codificación mediante una proyección geométrica estándar en 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] Cómo definir la "simplicidad" de la variedad depende del problema, sin embargo, comúnmente se mide 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 calidad de aproximación de datos y algunos términos de penalización por la flexión del colector. Las aproximaciones iniciales populares son generadas por PCA lineal y SOM de Kohonen.
Mapas propios laplacianos
Laplacian Eigenmaps utiliza técnicas espectrales para realizar la 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 incrustar puntos fuera de muestra, pero existen técnicas basadas en la reproducción de la regularización del espacio de Hilbert del kernel para agregar esta capacidad. [16] Estas 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 crean 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 los nodos se rige por la proximidad de los puntos vecinos (utilizando, por ejemplo, el algoritmo del vecino k más cercano ). El gráfico así generado se puede considerar 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 el colector se mapeen cerca entre sí en el espacio de baja dimensión, preservando las distancias locales. Las funciones propias del operador de Laplace-Beltrami en el colector sirven como dimensiones de incrustación, ya que en condiciones suaves este operador tiene un espectro contable que es una base para funciones cuadradas integrables en el colector (comparar con la serie de Fourier en el colector de círculo unitario). Los intentos de ubicar los mapas propios de Laplacia en una base teórica sólida han tenido cierto éxito, ya que bajo ciertos supuestos no restrictivos, se ha demostrado que la matriz gráfica de Laplacia converge al operador de Laplace-Beltrami cuando el número de puntos llega al infinito. [15]
En aplicaciones de clasificación, las variedades de baja dimensión se pueden utilizar para modelar clases de datos que se pueden definir a partir de conjuntos de instancias observadas. Cada instancia observada puede describirse mediante dos factores independientes denominados "contenido" y "estilo", donde "contenido" es el factor invariante relacionado con la esencia de la clase y "estilo" expresa variaciones en esa clase entre instancias. [17] Desafortunadamente, los mapas propios laplacianos pueden no producir una representación coherente de una clase de interés cuando los datos de entrenamiento consisten en instancias que varían significativamente en términos de estilo. [18] En el caso de las clases que están representadas por secuencias multivariadas, se ha propuesto que los mapas propios de laplacianos estructurales superen este problema agregando restricciones adicionales dentro del gráfico de información de vecindad de mapas propios de Laplacia para reflejar mejor la estructura intrínseca de la clase. [19] Más específicamente, el gráfico se utiliza para codificar tanto la estructura secuencial de las secuencias multivariadas como, para minimizar las variaciones estilísticas, la proximidad entre puntos de datos de diferentes secuencias o incluso dentro de una secuencia, si contiene repeticiones. Utilizando la deformación temporal dinámica , la proximidad se detecta al encontrar correspondencias entre y dentro de las secciones de las secuencias multivariadas que exhiben una gran similitud. Los experimentos llevados a cabo en aplicaciones de reconocimiento de actividades basadas en la visión , clasificación de orientación de objetos y recuperación de poses humanas en 3D han demostrado el valor añadido de los mapas propios de laplacianos estructurales cuando se trata de datos de secuencia multivariante. [19] Una extensión de los Eigenmaps Laplacianos Estructurales, los Eigenmaps Laplacianos Generalizados llevaron a la generación de variedades donde una de las dimensiones representa específicamente variaciones en el estilo. Esto ha demostrado ser particularmente valioso en aplicaciones como el seguimiento del cuerpo articulado humano y la extracción de silueta. [20]
Isomap
Isomap [21] es una combinación del algoritmo Floyd-Warshall con el clásico Escalado multidimensional . La escala multidimensional clásica (MDS) toma una matriz de distancias por pares entre todos los puntos y calcula una posición para cada punto. Isomap asume 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 efectivamente la matriz completa de distancias geodésicas por pares entre todos los puntos. Luego, Isomap usa 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 múltiple, se supone que los datos de entrada se muestrean a partir de una variedad de baja dimensión que está incrustada dentro de un espacio vectorial de mayor dimensión. La principal intuición detrás de MVU es explotar la linealidad local de las variedades y crear un mapeo que preserve los vecindarios locales en cada punto de la variedad subyacente.
Incrustación localmente lineal
La incrustación localmente lineal (LLE) [22] se presentó aproximadamente al mismo tiempo que Isomap. 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 todavía se describe con la misma combinación lineal de sus vecinos. LLE tiende a manejar densidades de muestra no uniformes de manera deficiente porque no hay una unidad fija para evitar que los pesos se desvíen ya que varias regiones difieren en las densidades de muestra. LLE no tiene modelo interno.
LLE calcula las coordenadas baricéntricas de un punto X i basándose en sus vecinos X j . El punto original se reconstruye mediante una combinación lineal, dada por la matriz de ponderaciones W ij , de sus vecinos. El error de reconstrucción viene dado por la función de costo E ( W ).
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 W ij a ser cero si el punto X j no es vecino del punto X i y (b) La suma de cada fila de la matriz de ponderaciones es igual a 1.
Los puntos de datos originales se recopilan en un espacio dimensional D y el objetivo del algoritmo es reducir la dimensionalidad ad tal que D >> d . Los mismos pesos W ij que reconstruyen el i- ésimo punto de datos en el espacio dimensional D se usarán para reconstruir el mismo punto en el espacio dimensional d inferior . Se crea un mapa de conservación del vecindario basado en esta idea. Cada punto X i en el espacio dimensional D se asigna a un punto Y i en el espacio dimensional d minimizando la función de costo
En esta función de coste, 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 valor propio escaso de N X N ( siendo N el número de puntos de datos), cuyos vectores eigen inferiores d distintos de cero 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 tal implementación, el algoritmo tiene solo un parámetro libre K, que puede elegirse mediante validación cruzada.
Incrustación de arpillera localmente lineal (arpillera LLE)
Al igual que LLE, Hessian LLE también se basa en técnicas de matriz dispersa. [23] Tiende a producir resultados de una calidad mucho más alta que LLE. Desafortunadamente, tiene una complejidad computacional muy costosa, por lo que no es adecuado para múltiples muestreados. No tiene modelo interno.
Incrustación localmente lineal modificada (MLLE)
LLE modificado (MLLE) [24] es otra variante de LLE que utiliza múltiples pesos en cada vecindario para abordar el problema de condicionamiento de la matriz de peso local que conduce a distorsiones en los mapas de LLE. Hablando libremente, los pesos múltiples son la proyección ortogonal local de los pesos originales producidos por LLE. Los creadores de esta variante regularizada son también los autores de Local Tangent Space Alignment (LTSA), que está implícito en la formulación MLLE al darse cuenta de que la optimización global de las proyecciones ortogonales de cada vector de peso, en esencia, alinea los espacios tangentes locales. de cada punto de datos. Las implicaciones teóricas y empíricas de la correcta aplicación de este algoritmo son de gran alcance. [25]
Alineación del espacio tangente local
LTSA [26] se basa en la intuición de que cuando una variedad se despliega 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 se optimiza para encontrar una incrustación que alinee los espacios tangentes.
Despliegue de varianza máxima
El despliegue de varianza máxima , el isomapa y la incrustación localmente lineal comparten una intuición común que se basa en la noción de que si una variedad se despliega correctamente, la varianza sobre los puntos se maximiza. Su primer paso, al igual que Isomap y localmente lineal incrustación, es encontrar el k -nearest vecinos de cada punto. Luego busca resolver el problema de maximizar la distancia entre todos los puntos no vecinos, restringida de manera que se conserven 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 semidefinido. Desafortunadamente, los solucionadores de programación semidefinidos tienen un alto costo computacional. Al igual que la incrustación lineal local, no tiene un modelo interno.
Autoencoders
Un autoencoder es una red neuronal de retroalimentación que está entrenada para aproximarse a la función de identidad. Es decir, está entrenado para mapear desde un vector de valores al mismo vector. Cuando se utiliza con 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 a baja dimensión, y la segunda mitad mapea desde el espacio de baja a alta dimensión. Aunque la idea de los codificadores automáticos es bastante antigua, el entrenamiento de codificadores automáticos profundos solo se ha hecho posible recientemente mediante el uso de máquinas Boltzmann restringidas y codificadores automáticos de eliminación de ruido apilados. Relacionado con los codificadores automáticos está el algoritmo NeuroScale , que utiliza funciones de estrés inspiradas en el escalado multidimensional y los mapeos de Sammon (ver arriba) para aprender un mapeo no lineal del espacio de alta dimensión al espacio incrustado. Las asignaciones en NeuroScale se basan en redes de funciones de base radial . Otro uso de una red neuronal para la reducción de dimensionalidad es hacer que aprenda los planos tangentes en los datos. [27]
Modelos de variables latentes del proceso gaussiano
Los modelos de variables latentes del proceso gaussiano (GPLVM) [28] son métodos probabilísticos de reducción de dimensionalidad que utilizan procesos gaussianos (GP) para encontrar una incrustación no lineal de menor dimensión de datos de alta dimensión. Son una extensión de la formulación probabilística de PCA. El modelo se define probabilísticamente y las variables latentes luego se margina y los parámetros se obtienen maximizando la probabilidad. Al igual que el kernel PCA, utilizan una función del kernel para formar un mapeo no lineal (en forma de proceso gaussiano ). Sin embargo, en la GPLVM el mapeo es desde el espacio incrustado (latente) al espacio de datos (como redes de densidad y GTM) mientras que en el kernel PCA es en la dirección opuesta. Originalmente se propuso para la visualización de datos de alta dimensión, pero se ha ampliado para construir un modelo múltiple compartido entre dos espacios de observación. La GPLVM y sus muchas variantes se han propuesto especialmente para el modelado del movimiento humano, por ejemplo, GPLVM restringida hacia atrás, modelo dinámico GP (GPDM), GPDM equilibrado (B-GPDM) y GPDM restringido topológicamente. Para capturar el efecto de acoplamiento de la pose y las variedades de la marcha en el análisis de la marcha, se propuso una variedad multicapa conjunta de la marcha y la postura. [29]
Incrustación de vecinos estocásticos distribuidos en t
La incrustación de vecinos estocásticos distribuidos en t (t-SNE) [30] se utiliza ampliamente. Pertenece a una familia de métodos estocásticos de integración de vecinos. El algoritmo calcula la probabilidad de que los pares de puntos de datos en el espacio de alta dimensión estén relacionados y luego elige incrustaciones de baja dimensión que producen una distribución similar.
Otros algoritmos
Mapa de perspectiva relacional
El mapa de perspectiva relacional es un algoritmo de escalado multidimensional . El algoritmo encuentra una configuración de puntos de datos en un colector simulando un sistema dinámico de múltiples partículas en un colector cerrado, donde los puntos de datos se asignan a partículas y las distancias (o disimilitud) entre los puntos de datos representan una fuerza repulsiva. A medida que el colector crece 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 las partículas cargadas positivamente se mueven libremente sobre la superficie de una bola. Guiada por la fuerza de Coulomb entre partículas, la configuración de energía mínima de las partículas reflejará la fuerza de las fuerzas repulsivas entre las partículas.
El mapa de perspectiva relacional se introdujo en. [31] El algoritmo usó primero el toro plano como la variedad de imagen, luego se ha extendido (en el software VisuMap para usar otros tipos de variedades cerradas, como la esfera , el espacio proyectivo y Klein botella , como colectores 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. [32] En el caso del modelo de cascadas globales, la velocidad de propagación se puede ajustar con el parámetro de umbral. Parael mapa de contagio es equivalente al algoritmo Isomap .
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 preserva 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). [33]
Cabe señalar que CCA, como un algoritmo de aprendizaje iterativo, en realidad comienza con el enfoque en grandes distancias (como el algoritmo Sammon), 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 hacer concesiones entre las dos.
La función de estrés de CCA está relacionada con una suma de divergencias de Bregman a la derecha. [34]
Análisis de distancias curvilíneas
CDA [33] entrena una red neuronal autoorganizada para adaptarse 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
Diffeomorphic Dimensionality Reduction o Diffeomap [35] aprende un mapeo difeomórfico suave que transporta los datos a un subespacio lineal de menor dimensión. Los métodos resuelven un campo vectorial indexado en tiempo suave, de modo que los flujos a lo largo del campo que comienzan en los puntos de datos terminan en un subespacio lineal de menor dimensión, intentando así preservar las diferencias por pares bajo el mapeo directo e inverso.
Alineación del colector
La alineación múltiple aprovecha la suposición de que conjuntos de datos dispares producidos por procesos de generación similares compartirán una representación múltiple subyacente similar. Al aprender las proyecciones de cada espacio original a la variedad compartida, se recuperan las correspondencias y se puede transferir el conocimiento de un dominio a otro. La mayoría de las técnicas de alineación múltiples consideran solo dos conjuntos de datos, pero el concepto se extiende arbitrariamente a muchos conjuntos de datos iniciales. [36]
Mapas de difusión
Los mapas de difusión aprovechan la relación entre la difusión de calor y una caminata aleatoria ( Cadena de Markov ); Se traza una analogía entre el operador de difusión en una variedad y una matriz de transición de Markov que opera en funciones definidas en el gráfico cuyos nodos fueron muestreados de la variedad. [37] En particular, supongamos que un conjunto de datos se representa mediante. El supuesto subyacente del mapa de difusión es que los datos de alta dimensión se encuentran en una variedad de dimensiones de baja dimensión.. Sea X el conjunto de datos yrepresentar la distribución de los puntos de datos en X . Además, definir un núcleo que representa alguna noción de afinidad de los puntos en X . El kerneltiene las siguientes propiedades [38]
k es simétrico
k es la preservación de la positividad
Por lo tanto, uno puede pensar en los puntos de datos individuales como los nodos de un gráfico y el kernel k como definiendo algún tipo de afinidad en ese gráfico. La gráfica es simétrica 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 gráfico laplaciano.
Por ejemplo, el gráfico K = ( X , E ) se puede construir usando un kernel gaussiano.
En la ecuación anterior, denota que es un vecino más cercano de . De manera adecuada, la distancia geodésica debe usarse para medir realmente distancias en el colector . Dado que la estructura exacta de la variedad no está disponible, para los vecinos más cercanos la distancia geodésica se aproxima por la distancia euclidiana. La elección modula nuestra noción de proximidad en el sentido de que si luego y si luego . Lo primero significa que ha tenido lugar muy poca difusión, mientras que lo segundo implica que el proceso de difusión está casi completo. Diferentes estrategias para elegirse puede encontrar en. [39]
Para representar fielmente una matriz de Markov, debe estar normalizado por la correspondiente matriz de grados :
ahora representa una cadena de Markov. es la probabilidad de pasar de a en un paso de tiempo. De manera similar, la probabilidad de pasar de a en t pasos de tiempo viene dado por. Aquí es la matriz multiplicado por sí mismo t veces.
La matriz de Markov constituye una idea de la 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 solo las características locales de los datos se consideran en los mapas de difusión en lugar de tomar correlaciones de todo el conjunto de datos.
define un recorrido aleatorio en el conjunto de datos, lo que significa que el kernel captura alguna 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 la caminata 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. [38] La metáfora de la difusión surge de la definición de una distancia de difusión familiar {}
Para t fijo, define una distancia entre dos puntos cualesquiera del conjunto de datos en función de la conectividad de la ruta: el valor de será más pequeño cuanto más caminos que conectan x a y , y viceversa. Porque la cantidad implica una suma de todos los caminos 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 xey al calcular la distancia y sirve como una mejor noción de proximidad que la distancia euclidiana o incluso la distancia geodésica.
Escalado multidimensional local
El escalado multidimensional local realiza un escalado multidimensional en regiones locales y luego utiliza la optimización convexa para unir todas las piezas. [40]
PCA no lineal
La PCA no lineal (NLPCA) utiliza la retropropagación para entrenar un perceptrón multicapa (MLP) para que se ajuste a un colector. [41] 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.
Escalado de alta dimensión basado en datos
El escalado de alta dimensión basado en datos (DD-HDS) [42] está estrechamente relacionado con el mapeo de Sammon y el análisis de componentes curvilíneos, excepto que (1) penaliza simultáneamente los barrios falsos y las roturas al centrarse en distancias pequeñas tanto en el espacio original como en el de salida, y (2) tiene en cuenta el fenómeno de concentración de medida adaptando la función de ponderación a la distribución de la distancia.
Escultura múltiple
Manifold Sculpting [43] 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 las dimensiones más altas, al mismo tiempo que ajusta los puntos en las dimensiones más bajas para preservar esas relaciones. Si la tasa de escalado es pequeña, puede encontrar incrustaciones muy precisas. Cuenta con una precisión empírica más alta que otros algoritmos con varios problemas. También se puede utilizar para refinar los resultados de otros múltiples algoritmos de aprendizaje. Sin embargo, tiene dificultades para desplegar algunas variedades, a menos que se utilice una velocidad de escalado muy lenta. No tiene modelo.
RankVisu
RankVisu [44] está diseñado para preservar el rango de vecindad en lugar de distancia. RankVisu es especialmente útil en tareas difíciles (cuando la preservación de la distancia no se puede lograr satisfactoriamente). De hecho, el rango del vecindario es menos informativo que la distancia (los rangos se pueden deducir de las distancias pero las distancias no se pueden deducir de los rangos) y, por lo tanto, su conservación es más fácil.
Incrustación isométrica con restricciones topológicas
La incrustación isométrica topológicamente restringida (TCIE) [45] es un algoritmo basado en la aproximación de distancias geodésicas después de filtrar geodésicas inconsistentes 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 detecta en primer lugar los posibles puntos límite en los datos y, durante el cálculo de la longitud geodésica, marca las geodésicas inconsistentes, para que se le dé un pequeño peso en la mayorización de estrés ponderado que sigue.
Aproximación y proyección de colector uniforme
La aproximación y proyección de colector uniforme (UMAP) es una técnica de reducción de dimensionalidad no lineal. [46] Visualmente, es similar a t-SNE, pero asume que los datos se distribuyen uniformemente en una variedad Riemanniana localmente conectada y que la métrica Riemanniana es localmente constante o aproximadamente localmente constante. [47]
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 matriz de similitud o matriz de distancia . Todos estos métodos se incluyen en la clase más amplia de escalado multidimensional métrico . Las variaciones tienden a ser diferencias en cómo se calculan los datos de proximidad; por ejemplo, Isomap , incrustaciones lineales locales , despliegue de varianza máxima y mapeo Sammon (que de hecho no es un mapeo) son ejemplos de métodos de escalado multidimensional métrico.
Ver también
- Análisis discriminante
- Mapa elástico
- Aprendizaje de funciones
- Mapa autoorganizado en crecimiento (GSOM)
- Mapa autoorganizado (SOM)
- Teorema de Taken
- Teorema de inclusión de Whitney
Referencias
- ^ Lawrence, Neil D (2012). "Una perspectiva probabilística unificadora para la reducción de dimensionalidad espectral: conocimientos y nuevos modelos" . Revista de investigación sobre aprendizaje automático . 13 (mayo): 1609–1638. arXiv : 1010.4830 . Código Bib : 2010arXiv1010.4830L .
- ^ John A. Lee, Michel Verleysen, Reducción de dimensionalidad no lineal, Springer, 2007.
- ^ Gashler, M. y Martinez, T., Reducción de dimensionalidad no lineal temporal , en las actas de la Conferencia conjunta internacional sobre redes neuronales IJCNN'11 , págs. 1959-1966, 2011
- ^ La ilustración está preparada con software libre: EM Mirkes, Análisis de componentes principales y mapas autoorganizados : subprograma . Universidad de Leicester, 2011
- ^ Yin, Hujun; Manifolds principales no lineales de aprendizaje mediante mapas autoorganizados, en AN Gorban, B. Kégl, DC Wunsch y A. Zinovyev (Eds.), Manifolds principales para visualización de datos y reducción de dimensiones , Lecture Notes in Computer Science and Engineering (LNCSE), vol. 58, Berlín, Alemania: Springer, 2007, Cap. 3, págs. 68-95. ISBN 978-3-540-73749-0
- ↑ B. Schölkopf, A. Smola, K.-R. Müller, Análisis de componentes no lineales como problema de valores propios del núcleo. Computación neuronal 10 (5): 1299-1319, 1998, MIT Press Cambridge, MA, EE. UU., Doi: 10.1162 / 089976698300017467
- ^ Jihun Ham, Daniel D. Lee, Sebastian Mika, Bernhard Schölkopf. Una vista del 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
- ^ Gorban, AN; Zinovyev, A. (2010). "Principales variedades y gráficos 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 .
- ^ A. Zinovyev, ViDaExpert - Herramienta de visualización de datos multidimensionales (gratuita para uso no comercial). Institut Curie , París.
- ^ A. Zinovyev, descripción general de ViDaExpert , IHES ( Institut des Hautes Études Scientifiques ), Bures-Sur-Yvette, Île-de-France.
- ^ Hastie, T. (noviembre de 1984). Principales Curvas y Superficies (PDF) (Tesis Doctoral). Stanford Linear Accelerator Center, Universidad de Stanford.
- ^ Hastie, T .; Stuetzle, W. (junio de 1989). "Curvas principales" (PDF) . Revista de la Asociación Estadounidense de Estadística . 84 (406): 502–506.
- ^ Gorban, AN ; Kégl, B .; Wunsch, DC; Zinovyev, A., eds. (2007). Colectores principales para visualización de datos y reducción de dimensiones . Lecture Notes in Computer Science and Engineering (LNCSE). Vol. 58. Berlín - Heidelberg - Nueva York: Springer. ISBN 978-3-540-73749-0.
|volume=
tiene texto extra ( ayuda ) - ^ Belkin, Mikhail; Niyogi, Partha (2001). "Mapas propios laplacianos y técnicas espectrales para la incrustación y agrupación". Avances en sistemas de procesamiento de información neuronal . Prensa del MIT. 14 : 586–691.
- ^ a b Belkin, Mikhail (agosto de 2003). Problemas de aprendizaje en colectores (tesis doctoral). Departamento de Matemáticas, Universidad de Chicago.El código de Matlab para los mapas propios de Laplacia se puede encontrar en algoritmos en Ohio-state.edu
- ^ Bengio, Yoshua; et al. (2004). "Extensiones fuera de muestra para LLE, Isomap, MDS, mapas propios y agrupación espectral" (PDF) . Avances en sistemas de procesamiento de información neuronal .
- ^ Tenenbaum, J .; Freeman, W. (2000). "Separando estilo y contenido con modelos bilineales". Computación neuronal . 12 (6): 1247–1283. doi : 10.1162 / 089976600300015349 . PMID 10935711 . S2CID 9492646 .
- ^ Lewandowski, M .; Martínez-del Rincón, J .; Makris, D .; Nebel, J.-C. (2010). "Extensión temporal de mapas propios laplacianos para la reducción de dimensionalidad no supervisada de series de tiempo" . Actas de la Conferencia Internacional sobre Reconocimiento de Patrones (ICPR) .
- ^ a b Lewandowski, M .; Makris, D .; Velastin, SA; Nebel, J.-C. (2014). "Mapas propios laplacianos estructurales para modelar conjuntos de secuencias multivariantes". Transacciones IEEE sobre cibernética . 44 (6): 936–949. doi : 10.1109 / TCYB.2013.2277664 . PMID 24144690 . S2CID 110014 .
- ^ Martinez-del-Rincon, J .; Lewandowski, M .; Nebel, J.-C .; Makris, D. (2014). "Mapas propios laplacianos generalizados para el modelado y seguimiento de movimientos humanos". Transacciones IEEE sobre cibernética . 44 (9): 1646–1660. doi : 10.1109 / TCYB.2013.2291497 . PMID 25137692 . S2CID 22681962 .
- ^ JB Tenenbaum, V. de Silva, JC Langford, Un marco geométrico global para la reducción de dimensionalidad no lineal , Ciencia 290, (2000), 2319-2323.
- ^ ST Roweis y LK Saul, Reducción de dimensionalidad no lineal por incrustación localmente lineal , Science Vol 290, 22 de diciembre de 2000, 2323-2326.
- ^ Donoho, D .; Grimes, C. (2003). "Mapas propios de Hesse: técnicas de incrustación localmente lineal para datos de alta dimensión" . Proc Natl Acad Sci USA . 100 (10): 5591–5596. doi : 10.1073 / pnas.1031596100 . PMC 156245 . PMID 16576753 .
- ^ Z. Zhang y J. Wang, "MLLE: incrustación lineal localmente modificada utilizando pesos múltiples" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.382
- ^ Sidhu, Gagan (2019). "Selección de características de incrustación localmente lineal y fMRI en 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 .
- ^ Zhang, Zhenyue; Hongyuan Zha (2005). "Manifolds principales y reducción de dimensión no lineal a través de la alineación del espacio tangente local". Revista SIAM de Computación Científica . 26 (1): 313–338. CiteSeerX 10.1.1.211.9957 . doi : 10.1137 / s1064827502419154 .
- ^ Bengio, Yoshua; Monperrus, Martin; Larochelle, Hugo (octubre de 2006). "Estimación no local de la estructura del colector" (PDF) . Computación neuronal . 18 (10): 2509-2528. doi : 10.1162 / neco.2006.18.10.2509 . ISSN 0899-7667 . PMID 16907635 . S2CID 1416595 .
- ^ N. Lawrence, Análisis probabilístico de componentes principales no lineales con modelos de variables latentes del proceso gaussiano , Journal of Machine Learning Research 6 (noviembre): 1783-1816, 2005.
- ^ M. Ding, G. Fan, Manifolds de posición de marcha conjunta multicapa para el modelado del movimiento de la marcha humana , IEEE Transactions on Cybernetics, Volumen: 45, Número: 11, noviembre de 2015.
- ^ van der Maaten, LJP; Hinton, GE (noviembre de 2008). "Visualización de datos de alta dimensión utilizando t-SNE" (PDF) . Revista de investigación sobre aprendizaje automático . 9 : 2579-2605.
- ^ James X. Li, Visualización de datos de alta dimensión con mapa de perspectiva relacional , Visualización de información (2004) 3, 49-59
- ^ 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" . Comunicaciones de la naturaleza . 6 : 7723. doi : 10.1038 / ncomms8723 . PMC 4566922 . PMID 26194875 .
- ^ a b 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) . Transacciones IEEE en redes neuronales . 8 (1): 148-154. doi : 10.1109 / 72.554199 . PMID 18255618 .
- ^ 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 del lado d. págs. 81–86.
- ^ Christian Walder y Bernhard Schölkopf, Reducción de dimensionalidad difeomórfica , Avances en sistemas de procesamiento de información neuronal 22, 2009, págs. 1713-1720, MIT Press
- ^ Wang, Chang; Mahadevan, Sridhar (julio de 2008). Alineación de colectores mediante análisis de Procrustes (PDF) . La 25a Conferencia Internacional de Aprendizaje Automático. págs. 1120–1127.
- ^ Lafon, Stephane (mayo de 2004). Mapas de Difusión y Armónicos Geométricos (Tesis Doctoral). Universidad de Yale .
- ^ a b Coifman, Ronald R .; Lafon, Stephane (19 de junio de 2006). "Mapas de difusión". Ciencia .
- ^ Bah, B. (2008). Mapas de Difusión: Aplicaciones y Análisis (Tesis de Maestría). Universidad de Oxford.
- ^ Venna, J .; Kaski, S. (2006). "Escalado multidimensional local". Redes neuronales . 19 (6–7): 889–899. doi : 10.1016 / j.neunet.2006.05.014 . PMID 16787737 .
- ^ Scholz, M .; Kaplan, F .; Guy, CL; Kopka, J .; Selbig, J. (2005). "PCA no lineal: un enfoque de datos faltantes" . Bioinformática . Prensa de la Universidad de Oxford. 21 (20): 3887–3895. doi : 10.1093 / bioinformatics / bti634 . PMID 16109748 .
- ^ 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.
- ^ Gashler, M. y Ventura, D. y Martinez, T., Reducción de dimensionalidad no lineal iterativa con escultura múltiple , In Platt, JC y Koller, D. y Singer, Y. y Roweis, S., editor, Avances en Sistemas de procesamiento de información neuronal 20, págs. 513–520, MIT Press, Cambridge, MA, 2008
- ^ Lespinats S., Fertil B., Villemain P. y Herault J., Rankvisu: Mapeo de la red de vecinos , Neurocomputing, vol. 72 (13–15), págs. 2964–2978, 2009.
- ^ Rosman G., Bronstein MM, Bronstein AM y Kimmel R., Reducción de dimensionalidad no lineal por incrustación isométrica con restricciones topológicas , International Journal of Computer Vision, Volumen 89, Número 1, 56–68, 2010
- ^ McInnes, Leland; Healy, John; Melville, James (7 de diciembre de 2018). "Aproximación y proyección de colector uniforme para reducción de dimensiones". arXiv : 1802.03426 .
- ^ "UMAP: Aproximación uniforme de colector y proyección para reducción de dimensiones - documentación de umap 0.3" . umap-learn.readthedocs.io . Consultado el 4 de mayo de 2019 .
enlaces externos
- Isomap
- Cartografía topográfica generativa
- Tesis de Mike Tipping
- Modelo de variable latente del proceso gaussiano
- Incrustación localmente lineal
- Mapa de perspectiva relacional
- Waffles es una biblioteca C ++ de código abierto que contiene implementaciones de LLE, Manifold Sculpting y algunos otros algoritmos de aprendizaje.
- 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 con codificador automático