Binary generation procedure

[marcoct]

Something like this, but where the two programs and their arguments have also been defined. The problem is that the constraint can't work as is because the value isn't available in the inference program trace yet. We want to be able to set up the pipes and then run the model program, which will trigger execution of the proposal program. It's almost as if they should just be combined into one program...

 37             tape = Tape()                                                                      
 38             slope_mu_num = GenNum(slope_mu, tape)                                              
 39             intercept_mu_num = GenNum(intercept_mu, tape)                                      
 40             inference_trace = DifferentiableTrace(tape)                                        
 41     
 42             # add contraints to model trace and set up pipes                                   
 43             model_trace = Trace()                                                              
 44             @in model_trace <= inference_trace begin                                           
 45                 for (i, y) in enumerate(ys)                                                    
 46                     @constrain("y$i", y)                                                       
 47                 end 
 48                 @constrain("slope" <= "slope") # a pipe
 49                 @constrain("intercept" <= "intercept")                                         
 50             end
 51     

[marcoct]

My current thinking is that before introducing any fancy syntactic sugars, there should be a generate function with roughly the following signature:

generate(p, p_args::Tuple, q, q_args::Tuple, ptrace::Trace, qtrace::Trace, mapping::Dict{String,String}) -> score::Real

where p and q are probabilistic programs / modules / generators of some form, and where mapping defines a mapping from names (addresses) in q to names in p. Then, generate proposes new values from q for those names in mapping, fills in the mapped names in ptrace with those new values (as constraints), and returns the difference in the scores (i.e. score(ptrace) - score(qtrace)).

This is related to the ability to request that a specific subproblem be scored, which although it can be expressed in the current syntax (by converting all other constraints to intervenes and only constraining the values in the subproblem), is not implemented efficiently without dependency tracking.

[marcoct]

Very interestingly, as I worked out a while ago when working on meta-inference MH, the binary regeneration procedure can probably handle non-independent proposals, which can be seen as an instance of regular independent MH when you think in the extended space that includes both the 'actual' and 'proposed' values as distinct choices. The non-independent proposal can then be represented as the following two step independent proposal on an extended state space:

1. sample from the proposal generating X' given X
2. propose swapping X' and X The details aren't exactly right, but this is written up somewhere in the meta-inference MH writeup.

[marcoct]

Also see http://probcomp.csail.mit.edu/papers/lua-thesis-2016.pdf

[marcoct]

Latest thinking:

  1 # SIR
  2 # precondition: model_trace has a hole in it
  3 # precondition: proposal_trace has a hole in it
  4 mapping = Dict("m" => "m", "r" => "r")
  5 proposal_score = generate(proposal, proposal_trace, values(mapping))
  6 copy(proposal_trace, model_trace, mapping) # constrains model_trace
  7 model_score = generate(model, model_trace, keys(mapping))
  8 
  9 # MH
 10 # precondition: model_trace has values for named choices
 11 # precondition: proposal_trace has a hole in it
 12 mapping = Dict("m" => "m", "r" => "r")
 13 prev_model_score = generate(model, model_trace, keys(mapping))
 14 copy(model_trace, proposal_trace, mapping # constraints model_trace
 15 prev_proposal_score = generate(proposal, proposal_trace, values(mapping))
 16 swap(model_trace, proposal_trace, mapping) # constraints both
 17 new_model_score = generate(model, model_trace, keys(mapping))
 18 new_proposal_score = generate(model, model_trace, values(mapping))

[marcoct]

I added a version of this feature at: https://github.com/probcomp/Gen.jl/commit/5f8de6d943dc490d79a55bb41f892d0c74dc0161

[marcoct]

As implemented the binary form of generate! currently only applies to two probabilistic programs because their traces use explicit addresses that can be mapped from one to another with a dictionary. Currently, a Generator{TraceType} can have an arbitrary TraceType (with the only requirement being a method score = generate!(generator, args, trace). It is not currently required for traces of general Generators to have a notion of addresses. Instead of a dictionary mapping keys to keys, the general mapping could be a mutation procedure synchronize!(trace_a::T, trace_b:U) that may be specialized to the two traces (or possible two such procedures).

[marcoct]

I wrote a binary generator combinator, called compose, in https://github.com/probcomp/Gen.jl/blob/20170713-marcoct-generators/src/generator.jl#L218-L289.

However, my current thinking is that this is a fairly 'shallow' form of combining two generators. There is definitely a need for a finer-grained binary combinator, which may only apply to two probabilistic programs (not two arbitrary Generators), which runs both programs in tandem, passing control flow from the model program to the proposal program and back again, at each tagged generator invocation.

This more fine-grained binary combinator for two probabilistic programs is important because we need proposals that interleave use of resimulation as well as external proposals. Simply writing a proposal program that has chunks that match the model program does not achieve the same thing, because the generators invoked in the proposal program may not be assessable---therefore the scores will be unecessarily noisy, because the knowledge that the fragment of the proposal distribution exactly matches the model program is not provided.

For example, I think that the following, if mu is sampled from a non-assessable generator something (i.e. an atomic generator with a noise estimate of its density), will result in noisy importance weights:

model = @program () begin
    mu = @g(something(), "mu")
    @g(normal(mu, 2.), "x")
end

sir = SIRGenerator(model, model, Dict(["mu" => ("mu", Float64)]))

Knowledge that two code fragments are the same is essential for scoring resimulations efficiently in the general setting. Explicitly running fragments of the model program is one particular way of implementing this knowledge. Transferring control between the two programs seems like it could be a particularly clean way of implementing this feature.

This came up because I am currently writing a generic SIR combinator (https://github.com/probcomp/Gen.jl/issues/67). I was experimenting with adding a feature to do re-simulation opaquely for certain choices opaquely, but this resulted in more code complexity, and difficult-to-reason-about requirements on the relationship between the resimulated and proposed random choices.

[marcoct]

When I pick this up later, I'll quickly prototype the interleaved execution combinator, and then collaborate with @axch on a refined design---the idea seems related to continuations and yielding, which are things @axch seems to know a lot about.