Embedded Probabilistic Programming
in Rust

Modelling

• Human mind creates approximate models of world
  • How? No clue (._.')
• Science creates more precise approximate models of world
  • How? Math!
• Models specify structure, with open parameters
• E.g. Newton's law of gravity
  • Structure:
  • Parameter:

Probabilistic Modelling

• Don't try to model system exactly
• Treat it as a partially random process
• E.g. Coin flip
  • Don't try to predict singular throw (physics is hard)
  • Instead describe distribution of many throws
• Trade predictive power for tractability & generality
• → Bayesian statistics

Probabilistic Programming

• Usually:
  • Take simple distributions
  • Combine them in some simple way
  • Do efficient inference
  • E.g. Generalized linear models
• Instead:
  • Take simple distributions
  • Combine them in most general way: Programming
  • Do somewhat less efficient inference
  • ⇒ Probabilistic Programming

Probabilistic Programming (cont.)

• Take Turing-complete programming language
• Introduce probabilistic elements:
  • sample: Sample from distribution
  • observe: Observe value from distribution
• Develop general inference algorithm (the hard part)
• Generate samples from probabilistic program

Example

• Is the coin we are flipping a fair coin?
• I.e. What weight explains our observations the best?

#[prob]
fn coin(observations: Vec<bool>) -> f64 {
    let weight = sample!(uniform(0., 1.));
    for o in &observations {
        observe!(bernoulli(weight), o);
    }
    weight
}

• ⇒ Probabilistic program represents structured space of programs

Inference

• We have some probabilistic program
• How do we draw representative samples?
• Just run it?
  • Problem: How do we respect observe statements?
• Solution: Markov Chain Monte Carlo

Markov Chain Monte Carlo

• We want samples from a distribution
• But we can only calculate it's density
• First idea: Rejection Sampling
  • Propose random values, accept them with probability
  • Problem: Inefficient
• Better idea: Markov Chain Monte Carlo
  • Propose random values, but not independently
  • Accept them with just the right probability
  • Prefer high-probability regions in support of

Metropolis Hastings

• Take a simple proposal kernel
• Start at a random value
• Repeat:
  • Propose random new value:
     
  • Make it the next value,
    or don't, randomly
    • acceptance ratio

Trace Space

• We want samples from probabilistic program
• We can't calculate probability of return values
  • ⇒ We can't apply MCMC directly
• But we can calculate probability of a trace of
• Trace ⇔ deterministic instance of

#[prob]
fn flip() -> bool {
    sample!(bernoulli(0.5))
}

#[prob]
fn example10() -> f64 {
    let x = sample!(uniform(0., 10.));
    let y = if sample!(flip()) {
        sample!(normal(0., 1.))
    } else {
        sample!(uniform(-1., 1.))
    };
    x + y
}

MCMC in Trace Space

• Run to get initial random trace
• Repeat:
  • Vary slightly to get
  • Run with proposal trace to get probability of it
  • Accept as or don't, randomly
    • Omitting some tricky details here

Embedding into Rust

• Macros!
• #[prob] translates ordinary function into probabilistic program
  • Fn(Trace) → (Trace, f64, T) for type T of samples
  • Injects tracing scaffolding
• sample! & observe! read and modify trace
• Inference just normal higher-order function
• ⇒ Probabilistic programming in a crate

Conclusion

• Probabilistic programs are computationally general models
• Explore the trace space of probabilistic programs for inference
• Embed probabilistic programs with macros
• Challenge: General efficient inference algorithms
• Practice: Combine with machine learning methods
• Slides at: https://github.com/Garbaz/bachelor-thesis