A General Importance Sampling Algorithm for Probabilistic Programs

Abstract

Highly expressive probabilistic modeling languages are capable of describing a wide variety of models. Some of these models are quite complex, so approximate inference algorithms are needed. One approach to approximate inference is importance sampling, but this can be hard to do in expressive languages because of the many deterministic relationships between concepts. This paper presents an importance sampling algorithm for the IBAL language based on the principle of using the structure of a model to infer as much as possible about a decision before making a commitment. The paper demonstrates using a musical example how easy it is to encode interesting new models in IBAL. Results show that the importance sampling algorithm is able to make useful inferences, and is far superior to a rejection sampling algorithm. The paper presents proof of concept on the musical example that the algorithm is capable of handling real applications.