Variational Program Inference
  We introduce a framework for representing a variety of interesting problems
as inference over the execution of probabilistic model programs. We represent a
"solution" to such a problem as a guide program which runs alongside the model
program and influences the model program's random choices, leading the model
program to sample from a different distribution than from its priors. Ideally
the guide program influences the model program to sample from the posteriors
given the evidence. We show how the KL- divergence between the true posterior
distribution and the distribution induced by the guided model program can be
efficiently estimated (up to an additive constant) by sampling multiple
executions of the guided model program. In addition, we show how to use the
guide program as a proposal distribution in importance sampling to
statistically prove lower bounds on the probability of the evidence and on the
probability of a hypothesis and the evidence. We can use the quotient of these
two bounds as an estimate of the conditional probability of the hypothesis
given the evidence. We thus turn the inference problem into a heuristic search
for better guide programs.
