Paseo aleatorio de entropía máxima

El paseo aleatorio de entropía máxima ( MERW ) es un tipo popular de paseo aleatorio sesgado en un gráfico , en el que las probabilidades de transición se eligen de acuerdo con el principio de entropía máxima , que dice que la distribución de probabilidad que mejor representa el estado actual del conocimiento es la que tiene la entropía más grande. Mientras que el paseo aleatorio estándar elige para cada vértice una distribución de probabilidad uniforme entre sus bordes salientes, maximizando localmente la tasa de entropía , MERW la maximiza globalmente ( producción de entropía promedio ) al suponer una distribución de probabilidad uniforme entre todos los caminos en un gráfico dado.

El algoritmo MERW se utiliza en varios campos científicos. Una aplicación directa es la elección de probabilidades para maximizar la tasa de transmisión a través de un canal restringido, de forma análoga a la codificación de Fibonacci . Sus propiedades también lo hacen útil, por ejemplo, en el análisis de redes complejas, ^[1] como la predicción de enlaces , ^[2] la detección de comunidades, ^[3] el transporte robusto sobre redes ^[4] y las medidas de centralidad . ^[5] También en el análisis de imágenes , por ejemplo, para detectar regiones de prominencia visual, ^[6] la localización de objetos, ^[7] la detección de manipulaciones ^[8] o problemas de tractografía . ^[9]

Además, recrea algunas propiedades de la mecánica cuántica , sugiriendo una forma de reparar la discrepancia entre los modelos de difusión y las predicciones cuánticas, como la localización de Anderson . ^[10]

Modelo básico

Izquierda: concepto básico del paseo aleatorio genérico (GRW) y el paseo aleatorio de entropía máxima (MERW).
Derecha: ejemplo de su evolución en la misma red 2D no homogénea con condiciones de contorno cíclicas: densidad de probabilidad después de 10, 100 y 1000 pasos mientras se comienza desde el mismo vértice. Los cuadros pequeños representan defectos: todos los vértices excepto los marcados tienen un autobucle adicional (borde hacia sí mismo). Para redes regulares (sin defectos), GRW y MERW son idénticos. Si bien los defectos no afectan fuertemente el comportamiento local, conducen a una probabilidad estacionaria global completamente diferente aquí. Mientras que GRW (y en base a él la difusión estándar ) conduce a una densidad estacionaria casi uniforme, MERW tiene una fuerte propiedad de localización, aprisionando a los caminantes en pozos entrópicos en analogía a los electrones en la red defectuosa de semiconductores .

Consideremos un grafo con vértices, definido por una matriz de adyacencia : si hay una arista desde el vértice hasta , 0 en caso contrario. Para simplificar, supongamos que es un grafo no dirigido , que corresponde a un ; sin embargo, MERW también se puede generalizar para grafos dirigidos y ponderados (por ejemplo, distribución de Boltzmann entre caminos en lugar de uniforme). ${\displaystyle n}$ ${\displaystyle A\in \left\{0,1\right\}^{n\times n}}$ ${\displaystyle A_{ij}=1}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle A}$

Nos gustaría elegir un paseo aleatorio como un proceso de Markov en este gráfico: para cada vértice y su borde saliente a , elija la probabilidad de que el caminante use aleatoriamente este borde después de visitar . Formalmente, encuentre una matriz estocástica (que contenga las probabilidades de transición de una cadena de Markov) tal que ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle S_{ij}}$ ${\displaystyle i}$ ${\displaystyle S}$

• ${\displaystyle 0\leq S_{ij}\leq A_{ij}}$Para todos y ${\displaystyle i,j}$
• ${\displaystyle \sum _{j=1}^{n}S_{ij}=1}$Para todos . ${\displaystyle i}$

Suponiendo que este gráfico está conectado y no es periódico , la teoría ergódica dice que la evolución de este proceso estocástico conduce a una distribución de probabilidad estacionaria tal que . ${\displaystyle \rho }$ ${\displaystyle \rho S=\rho }$

Usando la entropía de Shannon para cada vértice y promediando la probabilidad de visitar este vértice (para poder usar su entropía), obtenemos la siguiente fórmula para la producción de entropía promedio ( tasa de entropía ) del proceso estocástico:

