Maximální entropická náhodná chůze - Maximal entropy random walk - Wikipedia

Maximální entropická náhodná chůze (MERW) je populární typ zaujatá náhodná procházka po grafu, ve kterém jsou pravděpodobnosti přechodu voleny podle princip maximální entropie, který říká, že rozdělení pravděpodobnosti, které nejlépe odpovídá současnému stavu poznání, je ten s největší entropií. Zatímco standardní náhodná procházka zvolí pro každý vrchol rovnoměrné rozdělení pravděpodobnosti mezi jeho odchozí hrany, lokálně maximalizující míra entropie, MERW to maximalizuje globálně (průměrná produkce entropie) za předpokladu rovnoměrného rozdělení pravděpodobnosti mezi všechny cesty v daném grafu.

MERW se používá v různých oblastech vědy. Přímá aplikace vybírá pravděpodobnosti k maximalizaci přenosové rychlosti přes omezený kanál, analogicky k Fibonacciho kódování. Díky svým vlastnostem byl užitečný například při analýze složitých sítí,^[1] jako predikce odkazu,^[2] detekce komunity,^[3]robustní přenos po sítích^[4] a ústřednost opatření.^[5] Také v analýza obrazu, například pro detekci oblastí vizuálního výběžku,^[6] lokalizace objektu,^[7] detekce neoprávněné manipulace^[8] nebo traktografie problém.^[9]

Navíc obnovuje některé vlastnosti kvantová mechanika, což naznačuje způsob, jak opravit nesrovnalost mezi difúze modely a kvantové předpovědi Andersonova lokalizace.^[10]

Základní model

Vlevo, odjet: základní koncept generické náhodné chůze (GRW) a maximální entropické náhodné chůze (MERW)
Že jo: příklad jejich vývoje na stejné nehomogenní 2D mřížce s cyklickými okrajovými podmínkami - hustota pravděpodobnosti po 10, 100 a 1000 krocích při startu ze stejného vrcholu. Malá políčka představují vady: všechny vrcholy kromě označených mají další vlastní smyčka (hrana k sobě). U běžných svazů (bez závad) jsou GRW a MERW identické. I když defekty silně neovlivňují místní chování, vedou zde ke zcela odlišné globální stacionární pravděpodobnosti. Zatímco GRW (a na základě toho standard difúze ) vede k téměř rovnoměrné stacionární hustotě, MERW má silnou lokalizační vlastnost a uvězňuje chodce v entropických jamkách analogicky k elektronům v defektní mřížce polovodič.

Zvažte a graf s ${ displaystyle n}$ vrcholy, definované pomocí matice sousedství ${ displaystyle A in left {0,1 right } ^ {n krát n}}$: ${ displaystyle A_ {ij} = 1}$ pokud existuje hrana z vrcholu ${ displaystyle i}$ na ${ displaystyle j}$, Jinak 0. Pro jednoduchost předpokládejme, že je neorientovaný graf, což odpovídá symetrickému ${ displaystyle A}$; MERW však lze také zobecnit na směrované a vážené grafy (například Boltzmannova distribuce mezi cestami místo uniformy).

Chtěli bychom zvolit náhodnou procházku jako Markov proces na tomto grafu: pro každý vrchol ${ displaystyle i}$ a jeho odchozí hrana do ${ displaystyle j}$, zvolte pravděpodobnost ${ displaystyle S_ {ij}}$ chodce náhodně pomocí tohoto okraje po návštěvě ${ displaystyle i}$. Formálně najděte a stochastická matice ${ displaystyle S}$ (obsahující pravděpodobnosti přechodu Markovova řetězce) takové, že

• ${ displaystyle 0 leq S_ {ij} leq A_ {ij}}$ pro všechny ${ displaystyle i, j}$ a
• ${ displaystyle sum _ {j = 1} ^ {n} S_ {ij} = 1}$ pro všechny ${ displaystyle i}$.

Za předpokladu, že tento graf je spojen, a ne periodicky, ergodická teorie říká, že vývoj tohoto stochastický proces vede k nějakému stacionárnímu rozdělení pravděpodobnosti ${ displaystyle rho}$ takhle ${ displaystyle rho S = rho}$.

Použitím Shannonova entropie pro každý vrchol a průměrování nad pravděpodobností návštěvy tohoto vrcholu (abychom mohli použít jeho entropii) dostaneme následující vzorec pro průměrnou produkci entropie (míra entropie ) stochastického procesu:

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

