La caminata aleatoria de entropía máxima ( MERW ) es un tipo popular de caminata aleatoria sesgada 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 con mayor entropía. Mientras que la caminata aleatoria 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 promedio de entropía) asumiendo una distribución de probabilidad uniforme entre todas las rutas en un gráfico dado.
MERW se utiliza en varios campos de la ciencia. Una aplicación directa es elegir probabilidades para maximizar la tasa de transmisión a través de un canal restringido, de manera análoga a la codificación de Fibonacci . Sus propiedades también lo hicieron útil, por ejemplo, en el análisis de redes complejas, [1] como predicción de enlaces, [2] detección de comunidades, [3] transporte robusto a través de redes [4] y medidas de centralidad . [5] También en análisis de imágenes , por ejemplo para detectar regiones de prominencia visual, [6] localización de objetos, [7] detección de manipulación [8] o problemas de 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 basica
Considere una gráfica convértices, definidos por una matriz de adyacencia : si hay una arista desde el vértice a , 0 en caso contrario. Para simplificar, suponga que es un gráfico no dirigido , que corresponde a un simétrico; sin embargo, MERW también se puede generalizar para gráficos dirigidos y ponderados (por ejemplo, distribución de Boltzmann entre caminos en lugar de uniforme).
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 , elige probabilidad del caminante que usa aleatoriamente este borde después de visitar . Formalmente, encuentre una matriz estocástica (que contiene las probabilidades de transición de una cadena de Markov) tal que
- para todos y
- para todos .
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 alguna distribución de probabilidad estacionaria tal que .
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:
Esta definición resulta ser equivalente a la entropía promedio asintótica (por longitud) de la distribución de probabilidad en el espacio de caminos para este proceso estocástico.
En el paseo aleatorio estándar, denominado aquí como paseo aleatorio genérico (GRW), naturalmente elegimos que cada borde de salida sea igualmente probable:
- .
Para un simétrico conduce a una distribución de probabilidad estacionaria con
- .
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 .
MERW elige la matriz estocástica que maximiza o, de manera equivalente, asume una distribución de probabilidad uniforme entre todos los caminos en un gráfico dado. Su fórmula se obtiene calculando primero el autovalor dominante y el vector propio correspondiente de la matriz de adyacencia, es decir, la mayor con correspondiente tal que . Entonces la matriz estocástica y la distribución de probabilidad estacionaria están dadas por
por lo que cada posible camino de longitud desde el -th a -th vértice tiene probabilidad
- .
Su tasa de entropía es y la distribución de probabilidad estacionaria es
- .
A diferencia de GRW, las probabilidades de transición de MERW generalmente dependen de la estructura de todo el gráfico (no son locales). Por lo tanto, no deben imaginarse como aplicados directamente por el caminante: si se toman decisiones al azar 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.
Bosquejo de derivación
Suponga por simplicidad que el gráfico considerado es indirecto, conectado y aperiódico, lo que permite concluir del teorema de Perron-Frobenius que el autovector dominante es único. Por eso puede ser asintóticamente) aproximado por (o en notación bra-ket ).
MERW requiere una distribución uniforme a lo largo de los caminos. El número de caminos con longitud y vértice en el centro está
- ,
por lo tanto para todos ,
- .
Calculando análogamente la distribución de probabilidad para dos vértices sucesivos, se obtiene que la probabilidad de estar en el -th vértice y siguiente en el -th vértice es
- .
Dividiendo por la probabilidad de estar en el -th vértice, es decir , da para la probabilidad condicional de El -th vértice es el siguiente después del -th vértice
- .
MERW ponderado: conjunto de caminos de Boltzmann
Hemos asumido que para MERW correspondiente al conjunto uniforme entre caminos. Sin embargo, la derivación anterior funciona para valores reales no negativos.. Parametrización y preguntando por probabilidad de longitud camino , obtenemos:
Como en la distribución de Boltzmann de trayectorias para la energía definida como la suma desobre el camino dado. Por ejemplo, permite calcular la distribución de probabilidad de patrones en el modelo de Ising .
Ejemplos de
Veamos primero una situación simple y 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 tal secuencia, deberíamos suponer una distribución de probabilidad uniforme en el espacio de todas las secuencias posibles que cumplan con esta restricción. Para usar prácticamente 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 determinado resulta ser . Por tanto, la producción de entropía es, que se maximiza para , conocida como la proporción áurea . Por el contrario, la caminata aleatoria estándar elegiría subóptima. Mientras elige más grande reduce la cantidad de información producida después de 0, también reduce la frecuencia de 1, después de lo cual no podemos escribir ninguna información.
Un ejemplo más complejo es el entramado cíclico unidimensional defectuoso: digamos 1000 nodos conectados en un anillo, para los cuales todos los nodos, excepto los defectos, tienen un bucle propio (borde a sí mismo). En la caminata aleatoria 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:
para todas las posiciones , dónde para defectos, 0 en caso contrario. Sustituyendo y multiplicando la ecuación por -1 obtenemos:
dónde se minimiza ahora, convirtiéndose en el análogo de la energía. La fórmula dentro del corchete es un operador de Laplace discreto , lo que hace que esta ecuación sea un análogo discreto de la ecuación de Schrodinger estacionaria . Al igual que 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 Schrodinger estacionaria continua estándar (independiente del tiempo) ( por ) aquí. [11]
Ver también
- Principio de máxima entropía
- Centralidad del vector propio
- Cadena de Markov
- Localización de Anderson
Referencias
- ^ 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) . Revisión E física . 83 (3): 030103. arXiv : 1007.4936 . Código Bibliográfico : 2011PhRvE..83c0103S . doi : 10.1103 / PhysRevE.83.030103 . ISSN 1539-3755 . PMID 21517435 .
- ^ Li, Rong-Hua; Yu, Jeffrey Xu; Liu, Jianquan (2011). Predicción de enlaces: el poder de la caminata aleatoria de entropía máxima (PDF) . Conferencia de la Asociación de Maquinaria de Computación sobre Gestión de la Información y el Conocimiento . pag. 1147. doi : 10.1145 / 2063576.2063741 . Archivado desde el original (PDF) el 12 de febrero de 2017.
- ^ Ochab, JK; Burda, Z. (2013). "Paseo aleatorio de entropía máxima en la detección de la comunidad". Temas especiales de la revista European Physical Journal . 216 (1): 73–81. arXiv : 1208.3688 . Código Bibliográfico : 2013EPJST.216 ... 73O . doi : 10.1140 / epjst / e2013-01730-6 . ISSN 1951-6355 .
- ^ Chen, Y .; Georgiou, TT; Pavon, M .; Tannenbaum, A. (2016). "Transporte robusto sobre redes" . Transacciones IEEE sobre control automático . 62 (9): 4675–4682. arXiv : 1603.08129 . Código bibliográfico : 2016arXiv160308129C . doi : 10.1109 / TAC.2016.2626796 . PMC 5600536 . PMID 28924302 .
- ^ Delvenne, Jean-Charles; Libert, Anne-Sophie (2011). "Medidas de centralidad y formalismo termodinámico para redes complejas". Revisión E física . 83 (4): 046117. arXiv : 0710.3972 . Código Bibliográfico : 2011PhRvE..83d6117D . doi : 10.1103 / PhysRevE.83.046117 . ISSN 1539-3755 . PMID 21599250 .
- ^ Jin-Gang Yu; Ji Zhao; Jinwen Tian; Yihua Tan (2014). "Paseo aleatorio de entropía máxima para la prominencia visual basada en la región". Transacciones IEEE sobre cibernética . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 44 (9): 1661–1672. doi : 10.1109 / tcyb.2013.2292054 . ISSN 2168-2267 . PMID 25137693 .
- ^ L. Wang, J. Zhao, X. Hu, J. Lu, Localización de objetos débilmente supervisada mediante caminata aleatoria de entropía máxima , ICIP, 2014.
- ^ Korus, Pawel; Huang, Jiwu (2016). "Mejora de la localización de alteraciones en el análisis forense de imágenes digitales basada en el paseo aleatorio de entropía máxima". Cartas de procesamiento de señales IEEE . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 23 (1): 169-173. Código bibliográfico : 2016ISPL ... 23..169K . doi : 10.1109 / lsp.2015.2507598 . ISSN 1070-9908 .
- ^ Galinsky, Vitaly L .; Frank, Lawrence R. (2015). "Estimación de difusión simultánea multiescala y tractografía guiada por vías de espectro de entropía" . Transacciones IEEE sobre imágenes médicas . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 34 (5): 1177-1193. doi : 10.1109 / tmi.2014.2380812 . ISSN 0278-0062 . PMC 4417445 . PMID 25532167 .
- ^ Burda, Z .; Duda, J .; Suerte, JM; Waclaw, B. (23 de abril de 2009). "Localización de la caminata aleatoria de máxima entropía". Cartas de revisión física . 102 (16): 160602. arXiv : 0810.4113 . Código Bibliográfico : 2009PhRvL.102p0602B . doi : 10.1103 / physrevlett.102.160602 . ISSN 0031-9007 . PMID 19518691 .
- ^ J. Duda, Paseo aleatorio de entropía máxima extendida , Tesis de doctorado, 2012.
enlaces externos
- Gábor Simonyi, Y. Lin, Z. Zhang, "Tiempo medio de primer paso para paseos aleatorios de entropía máxima en redes complejas" . Informes científicos, 2014.
- Modelos de conductancia electrónica que utilizan entropía máxima Paseos aleatorios Proyecto de demostración Wolfram