${\displaystyle H(S)=\sum _{i=1}^{n}\rho _{i}\sum _{j=1}^{n}S_{ij}\log(1/S_{ij})}$

Esta definición resulta equivalente a la entropía promedio asintótica (por longitud) de la distribución de probabilidad en el espacio de trayectorias para este proceso estocástico.

En el paseo aleatorio estándar, al que aquí se denomina paseo aleatorio genérico (GRW), elegimos naturalmente que cada borde saliente sea igualmente probable:

${\displaystyle S_{ij}={\frac {A_{ij}}{\sum \limits _{k=1}^{n}A_{ik}}}}$.

Para una simétrica conduce a una distribución de probabilidad estacionaria con ${\displaystyle A}$ ${\displaystyle \rho }$

${\displaystyle \rho _{i}={\frac {\sum \limits _{j=1}^{n}A_{ij}}{\sum \limits _{i=1}^{n}\sum \limits _{j=1}^{n}A_{ij}}}}$.

Maximiza localmente la producción de entropía (incertidumbre) para cada vértice, pero generalmente conduce a una tasa de entropía global promedio subóptima . ${\displaystyle H(S)}$

MERW elige la matriz estocástica que maximiza , o equivalentemente supone una distribución de probabilidad uniforme entre todas las rutas en un gráfico dado. Su fórmula se obtiene calculando primero el valor propio dominante y el vector propio correspondiente de la matriz de adyacencia, es decir, el más grande con correspondiente tal que . Luego, la matriz estocástica y la distribución de probabilidad estacionaria se dan por ${\displaystyle H(S)}$ ${\displaystyle \lambda }$ ${\displaystyle \psi }$ ${\displaystyle \lambda \in \mathbb {R} }$ ${\displaystyle \psi \in \mathbb {R} ^{n}}$ ${\displaystyle \psi A=\lambda \psi }$

${\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}}$

para el cual cada camino posible de longitud desde el -ésimo al -ésimo vértice tiene probabilidad ${\displaystyle l}$ ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle {\frac {1}{\lambda ^{l}}}{\frac {\psi _{j}}{\psi _{i}}}}$.

Su tasa de entropía es y la distribución de probabilidad estacionaria es ${\displaystyle \log(\lambda )}$ ${\displaystyle \rho }$

${\displaystyle \rho _{i}={\frac {\psi _{i}^{2}}{\|\psi \|_{2}^{2}}}}$.

A diferencia de GRW, las probabilidades de transición de MERW generalmente dependen de la estructura de todo el grafo (no son locales). Por lo tanto, no se las debe imaginar como algo que aplica directamente el caminante: si se toman decisiones que parecen aleatorias en función de la situación local, como lo haría una persona, el enfoque GRW es más apropiado. MERW se basa en el principio de máxima entropía, lo que lo convierte en la suposición más segura cuando no tenemos ningún conocimiento adicional sobre el sistema. Por ejemplo, sería adecuado para modelar nuestro conocimiento sobre un objeto que realiza una dinámica compleja, no necesariamente aleatoria, como una partícula.

Esquema de derivación

Supongamos, para simplificar, que el grafo considerado es indirecto, conexo y aperiódico, lo que permite concluir a partir del teorema de Perron-Frobenius que el vector propio dominante es único. Por lo tanto, puede aproximarse asintóticamente ( ) mediante (o en notación de corchetes ). ${\displaystyle A^{l}}$ ${\displaystyle l\rightarrow \infty }$ ${\displaystyle \lambda ^{l}\psi \psi ^{T}}$ ${\displaystyle \lambda ^{l}|\psi \rangle \langle \psi |}$

MERW requiere una distribución uniforme a lo largo de las trayectorias. La cantidad de trayectorias con longitud y vértice en el centro es ${\displaystyle m_{il}}$ ${\displaystyle 2l}$ ${\displaystyle i}$

