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: https://github.com/JuliaRobotics/IncrementalInference.jl/blob/62a87ed1b02e7f5488911051348dc039a4eaad77/src/CliqStateMachine.jl#L369

[dehann]

Also see:

• #458
• #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.

[tonioteran]

similar graph as the one at the top, but with one additional variable (l_1). specifies how to go from factor graph, to chordal bayes net, to bayes tree for a specific ordering. you wonder, aren't cliques densely connected: well yes, in the chordal bayes net sense (color coded). nonetheless, when one analyses the factors and the portion of the factor graph contained within each clique (which is the actual information being used for inference), then the variables involved are not fully connected: the tree just specifies us the order in which to carry out operations.

hex-slam.pdf

[tonioteran]

the latter part (which parts of the factor graph land in which cliques) i will have pictorially depicted in a bit

[tonioteran]

here's what the upstream messages would look like, e.g., the "smart factors" or priors being passed up towards the root (all based on the previous example)

hex-slam-upstream-factors-in-cliques.pdf

EDIT: TT, errata -- yellow root matrix should be fully dense (top right corner of submatrix is nonzero)

[dehann]

hi @tonioteran , thanks those are great!!

So after many hours today we think we have better wording to describe what is going on with Bayes net vs Bayes tree, will post that text here.

[dehann]

Definitions

• Squashing or collapsing the Bayes tree back into a 'flat' Bayes net,
• Chain rule: p(x,y) = p(x|y)p(y) = p(y|x)p(x)
  • p(x,y,z) = p(x|y,z)p(y,z) = p(x,y|z)p(z) = p(x|y,z)p(y|z)p(z)
  • p(x,y,z) = p(x|y,z)p(y)p(z) iff y is independent of z === p(y|z)=p(y)

Example

Look at clique: (x0:x1,x5)

eliminate x0 from factor graph produces (in the Bayes net) conditionals x5->x0, x1->x0, plus a new product-factor between x0,x5:

• chain rule: (prod factors on x0) = p(x0,x1,x5) = p(x0|x1,x5)p(x1,x5)

• p(x0,x1,x5|z0,z1,z2) ∝ p(z0|x0)p(z1|x0,x1)p(z2|x0,x5)

  • Bayes tree message passing
    • p(x0|x1,x5) is the belief over clique (x0:x1,x5)
    • p(x1,x5) is the message passed on the tree

Expontial Families are special (congruency)

• Gaussian * Gaussian = Gaussian!!!!

Non-parametric design:

• (small)KDE * (small)KDE = (big)KDE ≈ (small)KDE

[dehann]

https://github.com/JuliaRobotics/Caesar.jl/pull/445/files

[dehann]

Previous comment, placing here so that it does not get lost

See node x1 to x3 in IncrementalInference issue 464. It does not branch or provide additional prior information. so it is collapsed into one factor between x1 and x3, solved in the root and the individual variable can be solved by inference.

[Affie]

https://github.com/JuliaRobotics/IncrementalInference.jl/compare/23Q4/exp/par_tree