Loopy Belief Propagation

[awohns]

One of the issues with the tsdate approach is that there are (undirected) cycles in the tree sequence DAG, which makes the passing up and down of likelihoods not quite exact. This is a known issue in Bayesian network theory which goes under the name of "Loopy Belief Propagation". The solution is usually to iterate over the passing of information between nodes, but we're not quite sure how to apply to this to the current tsdate implementation.

I've spent some time investigating this, and it seems likely running the inside-outside algorithms more than once will result in accuracy improvements. The idea is simple: use the posterior from a single run as the prior for subsequent runs. This is quick, as we don't need to recalculate the prior or recalculate likelihoods. We could add a num_iterations argument to date to specify how many iterations the user wants to run.

[hyanwong]

If we do it repeatedly, we dilute the prior, I think? So I suspect that it's not quite the right way to go about it.

[awohns]

Why is that, do you have a cite? Empirically we get better accuracy by not using the prior in subsequent iterations

[hyanwong]

Well, if the prior has no effect, then you're simply finding the likelihood, I think?

[awohns]

This is the key paper: https://arxiv.org/pdf/1301.6725.pdf And here's the part that's relevant to incorporating the prior:

Nodes were updated in parallel: at each iteration all nodes calculated their outgoing messages based on the incoming messages of their neighbors from the previous iteration. The messages were said to converge if none of the beliefs in successive iterations changed by more than a small threshold (10-4). All messages were initialized to a vector of ones; random initialization yielded similar results, since the initial conditions rapidly get "washed out".

So I think repeatedly running the inside-outside algorithm isn't quite the same thing that they do in this paper. It seems like we can update all the messages from children to parents and parents to children at the same time in each update step

[hyanwong]

I think that the Expectation Propagation (EP) approach described by @nspope in https://github.com/tskit-dev/tsdate/pull/257#issuecomment-1562020587 and now implemented in tsdate using method="variational_gamma" correctly accounts for loopy belief propagation? If so, and we want to switch to using this as the default approach, then this issue may be more-or-less solved.

Nevertheless, it might still be useful to allow multiple iterations of the inside-outside algorithm, as described here. Previously this has actually made the estimations worse, but I wonder if it will improve things if geometric scaling is not used?

[hyanwong]

@nspope says:

It's more complicated (than feeding the posterior back in as a prior). Like with EP, you can't just store the current approximation in a NodeGridValues object. You have to store the messages per edge, so they can be "subtracted" and "re-approximated" edge by edge. It's very similar to what is done during the outside step, where the inside value for the edge is removed before updating the approximation.

[hyanwong]

This is solved when using variational_gamma, by iterating and looking for convergence. I guess it would be possible to add that to the inside_outside method too, but that sounds like a different issue, so I'm closing this and opening a new one.