Maximum a Posteriori Estimation by Search in 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

Frank Wood, Jan Willem van de Meent, and Vikash Mansinghka. A new approach to probabilistic programming inference. In AISTATS-2014.
Agrawal, S., and Goyal, N. 2012. Analysis of Thompson sampling for the multi-armed bandit problem. In Proc. of COLT-12.
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.
Shimony, S. E., and Charniak, E. 1991. A new algorithm for finding MAP assignments to belief networks. In Proc. of UAI ’90, 185–196.
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)$$

What we get from inference:

Algorithm Outline

For every random variable, keep reward beliefs for seen values.
Using Thompson sampling (twice):
- Guess reward distribution of a random value.
- Select a value, either seen or randomly drawn.
If the value is new, add it to the list of choices.
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.

Maximum a Posteriori Estimation by Searchin Probabilistic Programs