Hispanopedia Wiki
Articulo de referencia

Paseo aleatorio de máxima entropía

Un paseo aleatorio de entropía máxima ( MERW ) es un tipo popular de paseo aleatorio sesgado en un grafo , en el que las probabilidades de transición se eligen de acuerdo con el...

Hispanopedia WikiContenido en espanolLectura gratuita

Un paseo aleatorio de entropía máxima ( MERW ) es un tipo popular de paseo aleatorio sesgado en un grafo , en el que las probabilidades de transición se eligen de acuerdo con el principio de entropía máxima , que establece que la distribución de probabilidad que mejor representa el estado actual del conocimiento es la que tiene la mayor entropía. Mientras que un paseo aleatorio estándar muestrea para cada vértice una distribución de probabilidad uniforme de aristas salientes, maximizando localmente la tasa de entropía , MERW la maximiza globalmente ( producción de entropía promedio ) muestreando una distribución de probabilidad uniforme entre todos los caminos en un grafo dado.

MERW se utiliza en diversos campos de la ciencia. Una aplicación directa es la selecció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 a través de redes [ 4 ] y las medidas de centralidad . [ 5 ] También se utiliza 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 manipulación [ 8 ] o el problema de la tractografía . [ 9 ]

Además, recrea algunas propiedades de la mecánica cuántica , lo que sugiere 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 del 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 parte del mismo vértice. Los pequeños recuadros representan defectos: todos los vértices excepto los marcados tienen un bucle adicional (arista a 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 basado en él la difusión ) 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 con los electrones en una red defectuosa de semiconductor .

Consideremos un gráfico connorte{\displaystyle n}vértices, definidos por una matriz de adyacenciaA∈{0,1}norte×norte{\displaystyle A\in \left\{0,1\right\}^{n\times n}}:Aij=1{\displaystyle A_{ij}=1}si hay una arista desde el vérticei{\displaystyle i}aj{\displaystyle j}, 0 en caso contrario. Para simplificar, supongamos que es un grafo no dirigido , lo que corresponde a un grafo simétrico.A{\displaystyle A}Sin embargo, los MERW también se pueden generalizar para grafos dirigidos y ponderados (por ejemplo, distribución de Boltzmann entre caminos en lugar de una distribución uniforme).

Nos gustaría elegir un paseo aleatorio como un proceso de Markov en este grafo: para cada vérticei{\displaystyle i}y su borde saliente aj{\displaystyle j}, elige probabilidadSij{\displaystyle S_{ij}}del caminante usando aleatoriamente este borde después de visitari{\displaystyle i}Formalmente, encuentre una matriz estocásticaS{\displaystyle S}(que contiene las probabilidades de transición de una cadena de Markov) tal que

  • 0≤Sij≤Aij{\displaystyle 0\leq S_{ij}\leq A_{ij}}a pesar dei,j{\displaystyle i,j}y
  • ∑j=1norteSij=1{\displaystyle \sum _{j=1}^{n}S_{ij}=1}a pesar dei{\displaystyle i}.

Suponiendo que este grafo es conexo y no periódico , la teoría ergódica afirma que la evolución de este proceso estocástico conduce a una distribución de probabilidad estacionaria.ρ{\displaystyle \rho }de tal manera queρS=ρ{\displaystyle \rho S=\rho }.

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

H(S)=∑i=1norteρi∑j=1norteSijregistro⁡(1/Sij){\displaystyle H(S)=\sum _{i=1}^{n}\rho _{i}\sum _{j=1}^{n}S_{ij}\log(1/S_{ij})}

