Last modified 7 months ago Last modified on 03/27/17 09:28:46

Modified Mon Mar 27 09:28:46 2017 by Eric.Woldridge.

Challenge Problem #4: Small Problems Collection


The goal of the “Small Problems Collection” is to create a set of problems that span important dimensions of the space of probabilistic programs in terms of both program formulation and probabilistic inference.

We hope that this set of problems can help the PPAML teams identify important tradeoffs in the design and implementation of Probabilistic Programming Systems. Note that this is an important change in direction from the previous focus on benchmarking of PPS systems.

Problem Overview

  • The following small problems are listed in this document.
  • Additional detail can be provided by contacting
  • Solution resources for Problems 4.1, 4.2, 4.3, 4.5, and 4.7 are available on Github.

“Textbook” Problems

  1. Bayesian linear regression
  2. Bayesian network for medical diagnosis
  3. Standard Hidden Markov Model

Non-parametric Bayes “Classic”

  1. Topic models with Hierarchical Dirichlet Process prior (Teh, Jordan, Beal & Blei, 2006)

Grammar Problem

  1. Given an infinite PCFG grammar 𝐺 and two strings 𝑥 and 𝑦, compute 𝑃(𝑥𝑦|𝑥). What is the probability that the grammar 𝐺 will generate the (complete) string 𝑥𝑦 given that it has generated the prefix 𝑥?

Social Network Inference

  1. Given an observed network and a model that mixes uniform attachment (UA) with preferential attachment (PA), infer the most likely mixture of UA and PA that would have generated the observed network
  1. Reasoning about homophily: Given a network of friendships and some observations (about smokers and non-smokers), predict the marginal probability of each person smoking

Signal Interpretation

  1. Given signals measured at an array of seismometers, determine the location and magnitude of each seismic event.

Recursive Reasoning about Other Agents

  1. Scalar Implicature: Decide what to say in order to cause the hearer to draw the most accurate conclusion about an uncertain event

Lifted Inference

  1. Solve a simple lifted inference problem.