Ukázalo se, že tato definice je ekvivalentní asymptotické průměrné entropii (na délku) rozdělení pravděpodobnosti v prostoru cest pro tento stochastický proces.

Ve standardní náhodné procházce, která se zde označuje jako generická náhodná procházka (GRW), přirozeně volíme, že každá odchozí hrana je stejně pravděpodobná:

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

Pro symetrický ${ displaystyle A}$ vede to ke stacionárnímu rozdělení pravděpodobnosti ${ displaystyle rho}$ s

${ displaystyle rho _ {i} = { frac { sum limity _ {j = 1} ^ {n} A_ {ij}} { sum limity _ {i = 1} ^ {n} součet limits _ {j = 1} ^ {n} A_ {ij}}}}$.

Lokálně maximalizuje produkci entropie (nejistotu) pro každý vrchol, ale obvykle vede k suboptimální průměrované globální rychlosti entropie ${ displaystyle H (S)}$.

MERW vybírá stochastickou matici, která maximalizuje ${ displaystyle H (S)}$, nebo ekvivalentně předpokládá rovnoměrné rozdělení pravděpodobnosti mezi všechny cesty v daném grafu. Jeho vzorec se získá nejprve výpočtem dominantní vlastní číslo ${ displaystyle lambda}$ a odpovídající vlastní vektor ${ displaystyle psi}$ matice sousedství, tj. největší ${ displaystyle lambda v mathbb {R}}$ s odpovídajícími ${ displaystyle psi in mathbb {R} ^ {n}}$ takhle ${ displaystyle psi A = lambda psi}$. Pak je dána stochastická matice a stacionární rozdělení pravděpodobnosti

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

pro které je každá možná délka cesty ${ displaystyle l}$ z ${ displaystyle i}$- až ${ displaystyle j}$-tý vrchol má pravděpodobnost

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

Míra jeho entropie je ${ displaystyle log ( lambda)}$ a stacionární rozdělení pravděpodobnosti ${ displaystyle rho}$ je

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

Na rozdíl od GRW pravděpodobnosti přechodu MERW obecně závisí na struktuře celého grafu (jsou nelokální). Proto by si neměla být představována jako přímo aplikovaná chodcem - jsou-li náhodně vyhlížející rozhodnutí přijímána na základě místní situace, jako by to činil člověk, je vhodnější přístup GRW. MERW je založen na princip maximální entropie, což z něj činí nejbezpečnější předpoklad, když nemáme o systému žádné další znalosti. Například by bylo vhodné modelovat naše znalosti o objektu provádějící nějakou složitou dynamiku - ne nutně náhodnou, jako částice.

Náčrt odvození

Pro jednoduchost předpokládejme, že uvažovaný graf je nepřímý, propojený a neperiodický, což umožňuje vyvodit závěr z Perron-Frobeniova věta že dominantní vlastní vektor je jedinečný. Proto ${ displaystyle A ^ {l}}$ může být asymptoticky (${ displaystyle l rightarrow infty}$) přibližně ${ displaystyle lambda ^ {l} psi psi ^ {T}}$ (nebo ${ displaystyle lambda ^ {l} | psi rangle langle psi |}$ v bra-ket notace ).

MERW vyžaduje rovnoměrné rozdělení podél cest. Číslo ${ displaystyle m_ {il}}$ cest s délkou ${ displaystyle 2l}$ a vrchol ${ displaystyle i}$ ve středu je

${ displaystyle m_ {il} = součet _ {j = 1} ^ {n} součet _ {k = 1} ^ {n} left (A ^ {l} right) _ {ji} left ( A ^ {l} right) _ {ik} přibližně 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}}$,

tedy pro všechny ${ displaystyle i}$,

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

Analogickým výpočtem rozdělení pravděpodobnosti pro dva následující vrcholy získá jeden pravděpodobnost, že bude na ${ displaystyle i}$-tý vrchol a další na ${ displaystyle j}$-tý vrchol je