${\displaystyle m_{il}=\sum _{j=1}^{n}\sum _{k=1}^{n}\left(A^{l}\right)_{ji}\left(A^{l}\right)_{ik}\approx \sum _{j=1}^{n}\sum _{k=1}^{n}\left(\lambda ^{l}\psi \psi ^{\top }\right)_{ji}\left(\lambda ^{l}\psi \psi ^{\top }\right)_{ik}=\sum _{j=1}^{n}\sum _{k=1}^{n}\lambda ^{2l}\psi _{j}\psi _{i}\psi _{i}\psi _{k}=\lambda ^{2l}\psi _{i}^{2}\underbrace {\sum _{j=1}^{n}\psi _{j}\sum _{k=1}^{n}\psi _{k}} _{=:b}}$,

Por lo tanto, para todos , ${\displaystyle i}$

${\displaystyle \rho _{i}=\lim _{l\rightarrow \infty }{\frac {m_{il}}{\sum \limits _{k=1}^{n}m_{kl}}}=\lim _{l\rightarrow \infty }{\frac {\lambda ^{2l}\psi _{i}^{2}b}{\sum \limits _{k=1}^{n}\lambda ^{2l}\psi _{k}^{2}b}}=\lim _{l\rightarrow \infty }{\frac {\psi _{i}^{2}}{\sum \limits _{k=1}^{n}\psi _{k}^{2}}}={\frac {\psi _{i}^{2}}{\sum \limits _{k=1}^{n}\psi _{k}^{2}}}={\frac {\psi _{i}^{2}}{\|\psi \|_{2}^{2}}}}$.

Calculando de manera análoga la distribución de probabilidad para dos vértices sucesivos, se obtiene que la probabilidad de estar en el -ésimo vértice y luego en el -ésimo vértice es ${\displaystyle i}$ ${\displaystyle j}$

${\displaystyle {\frac {\psi _{i}A_{ij}\psi _{j}}{\sum \limits _{i'=1}^{n}\sum \limits _{j'=1}^{n}\psi _{i'}A_{i'j'}\psi _{j'}}}={\frac {\psi _{i}A_{ij}\psi _{j}}{\psi A\psi ^{\top }}}={\frac {\psi _{i}A_{ij}\psi _{j}}{\lambda \|\psi \|_{2}^{2}}}}$.

Dividiendo por la probabilidad de estar en el -ésimo vértice, es decir , se obtiene la probabilidad condicional de que el -ésimo vértice esté después del -ésimo vértice. ${\displaystyle i}$ ${\displaystyle \rho _{i}}$ ${\displaystyle S_{ij}}$ ${\displaystyle j}$ ${\displaystyle i}$

${\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}}$.

MERW ponderado: conjunto de trayectorias de Boltzmann

Hemos supuesto que para MERW corresponde a un conjunto uniforme entre caminos. Sin embargo, la derivación anterior funciona para valores no negativos reales . Al parametrizar y solicitar la probabilidad de longitud de camino , obtenemos: ${\displaystyle A_{ij}\in \{0,1\}}$ ${\displaystyle A}$ ${\displaystyle A_{ij}=\exp(-E_{ij})}$ ${\displaystyle l}$ ${\displaystyle (\gamma _{0},\ldots ,\gamma _{l})}$

${\displaystyle {\textrm {Pr}}(\gamma _{0},\ldots ,\gamma _{l})=\rho _{\gamma _{0}}S_{\gamma _{0}\gamma _{1}}\ldots S_{\gamma _{l-1}\gamma _{l}}=\psi _{\gamma _{0}}{\frac {A_{\gamma _{0}\gamma _{1}}\ldots A_{\gamma _{l-1}\gamma _{l}}}{\lambda ^{l}}}\psi _{\gamma _{l}}=\psi _{\gamma _{0}}{\frac {\exp(-(E_{\gamma _{0}\gamma _{1}}+\ldots +E_{\gamma _{l-1}\gamma _{l}}))}{\lambda ^{l}}}\psi _{\gamma _{l}}}$

Como en la distribución de Boltzmann de trayectorias para la energía definida como la suma de las trayectorias dadas. Por ejemplo, permite calcular la distribución de probabilidad de patrones en el modelo de Ising . ${\displaystyle E_{ij}}$

Ejemplos

