Consolidate belief messages and message channels

[Affie]

This is a summary:

• 1. Messages
• 2. Channels
  • up (IIF v0.13)
  • dwn (IIF v0.16, planned)

---

xref summary of related aspects:

• refactor tree messages to single up and single down container #385 (refactor tree messages up and dwn to single container type)
• [FEATURE] make VND.bw a 3 index array in preparation for parametric #465 (VND.bw a 3 index array ✖️ )
• WIP Linear parametric solution #468 (first merge linear parametric solution)
• [DEV] Overview of issues related to parametric and consolation #558 (overview of issues relating to parametric and consolidation)
• Generalized deconv #579 (generalized deconvolution)
• Add covariance calculations to parametric #600 (add covariance calculations to parametric)
• refactor LikelihoodMessage TreeBelief #647 (refactor LikelihoodMessage TreeBelief)
• drop TempBeliefMsg #648 (drop TempBeliefMsg)
• fix tests after prev merge #650 (fix test failure)
• further consolidation of tree messages #651 (further consolidate tree messages)
• fast forward parametric dev #652 (fast-forward parametric dev)
• Add cliqueLikelihood to LikelihoodMessage and remove BeliefMessage #653 (add Likelihoods rm BeliefMessage)
• refactoring tree msg types (459) #654 (refactor tree msg types)
• Simultaneous solvers use same CSMC / Tree? #673 (super solving)
• CSM message passing push or pull model #674 (push pull model)
• Decide if msg channels in BTND or edges only #675 (store msg channels in csmc/btnd or separately in tree & edges)
• fetch vs take! on message channels #855 (fetch vs. take!)

---

1. Likelihood messages

• Message will be the marginalized likelihood of the separators in the clique
• variableOrder are variable labels to identify the values
• In the case of parametric an MvNormal can be used to store μ and Σ <: SampleableBelief
• inferdim
• softtype (for manifold and variable dimension)
• Flag or other way to show the presence of prior information.
• Earlier names include: productFactor, Fnew, MsgPrior, LikelihoodMessage

Types of factors made from messages so far

• Prior factor (as existing)
• Conditional factors constructed from the deconvolution of the likelihood message.
  • Need to identify the type such as Pose2Pose2, Pose2Point2BearingRange

Structure used for the Likelihood message WIP

"""
    CliqStatus
Clique status message enumerated type with status:
initialized, upsolved, marginalized, downsolved, uprecycled
"""
@enum CliqStatus INITIALIZED UPSOLVED MARGINALIZED DOWNSOLVED UPRECYCLED ERROR_STATUS
#we probably also need: CANT_INITIALIZE, PARTIAL_INIT, etc.

struct LikelihoodMessage{T <: SamplableBelief} #<: Singleton
  status::CliqStatus
  belief::Dict{Symbol, TreeBelief}
  variableOrder::Vector{Symbol}
  cliqueLikelihood::{T} # MvNormal for parametric
end

TreeBelief:

struct TreeBelief{T <: InferenceVariable}
  val::Array{Float64,2}
  bw::Array{Float64,2}
  inferdim::Float64
  softtype::T
end

Message Design

It looks like parametric and mm can fit in a standard message type. Since the standard variable node data is used for now.
Can we have a look at what might be needed in the future and define a message type. I see:

• EasyMessage
  • DF the first type ever written which tried to avoid sending circular references to multiprocess dispatch. BallTreeDensity currently still has a circular reference in its data types.
  • DF, this also created large amounts of unnecessary memory allocation and repeat type conversion workload overhead, and think a chunk of that is still being done today.
• TempBeliefMsg - used
  • DF, think this might even just be an alias of a Tuple or something.
• NBPMessage
  • DF, old short lived attempt to consolidate, but was never completed due to time pressure.

I'll base parametric on it then. We can use it a bit and then update mm when we are happy.

• DF, sounds good

---

2. Message Channels

High level decision to store

One up and one down channel for every edge in the tree.

• upMsgChannel::Channel{BeliefMessage} can also be a remote channel
• downMsgChannel::Channel{BeliefMessage}

Note: up messages are from child to parent.

In concept I think this should work, its simple and only has one up and one down channel for synchronization. However, the current CSM is a bit more complicated and consolidation might be a bit harder.

• consolidate clique / tree likelihood messages (intermediate)
• Message passing as channels of LikelihoodMessage
• One upMsgChannel::Channel{LikelihoodMessage} per clique/edge
• One downMsgChannel::Channel{LikelihoodMessage} per clique/edge

