# Variational Program Inference

Harik Shazeer Labs Google Research 444 Ramona 1600 Amphitheatre Pkwy.

Mountain View, CA 94043 Palo Alto, CA 94301 georges@gmail.com noam@google.com 

## Georges Harik Noam Shazeer Abstract

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 KLdivergence 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. 

## Problem Specification

Given partial observations of a complicated system governed by known or unknown probabilistic rules, we would like to automatically reason about the likely state of hidden parts of the system.

## Systems With Known Rules

We model our system as a program in a general purpose programming language. We call this the model program. We will be agnostic to what programming language we are using. We will only insist that it be deterministic except for a choose function which takes a probability distribution as an argument and returns a random choice from it. The model program thus defines a probability distribution P(x) over execution paths x. If over the course of an execution path x of the model program, the choose function is called n times with distributions (P1, P2 ... Pn) and the randomly chosen values are (c1, c2 .. cn) respectively, then the probability of that execution path is

## P(X) = ∏I Pi(Ci).

We are interested in the conditional expected value E(h(x)|e), where h is some function of the execution path, and e is some evidence such that we can easily compute P(e|x) for any x.

Our programming language needs to include constructs for specifying P(e|x) and h(x). The model program reports P(e|x) as the product of all calls to a function: 
evidence. This is a particularly convenient in that the evidence function can be passed boolean values which are interpreted as 0 or 1. For example, we could represent an observation that the grass is wet with the call evidence(grass_wet). If grass_wet is false, P(e|x) is multiplied by 0, and if grass_wet is false, P(e|x) is left unchanged. The value of the hypothesis h(x) is defined as the final value of a global variable *h*. We may not have a hypothesis, and may only be interested in sampling runs of the program given the evidence. In this case, *h* might not be set or used. Example 1: Three fair dice are rolled and it is observed that their sum is 7. What is the probability that the first die rolled was a 5? The following model program 
(shown in pseudocode) might encode that problem.

die1 := choose(uniform(1..6)) die2 := choose(uniform(1..6))
die3 := choose(uniform(1..6)) *h* := (die1 == 5)
evidence (die1 + die2 + die3 == 7)

## Modeling Systems With Unknown Rules

A system with unknown rules is in fact a special case of a system with known rules if we model the unknown rules as being randomly generated by known rules. 

In particular, we include in our model program a **random** 
program generator. A random program generator is a function which generates a random program and executes it. The exact code of the random program generator will depend on the programming language and our arbitrary choice of probability distribution. It turns out that our 