Izquierda: elección de la probabilidad óptima después del símbolo 0 en la codificación de Fibonacci . Derecha: red unidimensional con defectos y su densidad estacionaria para una longitud de 1000 ciclos (tiene tres defectos). Mientras que en el recorrido aleatorio estándar la densidad estacionaria es proporcional al grado de un vértice, lo que lleva a una diferencia de 3/2 aquí, en MERW la densidad está casi completamente localizada en la región libre de defectos más grande, análoga al estado fundamental predicho por la mecánica cuántica .

Veamos primero una situación simple no trivial: la codificación de Fibonacci, donde queremos transmitir un mensaje como una secuencia de 0 y 1, pero sin usar dos 1 sucesivos: después de un 1 tiene que haber un 0. Para maximizar la cantidad de información transmitida en dicha secuencia, debemos suponer una distribución de probabilidad uniforme en el espacio de todas las secuencias posibles que cumplan esta restricción. Para usar de manera práctica secuencias tan largas, después de 1 tenemos que usar 0, pero queda la libertad de elegir la probabilidad de 0 después de 0. Denotemos esta probabilidad por , entonces la codificación de entropía permitiría codificar un mensaje usando esta distribución de probabilidad elegida. La distribución de probabilidad estacionaria de símbolos para un dado resulta ser . Por lo tanto, la producción de entropía es , que se maximiza para , conocido como la proporción áurea . Por el contrario, el paseo aleatorio estándar elegiría subóptimo . Si bien elegir un valor mayor reduce la cantidad de información producida después de 0, también reduce la frecuencia de 1, después de la cual no podemos escribir ninguna información. ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle \rho =(1/(2-q),1-1/(2-q))}$ ${\displaystyle H(S)=\rho _{0}\left(q\log(1/q)+(1-q)\log(1/(1-q))\right)}$ ${\displaystyle q=({\sqrt {5}}-1)/2\approx 0.618}$ ${\displaystyle q=0.5}$ ${\displaystyle q}$

Un ejemplo más complejo es el entramado cíclico unidimensional defectuoso: digamos 1000 nodos conectados en un anillo, para el cual todos los nodos excepto los defectos tienen un bucle propio (borde consigo mismo). En el recorrido aleatorio estándar (GRW), la distribución de probabilidad estacionaria tendría una probabilidad de defecto de 2/3 de la probabilidad de los vértices sin defecto; casi no hay localización, también de manera análoga para la difusión estándar, que es el límite infinitesimal de GRW. Para MERW, primero tenemos que encontrar el vector propio dominante de la matriz de adyacencia, maximizando en: ${\displaystyle \lambda }$

${\displaystyle (\lambda \psi )_{x}=(A\psi )_{x}=\psi _{x-1}+(1-V_{x})\psi _{x}+\psi _{x+1}}$

para todas las posiciones , donde para defectos, 0 en caso contrario. Sustituyendo y multiplicando la ecuación por −1 obtenemos: ${\displaystyle x}$ ${\displaystyle V_{x}=1}$ ${\displaystyle 3\psi _{x}}$

${\displaystyle E\psi _{x}=-(\psi _{x-1}-2\psi _{x}+\psi _{x+1})+V_{x}\psi _{x}}$

donde ahora se minimiza, convirtiéndose en el análogo de la energía. La fórmula dentro del corchete es el operador de Laplace discreto , lo que hace que esta ecuación sea un análogo discreto de la ecuación estacionaria de Schrödinger . Como en la mecánica cuántica, MERW predice que la distribución de probabilidad debería conducir exactamente a la del estado fundamental cuántico : con su densidad fuertemente localizada (en contraste con la difusión estándar). Tomando el límite infinitesimal , podemos obtener la ecuación de Schrödinger estacionaria continua estándar (independiente del tiempo) ( para ) aquí. ^[11] ${\displaystyle E=3-\lambda }$ ${\displaystyle \rho _{x}\propto \psi _{x}^{2}}$ ${\displaystyle E\psi =-C\psi _{xx}+V\psi }$ ${\displaystyle C=\hbar ^{2}/2m}$

Véase también

• Principio de máxima entropía
• Centralidad del vector propio
• Cadena de Markov
• Localización de Anderson

Referencias

