Introduction

Conceptually, logic programming provides a way to model non-determinism. This is accomplished by maintaining a set of answers that satisfy a set of logical constraints. A natural generalisation to this domain is adding a notion of uncertainty to this set of answers by associating with them a probability distribution.

But the conceptual simplicity of this sort of generalisation is not reflected in the complexity of many existing probabilistic logic programming systems. They often involve implementing sophisticated inference algorithms and the underlying systems are not just implemented on top of existing logic programming systems.

We believe that a conceptually simple extension deserves a conceptually simple implementation to go along with it. We thus contribute a simple way to extend microKanren, a small logic programming domain-specific language such that it becomes a probabilistic programming language.

Illustrated Example

To help explain how to use probKanren we introduce the following example:

PLP 2021 Envelope zinkov@robots.ox.ac.uk (R. Zinkov); webyrd@uab.edu (W. E. Byrd) GLOBE https://zinkov.com/ (R. Zinkov); http://webyrd.net/ (W. E. Byrd) ( r u n 1 0 0 0 ( q ) ( c o n j ( n o r m a l 0 3 q ) ( n o r m a l q 2 4 ) ) )

In the above program, we have a probabilistic model for the Gaussian unknown mean problem. We observe a value 4 from the 𝒩 (𝑞, 2) distribution, and that 𝑞 has a prior distribution of 𝒩 (0, 3). This probKanren program draws 1000 samples from a conditional normal distribution that represents the posterior probability distribution associated with 𝑞.

Related Work

There is a rich history of extending logic programming formalisms to support probabilistic inference. Early systems like PRISM [1] and ProbLog [2] allowed associating discrete distributions with facts. Early versions of ProbLog were also built on top of Prolog, matching one of the goals of our work. Later work [3] introduces distribution clauses so that some continuous distributions like Gaussians can be represented. Other work extended these methods further while focusing on efficient exact inference algorithms like weighted model integration [4,5]. Our work is most similar to [6], except that while they combine their forward reasoning with an importance sampler we use a particle cascade instead which can be more sample efficient.

Background

microKanren

microKanren [7,8] is a pure logic programming language embedded in Scheme. The language consists of a set of terms, a set of goal primitives, and two run forms that turn goal queries into a set of answers. The goal primitives consist of a f r e s h form for introducing logic variables, a unification primitive = = , a conjunction combinator c o n j , a disjunction combinator d i s j , and ways to define and apply relations. Further forms are shown in detail in Figure 1.

Goal expressions represent a possibly backtracking search procedure. These goals all take as input some state and output a stream of possible output states. We run these goals by starting with an initial state that holds an empty substitution dictionary, and passing it into the top-level goal expression which then passes it recursively down to sub-expressions. Encountering f r e s h extends the lexical environment with a binding between a lexical variable and a logic variable; c o n j will apply the first goal to the state passed in, and then apply the second goal to the states associated with each resulting stream from the first goal and finally unify the results; d i s j will apply both goals to the same input state and concatenate the resulting streams; and = = unifies its arguments in the context of the current state, discarding any streams which fail to unify.

To handle goal expressions that might diverge, the streams are expanded in an interleaving[9] fashion, giving each branch a chance to produce answers. This interleaving search is sound and complete [10].

Grammar and Definitions

To create probKanren, we extend this grammar with distribution clauses such as n o r m a l and b e r n . Distribution clauses take as arguments the parameters of the distribution and a last argument representing a draw from that distribution. For example, ( n o r m a l 0 1 x ) means x represents a draw from the 𝒩 (0, 1) distribution. These are just another type of goal expression. We do not need to add a notion of probabilistic variables to the language grammar, as they can treated as logic variables constrained in a particular way. The semantics of the language though does change from an answer set to a probability distribution on that answer set.

We follow the semantics of [11], this is a denotational semantics where each language form is associated with a measurable function, and an operational semantics of a sampler.

Probabilistic Programming

Probabilistic Programming Languages [12,13] are a family of domain-specific languages for posing and efficiently solving probabilistic modelling problems. At their core, all have a way to s a m p l e and o b s e r v e data under a probability distribution or Markov kernel.

There are many inference algorithms for probabilistic programming languages, but methods based on likelihood-weighting and Sequential Monte Carlo algorithms are the simplest to implement.

Sequential Monte Carlo

Sequential Monte Carlo [14](SMC) is an efficient online way to sample from probabilistic models, which is especially suited for state-space domains. If we imagine our probabilistic programs as straight-line programs with no control-flow we can imagine numbering every sample function 𝑓 1 , 𝑓 2 , … , 𝑓 𝑛 and every observe function 𝑔 1 , 𝑔 2 , … , 𝑔 𝑛 then our probability density over our latent variables 𝑥 0∶𝑇 and observed data 𝑦 0∶𝑇 can be defined as:

𝑝(𝑥 0∶𝑇 , 𝑦 0∶𝑇 ) = 𝑝(𝑥 0 ) 𝑇 ∏ 𝑡=1 𝑓 𝑡 (𝑥 𝑡 | 𝑥 𝑡−1 ) 𝑇 ∏ 𝑡=0 𝑔 𝑡 (𝑦 𝑡 | 𝑥 𝑡 )(1)

Sequential Importance Sampling