Esta definición resulta ser equivalente a la entropía media asintótica (por unidad de 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í nos referimos como paseo aleatorio genérico (GRW), elegimos naturalmente que cada arista saliente tenga la misma probabilidad: Sij=Aij∑k=1norteAik.{\displaystyle S_{ij}={\frac {A_{ij}}{\sum \limits _{k=1}^{n}A_{ik}}}.} Para una simetríaA{\displaystyle A}Esto conduce a una distribución de probabilidad estacionaria.ρ{\displaystyle \rho }con ρi=∑j=1norteAij∑i=1norte∑j=1norteAij.{\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.H(S){\displaystyle H(S)}.

MERW elige la matriz estocástica que maximizaH(S){\displaystyle H(S)}o, equivalentemente, asume una distribución de probabilidad uniforme entre todos los caminos en un grafo dado. Su fórmula se obtiene calculando primero el valor propio dominante.λ{\displaystyle \lambda }y el vector propio correspondienteψ{\displaystyle \psi }de la matriz de adyacencia, es decir, la más grandeλ∈R{\displaystyle \lambda \in \mathbb {R} }con correspondienteψ∈Rnorte{\displaystyle \psi \in \mathbb {R} ^{n}}de tal manera queψA=λψ{\displaystyle \psi A=\lambda \psi }Entonces, la matriz estocástica y la distribución de probabilidad estacionaria vienen dadas por Sij=Aijλψjψi{\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}} para el cual cada posible camino de longitudl{\displaystyle l}desdei{\displaystyle i}-aj{\displaystyle j}El vértice -ésimo tiene probabilidad 1λlψjψi.{\displaystyle {\frac {1}{\lambda ^{l}}}{\frac {\psi _{j}}{\psi _{i}}}.} Su tasa de entropía esregistro⁡(λ){\displaystyle \log(\lambda)}y la distribución de probabilidad estacionariaρ{\displaystyle \rho }es ρi=ψi2‖ψ‖22.{\displaystyle \rho _{i}={\frac {\psi _{i}^{2}}{\left\|\psi \right\|_{2}^{2}}}.}

A diferencia de GRW, las probabilidades de transición de MERW generalmente dependen de la estructura de todo el grafo, lo que las hace no locales. Por lo tanto, no deben considerarse aplicadas directamente por el caminante ; si se toman decisiones aparentemente aleatorias basadas en 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 apropiado 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 no dirigido, 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,Al{\displaystyle A^{l}}puede ser asintóticamente (l→∞{\displaystyle l\rightarrow \infty }) aproximado porλlψψT{\displaystyle \lambda ^{l}\psi \psi ^{T}}(oλl|ψ⟩⟨ψ|{\displaystyle \lambda ^{l}|\psi \rangle \langle \psi |}en notación bra-ket ).

MERW requiere una distribución uniforme a lo largo de las trayectorias. El númerometroil{\displaystyle m_{il}}de caminos con longitud2l{\displaystyle 2l}y vérticei{\displaystyle i}en el centro está metroil=∑j=1norte∑k=1norte(Al)ji(Al)ik≈∑j=1norte∑k=1norte(λlψψ⊤)ji(λlψψ⊤)ik=∑j=1norte∑k=1norteλ2lψjψiψiψk=λ2lψi2∑j=1norteψj∑k=1norteψk⏟=:b,{\displaystyle {\begin{aligned}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}\\[1ex]&=\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},\end{aligned}}} por lo tanto para todosi{\displaystyle i}, ρi=límitel→∞metroil∑k=1nortemetrokl=límitel→∞λ2lψi2b∑k=1norteλ2lψk2b=límitel→∞ψi2∑k=1norteψk2=ψi2∑k=1norteψk2=ψi2‖ψ‖22.{\displaystyle {\begin{aligned}\rho _{i}&=\lim _{l\to \infty }{\frac {m_{il}}{\sum \limits _{k=1}^{n}m_{kl}}}=\lim _{l\to \infty }{\frac {\lambda ^{2l}\psi _{i}^{2}b}{\sum \limits _{k=1}^{n}\lambda ^{2l}\psi _{k}^{2}b}}\\[1ex]&=\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}}{\left\|\psi \right\|_{2}^{2}}}.\end{aligned}}}

