The design of a general probabilistic programming system involves a balancing act between two deeply conflicting concerns. On the one hand, the system should provide as uniform and flexible an interface for specifying models as possible; on the other, it should be capable of doing efficient inference for any particular model specified. Current systems lie somewhere on a spectrum that ranges from highly expressive languages such as Church, Anglican, and Venture, to highly performant languages like Figaro, FACTORIE, and Infer.NET. It has not yet been shown possible to optimise both these concerns simultaneously.
To improve on this predicament we consider the class of discrete graphical models, for which various efficient exact inference algorithms exist. We present a technique for determining when an Anglican program expresses such a model, which allows us to achieve a substantial increase in inference performance in this case. Our approach can handle complicated language features including higher-order functions, bounded recursion, and data structures, which means that, for the discrete subset of Anglican, we do not incur any loss in expressiveness. Moreover, the resulting inference is exact, which can be useful in contexts where very high accuracy is required, or for doing nested inference inside larger models.
Extended abstract: Efficient exact inference in discrete Anglican programs
Authors: Robert Cornish, Frank Wood, Hongseok Yang