Reducción de dimensionalidad no lineal.

Proyección de datos sobre variedades de dimensiones inferiores.

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, izquierda y derecha: recuperaciones 2D del colector, respectivamente, utilizando los algoritmos LLE y Hessian LLE implementados por el kit de herramientas de procesamiento de datos modular.

La reducción de dimensionalidad no lineal , también conocida como aprendizaje de variedades , es cualquiera de varias técnicas relacionadas que tienen como objetivo proyectar datos de alta dimensión en variedades latentes de dimensiones inferiores , con el objetivo de visualizar los datos en el espacio de baja dimensión o aprender el mapeo. (ya sea desde el espacio de alta dimensión a la incrustación de baja dimensión o viceversa) en sí. ^{[1] [2]} Las técnicas que se describen 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 de valores singulares y el análisis de componentes principales .

Aplicaciones de NLDR

Considere un conjunto de datos representado como una matriz (o una tabla de base de datos), de modo que cada fila represente 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 únicas posibles es exponencialmente grande. Por tanto, cuanto mayor es la dimensionalidad, más difícil resulta muestrear el espacio. Esto causa muchos problemas. Los algoritmos que operan con datos de alta dimensión tienden a tener una complejidad temporal muy alta. Muchos algoritmos de aprendizaje automático, por ejemplo, tienen dificultades 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 dimensiones elevadas. Por lo tanto, reducir los datos a una pequeña cantidad de dimensiones es útil para fines de visualización.

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

Las representaciones de datos de dimensiones reducidas a menudo se denominan "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 ha sido escalada y rotada en cantidades variables. Cada imagen tiene 32×32 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 sólo dos dimensiones.

PCA (un algoritmo de reducción de dimensionalidad lineal) se utiliza para reducir este mismo conjunto de datos en 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 en 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 resultar 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 de una variedad en un espacio de alta dimensión, y las variables intrínsecas de esa variedad representarán la posición y 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 fase, las trayectorias cercanas convergerán hacia ella y permanecerán en ella indefinidamente, convirtiéndola en una candidata para la reducción de dimensionalidad del sistema dinámico. Si bien no se garantiza que tales variedades existan en general, la teoría de las subvariedades espectrales (SSM) proporciona las condiciones para la existencia de objetos invariantes que atraen únicos en una amplia clase de sistemas dinámicos. ^[3] La investigación activa en NLDR busca desplegar las múltiples observaciones asociadas con los sistemas dinámicos para desarrollar técnicas de modelado. ^[4]

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 NLDR.

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

Mapa autoorganizado

El mapa autoorganizado (SOM, también llamado mapa de Kohonen ) y su variante probabilística de 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 desde el espacio incrustado hasta el 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 kernel.

Quizás el algoritmo más utilizado para la reducción dimensional sea el kernel PCA . ^[7] 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 en 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 en los primeros k vectores propios de esa matriz, al igual que PCA. Utiliza el truco del kernel para descartar gran parte del cálculo, de modo que todo el proceso se pueda realizar sin tener que realizar cálculos . Por supuesto, debe elegirse de modo que tenga un núcleo correspondiente conocido. Desafortunadamente, no es trivial encontrar un buen núcleo para un problema determinado, por lo que KPCA no produce buenos resultados con algunos problemas cuando se utilizan núcleos estándar. Por ejemplo, se sabe que estos granos funcionan mal en el colector de rodillos suizos . Sin embargo, se pueden ver otros métodos que funcionan bien en tales entornos (por ejemplo, mapas propios laplacianos, LLE) como casos especiales de PCA del núcleo mediante la construcción de una matriz del núcleo 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 incorporació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 , incidencia de tuberculosis . Diferentes formas y colores corresponden a diversas ubicaciones geográficas. La línea roja en negrita representa la curva principal , que se aproxima al conjunto de datos. Esta curva principal fue producida por el método del mapa elástico . ^[10]

Las curvas y variedades principales brindan 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 integrada y la codificación utilizando una 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] 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. Generalmente, 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 los 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] 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 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 se rige por la proximidad de los puntos vecinos (utilizando, por ejemplo, el algoritmo k-vecino más cercano ). 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 garantiza que los puntos cercanos entre sí en la variedad 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 la variedad sirven como dimensiones de incrustación, ya que en condiciones suaves este operador tiene un espectro contable que es la base para funciones cuadradas integrables en la variedad (compárese con la serie de Fourier en la variedad de círculo unitario). Los intentos de colocar los mapas propios laplacianos 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 laplaciana converge al operador de Laplace-Beltrami cuando el número de puntos llega al infinito. ^[15]