Calculando análogamente la distribución de probabilidad para dos vértices sucesivos, se obtiene que la probabilidad de estar en eli{\displaystyle i}vértice -ésimo y el siguiente en elj{\displaystyle j}el vértice -ésimo es ψiAijψj∑i′=1norte∑j′=1norteψi′Ai′j′ψj′=ψiAijψjψAψ⊤=ψiAijψjλ‖ψ‖22.{\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 \left\|\psi \right\|_{2}^{2}}}.} Dividiendo por la probabilidad de estar en eli{\displaystyle i}vértice -ésimo, es decirρi{\displaystyle \rho _{i}}, da para la probabilidad condicionalSij{\displaystyle S_{ij}}delj{\displaystyle j}-ésimo vértice siendo el siguiente después deli{\displaystyle i}vértice -ésimo Sij=Aijλψjψi.{\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}.}

MERW ponderado: conjunto de trayectorias de Boltzmann

Hemos asumido queAij∈{0,1}{\displaystyle A_{ij}\in \{0,1\}}, lo que produce un MERW correspondiente al conjunto uniforme entre trayectorias. Sin embargo, la derivación anterior funciona para cualquier número real no negativo.A{\displaystyle A}para el cual se aplica el teorema de Perron-Frobenius. DadoAij=exp⁡(−miij){\displaystyle A_{ij}=\exp(-E_{ij})}, la probabilidad de una longitud particular-l{\displaystyle l}camino(γ0,…,γl){\displaystyle (\gamma _{0},\ldots ,\gamma _{l})}es el siguiente: Pr(γ0,…,γl)=ργ0Sγ0γ1…Sγl−1γl=ψγ0Aγ0γ1…Aγl−1γlλlψγl=ψγ0exp⁡(−(miγ0γ1+⋯+miγl−1γl))λlψγl,{\displaystyle {\begin{aligned}\Pr(\gamma _{0},\ldots ,\gamma _{l})&=\rho _{\gamma _{0}}S_{\gamma _{0}\gamma _{1}}\ldots S_{\gamma _{l-1}\gamma _{l}}\\[1ex]&=\psi _{\gamma _{0}}{\frac {A_{\gamma _{0}\gamma _{1}}\ldots A_{\gamma _{l-1}\gamma _{l}}}{\lambda ^{l}}}\psi _{\gamma _{l}}\\[1ex]&=\psi _{\gamma _{0}}{\frac {\exp \left(-\left(E_{\gamma _{0}\gamma _{1}}+\dots +E_{\gamma _{l-1}\gamma _{l}}\right)\right)}{\lambda ^{l}}}\psi _{\gamma _{l}},\end{aligned}}} que es lo mismo que la distribución de Boltzmann de trayectorias con energía definida como la suma demiij{\displaystyle E_{ij}}sobre los bordes del camino. Por ejemplo, esto se puede utilizar con la matriz de transferencia para calcular la distribución de probabilidad de patrones en el modelo de Ising .

Ejemplos

Izquierda: elección de la probabilidad óptima después del símbolo 0 en la codificación de Fibonacci . Derecha: una red defectuosa unidimensional y su densidad estacionaria para un ciclo de longitud 1000 (tiene tres defectos). En un paseo aleatorio estándar, la densidad estacionaria es proporcional al grado de un vértice, lo que da como resultado una diferencia de 3/2 aquí; sin embargo, 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 .

Consideremos primero una situación sencilla pero no trivial: la codificación de Fibonacci, donde queremos transmitir un mensaje como una secuencia de 0 y 1, pero sin usar dos 1 consecutivos: después de un 1 debe haber un 0. Para maximizar la cantidad de información transmitida en dicha secuencia, debemos asumir una distribución de probabilidad uniforme en el espacio de todas las secuencias posibles que cumplen esta restricción.