1. Sinatra, Roberta; Gómez-Gardeñes, Jesús; Lambiotte, Renaud; Nicosia, Vincenzo; Latora, Vito (2011). "Caminatas aleatorias de máxima entropía en redes complejas con información limitada" (PDF) . Physical Review E . 83 (3): 030103. arXiv : 1007.4936 . Bibcode :2011PhRvE..83c0103S. doi :10.1103/PhysRevE.83.030103. ISSN  1539-3755. PMID  21517435. S2CID  6984660.
2. Li, Rong-Hua; Yu, Jeffrey Xu; Liu, Jianquan (2011). Predicción de enlaces: el poder del paseo aleatorio de máxima entropía (PDF) . Conferencia de la Association for Computing Machinery sobre gestión de la información y el conocimiento. p. 1147. doi :10.1145/2063576.2063741. S2CID  15309519. Archivado desde el original (PDF) el 12 de febrero de 2017.
3. Ochab, JK; Burda, Z. (2013). "Caminata aleatoria de entropía máxima en la detección de comunidades". The European Physical Journal Special Topics . 216 (1): 73–81. arXiv : 1208.3688 . Código Bibliográfico :2013EPJST.216...73O. doi :10.1140/epjst/e2013-01730-6. ISSN  1951-6355. S2CID  56409069.
4. Chen, Y.; Georgiou, TT; Pavon, M.; Tannenbaum, A. (2016). "Transporte robusto sobre redes". IEEE Transactions on Automatic Control . 62 (9): 4675–4682. arXiv : 1603.08129 . Bibcode :2016arXiv160308129C. doi :10.1109/TAC.2016.2626796. PMC 5600536 . PMID  28924302. 
5. Delvenne, Jean-Charles; Libert, Anne-Sophie (2011). "Medidas de centralidad y formalismo termodinámico para redes complejas". Physical Review E . 83 (4): 046117. arXiv : 0710.3972 . Bibcode :2011PhRvE..83d6117D. doi :10.1103/PhysRevE.83.046117. ISSN  1539-3755. PMID  21599250. S2CID  25816198.
6. Jin-Gang Yu; Ji Zhao; Jinwen Tian; Yihua Tan (2014). "Paseo aleatorio de entropía máxima para prominencia visual basada en regiones". IEEE Transactions on Cybernetics . 44 (9). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1661–1672. doi :10.1109/tcyb.2013.2292054. ISSN  2168-2267. PMID  25137693. S2CID  20962642.
7. L. Wang, J. Zhao, X. Hu, J. Lu, Localización de objetos débilmente supervisada a través de un recorrido aleatorio de entropía máxima, ICIP, 2014.
8. Korus, Pawel; Huang, Jiwu (2016). "Localización mejorada de alteraciones en la investigación forense de imágenes digitales basada en un recorrido aleatorio de entropía máxima". IEEE Signal Processing Letters . 23 (1). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 169–173. Bibcode :2016ISPL...23..169K. doi :10.1109/lsp.2015.2507598. ISSN  1070-9908. S2CID  16305991.
9. Galinsky, Vitaly L.; Frank, Lawrence R. (2015). "Estimación simultánea de difusión multiescala y tractografía guiada por vías del espectro de entropía". IEEE Transactions on Medical Imaging . 34 (5). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1177–1193. doi :10.1109/tmi.2014.2380812. ISSN  0278-0062. PMC 4417445 . PMID  25532167. 
10. Burda, Z.; Duda, J.; Luck, JM; Waclaw, B. (23 de abril de 2009). "Localización del paseo aleatorio de máxima entropía". Physical Review Letters . 102 (16): 160602. arXiv : 0810.4113 . Bibcode :2009PhRvL.102p0602B. doi :10.1103/physrevlett.102.160602. ISSN  0031-9007. PMID  19518691. S2CID  32134048.
11. J. Duda, Paseo aleatorio de entropía máxima extendida, tesis doctoral, 2012.

Enlaces externos

• Gábor Simonyi, Y. Lin, Z. Zhang, "Tiempo medio de primer paso para recorridos aleatorios de máxima entropía en redes complejas". Scientific Reports, 2014.
• Modelos de conductancia electrónica que utilizan paseos aleatorios de entropía máxima Proyecto de demostración de Wolfram