${ displaystyle { frac { psi _ {i} A_ {ij} psi _ {j}} { součet limity _ {i '= 1} ^ {n} součet limity _ {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}}}}$.

Dělením pravděpodobností, že budete na ${ displaystyle i}$-tý vrchol, tj. ${ displaystyle rho _ {i}}$, dává za podmíněná pravděpodobnost ${ displaystyle S_ {ij}}$ z ${ displaystyle j}$-tý vrchol je další po ${ displaystyle i}$-tý vrchol

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

Příklady

Vlevo: výběr optimální pravděpodobnosti za symbolem 0 palců Fibonacciho kódování. Vpravo: jednorozměrná defektní mřížka a její stacionární hustota pro cyklus délky 1000 (má tři defekty). Zatímco při standardní náhodné chůzi je stacionární hustota úměrná stupni vrcholu, což zde vede k rozdílu 3/2, v MERW je hustota téměř úplně lokalizována v největší oblasti bez defektů, analogicky k základní stav předpovídal kvantová mechanika.

Nejprve se podívejme na jednoduchou netriviální situaci: Fibonacciho kódování, kde chceme vyslat zprávu jako sekvenci 0 s a 1 s, ale nepoužíváme dvě po sobě jdoucí 1 s: po 1 musí být 0. Abychom maximalizovali množství informací přenášených v takové posloupnosti, měli bychom předpokládat jednotné rozdělení pravděpodobnosti v prostoru všech možných sekvencí splňujících toto omezení. K praktickému použití takových dlouhých sekvencí musíme po 1 použít 0, ale zůstává svoboda volby pravděpodobnosti 0 po 0. Pojďme tuto pravděpodobnost označit ${ displaystyle q}$, pak entropické kódování by umožnilo kódování zprávy pomocí tohoto zvoleného rozdělení pravděpodobnosti. Stacionární rozdělení pravděpodobnosti symbolů pro daný ${ displaystyle q}$ se ukáže být ${ displaystyle rho = (1 / (2-q), 1-1 / (2-q))}$. Produkce entropie tedy je ${ Displaystyle H (S) = rho _ {0} vlevo (q log (1 / q) + (1-q) log (1 / (1-q)) vpravo)}$, který je maximalizován pro ${ displaystyle q = ({ sqrt {5}} - 1) / 2 přibližně 0,618}$, známý jako Zlatý řez. Naproti tomu standardní náhodná chůze by zvolila neoptimální ${ displaystyle q = 0,5}$. Při výběru větší ${ displaystyle q}$ snižuje množství informací produkovaných po 0, také snižuje frekvenci 1, po které nemůžeme zapsat žádné informace.

Složitějším příkladem je vadná jednorozměrná cyklická mřížka: řekněme 1000 uzlů spojených v kruhu, pro které mají všechny uzly kromě defektů vlastní smyčku (hranu k sobě). Při standardním náhodném chodu (GRW) by stacionární rozdělení pravděpodobnosti mělo pravděpodobnost defektu 2/3 pravděpodobnosti bezporuchových vrcholů - neexistuje téměř žádná lokalizace, rovněž analogicky pro standardní difúze, což je nekonečně malý limit GRW. Pro MERW musíme nejprve najít dominantní vlastní vektor matice sousedství - maximalizovat ${ displaystyle lambda}$ v:

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

pro všechny pozice ${ displaystyle x}$, kde ${ displaystyle V_ {x} = 1}$ za vady, 0 jinak. Střídání ${ displaystyle 3 psi _ {x}}$ a vynásobením rovnice −1 dostaneme:

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

kde ${ displaystyle E = 3- lambda}$ je nyní minimalizován a stává se analogem energie. Vzorec uvnitř závorky je diskrétní Laplaceův operátor, což činí tuto rovnici diskrétním analogem stacionáře Schrodingerova rovnice. Jako v kvantová mechanika, MERW předpovídá, že rozdělení pravděpodobnosti by mělo vést přesně k kvantovému základní stav: ${ displaystyle rho _ {x} propto psi _ {x} ^ {2}}$ s jeho silně lokalizovanou hustotou (na rozdíl od standardní difúze). Užívání infinitezimální limitu, můžeme získat standardní spojitou stacionární (časově nezávislou) Schrodingerovu rovnici (${ displaystyle E psi = -C psi _ {xx} + V psi}$ pro ${ displaystyle C = hbar ^ {2} / 2 m}$) tady.^[11]

Viz také

• Princip maximální entropie
• Centrality vlastního vektoru
• Markovův řetězec
• Andersonova lokalizace

Reference

externí odkazy

• Gábor Simonyi, Y. Lin, Z. Zhang, „Průměrná doba prvního průchodu pro náhodné procházky maximální entropií v komplexních sítích“. Vědecké zprávy, 2014.
• Modely elektronové vodivosti využívající náhodné procházky maximální entropií Demonstrační projekt Wolfram