$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance.

The objective is for all nodes in the graph to find Maximum Likelihood estimates for $\mu$ and $\sigma^2$. To do this, nodes are allowed to pass messages to their neighbors at each time step.

My question is what is a good scheme to accomplish this with few iterations? In particular, what messages should be sent, and how should they be used to update a node's estimate for $\mu$ and $\sigma^2$?

I'd like the answer for the following scenarios. The more general scenario you can answer for, the better.

  • Undirected Graph
  • Directed Graph
  • Scalar messages (message can only be a single value)
  • Vector messages with a maximum length $k$ (e.g. messages can only be up to $k$ values)
  • Distributions besides the Gaussian Distribution. E.g. Gamma distribution with unknown $\alpha$ and $\beta$.

I'd also like to know roughly at what rate $\tau$ the algorithm will converge. E.g. every $\tau$ timesteps, you've converged by a factor of 2.

So far, the only solution I can simply think of is for estimating the mean $\mu$. In that case, the message $m_i$ a node sends out will be its current estimate for the mean, and it updates its estimate by averaging all the messages it receives (along with its sample $x_i$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.