[Design] possible refactor manellic tree and leaf kernels to mixture or nonparametrics

[dehann]

Description

History

Currently ManellicKernelDensity (MKD) relies on two collections of kernels, either .tree_ or .leaf_ kernels. The reason for this was to try save memory when large particle counts don't need to store full Gaussian kernel covariances as bandwidths for all the "nonparametric" points. So called "tree kernels" does however store full covariances so that we could have "hybrid-parametric".

Related

• Standardize [Packed]State DistributedFactorGraphs.jl#1188 (comment)
• https://github.com/JuliaRobotics/IncrementalInference.jl/blob/d98ce5744afa5cf57a7a[…]c6fdfc946c118439567/IncrementalInference/src/Factors/Mixture.jl

Design Question

Should

• HomotopyBelief rather have containers for "mixture kernels" and "bare nonparametric kernels"
  • Implication for (especially unbalanced trees) is that the depth boundary where "mixture kernels" transition to "bare nonparametric kernels" will vary for each branch in the belief tree -- and we'd need to track that somehow
  • Also, do we rebuild or serialize store this info.
    • DF, first instinct is to serialize this info and avoid rebuilding, since the build may be expensive while storing might just be a vector of indices.
• pick a naming convention, {mixture + twig} kernels vs {parametric + nonparametric} kernels.
  • Relates to heterogeneous kernel types decision [Design] Should HomotopyBelief support heterogeneous kernel types (aka be a mixture)? #326
  • Concern regarding confusion that parametric vs nonparametric kernels might be seen as either or, not parent-child relationship. mixture vs twig is more bespoke but also more clearly speaks to the problem being solved.

[dehann]

One way to achieve this is to use uniform bandwidth vs non-uniform. Basically "twig kernels" just don't store a bandwidth (eg covariance) at all, and is always calculated for the truly non-parametric twigs of the tree. A single "leaf bandwidth" could be shard for all "leaf kernels".

Remember, a tree can always consist of full mixture kernels all the way to the leaves, which would store a full covariance (if not required to switch over to twig kernels some depth down). This same depth represents the "hybrid" transition from parametric to non-parametric. EDIT above to choose a naming convention.

Trade-offs:

• intermediate twig ball node covariances would need to be recalculated every time, however, the hard part during construction is finding a bandwidth for leaves of a kernel density (this approach solves that problem).
• slight increase in complexity on tracking depth for transition from mixture to twig kernels.

[dehann]

Another aspect to consider is maybe a NamedTuple approach on heterogeneous types is reserved for DFG v1.x; if so, we can maybe get away with deferring at least the second half of this decision to post DFG v1.0.

In other words, design for sufficient performance heterogeneous kernels when used with only one or two kernels for now. Then worry about performance aspects during DFG v1.x.

A possible design solution for this is to index into a collection of vectors per type... Here is a first guess:

struct HomotopyBelief{SIZE,S,T}    # upgrade from MKD
  kernels::NamedTuple{S,T}            # (;gauss=[ker1, ker2, ker3,...]; twig=[bare1,bare2,...])
  # 2*SIZE, in the familiar format of binary tree kernel density
  indices::Vector{Tuple{Symbol,Int}}    # [(:gauss,3), (:gauss,1), (:gauss,2), #undef, (:bare,2), (:bare,1), (:bare,3),]
  # permute::___      # TBD the sorting permutation, if not already baked into indices
  ...
end

In this case (:gauss,3) is the root of the tree, with two modes (:gauss,1/2) which in turn have bare kernels hanging below. This allows for both mixture and non-parametric treatment.

TBD, properly tracking the parent child relationship which is usually done with binary tree indices field. (WIP)

• xref

  ApproxManifoldProducts.jl/src/entities/ManellicTree.jl

  Line 22 in 220c039

  permute::MVector{N, Int}

Refresher

In BallTrees (binary) with N data, when trying to lookup the root of the tree one would say tree.centers[tree.indices[1]] (old language). If you wanted the largest data value via sorted lookup tree.data[tree.indices[2N]] or equally for leaves tree.centers[tree.indices[2N]]. PS, depending on implementation, may also need to index through .permute

---

Discussion at _ helps motivate...

• [Design] possible refactor manellic tree and leaf kernels to mixture or nonparametrics #327

[Affie]

Maybe the balanced binary ball tree and the mixture tree should be kept separate. The ball tree can still be built from points for efficient non-parametric operations, while the mixture tree remains a semantic, possibly unbalanced structure encoding modes and kernels. One approach is to use a many-child mixture hierarchy and, once a satisfactory depth is reached, store multiple kernel points directly at the leaves (or sample a parametric leave node if it accurately describes the mode).
The old PPE.mean equivalent would be just a root mode for the mean with the N points as children.
For 3 modes the root node remains the mean, but this time there is 3 children (one for each mode) and each child has its kernel samples and bw.

[dehann]

Maybe the balanced binary ball tree and the mixture tree should be kept separate.

Do you intend separate fields in the same HomotopyBelief data structure, or do you mean to undo HomotopyBelief/Hybrid path and keep Mixtures completely separate from kernel densities?

The ball tree can still be built from points for efficient non-parametric operations

The whole point of HomotopyBelief is precisely to purposefully merge mixtures with non-parametrics. That is the path we should stay on. If I'm reading your text right, then you should stop compartmentalizing "non-parametric" as something other than what Manopt is doing -- yes there is some novelty here and that is a good thing. I can re-explain in a call if it is still not clear.

many-child mixture hierarchy
For 3 modes the root node remains the mean, but this time there is 3 children (one for each mode) and each child has its kernel samples and bw.

Binary trees are better for a number of reasons and can draw from existing art more easily. The performance loss with many child trees seem too negative at this stage. We should stick with binary.

once a satisfactory depth is reached

We need a name for this. So far I have been trying out "transition depth" or "where twigs start".

The old [single mode] PPE.mean equivalent would be just a [mean for the root node] with the N points as children.

Yes you're right, that is one of the reasons for going down this road.

Another aspect to consider is maybe a NamedTuple approach

So I take it you don't have specific objections to NamedTuple suggestion above.

A single "leaf bandwidth" could be shard for all "leaf kernels".

Along with this relatively hard decision to cut down on the size of HomotopyBelief objects. Again, this will allow for very large (old word) non-parametrics, but simultaneously support "mixture-only hierarchies" within the same structure -- just depends on how the user instantiates.

PS, it's likely that HomotopyBelief will be fully immutable. I haven't gotten as far as ensuring isbitstypes for all fields yet. Looking at that now...

[Affie]

I realize this issue is about manellic tree and I was thinking more about the data structure in DFG State. The core of what I was thinking is to not store the full tree, but the mixture above the transition depth and just the points (as with .val we had before) below the transition depth and rebuild that part of the binary tree when needed. So only store the mixture nodes above the "transition depth" and then points and bandwidths.

I can re-explain in a call if it is still not clear.

Sure, there are still some aspects I do not understand.

So I take it you don't have specific objections to NamedTuple suggestion above.

Not that I can think of, but I think there will still be a single unavoidable dynamic dispatch.