The simplest way to sample from our target distribution 𝑝(𝑥 0∶𝑇 | 𝑦 0∶𝑇 ) is to sample from a sequence of intermediary distributions 𝑝(𝑥 0∶𝑡 | 𝑦 0∶𝑡 ) where 𝑡 goes from 1 to 𝑇. We do this by sampling a population of 𝑁 particles {𝑥 Thanks to the recurrence relation:

𝑝(𝑥 0∶𝑡 | 𝑦 0∶𝑡 ) = 𝑝(𝑥 0∶𝑡−1 | 𝑦 0∶𝑡−1 ) 𝑓 𝑡 (𝑥 𝑡 | 𝑥 𝑡−1 )𝑔 𝑡 (𝑦 𝑡 | 𝑥 𝑡 ) 𝑝(𝑦 𝑡 | 𝑦 0∶𝑡−1 )(2)

we know in 𝑇 rounds we compute the desired distribution as follows:

Initialise with:

𝑥 (𝑖) 0 ∼ 𝑝(𝑥 0 )(3)𝑤 (𝑖) 0 = 1/𝑁(4)

Then for 𝑡 from 1 to 𝑇 𝑥

(𝑖) 𝑡 ∼ 𝑞(𝑥 𝑡 | 𝑥 (𝑖) 0∶𝑡−1 )(5)𝑤 (𝑖) 𝑡 ∝ 𝑤 (𝑖) 𝑡−1 𝑓 (𝑥 (𝑖) 𝑡 | 𝑥 (𝑖) 𝑡−1 )𝑔(𝑦 𝑡 | 𝑥 (𝑖) 𝑡 ) 𝑞(𝑥 (𝑖) 𝑡 | 𝑥 (𝑖) 0∶𝑡−1 ) (6) We get the best results if 𝑞(𝑥 𝑡 | 𝑥 0∶𝑡−1 ) is equal to 𝑝(𝑥 𝑡 | 𝑥 0∶𝑡−1 , 𝑦 0∶𝑡 ).

Sequential Importance Resampling

Unfortunately, over time SIS is likely to lead to most of the importance weight in a small fraction of the particles, with the rest of the particles having negligible weight. This is usually called weight degeneracy. We address this sample efficiency issue in the standard way by replicating the particles with high weight and dropping the ones with low weight. This is called a resampling step, and it happens after each round. Resampling effectively removes particles with low weight and duplicates particles with higher weight by sampling with replacement our existing particles.

𝑎 (𝑖) 𝑡 ∼ 𝑟(𝑤 (1∶𝑁 ) 𝑡−1 ) 𝑥 (𝑖) 𝑡 ∼ 𝑞(𝑥 𝑡 | 𝑥 (𝑎 (𝑖) 𝑡 ) 0∶𝑡−1 ) 𝑤 (𝑖) 𝑡 ∝ 𝑤 (𝑖) 𝑡−1 𝑓 (𝑥 (𝑖) 𝑡 | 𝑥 (𝑖) 𝑡−1 )𝑔(𝑦 𝑡 | 𝑥 (𝑖) 𝑡 ) 𝑞(𝑥 (𝑖) 𝑡 | 𝑥 (𝑖) 0∶𝑡−1 )

For each particle 𝑖, resampling tells us which of the existing particles 𝑎 𝑖 will be its ancestor. We set 𝑟(𝑤) = Categorical(𝑤), which is called multinomial resampling but there are other methods as well [15].

Particle Cascade

Unfortunately, SMC as defined here requires having access to all the particles at every step in the process. This conflicts with the functional nature of our implementation. Instead we make use of Particle Cascades [16], removing this barrier allowing every particle to be resampled asynchronously with the associated weights being relative to a global running average.

Proposed Method

We propose to extend microKanren by turning the search into an SMC sampler. We accomplish this by augmenting each of the search streams with a set of particles. These particles represent the empirical distribution of that stream. Each particle has associated with it a substitution of all the logic and random variables as well as a weight that is proportional to the likelihood of the substitution.

We follow [3] and place the following restrictions on our distribution clauses and the random variables they specify.

Firstly, the arguments of distribution clauses must be grounded. Secondly, a random variable cannot unify with any arithmetic expression.

An initial set of particles is created from the probabilistic program when it is first run. When encountering primitives such as n o r m a l we first check if all the parameter terms are grounded and then if the last argument is fresh, we sample a value for it for each particle and then add this sampled value along with the associated logic variable to the substitution associated with that particle. If all the terms are ground, we treat the primitive like an observation statement and multiply the weights of each substitution with the likelihood of the observation.

As conjunctions (conj) are encountered, all particles in all output streams from the first goal become part of the initial states that are each passed to the second goal.

As disjunctions (disj) are encountered, we split evenly the number of particles allocated to each stream. Whenever we encounter a unification primitive, we run a resampling step. This helps to prune particles with low weight and replicate particles with high weight.

As an optimisation, we may create more particles during resampling based on a globally stored counter of the effective sample size of all particles across all streams. This extension does not modify the search and streams are managed exactly as in microKanren. An additional advantage, due to the microKanren search being complete, we are guaranteed to recover the true posterior as all paths of the search space will eventually be explored given enough particles.

Experiments

We validate that probKanren is at least as expressive as other probabilistic logic programming languages by implementing the Friends who Smoke model.

Friends who Smoke is a probabilistic logic program which models the social nature of who smokes cigarettes. The model predicts that people who are friends with people who smoke are more likely to smoke. We replicate the example on https://dtai.cs.kuleuven.be/problog/ tutorial/basic/05_smokers.html using 2000 particles and get an empirical distribution that seems to match up with the discrete distribution returned from ProbLog.

Conclusions

We made a simple-to-implement extension to microKanren that lets us support probabilistic inference on both discrete and continuous distributions. The approach does not require modifying the underlying search algorithm or touching any of the backtracking code and comes with a theoretical guarantee that if the underlying search is complete then the probabilistic extension will recover the true posterior given enough particles.