Maximal entropy random walk: Difference between revisions

Revision as of 08:19, 11 February 2017

Revision as of 21:12, 12 February 2017

Line 1:

'''Maximal Entropy Random Walk (MERW)''' is a popular type of [[biased random walk on a graph]], in which transition probabilities are chosen accordingly to the [[principle of maximum entropy]], which says that the probability distribution which best represents the current state of knowledge is the one with largest entropy. While standard [[random walk]] chooses for every vertex uniform probability distribution among its outgoing edges, locally maximizing [[entropy rate]], MERW maximizes it globally (average entropy production) by assuming uniform probability distribution among all paths in a given graph.

MERW is used in various fields of science. A direct application is choosing probabilities to maximize transmission rate through a constrained channel, analogously to [[Fibonacci coding]]. Its properties also made it useful for example in analysis of complex networks ,<ref name=Sinatra>[http://www.robertasinatra.com/pdf/sinatra_maximal_entropy.pdf R. Sinatra, J. Gómez-Gardenes, R. Lambiotte, V. Nicosia, ''Maximal-entropy random walks in complex networks with limited information''], Phys. Rev. E, 2011.</ref>, like link prediction ,<ref name=link>[https://pdfs.semanticscholar.org/f185/bc2499be95b4312169a7e722bac570c2d509.pdf R.H. Li, J.X. Yu, J. Liu, ''Link Prediction: the Power of Maximal Entropy Random Walk''], CIKM '11, 2011.</ref>, community detection<ref name=community>[http://link.springer.com/article/10.1140/epjst/e2013-01730-6 J. Ochab, Z. Burda, ''Maximal entropy random walk in community detection''], Z. Eur. Phys. J., 2013.</ref> and [[centrality]] measures.<ref name=central> [https://journals.aps.org/pre/abstract/10.1103/PhysRevE.83.046117 J.C. Delvenne, A.S. Libert, ''Centrality measures and thermodynamic formalism for complex networks''], Phys. Rev. E, 2011.</ref> Also in [[image analysis]], for example for detecting visual saliency regions,<ref name=saliency> [http://ieeexplore.ieee.org/abstract/document/6678551/ J.G. Yu, J. Zhao, J. Tian, Y. Tan, ''Maximal entropy random walk for region-based visual saliency''], IEEE Transactions on Cybernetics, 2014.</ref>, object localization,<ref name=local> [http://ieeexplore.ieee.org/abstract/document/6678551/ L. Wang, J. Zhao, X. Hu, J. Lu, ''Weakly supervised object localization via maximal entropy random walk''], ICIP, 2014.</ref>, tampering detection <ref name=tamp> [http://ieeexplore.ieee.org/abstract/document/7353154/ P. Korus, J. Huang, ''Improved Tampering Localization in Digital Image Forensics Based on Maximal Entropy Random Walk''], IEEE Signal Processing Letters, 2016.</ref> or [[tractography]] problem. <ref name=trac> [http://ieeexplore.ieee.org/abstract/document/6985622/ V.L. Galinsky, L.R. Frank, ''Simultaneous multi-scale diffusion estimation and tractography guided by entropy spectrum pathways''], IEEE Transactions on Medical Imaging, 2015.</ref>

Additionally, it recreates some properties of [[quantum mechanics]], suggesting a way to repair the discrepancy between [[diffusion]] models and quantum predictions, like [[Anderson localization]].<ref name=prl>[http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.102.160602 Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, ''Localization of the Maximal Entropy Random Walk''], Phys. Rev. Lett., 2009.</ref>

Line 8:

[[Image:General picture for Maximal Entropy Random Walk.png|thumb|480px|right|Left: the basic concept of the standard random walk (GRW) and Maximal Entropy Random Walk (MERW). Right: example of their evolution on the same inhomogeneous 2D lattice with cyclic boundary conditions - probability density after 10, 100 and 1000 steps while starting from the same vertex. The small boxes represent defects: all vertices but the marked ones have additional [[self-loop]] (edge to itself). For a regular lattice (no defects), GRW and MERW are identical. While defects do not strongly affect the local behavior, they lead to a completely different global stationary probability here. While GRW (and based on it standard [[diffusion]]) leads to nearly uniform stationary density, MERW has strong localization property, imprisoning the walkers in entropic wells in analogy to electrons in defected lattice of [[semi-conductor]].]]

Imagine there is a [[graph]] given by [[adjacency matrix]]: <math>A_{ij}=1</math> if there is an edge from vertex <math>i</math> to <math>j</math>, 0 otherwise. For simplicity assume it is an [[Graph_Graph (discrete_mathematicsdiscrete mathematics)#Undirected_graphUndirected graph|undirected graph]], what corresponds to symmetric <math>A</math>, however, MERW can be also generalized for directed and [[Graph_Graph (discrete_mathematicsdiscrete mathematics)#Weighted_graphWeighted graph|weighted graphs]] (getting [[Boltzmann distribution]] among paths instead of uniform).

We would like to choose a random walk as [[Markov process]] on this graph: for every vertex <math>i</math> and its outgoing edge to <math>j</math>, choose probability <math>S_{ij}</math> of the walker randomly using this edge after visiting <math>i</math>. Formally, choose <math>S_{ij}</math> [[stochastic matrix]] such that <math>0\leq S_{ij} \leq A_{ij},\ \sum_j S_{ij}=1</math>. Assuming this graph is connected and not [[Periodic_graph_Periodic graph (graph_theory)graph theory)| periodic]], [[ergodic theory]] says that evolution of this [[stochastic process]] leads to some stationary probability distribution <math>\rho_i</math>, such that <math>\sum_i \rho_i S_{ij} = \rho_j</math>.

Using [[Shannon entropy]] for every vertex and averaging over probability of visiting this vertex (to be able to use its entropy), we get the following formula for average entropy production ([[entropy rate]]) of a stochastic process:

Line 41:

<math>E \psi_x =-(\psi_{x-1} -2 \psi_x +\psi_{x+1}) + V_x \psi_x</math>

where <math>E = 3-\lambda</math> is minimized now, becoming the analog of energy. The formula inside the bracket is [[discrete Laplace operator]], making this equation a discrete analogue of stationary [[Schrodinger equation]]. Like in [[quantum mechanics]], MERW predicts that the probability distribution should lead exactly to the one of quantum [[ground state]]: <math>\rho_x \propto \psi_x^2</math> with its strongly localized density (in contrast to standard diffusion). Performing [[infinitesimal]] limit, we can get standard continuous stationary Schrodinger equation (<math>E\psi=-C\psi_{xx}+V\psi</math> for <math>C=\hbar^2/2m</math>) here.<ref name=ext> [http://www.fais.uj.edu.pl/documents/41628/d63bc0b7-cb71-4eba-8a5a-d974256fd065 J. Duda, ''Extended Maximal Entropy Random Walk''], PhD Thesis, 2012.</ref>

==See also==