Mapa de difusión

Dados puntos de datos muestreados de manera no uniforme en una hélice toroidal (arriba), se trazan las dos primeras coordenadas del mapa de difusión con normalización de Laplace-Beltrami (abajo). El Mapa de Difusión desenreda la hélice toroidal recuperando la geometría circular intrínseca subyacente de los datos.

Los mapas de difusión son un algoritmo de reducción de dimensionalidad o extracción de características introducido por Coifman y Lafon ^{[1] [2] [3] [4]} que calcula una familia de incrustaciones de un conjunto de datos en el espacio euclidiano (a menudo de baja dimensión) cuyas coordenadas pueden ser calculado a partir de los vectores propios y valores propios de un operador de difusión en los datos. La distancia euclidiana entre puntos en el espacio incrustado es igual a la "distancia de difusión" entre distribuciones de probabilidad centradas en esos puntos. A diferencia de los métodos de reducción de dimensionalidad lineal, como el análisis de componentes principales (PCA), los mapas de difusión son parte de la familia de métodos de reducción de dimensionalidad no lineal que se centran en descubrir la variedad subyacente de la que se han tomado muestras de los datos. Al integrar similitudes locales a diferentes escalas, los mapas de difusión brindan una descripción global del conjunto de datos. En comparación con otros métodos, el algoritmo del mapa de difusión es robusto a la perturbación del ruido y computacionalmente económico.

Definición de mapas de difusión

Los siguientes mapas de difusión ^[3] y ^[5] se pueden definir en cuatro pasos.

Conectividad

Los mapas de difusión explotan la relación entre la difusión de calor y la cadena de Markov de paseo aleatorio . La observación básica es que si realizamos un paseo aleatorio sobre los datos, es más probable caminar hasta un punto de datos cercano que caminar hasta otro que esté lejos. Sea un espacio de medida , donde está el conjunto de datos y representa la distribución de los puntos . ${\displaystyle (X,{\mathcal {A}},\mu )}$ ${\displaystyle X}$ ${\displaystyle \mu }$ ${\displaystyle X}$

En base a esto, la conectividad entre dos puntos de datos, y , se puede definir como la probabilidad de caminar de a en un paso de la caminata aleatoria. Generalmente, esta probabilidad se especifica en términos de una función nuclear de los dos puntos: . Por ejemplo, el popular núcleo gaussiano: ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle k:X\times X\rightarrow \mathbb {R} }$

${\displaystyle k(x,y)=\exp \left(-{\frac {||x-y||^{2}}{\epsilon }}\right)}$

De manera más general, la función del núcleo tiene las siguientes propiedades

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

( es simétrico) ${\displaystyle k}$

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

( preserva la positividad). ${\displaystyle k}$

El núcleo constituye la definición previa de la geometría local del conjunto de datos. Dado que un núcleo determinado capturará una característica específica del conjunto de datos, su elección debe estar guiada por la aplicación que se tenga en mente. Esta es una diferencia importante con métodos como el análisis de componentes principales , donde las correlaciones entre todos los puntos de datos se tienen en cuenta a la vez.

Dado , podemos construir una cadena de Markov de tiempo discreto reversible (un proceso conocido como construcción laplaciana del gráfico normalizado): ${\displaystyle (X,k)}$ ${\displaystyle X}$

${\displaystyle d(x)=\int _{X}k(x,y)d\mu (y)}$

y definir:

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

Aunque el nuevo núcleo normalizado no hereda la propiedad simétrica, sí hereda la propiedad de conservación de la positividad y adquiere una propiedad de conservación:

${\displaystyle \int _{X}p(x,y)d\mu (y)=1}$

Proceso de difusión

A partir de podemos construir una matriz de transición de una cadena de Markov ( ) en . En otras palabras, representa la probabilidad de transición de un paso de a y proporciona la matriz de transición de t pasos. ${\displaystyle p(x,y)}$ ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle p(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M^{t}}$

Definimos la matriz de difusión (también es una versión del gráfico matriz laplaciana ) ${\displaystyle L}$