Para utilizar en la 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 probabilidadq{\displaystyle q}La codificación de entropía permite codificar un mensaje utilizando esta distribución de probabilidad elegida. La distribución de probabilidad estacionaria de los símbolos para un dadoq{\displaystyle q}resulta serρ=(1/(2−q),1−1/(2−q)){\displaystyle \rho =(1/(2-q),1-1/(2-q))}Por lo tanto, la entropía producida esH(S)=ρ0(qregistro⁡(1/q)+(1−q)registro⁡(1/(1−q))){\displaystyle H(S)=\rho _{0}\left(q\log(1/q)+(1-q)\log(1/(1-q))\right)}, que se maximiza paraq=(5−1)/2≈0,618{\displaystyle q=({\sqrt {5}}-1)/2\approx 0.618}, conocida como la proporción áurea . En contraste, un paseo aleatorio estándar elegiría el subóptimoq=0,5{\displaystyle q=0.5}. Al elegir uno más grandeq{\displaystyle q}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.

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

(λψ)incógnita=(Aψ)incógnita=ψincógnita−1+(1−Vincógnita)ψincógnita+ψincógnita+1{\displaystyle (\lambda \psi )_{x}=(A\psi )_{x}=\psi _{x-1}+(1-V_{x})\psi _{x}+\psi _{x+1}}

para todos los puestosincógnita{\displaystyle x}, dóndeVincógnita=1{\displaystyle V_{x}=1}para defectos, 0 en caso contrario. Sustituyendo3ψincógnita{\displaystyle 3\psi _{x}}y multiplicando la ecuación por −1 obtenemos:

miψincógnita=−(ψincógnita−1−2ψincógnita+ψincógnita+1)+Vincógnitaψincógnita{\displaystyle E\psi _{x}=-(\psi _{x-1}-2\psi _{x}+\psi _{x+1})+V_{x}\psi _{x}}

dóndemi=3−λ{\displaystyle E=3-\lambda }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 de Schrödinger estacionaria . Como en mecánica cuántica, los MERW predicen que la distribución de probabilidad es la del estado fundamental cuántico :ρincógnita∝ψincógnita2{\displaystyle \rho _{x}\propto \psi _{x}^{2}}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 continua estándar (independiente del tiempo) (miψ=−doψincógnitaincógnita+Vψ{\displaystyle E\psi =-C\psi _{xx}+V\psi }parado=ℏ2/2metro{\displaystyle C=\hbar ^{2}/2m}) aquí. [ 11 ]

Véase también

Referencias

  1. ↑ Sinatra, Roberta; Gómez-Gardeñes, Jesús; Lambiotte, Renaud; Nicosia, Vincenzo; Latora, Vito (2011). " Paseos aleatorios 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 entropía máxima (PDF) . Conferencia de la Asociación para la Maquinaria de Computación sobre Gestión de Información y Conocimiento . pág. 1147. doi : 10.1145/2063576.2063741 . S2CID 15309519. Archivado del original (PDF) el 12 de febrero de 2017.  
  3. ↑ Ochab, JK; Burda, Z. (2013). "Paseo aleatorio de entropía máxima en la detección de comunidades". The European Physical Journal Special Topics . 216 (1): 73– 81. arXiv : 1208.3688 . Bibcode : 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 la 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 mediante paseo aleatorio de entropía máxima , ICIP, 2014.
  8. ↑ Korus, Pawel; Huang, Jiwu (2016). "Mejora de la localización de manipulaciones en el análisis forense de imágenes digitales basada en el paseo 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 guiadas por rutas de 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 entropía máxima". 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.
  • Gábor Simonyi, Y. Lin, Z. Zhang, "Tiempo medio de primer paso para caminatas aleatorias de entropía máxima en redes complejas" . Scientific Reports, 2014.
  • Modelos de conductancia electrónica mediante caminatas aleatorias de entropía máxima: Proyecto de demostración de Wolfram