 |
Keverés és információterjedés, Markov láncok a komfortzónán túl
|
súgó 
nyomtatás 
|
Ezen az oldalon az NKFI Elektronikus Pályázatkezelő Rendszerében nyilvánosságra hozott projektjeit tekintheti meg.
vissza »
|
| |
Projekt adatai |
|
|
| azonosító |
135711 |
| típus |
FK |
| Vezető kutató |
Gerencsér Balázs |
| magyar cím |
Keverés és információterjedés, Markov láncok a komfortzónán túl |
| Angol cím |
Mixing and information spread, Markov chains outside the comfort zone |
| magyar kulcsszavak |
Markov láncok, keverési idő, nem-reverzibilitás, push-sum, konszenzus, szinkronizálás |
| angol kulcsszavak |
Markov chains, mixing time, non-reversibility, push-sum, consensus, synchronization |
| megadott besorolás |
| Matematika (Műszaki és Természettudományok Kollégiuma) | 100 % | | Ortelius tudományág: Valószínűségelmélet |
|
| zsűri |
Matematika–Számítástudomány |
| Kutatóhely |
HUN-REN Rényi Alfréd Matematikai Kutatóintézet |
| résztvevők |
Kornyik Miklós
|
| projekt kezdete |
2020-12-01 |
| projekt vége |
2021-09-30 |
| aktuális összeg (MFt) |
7.706 |
| FTE (kutatóév egyenérték) |
0.90 |
| állapot |
lezárult projekt |
magyar összefoglaló A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
Markov láncok kutatását motiválja sok és széles körű alkalmazása, kezdve a mintavételezésen, optimalizáláson át integrálközelítésekig. Ilyen algoritmusok fejlesztésének fontos kihívása, hogy a felhasznált Markov láncot gyorsítsuk, azaz minimalizáljuk a keverési időt. Ismerve a lehetséges átmenetek gráfját és az elérendő stacionárius eloszlást, meg kell találni az optimális átmenetvalószínűségeket.
Ebben a kutatásban a nem-reverzibilitás adta szabadságot szeretnénk kiaknázni, látva a példákat, ahol jelentős gyorsulás érhető el hagyományos reverzibilis Markov láncokhoz képest.
Az első modulban először konkrét (véletlen) gráfokkal foglalkozunk, amiket kis-világ hálózatok modellezésére is használnak.
Ezentúl általánosabban is kielemezzük a módszert, hogy egy gráf körei mentén aszimmetriát vezetünk be, kiterjesztve úgy is, hogy néhány éllel bővíthetjük a gráfot.
A második modulban elosztott kommunikációs hálózatokban hasonló folyamatokkal dolgozunk, amikor közösen kiinduló mérések átlagolása a cél.
Először az ún. "push-sum" algoritmust finomítjuk, ami aszinkron üzenetek kezelésére alkalmas, hogy az átlagolás konvergenciasebességét javítsuk.
Ezután azt vizsgáljuk, amikor fázisok szinkronizálása a cél, és aszimmetrikus kölcsönhatásokat is megengedünk. Végül a fázis-szinkronizáló feladatnak egy variánsát tekintjük, ahol ismét aszinkron kommunikáció bonyolítja a dinamikát.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A kiinduló kérdés: hogyan lehet Markov láncok keverését gyorsítani?
Ezzel formálisan ekvivalens feladatot ad: hogyan lehet gyorsan konszenzusra jutni nagyszámú ágenssel, csupán lokális kommunikációval?
Bár a két kiindulási helyzetben a kérdések formálisan azonosak, az eltérő motiváció miatt más irányba mozdulnak el a vizsgálódásaink.
Markov láncok esetén a fókusz egy megadott átmenetgráf mentén az átmenetvalószínűségek előnyös módosításán van, megengedve aszimmetriát (nem-reverzibilitást). Távolabb tekintve a megengedett átmenetek enyhe bővítésének hatását is szeretnék megérteni és kiaknázni.
Konszenzus aspektusából a kommunikációs bizonytalanságok hatását szeretnénk érteni, mint aszinkron kommunikáció, üzenetvesztés, stb. Kiemelten dolgozunk egy ilyen helyzetekre tervezett és részben megértett, ún. push-sum algoritmussal, kihívásaink közé tartozik ennek gyorsabb variánsának kifejlesztése.
Kiemelt figyelmet kap az a probléma, amikor valós értékek helyett fázis értékű a konszenzus dinamika, ami gyakran frekvenciaszinkronizációhoz vezet, itt ismét vizsgáljuk az aszimmetrikus kapcsolati erősségek hatását.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
Olyan alapvető sztochasztikus folyamatokat értelmezünk és alkotunk, melyek használata már rutinszerűen beépült matematikai és külső alkalmazási területekre is.
Kiragadott példák Markov lánc alkalmazásokra:
Térfogatszámítás magas dimenzióban, gráfszínezések mintavételezése, közelítő leszámlálás és integrálás.
Kiragadott példák konszenzus és frekvenciaszinkronizáció megjelenésére:
Szenzorhálózatok, fizika, kémiai reakcióhálózatok, idegtudomány, járműirányítás.
Jelen kutatás a matematikai részlegre fókuszál. De amint elérhető egy javulás, például gyorsabb Markov lánc, erősebb bizonyított sebességbecslés, erre az adott területek építhetnek, hogy hatékonyabb, pontosabb eredményre jussanak.
A kutatás fő erőssége, hogy bátran mer az aszimmetria irányába lépni. Látszanak példák, ahol pl. aszimmetrikus Markov láncok lényegesen gyorsabban kevernek, azonban legtöbb esetben ezek analízise nehéz és az eszköztár korlátos. Úgyhogy bőven van potenciál és kemény munka ebbe az irányba.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Milyen alakú teremben alakul ki könnyebben vagy nehezebben vastaps?
A kérdés ebben a formában szórakoztató, de sokkal mélyebb általános kérdés húzódik meg mögötte: különböző frekvenciával tevékenykedő (tapsoló) nagyszámú ágens (elégedett vendég) milyen kapcsolódási struktúrája (mennyire hallják egymást, mennyire követik egymást) garantálja, hogy frekvenciaszinkronizáció alakuljon ki (vastaps)?
Az általános kérdés pedig már fizika, kémiai reakcióhálózatok, idegtudomány, járműirányítás területén is visszaköszön.
Jelen kutatásban az az irány van a középpontban, ha egyes ágensek közötti kapcsolatok nem szimmetrikusak, egyik jobban követi a másik fázisát, mint viszont. Ez egy újszerű irány a nemzetközi kutatásban, ami egyrészt bővítheti az alkalmazhatóságot, másrészt hatékonyabban szinkronizáló rendszerek tervezésére ad kilátást.
A kutatás másik ágán nem fázisokról, hanem valós számokról kell az ágenseknek megegyezniük, ilyet lehet például szenzorhálózatokon elképzelni, ahogy a mért adatokat szeretnék közösen kiátlagolni. Célunk a jelenleg elterjedt algoritmusok hatékonyságát növelni a tökéletlen kommunikáció figyelembevételével, valamint a mögöttes Markov-lánc elméletnél szintén a gyorsabb keverést elérni. A kulcs itt is az aszimmetrikus kommunikáció kiaknázásában rejlik.
| angol összefoglaló Summary of the research and its aims for experts
Describe the major aims of the research for experts.
Our motivation to study Markov chains is knowing that it is at the heart of uncountable applications, from sampling through optimization to approximate integration and onward. To improve such algorithms, an important challenge is to strengthen the ergodic behavior of the underlying Markov chains, to minimize their mixing time. Given a graph of possible transitions and a stationary distribution to attain, the optimal transition probabilities should be found.
In this project we exploit the freedom of non-reversible chains, already having examples demonstrating significant speedup compared to traditional reversible Markov chains.
In the first package we initially target specific (random) graphs which are also used for modeling Small World Networks.
We then further explore the power of implementing drifts along cycles of the graph, extending to the case when even a few new edges can be used.
In the second package we refine analogous dynamics which emerge in distributed communication systems when collectively computing an average, say, of sensor measurements (average consensus).
First, we generalize the "push-sum" algorithm designed to handle asynchronous communication to achieve faster averaging performance.
Next, we analyze the scenario when phase synchronization is the goal in the case when asymmetric connection strengths can appear. Finally, we target a problem of phase synchronization when asynchronous updates alter the dynamics.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
The baseline question is: how can we speed up Markov chain mixing?
We get a formally equivalent problem by asking: how can we get faster to consensus for a number of agents using only local communication?
Although the initial formal questions are the same, due to the different motivations our research leads to different directions.
In the case of Markov chains, once a graph of possible transitions is given, the focus is on choosing favorable transition probabilities, even allowing asymmetry (non-reversibility). As a further step, we want to analyze and exploit the benefits of minor augmentation of the transition graph.
Concerning consensus, we attempt to handle communication imperfections, like asynchronous communication, packet loss, etc. We put emphasis on so-called 'push-sum' algorithm designed for such contexts, we want to develop more efficient variants of it.
We focus on the problem where instead of averaging real numbers, phases are attracted to each other, which often leads to frequency synchronization, once again looking at the effect of asymmetric connection strengths.
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
We are analyzing and constructing fundamental stochastic processes which are already routinely used in applications within and outside of mathematics.
Selecting a few Markov chain applications:
Volume computation in high dimension, sampling graph coloring, approximate counting and integration.
Picking a few applications of consensus and frequency synchronization:
Sensor networks, physics, chemical reaction networks, neuroscience, vehicle coordination.
The current research focuses on the mathematical aspect. Still, as soon as there is an improvement, for example a better mixing Markov chain or a stronger proven bound on speed, application areas may use it to get more efficient and precise results.
The main strength of the research is that it boldly steps in the direction of asymmetry. There are already examples which demonstrate that asymmetric Markov chains sometimes mix substantially faster, but in most cases their analysis is hard and available tools are scarce. Clearly, there is a lot of potential and a lot of work along this road.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Probably folk dancers in a circle would step together if the music went shut for some reason. But if they were facing outwards, they would start to get puzzled very soon. What's the difference?
First, they had the (visual) information of everyone's phase, which was enough, next, only of their two neighbor's which was insufficient.
This looks like an amusing question in this form, but there is a deep and fundamental question behind: a lot of agents (dancers) are acting at different own frequencies with a willingness to follow each other and with measurements on some of them. The question is what condition ensures global synchronization.
Now in this general form, we face the question in physics, chemical reaction networks, neuroscience and vehicle coordination.
In the current research the primary goal is to analyze the case when connections are not symmetric, one agent may strongly follow another one with no or little effect in the other direction. This is a novel direction in international research, which can broaden the applicability of the mathematical framework once properly understood, and may help constructing, engineering systems with faster, more robust synchronization.
In the other part agents have to agree on real numbers rather than phases, this happens, e.g., on sensor networks, where a number of sensors should average out their measurements. Our goal is to improve the efficiency of standard algorithms in the presence of communication imperfections like packet delay or loss, moreover to achieve faster mixing for Markov chains which form the fundamental layer of the problem. Once again the key is to exploit the possibility of asymmetric communication.
|
|
|
|
|
|
|
|
|
|
