Definition of Turing Complete PPL

1

Hello everyone,

My task is to understand which probabilistic models can be defined using Edward. In the ICLR 2017 paper, it has been stated that Edward is a Turing Complete PPL. And the term is explained as “it supports any computable probability distribution”.[1]

Let’s make a categorization as follows,

1. Parametric

  • Directed Graphical Models

I think for Directed Graphical Models, one can specify a P(Child|Parents) from the set of parametric distributions (or you can write your own distribution) and selects the parametric distributions parameters as a function of its Parent Variables.

  • Undirected Graphical Models

In forum post [3], Dustin states that they have very limited support.
In forum post [4], Dustin mentions a method of sampling from an unnormalized distribution which I think may be related the undirected graphical models because the energy function is not normalized.

  • Models that Cannot be Represeated by Above Graphical Models

In [1], the authors state the existence of probabilistic programming languages which can even models that cannot be represented by Graphical Models.

2. Non-Parametric

It can model Bayesian Nonparametrics as stated in [2]. I think the example is the Gaussian Process.

Comments:

I have previously posted a similar question on Gitter chat but couldn’t get a response. What are your opinions?

  • I think for directed graphs if the distribution is not defined using an if statement, it can model any parametric conditional distribution.
  • For the undirected graphs, I haven’t seen an example and would appreciate it.
  • For the models that are not representable by graphs, I’m wondering what can be an example of such a model. If you can give an example I would appreciate it.

Thanks in advance, I think since in Tensorflow Probability one can define a model using Edward language this post can help the users of Tensorflow Probability to understand its limits too.

References:
[1] https://arxiv.org/abs/1701.03757
[2] http://edwardlib.org/api/model-compositionality
[3] Hierarchical CRF
[4] Generate samples from an unnormalized distribution