David Tolpin, Frank Wood
University of Oxford
Oxford, UK

Maximum a Posteriori Estimation by Search
in Probabilistic Programs


Probabilistic Program

(let [;; Model
      dist (sample (categorical 
                    [[normal 1/2]
                     [gamma 1/2]]))
      a (sample (gamma 1 1))
      b (sample (gamma 1 1))
      d (dist a b)]
    ;; Observations
    (observe d 1) (observe d 2)
    (observe d 4) (observe d 7)
    ;; Explanation
    (predict :d (type d))
    (predict :a a) (predict :b b)))

Inference Objectives


  1. Frank Wood, Jan Willem van de Meent, and Vikash Mansinghka. A new approach to probabilistic programming inference. In AISTATS-2014.
  2. Agrawal, S., and Goyal, N. 2012. Analysis of Thompson sampling for the multi-armed bandit problem. In Proc. of COLT-12.
  3. Bai, A.; Wu, F.; and Chen, X. 2013. Bayesian mixture modelling and inference based Thompson sampling in Monte- Carlo tree search. In Advances in Neural Information Processing Systems 26. 1646–1654.
  4. Shimony, S. E., and Charniak, E. 1991. A new algorithm for finding MAP assignments to belief networks. In Proc. of UAI ’90, 185–196.
  5. Kocsis, L., and Szepesvari, C. 2006. Bandit based Monte Carlo planning. In Proc. of ECML’06, 282–293.


Hidden Markov Model

Probabilistic Deterministic Infinite Automata


This material is based on research sponsored by DARPA through the U.S. Air Force Research Laboratory under Cooperative Agreement number FA8750-14-2-0004.

Bayesian Ascent Monte Carlo (BaMC)

Distributions vs. Most Probable Explanation

What we (most probably) need:

$$Gamma(1.04, 0.28)$$

What we get from inference:

Algorithm Outline

  1. For every random variable, keep reward beliefs for seen values.
  2. Using Thompson sampling (twice):
    • Guess reward distribution of a random value.
    • Select a value, either seen or randomly drawn.
  3. If the value is new, add it to the list of choices.
  4. After each run, back-propagate log-weight to reward beliefs.

Elementary Distributions

$$d \sim Discrete(1,5,2)$$

$$d \sim Poisson(5)$$

$$d \sim Normal(1,1)$$


Future Work