University of Oxford
Oxford, UK

# Maximum a Posteriori Estimation by Searchin Probabilistic Programs

## Preliminaries

### Probabilistic Program

• A program with random computations.
• Distributions are conditioned by observations'.
• Values of certain expressions are predicted'.
(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

• Continuously and infinitely generate a sequence of samples.
• Approximately compute integral of the form $\Phi=\int_{-\infty}^{\infty} \varphi(x)p(x) dx$
• Suggest most probable explanation (MPE) - most likely assignment to random variables. ✓

## References

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.

## Experiments

### Hidden Markov Model

• Dirichlet, discrete, and normal distributions.
• 16 hidden states.
• Unknown transition probabilities.

• A single run of BaMC on HMM.

### Probabilistic Deterministic Infinite Automata

• Dirichlet and categorical distributions.
• Trained on "Alice's Adventures in Wonderland.

## Acknowledgments

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)

• Inspired by MCTS.
• Maximizes log probability of the program trace.
• Converges much faster than simulated annealing.

## Distributions vs. Most Probable Explanation

### What we (most probably) need:

$$Gamma(1.04, 0.28)$$

## 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)$$

## Contributions

• Works with any combination of variable types.
• Does not require tuning of parameters.
• Simple to implement.

## Future Work

• Full analysis of algorithm properties and convergence.
• Application of open randomized probability matching to other inference algorithms.
• Marginal MAP through probabilistic inference.