${\displaystyle L_{i,j}=k(x_{i},x_{j})\,}$

Luego definimos el nuevo kernel.

${\displaystyle L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,}$

o equivalente,

${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }\,}$

donde D es una matriz diagonal y ${\displaystyle D_{i,i}=\sum _{j}L_{i,j}.}$

Aplicamos la normalización laplaciana del gráfico a este nuevo núcleo:

${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )},\,}$

donde es una matriz diagonal y ${\displaystyle D^{(\alpha )}}$ ${\displaystyle {D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.}$

${\displaystyle p(x_{j},t|x_{i})=M_{i,j}^{t}\,}$

Una de las ideas principales del marco de difusión es que hacer avanzar la cadena en el tiempo (tomando potencias cada vez mayores de ) revela la estructura geométrica de a escalas cada vez mayores (el proceso de difusión). Específicamente, la noción de clúster en el conjunto de datos se cuantifica como una región en la que la probabilidad de escapar de esta región es baja (dentro de un cierto tiempo t). Por lo tanto, t no sólo sirve como parámetro de tiempo, sino que también tiene la doble función de parámetro de escala. ${\displaystyle M}$ ${\displaystyle X}$

La descomposición propia de la matriz produce ${\displaystyle M^{t}}$

${\displaystyle M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,}$

donde es la secuencia de valores propios de y y son los vectores propios biortogonales derecho e izquierdo respectivamente. Debido a la caída del espectro de los valores propios, sólo se necesitan unos pocos términos para lograr una precisión relativa determinada en esta suma. ${\displaystyle \{\lambda _{l}\}}$ ${\displaystyle M}$ ${\displaystyle \{\psi _{l}\}}$ ${\displaystyle \{\phi _{l}\}}$

Parámetro α y operador de difusión.

La razón para introducir el paso de normalización es ajustar la influencia de la densidad de puntos de datos en la transición infinitesimal de la difusión. En algunas aplicaciones, el muestreo de los datos generalmente no está relacionado con la geometría de la variedad que nos interesa describir. En este caso, podemos establecer y el operador de difusión se aproxima al operador de Laplace-Beltrami. Luego recuperamos la geometría de Riemann del conjunto de datos independientemente de la distribución de los puntos. Para describir el comportamiento a largo plazo de la distribución puntual de un sistema de ecuaciones diferenciales estocásticas, podemos utilizar y la cadena de Markov resultante se aproxima a la difusión de Fokker-Planck . Con , se reduce a la normalización laplaciana del gráfico clásico. ${\displaystyle \alpha }$ ${\displaystyle \alpha =1}$ ${\displaystyle \alpha =0.5}$ ${\displaystyle \alpha =0}$

Distancia de difusión

La distancia de difusión en el tiempo entre dos puntos se puede medir como la similitud de dos puntos en el espacio de observación con la conectividad entre ellos. esta dado por ${\displaystyle t}$

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}}$

donde está la distribución estacionaria de la cadena de Markov, dada por el primer vector propio izquierdo de . Explícitamente: ${\displaystyle \phi _{0}(y)}$ ${\displaystyle M}$

${\displaystyle \phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}}$

Intuitivamente, es pequeño si hay una gran cantidad de caminos cortos que conectan y . Hay varias características interesantes asociadas con la distancia de difusión, según nuestra discusión anterior que también sirve como parámetro de escala: ${\displaystyle D_{t}(x_{i},x_{j})}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle t}$

1. Los puntos están más cerca en una escala determinada (como lo especifica ) si están altamente conectados en el gráfico, lo que enfatiza el concepto de grupo. ${\displaystyle D_{t}(x_{i},x_{j})}$
2. Esta distancia es robusta al ruido, ya que la distancia entre dos puntos depende de todos los caminos posibles de longitud entre los puntos. ${\displaystyle t}$
3. Desde el punto de vista del aprendizaje automático, la distancia tiene en cuenta todas las evidencias vinculadas a , lo que nos permite concluir que esta distancia es apropiada para el diseño de algoritmos de inferencia basados ​​en la mayoría de preponderancia. ^[3] ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

