Draft:Dynamic message passing

Draft article not currently submitted for review. This is a draft Articles for creation (AfC) submission. It is not currently pending review. While there are no deadlines, abandoned drafts may be deleted after six months. To edit or make changes to this draft, simply click on the "Edit" tab at the top of the window. To be accepted, a draft should: Show the subject qualifies for a Wikipedia article by using multiple sources that meet four criteria. The sources should be (1) reliable (2) secondary (3) independent of the subject (4) talk about the subject in some depth. For some topics, there are alternative criteria. Be written from a neutral point of view Respect copyright and do not plagiarize. Do not copy-paste. It is strongly discouraged to write about either yourself or your business or employer. If you do so, you must declare it. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Last edited by MWilinski (talk | contribs) 4 days ago. (Update) Submit the draft for review!

Dynamic message passing (DMP) is a family of message-passing algorithms for computing marginal probabilities of various dynamical processes on networks. The need for such equations comes from the fact that standard message passing methods such as belief propagation (BP) are computationally inefficient when directly applied to dynamic problems. Though DMP equations can be directly derived from BP, they take advantage of the structure imposed on the problem by a specific type of dynamics. This allows for direct computation of the BP solution, without the need of iterating the equations. Good example are DMP equations for unidirectional compartmental models dynamics on trees, which were strictly derived from BP.^[1] Sometimes the name is used to refer to message passing like equations, which are applied to dynamic problems on networks, but are not directly connected to BP.^[2] In such cases the equations may not be exact on trees, but can still be useful in other settings.

Being able to compute marginal probabilities is specifically useful for prediction tasks. One particular example is the task of estimating the expected global spread for spreading models on networks. If we denote the number of infected individuals in the population at time ${\displaystyle t}$ by ${\displaystyle N_{t}^{I}}$, then we can write

${\displaystyle \operatorname {E} [N_{t}^{I}]=\sum _{i}p_{i}(X_{t}^{i}=I),}$

where ${\displaystyle I}$ is the infected state, ${\displaystyle N_{t}^{I}}$ is the number of infected individuals at time ${\displaystyle t}$ and ${\displaystyle X_{t}^{i}}$ is the state of node ${\displaystyle i}$ at time ${\displaystyle t}$. ... In the case of simple unidirectional dynamics the complexity of the problem can be further simplified... ...

Most popular use-case for DMP equations are epidemic models on networks. These are typically network versions of classical compartmental models, like for example Susceptible-Infected-Recovered model. Below are some examples of DMP equations for such models.

...In this simple model of epidemic spreading...

...adding the extra state...

...special case of the above described SIR model...with ${\displaystyle \gamma =1}$, which means every infected node immediately gets removed...popular in computer science...

${\displaystyle p_{i\rightarrow j}(t)=1-(1-p_{i}(0))\prod _{k\in \partial i\setminus j}(1-\alpha _{ki}\cdot p_{k\rightarrow i}(t)),}$

DMP equations can be directly derived from belief propagation equations, but it requires a modification of the original spreading graph. Straightforward... ...

${\displaystyle \mu ^{i\rightarrow j}({\vec {\sigma }}_{i})\propto \prod _{k\in \partial i\setminus j}\sum _{{\vec {\sigma }}_{k}}W_{i}({\vec {\sigma }}_{i};{\vec {\sigma }}_{k})\cdot \mu ^{k\rightarrow i}({\vec {\sigma }}_{k}),}$

...

${\displaystyle \mu ^{i\rightarrow j}({\vec {\sigma }}_{i\rightarrow j},{\vec {\sigma }}_{j\rightarrow i})\propto \sum _{\{{\vec {\sigma }}_{k\rightarrow i}\}_{k\in \partial i\setminus j}}W_{i}({\vec {\sigma }}_{i\rightarrow j};\{{\vec {\sigma }}_{k\rightarrow i}\}_{k\in \partial i})\prod _{k\in \partial i\setminus j}\mu ^{k\rightarrow i}({\vec {\sigma }}_{k\rightarrow i},{\vec {\sigma }}_{i\rightarrow k}),}$

...

${\displaystyle \mu ^{i\rightarrow j}({\vec {\sigma }}_{i}||{\vec {\sigma }}_{j})=\sum _{\{{\vec {\sigma }}_{k}\}_{k\in \partial i\setminus j}}W_{i}({\vec {\sigma }}_{i};\{{\vec {\sigma }}_{k}\}_{k\in \partial i})\prod _{k\in \partial i\setminus j}\mu ^{k\rightarrow i}({\vec {\sigma }}_{k}||{\vec {\sigma }}_{i}),}$

...

${\displaystyle \mu ^{i}({\vec {\sigma }}_{i})=\sum _{\{{\vec {\sigma }}_{k}\}_{k\in \partial i}}W_{i}({\vec {\sigma }}_{i};\{{\vec {\sigma }}_{k}\}_{k\in \partial i})\prod _{k\in \partial i}\mu ^{k\rightarrow i}({\vec {\sigma }}_{k}||{\vec {\sigma }}_{i}),}$

...

As an example...

${\displaystyle m_{T+1}^{i\rightarrow j}(\tau _{i}||\tau _{j})=\sum _{\{\tau _{k}\}_{k\in \partial i\setminus j}}W_{i}(\tau _{i};\{\tau _{k}\}_{k\in \partial i})\prod _{k\in \partial i\setminus j}m_{T}^{k\rightarrow i}(\tau _{k}||\tau _{i}),}$

...

${\displaystyle m_{T+1}^{i}(\tau _{i})=\sum _{\{\tau _{k}\}_{k\in \partial i}}W_{i}(\tau _{i};\{\tau _{k}\}_{k\in \partial i})\prod _{k\in \partial i}m_{T}^{k\rightarrow i}(\tau _{k}||\tau _{i}),}$

...

DMP inherits the properties of belief propagation and as such is exact on trees, unless other approximations were used. It is also asymptotically exact for sparse and tree-like graphs, but breaks down when many short loops are present. Low, even linear, complexity in time is achieved for models with unidirectional dynamics, where a single trajectory can be parametrised by only a few parameters, regardless of the time horizon. ...Trees, Unidirectional dynamics...

DMP is an approximate inference technique, but its main strength comes from the fact that, unlike standard BP, it does not require iteration and with certain realistic assumptions about the dynamics, can be as computationally efficient as a single Monte Carlo run [needs citation]. These advantages, together with marginalisation over time, make DMP a perfect sub-routine for more complex tasks, such as learning [needs citation] or optimisation^[3]. One good example is...(learning with partial observation <-- can deal with unobserved nodes due to marginalisation over nodes and is computationally efficient)... ...Inference, Learning, Optimisation...