Mapa de difusión

Dados puntos de datos muestreados de manera no uniforme en una hélice toroidal (arriba), se representan gráficamente 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 y recupera la geometría circular intrínseca subyacente de los datos.

Los mapas de difusión son un algoritmo de extracción de características o reducción de dimensionalidad 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 se pueden calcular a partir de los vectores propios y los 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 extraído los datos. Al integrar similitudes locales en 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 de mapas de difusión es robusto a la perturbación del ruido y computacionalmente económico.

Definición de mapas de difusión

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

Conectividad

Los mapas de difusión explotan la relación entre la difusión del calor y la cadena de Markov de paseo aleatorio . La observación básica es que si hacemos un paseo aleatorio sobre los datos, es más probable que caminemos hacia un punto de datos cercano que hacia otro que esté lejos. Sea un espacio de medida , donde es el conjunto de datos y representa la distribución de los puntos en . ${\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 del recorrido aleatorio. Por lo general, esta probabilidad se especifica en términos de una función kernel de los dos puntos: . Por ejemplo, el popular kernel 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 kernel 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}$

( es preservadora de 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 guiarse 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 se tienen en cuenta las correlaciones entre todos los puntos de datos a la vez.

Dado , podemos entonces construir una cadena de Markov reversible de tiempo discreto en (un proceso conocido como construcción laplaciana de grafo 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 kernel normalizado no hereda la propiedad simétrica, sí hereda la propiedad de preservación de la positividad y obtiene 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 da 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 de la matriz laplaciana gráfica ) ${\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 equivalentemente,

${\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 gráfica laplaciana a este nuevo kernel:

${\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 al ejecutar la cadena hacia adelante en el tiempo (tomando potencias cada vez mayores de ) se revela la estructura geométrica de a escalas cada vez mayores (el proceso de difusión). Específicamente, la noción de un grupo 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 solo sirve como un parámetro de tiempo, sino que también tiene el doble papel 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 descomposición espectral de los valores propios, solo se necesitan unos pocos términos para lograr una precisión relativa dada 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 que implica 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 de puntos de un sistema de ecuaciones diferenciales estocásticas, podemos usar y la cadena de Markov resultante se aproxima a la difusión de Fokker-Planck . Con , se reduce a la normalización laplaciana de grafos clásica. ${\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. Se da 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 es 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, basadas en 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 dada (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 que vinculan 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}\,}$

De esta forma, 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 descomposición del espectro, es suficiente utilizar solo los primeros k vectores y valores propios. De este modo, obtenemos el mapa de difusión de los datos originales a un espacio de dimensión k que está integrado 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}\,}$

Por lo tanto, 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. Normalizar la matriz según el parámetro : . ${\displaystyle \alpha }$ ${\displaystyle L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }}$

Paso 3. Formar 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. mostraron 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 dan 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 incluidos 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 ^[10] e identificación de hablantes, ^[11] muestreo en colectores, detección de anomalías, ^{[12] [13]} restauración de imágenes, ^[14] revelación de la organización de redes en 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.

Véase también

• Reducción de dimensionalidad no lineal
• Agrupamiento espectral

Referencias

1. Coifman, RR; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). "Difusiones geométricas como herramienta para el análisis armónico y la definición de la estructura de los datos: mapas de difusión". PNAS . 102 (21): 7426–7431. Bibcode :2005PNAS..102.7426C. doi : 10.1073/pnas.0500334102 . PMC  1140422 . PMID  15899970.
2. Coifman, RR; Lafon, S; Lee, AB; Maggioni, M; Nadler, B; Warner, F; Zucker, SW (2005). "Difusiones geométricas como herramienta para el análisis armónico y la definición de la estructura de datos: métodos multiescala". PNAS . 102 (21): 7432–7437. Bibcode :2005PNAS..102.7432C. doi : 10.1073/pnas.0500896102 . PMC 1140426 . PMID  15899969. 
3. Coifman, RR; S. Lafon. (2006). "Mapas de difusión". Análisis armónico computacional y aplicado . 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) (PhD). 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, Boaz; Stéphane Lafon; Ronald R. Coifman; Ioannis G. Kevrekidis (2005). "Mapas de difusión, agrupamiento espectral y funciones propias de los operadores de Fokker-Planck" (PDF) . Avances en sistemas de procesamiento de información neuronal . 18 . arXiv : math/0506090 . Código Bibliográfico :2005math......6090N.
7. Barkan, Oren; Weill, Jonathan; Wolf, Lior; Aronowitz, Hagai. "Reconocimiento rápido de rostros mediante multiplicación vectorial de alta dimensión" (PDF) . Actas de la Conferencia Internacional IEEE sobre Visión por Computador 2013 : 1960–1967.
8. Zeev, Farbman; Fattal Raanan; Lischinski Dani (2010). "Mapas de difusión para edición de imágenes con reconocimiento de bordes". ACM Trans. Graph . 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 agrupamiento espectral en el espacio de descriptores (PDF) . Transacciones ACM en 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 de procesamiento de señales 2011.
12. Mishne, Gal; Cohen, Israel (2013). "Detección de anomalías multiescala mediante mapas de difusión". IEEE Selected Topics in Signal Processing . 7 (1): 111–123. Bibcode :2013ISTSP...7..111M. doi :10.1109/jstsp.2012.2232279. S2CID  1954466.
13. Shabat, Gil; Segev, David; Averbuch, Amir (7 de enero de 2018). "Descubrimiento de incógnitas desconocidas en los macrodatos de servicios financieros mediante metodologías no supervisadas: tendencias presentes y futuras". Taller de KDD 2017 sobre detección de anomalías en finanzas . 71 : 8–19.
14. Gepshtein, Shai; Keller, Yosi (2013). "Completado de imágenes mediante mapas de difusión y relajación espectral". IEEE Transactions on Image Processing . 22 (8): 2983–2994. Bibcode :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). "Situación de la red por defecto a lo largo de un gradiente principal de organización cortical a macroescala". Actas de la Academia Nacional de Ciencias . 113 (44): 12574–12579. Bibcode :2016PNAS..11312574M. doi : 10.1073/pnas.1608282113 . PMC 5098630 . PMID  27791099. 
16. De Domenico, Manlio (2017). "La geometría de la difusión desentraña la aparición de cúmulos funcionales en fenómenos colectivos". Physical Review Letters . 118 (16): 168301. arXiv : 1704.07068 . Bibcode :2017PhRvL.118p8301D. doi :10.1103/PhysRevLett.118.168301. PMID  28474920. S2CID  2638868.