isomapa

Isomap ^[17] es una combinación del algoritmo Floyd-Warshall con el escalado 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 efectivamente 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 dimensiones reducidas 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 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 las vecindades locales en cada punto de la variedad subyacente.

Incrustación localmente lineal

La incrustación localmente lineal (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 algoritmos de matriz dispersa y mejores resultados con muchos problemas. LLE también comienza encontrando 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 mal las densidades de muestra no uniformes porque no existe una unidad fija para evitar que las ponderaciones 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 en función de sus vecinos X _j . El punto original se reconstruye mediante una combinación lineal, dada por la matriz de pesos Wij _, de sus vecinos. El error de reconstrucción viene 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 Wij _se refieren a la cantidad de contribución que tiene el punto _Xj al reconstruir el _punto Xi . La función de costo se minimiza bajo dos restricciones: (a) Cada punto de datos Xi se reconstruye sólo a partir de sus vecinos, lo que obliga a que _W j _sea cero si el punto X _j no es vecino del punto Xi _y (b) La suma de cada fila de la matriz de peso es igual a 1.

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

Los puntos de datos originales se recopilan en un espacio D dimensional y el objetivo del algoritmo es reducir la dimensionalidad a d tal que D >> d . Los mismos pesos Wij _que reconstruyen el i -ésimo punto de datos en el espacio dimensional D se utilizarán para reconstruir el mismo punto en el espacio dimensional d inferior . A partir de esta idea se crea un mapa de preservación del barrio. Cada punto Xi _en el espacio dimensional D se asigna a un punto Y _i en el espacio dimensional 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 costos, a diferencia de la anterior, los pesos Wij _se mantienen fijos y la minimización se realiza en los puntos Yi _para optimizar las coordenadas. Este problema de minimización se puede resolver resolviendo un problema de valores propios dispersos N X N ( siendo N el número de puntos de datos), cuyos d vectores propios inferiores 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 localmente lineal de Hesse (LLE de Hesse)

Al igual que LLE, Hessian LLE también se basa en técnicas de matrices dispersas. ^[19] Tiende a producir resultados de una calidad mucho mayor que LLE. Desafortunadamente, tiene una complejidad computacional muy costosa, por lo que no es adecuado para variedades con muchas muestras. No tiene modelo interno.

Incrustación localmente lineal modificada (MLLE)

El LLE modificado (MLLE) ^[20] es otra variante de LLE que utiliza múltiples pesos en cada vecindario para abordar el problema de condicionamiento de la matriz de pesos local que conduce a distorsiones en los mapas de LLE. En términos generales, 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. ^[21]

Alineación del espacio tangente local

LTSA ^[22] 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 vecindad local. Luego optimiza para encontrar una incrustación que alinee los espacios tangentes.

Despliegue de varianza máxima

El despliegue de varianza máxima , el isomap 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, entonces se maximiza la varianza sobre los puntos. Su paso inicial, al igual que Isomap y Locally Linear Embedding, 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, restringida de tal manera que se preserven las distancias entre puntos vecinos. La principal contribución de este algoritmo es una técnica para plantear 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 localmente lineal, no tiene modelo interno.

codificadores automáticos

Un codificador automático 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 de 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 del espacio de baja a alta dimensión. Aunque la idea de los codificadores automáticos es bastante antigua, ^[23] el entrenamiento de codificadores automáticos profundos sólo recientemente ha sido posible mediante el uso de máquinas Boltzmann restringidas y codificadores automáticos apilados con eliminación de ruido. Relacionado con los codificadores automáticos está el algoritmo NeuroScale, que utiliza funciones de estrés inspiradas en el escalado multidimensional y mapeos de Sammon (ver arriba) para aprender un mapeo no lineal desde el espacio de alta dimensión al incrustado. Las asignaciones en NeuroScale se basan en redes de funciones de base radial .

Modelos de variables latentes del proceso gaussiano

Los modelos de variables latentes de procesos gaussianos (GPLVM) ^[24] son ​​métodos probabilísticos de reducción de dimensionalidad que utilizan procesos gaussianos (GP) para encontrar una incrustación no lineal de dimensiones inferiores 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 luego se marginan las variables latentes y se obtienen los parámetros maximizando la probabilidad. Al igual que el PCA del núcleo, utilizan una función del núcleo para formar un mapeo no lineal (en forma de proceso gaussiano ). Sin embargo, en GPLVM el mapeo es desde el espacio incrustado (latente) al espacio de datos (como las 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. GPLVM y sus muchas variantes se han propuesto especialmente para el modelado de movimiento humano, por ejemplo, GPLVM con restricción posterior, modelo dinámico GP (GPDM), GPDM equilibrado (B-GPDM) y GPDM topológicamente restringido. Para capturar el efecto de acoplamiento de las variedades de postura y marcha en el análisis de la marcha, se propuso una combinación de múltiples capas de postura y marcha. ^[25]

incrustación de vecinos estocásticos distribuidos en t

La incrustación de vecinos estocásticos distribuidos en t (t-SNE) ^[26] se utiliza ampliamente. Pertenece a una familia de métodos de incrustación de vecinos estocásticos. 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 incorporaciones 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 escala 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 diferencias) entre los puntos de datos representan una fuerza repulsiva. A medida que la variedad crece gradualmente en 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 cargadas positivamente se mueven libremente sobre la superficie de una bola. Guiada por la fuerza de Coulomb entre partículas, la configuración energética 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. ^[27] El algoritmo utilizó primero el toroide plano como variedad de imágenes, luego se amplió (en el software VisuMap para usar otros tipos de variedades cerradas, como la esfera , el espacio proyectivo y Klein). botella , como colectores de imágenes.

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 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 CCA, como algoritmo de aprendizaje iterativo, en realidad comienza centrándose en distancias grandes (como el algoritmo de Sammon) y luego cambia gradualmente el foco a distancias pequeñas. La información de distancias pequeñas sobrescribirá la información de distancias grandes, si es necesario hacer concesiones entre ambas.

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

Análisis de distancia curvilínea

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

Reducción de dimensionalidad difeomorfa.

La reducción de dimensionalidad difeomorfica o Diffeomap ^[31] aprende un mapeo difeomorfo suave que transporta los datos a un subespacio lineal de dimensiones inferiores. El método resuelve 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 terminen en un subespacio lineal de dimensiones inferiores, intentando así preservar las diferencias por pares tanto en el mapeo directo como en el 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 el conocimiento de un dominio se puede transferir a otro. La mayoría de las técnicas de alineación consideran sólo dos conjuntos de datos, pero el concepto se extiende a muchos conjuntos de datos iniciales arbitrarios. ^[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 en funciones definidas en el gráfico cuyos nodos fueron muestreados de la variedad. ^[33] En particular, supongamos que un conjunto de datos esté representado por . La suposición subyacente del mapa de difusión es que los datos de alta dimensión se encuentran en una variedad de dimensión de baja 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 preserva la 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 que define 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 gráfico laplaciano.

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 el vecino más cercano de . Correctamente, la distancia geodésica debe usarse para medir 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 a la distancia euclidiana. La elección modula nuestra noción de proximidad en el sentido de que si entonces y si entonces . 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. 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 pasar de a en un paso de tiempo. De manera similar, la probabilidad de pasar de a en t pasos de tiempo viene 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 paseo 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ápida y lenta a través de los valores del núcleo. A medida que la caminata se propaga 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 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á menor cuantos más caminos conecten xey y viceversa . Debido a que 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 solo 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}}$

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. ^[36]

