AbstractVarInfo: the representation
#5
Replies: 28 comments 16 replies
-
|
The "dictionary" data structure is what I suggested to implement and test in a separate package and just use here. I also think we need hierarchical keys not just a dictionary-like data structure. We should allow keys to be more complex than just indexing so long as there is a way to Regarding vectorisation or not, I think we kind of agreed in the last meeting to have a vectorised global data structure in case random variables come in as scalars. But where they come as a whole, we should keep their shape. Making this type stable requires using |
Beta Was this translation helpful? Give feedback.
-
|
The Trie data structure from Gen is interesting https://github.com/probcomp/Gen.jl/blob/master/src/trie.jl |
Beta Was this translation helpful? Give feedback.
-
|
@phipsgabler @devmotion linearization does not destroy information if you have a reference construction shape. This works even when primitive random variables have vector values. (this is deconstruction to array of a map from addresses to values, and then back again given an existing map from which we can extract the shape) |
Beta Was this translation helpful? Give feedback.
-
|
@mohamed82008 The trie structure is used because Gen treats model calls as first class - e.g. you internal nodes mark model calls, and leaf nodes mark primitive random choices. This has the effective of creating a hierarchical address space - e.g. (if we consider tuple addresses) You could also use a flat dictionary structure where the keys are tuples - but there are access and filtering penalties which are not optimal for implementing the core interfaces at model call site boundaries. |
Beta Was this translation helpful? Give feedback.
-
For me, the main pain points are not loss of information but that 1) linearization only works with samples that can be linearized (we would like to work with samples of arbitrary type) and 2) for many samplers linearization is not needed and creates additional overhead, also for developers. Currently reconstruction is still annoying though, e.g., for samples of different element types or for scalar samples - they can be distinguished from multivariate samples of dimension 1 only by dispatching on the distribution it was generated from. Handling these special cases when implementing samplers is pretty annoying but could possibly be handled with better abstractions in VarInfo. |
Beta Was this translation helpful? Give feedback.
-
This is why I want to start from the Trie and adapt it for our needs and for performance. Also makes it easy to use it in Gen in the future. |
Beta Was this translation helpful? Give feedback.
-
|
@devmotion I don’t quite understand the arbitrary samples but - do you mean arbitrary shaped samples ? If a primitive sample is any subtype of array, you should be able to flatten that and even reconstruct it correctly. If it’s a sort of structure - I think you’re correct in pointing out that that’s not supported yet. I wonder if a clever usage of Flux’s restructure is the right thing. |
Beta Was this translation helpful? Give feedback.
-
No, I mean samples that are not arrays but of arbitrary type, e.g., graphs, trees, text etc. Of course, I guess even for many of these other structures there exists some way to encode the information in an array - but probably it is quite unnatural and a simple reshaping operation is definitely not enough. BTW is the |
Beta Was this translation helpful? Give feedback.
-
|
A “choice” can come from any of the primitive distributions defined in the distributions section of Gen repo - so it can be anything (scalar, vector, even a custom structure if you define your own distribution using a DSL provided by the lib) |
Beta Was this translation helpful? Give feedback.
-
|
@devmotion I’m hopping on a call with @phipsgabler to chat about relationship of VarInfo stuff and Gen at 10:30 AM EST - if you want to join chat send email! |
Beta Was this translation helpful? Give feedback.
-
|
Thanks! Unfortunately, I won't be able to join (and I also won't make it to the Turing gathering tomorrow in case you plan to attend it), I'm busy with teaching duties. |
Beta Was this translation helpful? Give feedback.
-
|
FWIW this is the same reason we're adding nested named tuple support in Soss. Nested names tuple correspond to nested scope and allow models within other models. And we currently have |
Beta Was this translation helpful? Give feedback.
-
|
I thought proposing a trie would be more controversial ("dictionary" was just me speaking losely), but nice that it seems to be consensus already. |
Beta Was this translation helpful? Give feedback.
-
|
Yeah, nesting is pretty natural. Something like Accessors can be very useful here too: |
Beta Was this translation helpful? Give feedback.
-
|
It's a bit unfortunate that the trie implementation in DataStructures does not allow general keys. |
Beta Was this translation helpful? Give feedback.
-
|
You can find my WIP experiment with trie implementations for DynamicPPL and hopefully Soss and Gen here https://github.com/mohamed82008/TrieLab.jl. I am trying to be as generic as possible allowing for any key => value mapping data structure to be used as the underlying data structure for the trie, or for multiple of them to be mixed and matched. Such data structures include Dict, StaticDict, NamedTuple, Tuple, Array, StaticArray etc. The underlying data structure also determines whether the trie is mutable or not and whether it is static or not. It is still a WIP and I have a list of missing features at the bottom of every file so any help is appreciated. |
Beta Was this translation helpful? Give feedback.
-
|
The idea behind allowing arbitrary mappings is because I want to allow keys at every level to be as arbitrary as possible: symbols, numbers, ranges, integer vectors, strings, structs, etc. Different data structures allow different key types but not others. So it can make sense to use a NamedTuple at the top but a dictionary or array somewhere lower to use numeric, string or struct keys, or vice versa. Also for some (sub-)models, static immutable mappings can make more sense while for others, dynamic mutable ones can be more convenient and being able to nest them seamlessly is going to facilitate nesting Turing, Gen and Soss models if such a trie is adopted everywhere. That's the vision anyways. |
Beta Was this translation helpful? Give feedback.
-
|
❤️ Mohamed, you must have read my mind. |
Beta Was this translation helpful? Give feedback.
-
|
Probably it would be good to use it to generalize the implementation in DataStructures, as soon as it's reasonably stable. Ref: JuliaCollections/DataStructures.jl#220, JuliaCollections/Tries.jl#2 |
Beta Was this translation helpful? Give feedback.
-
|
@mohamed82008 it's interesting that you're allowing for more general keys. To this point I've focused on You can see my progress with this at Also, |
Beta Was this translation helpful? Give feedback.
-
|
Well the nice thing about allowing arbitrary mappings is that nested tuples from NestedTuples.jl are also allowed so there is no conflict between our works. I want to use Setfield/Accessors but I need an API that works fine for mutable and immutable structs alike. So something like a combination of BangBang.jl and Accessors.jl would probably be required. |
Beta Was this translation helpful? Give feedback.
-
|
I really like the idea of making abstracting things like this. Your static string code is a nice trick, too. If you need to lift more values to the type level, you might check out some of the helper functions in GeneralizedGenerated. Accessors is still in the early stages, so I'd think it could be possible to have the mutability option there directly. Do you see a reason to have it separated? I've also wondered about making a wrapper around named tuples to allow implementation of broadcasting, and maybe some other operations that would otherwise be type piracy. No rush on this at this point, but it seems interfacing with your API ought to be straightforward. |
Beta Was this translation helpful? Give feedback.
-
|
FYI: 95 % of this or so was about the representation design (tries etc.), all of which is a bit fluid for now. So I moved the original issue into a discussion were we can keep on, and have split off the part about the sampler-related interface design (previously the "VarInfo proper" subsection) into a separate discussion. |
Beta Was this translation helpful? Give feedback.
-
|
@phipsgabler It's been a while since I've thought about this, but I was recently talking to Oliver Shulz about his ValueShapes package: Just passing it along here in case it can help with these issues |
Beta Was this translation helpful? Give feedback.
-
|
Actually, lets split the discussion into separate topics, e.g. the trie representation, the interface for a trace, etc. Trie representation |
Beta Was this translation helpful? Give feedback.
-
|
❤️ You are really writing out things in the fashion I have been thinking about. Very nice, thanks! |
Beta Was this translation helpful? Give feedback.
-
|
Ad "distribution-equivalent but differently specified models": very good point, I have been thinking for some time about how to nicely refactor the current subsumption mechanism which I'm not quite happy with. This should IMHO be implemented on the level of Maybe there is a way to formalize the subsumption relations in some mathematical structure (semilattice, preorder, ...?). Also related: first paragraphs from here. |
Beta Was this translation helpful? Give feedback.
-
|
Is there a reason why we can't just replace If we then also implement |
Beta Was this translation helpful? Give feedback.
-
|
I had the same thought, but it seems suspiciously easy. E.g., wouldn't we want to constrain So I'm not at all thinking this is a bad idea, but on the other hand, lenses are really small to implement. |
Beta Was this translation helpful? Give feedback.
-
The current And after thinking about it a bit, |
Beta Was this translation helpful? Give feedback.
-
InterfaceCopy-pasted from start of discussion:
|
Beta Was this translation helpful? Give feedback.
-
|
IMO, this should be separate from the trie-representation. Nothing should stop us from defining a very simple |
Beta Was this translation helpful? Give feedback.
-
|
Since BangBang.jl-style updaters are already in use somwhere else in the infrastructure of Turing (AbstractMCMC, IIRC?), perhaps specifying the "mutating functions" in bangbang-style would be a good idea? This then wouldn't preclude immutable/persistent implementations. |
Beta Was this translation helpful? Give feedback.
-
|
I like that! |
Beta Was this translation helpful? Give feedback.
-
|
Just a general comment, the concreteness of some of the discussion here is pretty confusing. When we talk about "using Setfield" or "using Tries", or even "how VarNames are set up", are we really saying that the abstractions introduced in this library should support those as special cases, or that this abstract library will make some very concrete design decisions? |
Beta Was this translation helpful? Give feedback.
-
|
Yeah, I'm also aways on the edge here between "we in DPPL" and "we specifying the general interface"... for VarNames though, they are already here in |
Beta Was this translation helpful? Give feedback.
-
Now I'm really confused |
Beta Was this translation helpful? Give feedback.
-
|
Whops, that was a typo. They have been moved from DPPL to APPL. To many acronymes here :P Thinking about it once more: I assumed that 1. every library that supports the APPL interface needs to have some concept of "named variables" anyway, and 2. in order to define the interface, there needs to be some specification for them. Now, there is much less choices for varnames than for, say, VarInfo/traces, so Hong and I decided to move the VarName implementation here. They are, in a way, "downwards compatible" to plain symbols/nested named tuples, but add functionality like indexing which cannot be nicely represented by only symbols which exists nowhere else. So far for my defense. Do you think it is a bad idea to have their implementation here? I guess one thing that could be done is, as soon as we have implemented that lense idea, to only provide the "wrapper type" and leave the choice of concrete lenses to implementors. |
Beta Was this translation helpful? Give feedback.
-
|
Thanks @phipsgabler . So it's something like, APPL provides an interface that's met by some external packages like Setfield and Accessors, and also has a simple reference implementation? |
Beta Was this translation helpful? Give feedback.
-
|
I haven't really thought yet about that aspect, honestly. Defining VarNames only via an interface seems like an overkill to me, but perhaps that's untrue. I'd go for something like a "base implementation" in APPL (at least at the level of the current VarNames with names and multi-level indexing), which is extensible by other implementations (e.g. with hierarchical namespaces, properties, etc.). |
Beta Was this translation helpful? Give feedback.
-
|
I'm late to the party, I wonder which page are people on now. I'm currently facing a problem where I need to generate a Turing "model" based on data and a user config file. I already figured out what to do if I can use
|
Beta Was this translation helpful? Give feedback.
-
|
Maybe have a look at TuringGLM.jl, they do a similar thing. Of course it gets difficult if your model config has "dynamic structure", then I think you can only work via metaprogramming. As for the arguments, they have a similar problem: TuringLang/TuringGLM.jl#36. AbstractPPL is not really the right place to discuss this, though -- it's only about the interface above DynamicPPL. |
Beta Was this translation helpful? Give feedback.
-
There are many aspects that make
VarInfoa very complex data structure:(would an ordered dictionary be enough for that?). Second, keys are themselves hierarchical,
since they contain index values, and we need to be able to handle "sub-keys": get out, say,
x[1:3]from the entryx.be transformed between the distribution supports and Euclidean space. This is currently
implemented by special logic in some getters/setters, which automatically call
link/invlink.Correct me if I'm missing something.
Now, it seems to me that a sensible separation of concerns would involve a separate interface of the
dictionary part, taking care of the mappings and the "sub-key" handling. Then the actual
VarInfocan just wrap this special dictionary (or several thereof), and add the additional metadata and
special logic to it. Then different implementation of the dictionary essentially replace the
different kinds of
Metadatathat separateUntypedVarInfofromTypedVarInfo.I haven’t really worked with traits yet, but they might also have some advantages. For example, the
recently added
ThreadSafeVarInfois really only adding a thin layer to add an orthogonal conceptto the other variants.
DictionaryTrie InterfaceShould describe an ordered mapping from
VarNameto whatever: actual values (<:Realor<:AbstractArray{<:Real}?), distributions, flags, etc. – but only one such mapping at a time.iterate, yielding pairs ofVarNameand the stored valueIteratorEltype == HasEltype(),IteratorSize = HasLength()keys,values,pairs,lengthconsistent withiterateeltype,keytype,valuetypeget,getindex,haskeyfor indexing byVarNamemergeto join two VarInfospush!,merge!to add and join elementssetindex!empty!,delete!Array, orcopyto!.David has argued that linearized storage destroys shape information. I think that is does not need
to: one could have one big array, with reshaped views into it – scalars would then just be
zero-dimensional views (akin to
Refs). On the other hand, a tree-like implementation could have some other advantages, both with respect to ease of implementation and behaviour.Subsumption, the issue of matching "sub-keys", can behave in different ways depending on the value
type. For sampled values, using sub-keys should always work: when a value of a vector-of-vectors
xis stored, thenx[1][1]must be a valid key. However, this does not need to be the case fordistributions: when
Scomes from a matrix valued distribution, thenS[1,1]is not necessarilyavailable.
Some pain points from the current implementation: vectorized access, shape preservation, association
of names and values.
Related: Gen's
ChoiceMapRelated work/discussions
VarInfo/AbstractVarInfoAPI DynamicPPL.jl#68Beta Was this translation helpful? Give feedback.
All reactions