Pending Decisions

• DF, (store channels in tree (edges or BTND, definitely not in csmc)
• DF, CSM message passing push or pull model #674 (pull model, definitely not push)

Channel Design

JT EDIT: @dehann please edit
Message passing refactoring:

• State machine containers have read only access to the tree.
  • DF, would the edge based message channels could either be stored outside the tree or in csmc?
• The concept should work in parallel/different processes. All information needed should be shareable with no direct memory access to children or parents (other than through channels or conditions). Think distributed tree solving.
  • DF, agree -- with current CSM does sometimes reach across to parent of child cliques but only to get status or messages via existing channels or conditions.
• The CSM should be able to run in debug mode on a single clique
  • DF, yes definitely :-)

Complications

• DF, One issue is that tree initialization currently requires a dictionary of up messages to be stored in the parent (given a push model).

• Suggestion was made to make channels a dictionary according to solveKey since multiple solvers can be working on the tree at different times.

  • DF, this depends on whether multiple solvers are using the same state machine (csmc) and the same tree? Suggest we solve this after consolidation and part of a separate issue (Simultaneous solvers use same CSMC / Tree? #673).

[dehann]

Hi, yes definitely need to consolidate both the belief messages as well as the channels over which the messages are sent in the Bayes tree CSM structures.

[dehann]

see edit comments in first post.

[Affie]

see discussion here #675 (comment)

[Affie]

To restate how I currently implement message storage:

• Messages are stored in the CSM container.
  • up, down, upinit, downinit, etc (separate for debugging)
  • This should allow a clique to be solved in isolation, with a little work needed to emulate the message passing on the channels if you want to debug those states, or we can just skip the wait for message states completely.
• Messages are communicated with channels associated with edges.
  • say you have tree with 3 cliques and 2 edges: 1 -> 2, 1 -> 3.
  • an up and down channel is created for each edge.
  • stored eg. upMsgChan{Edge,Channel}(Edge(1,2) => Channel{BeliefMessage}(0)

[Affie]

Messages are stored in the CSM container

The reason is messages are created at run time specific to the solve. If messages were to be stored in the clique, one would not be able to run 2 solves in parallel on the same tree (as currently implemented without a message solveKey). If that is even something we are interested in?

• DF, yes, multiple solves in parallel seems quite desirable and practical -- lets change accordingly (:resolve_mm1, :resolve_mm2 etc.).

[Affie]

@dehann, I updated the summary a bit. I think the biggest issue on the message is BallTreeDensity field vs val, bw arrays. I used the arrays from EasyMessage in parametric. As I understand you BallTreeDensity is the better way to go to save on conversions?

• DF, conversions are excess but note that calculating bw is by far the biggest cost -- so second best is if we have both val and bw that can be easily serialized and quickly rebuilt into a manikde. val only would require an internal recalc of bw which is not great for performance.

I missed that comment, I tried to find one message that could work for both and that could be easily serialized

• DF, should we just do val and bw so that we do one thing at a time and consolidate nonparametric with parametric. After consolidation we can change types again to try improve performance. Too much in one go is not good.

My original idea was to use inheritance to allow for different messages since I couldn't pack it in BallTreeDensisty. We can go back to the parametric type idea also.

• DF, In that case lets avoid inheritance to make the code simpler and just do val and bw.

---

DF EDIT:

• work for both parametric and nonparametric types,
• easy to serialize

[dehann]

I have a lot of catching up to do on this issue thread... in the mean time:

I have been thinking about BeliefMessage types also, will look more closely. I want to do best effort on BeliefMessage defintion and but then get to the meat of the tree message channels as fast possible, reduce the aperture there first. Belief messages are not the biggest computational part at this stage, so okay if its a little slower. I think its more important to get a common structure between the parametric and previous nonparametric CSM message passing. That way a fix for either results in a fix for both solving methods, hence the hit rate goes up. We can optimize stuff then.

[dehann]

Haven't forgotten -- this is high on my priority list

[dehann]

Slight change of tack here, this will be affected by #579 which will allow messages to encode the joint correlations beyond priors. So, lets resolve 579 first then consolidate the messages -- PoC on 579 is actually pretty easy.

[Affie]

Just to repeat it here. For #600 we will need additional information in the messages for covariances.

• DF, we added cobelief as the intermediate solution to store the partial joint for messages being passed between cliques on the tree. This will be renamed and better consolidated once this 459 issue is resolved. -- see specific issue Ensure clique message priors calculation captures multivariate correlations #577