how to do Gaussian belief propagation on tree

[dehann]

which variables and factors (maybe conditionals) are needed in each clique?

[dehann]

The Factor Graph

@Affie does not want to (immediately) upload himself -- so now im doing it ;-) Lets work from here. Calling on @tonioteran who draws beautiful graphics on the same issue.

The issue comes back to whether Bayes tree cliques are densely connected (like the Bayes Net). Remember the Bayes tree is picked up from the Bayes Net. Other way Bayes Net is a squashed Bayes tree.

First hypothesis is that the densely connected structure of the Bayes net is in large part carried by the ordering of the Bayes tree itself.

[dehann]

variable ordering is: 0, 2, 4, 1, 3, 5

[Affie]

The Tree for variable ordering 0,2,4,1,3,5

[dehann]

Look, closely at the structure of the tree.

Q: When does the relationship (conditionals) between x3, x5, x1 (root) come into affect?

A: Look at each of the children -- when calculating x3,x5 in the left child, the mixing through x4 does occur in both the up and downward direction.

This is easy to see in a numerical approach when initial values for x3, x4, x5 exist.

Aside Q: What if no initialization values exist? How should information from the prior on x0 arrive at upward frontal and separators for (x4 : x3,x5). Is cascading up and down passes the correct way to solve this problem? This is what is currently implemented in CSM treeinit:

IncrementalInference.jl/src/CliqStateMachine.jl

Line 369 in 62a87ed

# initialize clique in downward direction

[dehann]

Also see:

• Confirm clique sub-graphs only use priors once  #458
• simple prior use test #461

[dehann]

Just as a note, the "method of triples" also exists.

[tonioteran]

I'll finish some graphics and then post them here to try and elucidate some concepts.

[Affie]

Elimination of the factor graph illustrated in a tree

Flipped from tree image above.
"upsolve"

"downsolve" (back substitution in the matrix equivalent)

[dehann]

Okay, lets make this worse -- should up and down solves (on the tree message passing) be symmetric. Or should different factors be used in different cliques during the up or down pass -- think of priors as first case.

Also think of initializing variables on the tree. Should priors show up as early as possible during an up pass, or should priors only occur for frontals mid tree, and rather rely on downward initialization messages first.

[dehann]

Initialization on tree, how would we initialize x1,x2,x3 since prior is on x0.

FYI:
https://vimeo.com/332507701

[dehann]

you can only pass information on the tree following the links -- so if a clique does not have enough info lower from below, then it must initialize with a message from parent down.