Conditional independence by typing
  A central goal of probabilistic programming languages (PPLs) is to separate
modelling from inference. However, this goal is hard to achieve in practice.
Users are often forced to re-write their models in order to improve efficiency
of inference or meet restrictions imposed by the PPL. Conditional independence
(CI) relationships among parameters are a crucial aspect of probabilistic
models that capture a qualitative summary of the specified model and can
facilitate more efficient inference. We present an information flow type system
for probabilistic programming that captures conditional independence (CI)
relationships, and show that, for a well-typed program in our system, the
distribution it implements is guaranteed to have certain CI-relationships.
Further, by using type inference, we can statically deduce which CI-properties
are present in a specified model. As a practical application, we consider the
problem of how to perform inference on models with mixed discrete and
continuous parameters. Inference on such models is challenging in many existing
PPLs, but can be improved through a workaround, where the discrete parameters
are used implicitly, at the expense of manual model re-writing. We present a
source-to-source semantics-preserving transformation, which uses our CI-type
system to automate this workaround by eliminating the discrete parameters from
a probabilistic program. The resulting program can be seen as a hybrid
inference algorithm on the original program, where continuous parameters can be
drawn using efficient gradient-based inference methods, while the discrete
parameters are inferred using variable elimination. We implement our CI-type
system and its example application in SlicStan: a compositional variant of
Stan.