Proceso de difusión e incrustación de baja dimensión.

La distancia de difusión se puede calcular utilizando los vectores propios mediante

${\displaystyle D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,}$

Por tanto, los vectores propios se pueden utilizar como un nuevo conjunto de coordenadas para los datos. El mapa de difusión se define como:

${\displaystyle \Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))}$

Debido a la caída del espectro, es suficiente utilizar sólo los primeros k vectores propios y valores propios. Por lo tanto, obtenemos el mapa de difusión de los datos originales a un espacio k -dimensional que está incrustado en el espacio original.

En ^[6] se demuestra que

${\displaystyle D_{t}(x_{i},x_{j})^{2}\approx ||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,}$

entonces la distancia euclidiana en las coordenadas de difusión se aproxima a la distancia de difusión.

Algoritmo

El marco algorítmico básico del mapa de difusión es el siguiente:

Paso 1. Dada la matriz de similitud L.

Paso 2. Normalice la matriz según el parámetro : . ${\displaystyle \alpha }$ ${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }}$

Paso 3. Forme la matriz normalizada . ${\displaystyle M=({D}^{(\alpha )})^{-1}L^{(\alpha )}}$

Paso 4. Calcule los k valores propios más grandes de y los vectores propios correspondientes. ${\displaystyle M^{t}}$

Paso 5. Utilice el mapa de difusión para obtener la incrustación . ${\displaystyle \Psi _{t}}$

Solicitud

En el artículo ^[6] Nadler et al. mostró cómo diseñar un núcleo que reproduce la difusión inducida por una ecuación de Fokker-Planck . También explicaron que, cuando los datos se aproximan a una variedad, se puede recuperar la geometría de esta variedad calculando una aproximación del operador de Laplace-Beltrami . Este cálculo es completamente insensible a la distribución de los puntos y por lo tanto proporciona una separación de las estadísticas y la geometría de los datos. Dado que los mapas de difusión brindan una descripción global del conjunto de datos, pueden medir las distancias entre pares de puntos de muestra en la variedad en la que están incrustados los datos. Las aplicaciones basadas en mapas de difusión incluyen reconocimiento facial , ^[7] agrupamiento espectral , representación de imágenes de baja dimensión, segmentación de imágenes, ^[8] segmentación de modelos 3D, ^[9] verificación de hablantes ^[10] e identificación, ^[11] muestreo en colectores, anomalías. detección, ^{[12] [13]} imagen en pintura, ^[14] revelación de la organización de las redes del estado de reposo del cerebro ^[15] , etc.

Además, el marco de los mapas de difusión se ha extendido productivamente a redes complejas , ^[16] revelando una organización funcional de las redes que difiere de la puramente topológica o estructural.

Ver también

• Reducción de dimensionalidad no lineal.
• Agrupación espectral

Referencias