PCA no lineal

La PCA no lineal (NLPCA) utiliza la propagación hacia atrás 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 se asigna 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) ^[38] está estrechamente relacionado con el mapeo y el análisis de componentes curvilíneos de Sammon, excepto que (1) penaliza simultáneamente las falsas vecindades y los desgarros al centrarse en distancias pequeñas tanto en el espacio original como en el de salida, y que (2) tiene en cuenta el fenómeno de concentración de la medida adaptando la función de ponderación a la distribución de distancia.

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 las vecindades locales. Lentamente reduce la variación de las dimensiones superiores y, al mismo tiempo, ajusta los puntos en las dimensiones inferiores para preservar esas relaciones. Si la tasa de escalado es pequeña, se pueden encontrar incrustaciones muy precisas. Ofrece una mayor precisión empírica 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 tasa de escala muy lenta. No tiene modelo.

RangoVisu

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 de forma satisfactoria mantener la distancia). De hecho, el rango de vecindad 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 tanto, su preservación es más fácil.

Incrustación isométrica topológicamente restringida

La incrustación isométrica topológicamente restringida (TCIE) ^[41] 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 de peso 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 inconsistentes, para recibir una pequeña ponderación en la mayorización de tensiones ponderadas 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] Visualmente, es similar a t-SNE, pero supone que los datos se distribuyen uniformemente en una variedad de Riemann conectada localmente y que la métrica de Riemann es localmente constante o aproximadamente localmente constante. ^[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 pertenecen a 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, isomap , incrustaciones localmente lineales , despliegue de varianza máxima y mapeo de Sammon (que en realidad no es un mapeo) son ejemplos de métodos de escalamiento multidimensional métrico.

Ver también

• Hipótesis múltiple
• Subvariedad espectral
• teorema de tomado
• Teorema de incrustación de Whitney
• Análisis discriminante
• mapa elástico
• Aprendizaje de funciones
• Mapa autoorganizado en crecimiento (GSOM)
• Mapa autoorganizado (SOM)

Referencias

1. Lawrence, Neil D (2012). "Una perspectiva probabilística unificadora para la reducción de la dimensionalidad espectral: conocimientos y nuevos modelos". Revista de investigación sobre aprendizaje automático . 13 (mayo): 1609–38. arXiv : 1010.4830 . Código Bib : 2010arXiv1010.4830L.
2. Lee, John A.; Verleysen, Michel (2007). Reducción de dimensionalidad no lineal . Saltador. 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 temporal no lineal (PDF) . Actas de la Conferencia Internacional Conjunta sobre Redes Neuronales IJCNN'11. págs. 1959–66.
5. La ilustración está preparada con software gratuito: 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; Kegl, B.; Wunsch, DC; Zinovyev, A. (eds.). Principales colectores para visualización de datos y reducción de dimensiones . Apuntes de conferencias sobre informática e ingeniería. vol. 58. Saltador. 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 núcleo". Computación neuronal . 10 (5). Prensa del MIT : 1299–1319. doi :10.1162/089976698300017467. S2CID  6674407.
8. Jamón, Jihun; Lee, Daniel D.; Mika, Sebastián; Schölkopf, Bernhard. "Una visión central de la reducción de dimensionalidad de variedades". Actas de la XXI Conferencia Internacional sobre Aprendizaje Automático, Banff, Canadá, 2004 . doi :10.1145/1015330.1015417.
9. Gorban, AN; Zinóviev, 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.
10. A. Zinovyev, ViDaExpert - Herramienta de visualización de datos multidimensionales Institut Curie , París.
11. Hastie, T. (noviembre de 1984). Curvas y superficies principales (PDF) (Doctor). Centro del Acelerador Lineal de Stanford, Universidad de Stanford. Archivado (PDF) desde el 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 ; Kegl, B.; Wunsch, DC; Zinoviev, A., eds. (2007). Manifolds principales para visualización de datos y reducción de dimensiones. Apuntes de conferencias en Ingeniería y Ciencias de la Computación (LNCSE). vol. 58. Saltador. ISBN 978-3-540-73749-0.
14. Belkin, Miguel; Niyogi, Partha (2001). "Mapas propios laplacianos y técnicas espectrales para incrustación y agrupación" (PDF) . Avances en los sistemas de procesamiento de información neuronal . 14 . Prensa del MIT: 586–691. ISBN 0-262-27173-7. OCLC  52710683.
15. Belkin, Mikhail (agosto de 2003). Problemas de aprendizaje sobre variedades (Doctor). 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-François; Vicente, Pascal; Delalleau, Olivier; Le Roux, Nicolás; Ouimet, Marie (2004). "Extensiones fuera de muestra para LLE, Isomap, MDS, Eigenmaps y agrupación espectral" (PDF) . Avances en los sistemas de procesamiento de información neuronal . vol. 16. Prensa del MIT. ISBN 0-262-20152-6.
17. Tenenbaum, JB.; de Silva, V.; Langford, JC (2000). "Un marco geométrico global para la reducción de dimensionalidad no lineal" (PDF) . Ciencia . 290 (5500): 2319–23. Código bibliográfico : 2000Sci...290.2319T. doi : 10.1126/ciencia.290.5500.2319. PMID  11125149. S2CID  221338160.
18. Roweis, ST; Saúl, LK (2000). "Reducción de dimensionalidad no lineal mediante incrustación localmente lineal". Ciencia . 290 (5500): 2323–6. Código Bib : 2000 Ciencia... 290.2323R. doi : 10.1126/ciencia.290.5500.2323. PMID  11125150. S2CID  5987139.
19. 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 Estados Unidos . 100 (10): 5591–6. Código bibliográfico : 2003PNAS..100.5591D. doi : 10.1073/pnas.1031596100 . PMC 156245 . PMID  16576753. 
20. Zhang, Z.; Wang, J. (2006). "MLLE: incrustación lineal local modificada utilizando múltiples pesos". NIPS'06: Actas de la XIX Conferencia Internacional sobre Sistemas de Procesamiento de Información Neural : 1593–1600.
21. Sidhu, Gagan (2019). "Incrustación localmente lineal y selección de funciones de resonancia magnética funcional 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. 
22. Zhang, Zhenyue; Hongyuan Zha (2005). "Múltiples principales y reducción de dimensiones no lineales mediante 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. 
23. DeMers, D.; Cottrell, GW (1993). "Reducción de dimensionalidad no lineal". Avances en los 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 de componentes principales no lineal con modelos de variables latentes del proceso gaussiano". Revista de investigación sobre aprendizaje automático . 6 : 1783–1816.
25. Ding, M.; Fan, G. (2015). "Múltiples multicapa de postura de marcha conjunta para modelado del movimiento de la marcha humana". Transacciones IEEE sobre cibernética . 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 sobre 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 información . 3 : 49–59. doi : 10.1057/palgrave.ivs.9500051. S2CID  7566939.
28. Taylor, D.; Klimm, F.; Harrington, HA; Kramar, M.; Mischaikow, K.; Portero, 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. arXiv : 1408.1168 . Código Bib : 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) . Transacciones IEEE en redes neuronales . 8 (1): 148-154. doi : 10.1109/72.554199. PMID  18255618.
30. Sol, 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.
31. Walder, cristiano; Schölkopf, Bernhard (2009). "Reducción de dimensionalidad difeomorfa" (PDF) . Avances en los sistemas de procesamiento de información neuronal . vol. 22. Prensa del MIT. págs. 1713–20.
32. Wang, Chang; Mahadevan, Sridhar (julio de 2008). Alineación de colectores mediante análisis de Procrustes (PDF) . La 25ª Conferencia Internacional sobre Aprendizaje Automático. págs. 1120–7.
33. Lafon, Stéphane (mayo de 2004). Mapas de difusión y armónicos geométricos (Doctor). Universidad de Yale .
34. Coifman, Ronald R.; Lafon, Stéphane (julio de 2006). «Mapas de difusión» (PDF) . Análisis Armónico Aplicado y Computacional . 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). "Escalado multidimensional local". Redes neuronales . 19 (6–7): 889–899. doi :10.1016/j.neunet.2006.05.014. PMID  16787737.
37. Scholz, M.; Kaplan, F.; chico, CL; Kopka, J.; Selbig, J. (2005). "PCA no lineal: un enfoque de datos faltantes". Bioinformática . 21 (20). Prensa de la Universidad de Oxford: 3887–95. doi : 10.1093/bioinformática/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 dimensionalidad no lineal con escultura múltiple , en 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
40. Lespinats S., Fertil B., Villemain P. y Herault J., Rankvisu: Mapeo de la red vecinal, Neurocomputación, 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, Juan; Melville, James (7 de diciembre de 2018). "Aproximación y proyección de colectores uniformes para reducción de dimensiones". arXiv : 1802.03426 .
43. "UMAP: proyección y aproximación de colector uniforme para reducción de dimensiones - documentación de umap 0.3". umap-learn.readthedocs.io . Consultado el 4 de mayo de 2019 .

Otras lecturas

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

enlaces externos

• isomapa
• Mapeo topográfico generativo
• La 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 múltiples 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 de codificador automático.