Using complex combinatorial structures

[pawel-czyz]

Sometimes a latent variable $X$ is a complex combinatorial structure, e.g., a graph or a phylogenetic tree, which has:

• a different prior distribution than usual variables (although it may be parametrized by other random variables),
• several associated distributions which allow sampling other random variables from $X$ (e.g., probability of observing a vector of different species under the phylogenetic tree),
• custom transition kernels/ways of suggesting new moves for Metropolis–Hastings MCMC (e.g., for the tree structures there are moves like "prune-and-reattach").

I know that Blang allows defining such combinatorial structures in Java and then they can be plugged to the SMC samplers. I wonder if could implement some random variables to have similar behaviour in PyMC.

I looked at the tutorial on implementing distributions and then at the documentation of the SymbolicRandomVariable, but I am not sure whether the existing solutions (based around PyTensor structures) can be used to manipulate complex combinatorial structures (which includes iterating over them using for loops and perhaps libraries like NetworkX or anytree).

I wonder whether you think it'd be feasible and, if yes, if it could make a nice PR to PyMC (or rather if it should stay in another repository).

Thank you for your time!

[ricardoV94]

Sampler

The sampling component may be conceptually related to RJMCMC, for which there was a PR started quite some time ago (the author is still interested but has been doing background work in the meantime): pymc-devs/pymc-experimental#20

There's also more foundational work being done right now that allows traces with dynamic sized variables, which our default trace doesn't allow:
#6517
#6510

You can also try to go the SMC route, but may need to tweak it to allow variable sizes, and likely implement a new kernel

Graph

If you can represent your RVs /logp with Pytensor variables, using advanced indexing or branching (via IfElse) and looping (via scan) routines, there shouldn't be any limitations. Otherwise we don't have any native tree types in PyTensor.

It's possible to add new types, but that would be considerably more work

---

The right place to explore this kind of stuff would be pymc-experimental first: https://github.com/pymc-devs/pymc-experimental

You are definitely welcome to try out a PR.

[pawel-czyz]

Thank you very much for your fast and comprehensive answer! While the trees can be kept in the memory as Pytensors, I've taken a look at implementing basic moves (as prune-and-reattach or swap-subtrees) with scan and it does not simple at all...
Looks like combinatorial structures are indeed too tricky to implement using existing structures, but I've been using PyMC for other models (with real or discrete variables) and it's been excellent – thanks for developing it!