1. Coifman, RR; Lafón, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). "Difusiones geométricas como herramienta para el análisis armónico y definición de estructuras de datos: mapas de difusión". PNAS . 102 (21): 7426–7431. Código bibliográfico : 2005PNAS..102.7426C. doi : 10.1073/pnas.0500334102 . PMC  1140422 . PMID  15899970.
2. Coifman, RR; Lafón, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). "Difusiones geométricas como herramienta para el análisis armónico y definición de estructuras de datos: métodos multiescala". PNAS . 102 (21): 7432–7437. Código bibliográfico : 2005PNAS..102.7432C. doi : 10.1073/pnas.0500896102 . PMC 1140426 . PMID  15899969. 
3. Coifman, RR; S. Lafón. (2006). "Mapas de difusión". Análisis Armónico Aplicado y Computacional . 21 : 5–30. doi :10.1016/j.acha.2006.04.006. S2CID  17160669.
4. Lafon, SS (2004). Mapas de difusión y armónicos geométricos (PDF) (Doctor). Universidad de Yale.
5. De la Porte, J.; Herbst, BM; Hereman, W; Van der Walt, SJ (2008). "Introducción a los mapas de difusión". Actas del Decimonoveno Simposio Anual de la Asociación de Reconocimiento de Patrones de Sudáfrica (PRASA) . CiteSeerX 10.1.1.309.674 . 
6. Nadler, Booz; Stéphane Lafon; Ronald R. Coifman; Ioannis G. Kevrekidis (2005). "Mapas de difusión, agrupación espectral y funciones propias de los operadores Fokker-Planck" (PDF) . Avances en los sistemas de procesamiento de información neuronal . 18 . arXiv : matemáticas/0506090 . Código Bib : 2005 matemáticas ...... 6090N.
7. Barkan, Oren; Bueno, Jonathan; Lobo, Lior; Aronowitz, Hagai. "Reconocimiento facial rápido por multiplicación de vectores de alta dimensión" (PDF) . Actas de la Conferencia Internacional IEEE sobre Visión por Computadora 2013 : 1960-1967.
8. Zeev, Farbman; Fattal Raanan; Lischinski Dani (2010). "Mapas de difusión para la edición de imágenes con reconocimiento de bordes". Transmisión ACM. Gráfico . 29 (6): 145:1–145:10. doi :10.1145/1882261.1866171.
9. Oana, Sidi; van Kaick, Oliver; Kleiman, Yanir; Zhang, Hao; Cohen-Or, Daniel (2011). Cosegmentación no supervisada de un conjunto de formas mediante agrupación espectral de descriptor-espacio (PDF) . Transacciones ACM sobre gráficos .
10. Barkan, Oren; Aronowitz, Hagai (2013). "Mapas de difusión para la verificación de hablantes basada en PLDA" (PDF) . Actas de la Conferencia Internacional IEEE sobre Acústica, Habla y Procesamiento de Señales : 7639–7643.
11. Michalevsky, Yan; Talmon, Ronen; Cohen, Israel (2011). Identificación de hablantes mediante mapas de difusión (PDF) . Conferencia europea sobre procesamiento de señales 2011.
12. Mishné, Gal; Cohen, Israel (2013). "Detección de anomalías multiescala mediante mapas de difusión". Temas seleccionados de IEEE en procesamiento de señales . 7 (1): 111-123. Código Bib : 2013ISTSP...7..111M. doi :10.1109/jstsp.2012.2232279. S2CID  1954466.
13. Shabat, Gil; Segev, David; Averbuch, Amir (7 de enero de 2018). "Descubriendo incógnitas desconocidas en Big Data de servicios financieros mediante metodologías no supervisadas: tendencias presentes y futuras". Taller KDD 2017 sobre detección de anomalías en finanzas . 71 : 8-19.
14. Gepshtein, Shai; Keller, Yosi (2013). "Completación de imágenes mediante mapas de difusión y relajación espectral". Transacciones IEEE sobre procesamiento de imágenes . 22 (8): 2983–2994. Código Bib : 2013ITIP...22.2983G. doi :10.1109/tip.2013.2237916. PMID  23322762. S2CID  14375333.
15. Margulies, Daniel S.; Ghosh, Satrajit S.; Goulas, Alexandros; Falkiewicz, Marcel; Huntenburg, Julia M.; Langs, Georg; Bezgin, Gleb; Eickhoff, Simon B.; Castellanos, F. Xavier; Petrides, Michael; Jefferies, Elizabeth; Smallwood, Jonathan (2016). "Situar la red en modo predeterminado a lo largo de un gradiente principal de organización cortical a macroescala". Actas de la Academia Nacional de Ciencias . 113 (44): 12574–12579. Código Bib : 2016PNAS..11312574M. doi : 10.1073/pnas.1608282113 . PMC 5098630 . PMID  27791099. 
16. De Domenico, Manlio (2017). "La geometría de difusión desentraña el surgimiento de grupos funcionales en fenómenos colectivos". Cartas de revisión física . 118 (16): 168301. arXiv : 1704.07068 . Código bibliográfico : 2017PhRvL.118p8301D. doi : 10.1103/PhysRevLett.118.168301. PMID  28474920. S2CID  2638868.