Syntactic Requirements for Well-defined Hybrid Probabilistic Logic Programs

The power and expressivity of Probabilistic Logic Programming (PLP) [9, 19] have been utilized to represent many real world situations [3, 10, 15]. Usually, probabilistic logic programs involve only discrete random variables with Bernoulli or Categorical distributions. Numerous solutions emerged to also handle continuous distributions [11, 13, 26], increasing the expressiveness of PLP and giving birth to hybrid probabilistic logic programs, that is, programs that include discrete and continuous random variables. Inference in this type of programs is hard since it combines the complexity of the grounding computation with the intractability of a distribution defined by a mixture of random variables.

Usually, inference in general hybrid probabilistic logic programs (i.e., without imposing restrictions on the type of distributions allowed) is done by leveraging knowledge compilation and using external solvers [26] or by sampling [5, 17].

The semantics of hybrid programs has been proved well-defined in [4], but the authors neither provided an explicit syntax, nor introduced explicit syntactic requirements. In this paper, we close this gap by introducing an explicit syntax and the syntactic requirements needed to preserve the well-definedness of the semantics of hybrid probabilistic logic programs.

The paper is structured as follows: in Section 2 we introduce the semantics and the syntax for programs with only discrete random variables with both finite and infinite number of explanations. The semantics and syntax for hybrid programs is introduced in Section 3, and the syntactic requirements are analysed in Section 4. Section 5 concludes the paper. All the Sections are accompanied by several examples, to make the concepts clearer.

Probabilistic Logic Programming (PLP) allows the construction of complex yet interpretable probability models through the usage of Logic Programming. Several probabilistic logic languages based on the Distribution Semantics (DS) [22] have been proposed during the years, such as PRISM [22], and ProbLog [10]. Basically, they allow the definition of probabilistic facts, i.e., facts that can be true or false with a certain probability.

Following the ProbLog syntax [10], each probabilistic fact has the form $p::a$ where $p\in]0,1]$, meaning that $a$ is true with probability $p$ and false with probability $1-p$. If $p=1$, the fact is deterministic. An atomic choice indicates whether a grounding $a\theta$ of a probabilistic fact $p::a$ is selected or not, and it is represented with the triple $(a,\theta,k)$. $k\in\{0,1\}$, where $k=1$ means that the fact is selected and $k=0$ that it is not. If a set of atomic choices does not contain two atomic choices in which the fact is both selected and not, it is termed consistent. A consistent set $\kappa$ of atomic choices is called composite choice and its probability can be computed as:

A total composite choice contains one atomic choice for every grounding of every probabilistic fact. A world is a logic program identified by a total composite choice, and it is created by selecting the atoms corresponding to each atomic choice with $k=1$. Its probability is given by the probability of the total composite choice. Here we consider only programs where every world has a two-valued Well-Founded Model (WFM). A semantics for programs without a two-valued WFM [23] based on credal sets is discussed in [8]. If a program does not contain function symbols, the set of groundings for every probabilistic fact is finite, and so the set of worlds for a program is finite.

Example 1 illustrates a program without function symbols. If a program has at least one variable, one constant, and one function symbol, its grounding is infinite, so the previous definition must be extended [16].

The set of worlds $\omega_{\kappa}$ compatible with a composite choice $\kappa$ is defined as $\omega_{\kappa}=\{w_{\sigma}\in W_{P}\mid\kappa\subseteq\sigma\}$, where $W_{P}$ is the set of worlds for the whole probabilistic logic program, $\sigma$ is a total composite choice, and $w_{\sigma}$ is the world identified by the total choice. If the program does not have function symbols, the probability of a composite choice is equal to the sum of the probabilities of the worlds in $\omega_{\kappa}$. If the program has function symbols, $\omega_{\kappa}$ may be uncountable and the probability of each world is 0 (infinite product of values $\in]0,1[$). However, the probability of a composite choice can still be computed. The set of worlds compatible with a set of composite choices $K$ is given by the union of the worlds identified by each composite choice in the set. Two composite choices are incompatible if their union is not consistent. A set of composite choices is pairwise incompatible if every pair of different composite choices is incompatible. $P(K)$ is still well-defined for programs with function symbols and can be computed by constructing pairwise incompatible equivalent sets. A composite choice $\kappa$ is an explanation for a query $q$ (a conjunction of ground atoms) if, for all worlds $w\in\omega_{\kappa}$, $w\models q$. Furthermore, a set of composite choices is covering with respect to a query $q$ if $\forall w$ in which $q$ is true, $w\in\omega_{\kappa}$. We can also define as explanation a set of worlds and define the covering property for sets of worlds. The probability of a query $q$ is then computed by defining a probability measure over the set of worlds identified by countable sets of countable composite choices: $\mu_{P}(\omega_{K})=\lim_{n\to\infty}\mu(K^{{}^{\prime}}_{n})$, where $K^{{}^{\prime}}_{n}=\{\kappa^{{}^{\prime}}_{1},\dots,\kappa^{{}^{\prime}}_{n}\}$ is a pairwise incompatible set of composite choices equivalent to $K_{n}=\{\kappa_{1},\dots,\kappa_{n}\}$, $K=\{\kappa_{1},\kappa_{2},\dots\}$ is a covering set of explanations for $q$ and $\mu_{P}(K_{n})=\sum_{i=1}^{n}P(\kappa^{\prime}_{i})$. Programs with function symbols have a well-defined semantics [18].

If a probabilistic logic program is range restricted, i.e., every variable in the head appears also in a positive literal in the body, the answers of a query are always ground instantiations of it [14, 21], and probabilities are always assigned to ground atoms. However, in some cases, probabilistic facts may not be range restricted, and can contain variables (see, for instance, the probabilistic facts spades/1 and clubs/1 in Example 1). In this situation, queries’ answers are still ground instantiations and the program can be well-defined provided that the variables in probabilistic facts are ground when the fact is called: they can be directly bound to a constant (as in Example 1, where X is bound to 0), or they must appear in a previous literal in the body.

Before illustrating the proof, we introduce some basic concepts following [14]. Given two atoms, $a$ and $b$, a substitution $\theta$ (a replacement of variables with terms) is a unifier for $a$ and $b$ if $a\theta=b\theta$. A substitution is a grounding if all the involved terms are ground. Furthermore, a unifier $\sigma$ is the most general unifier (mgu) for $a$ and $b$ if, for all unifiers $\mu$ of both $a$ and $b$, exists a substitution $\rho$ such that ($a\sigma)\rho=a\mu$.

The main step of resolution is the following: given two clauses $A$ and $B$ with no common variables, $l\in A$ and $\neg l^{\prime}\in B$, and $\theta$ being the mgu of $l$ and $l^{\prime}$, the resolvent of $A$ and $B$ is defined as $((A\setminus\{l\})\cup(B\setminus\{l^{\prime}\}))\theta$; for a program $P$ and a query $q$, resolution is linear when $B$ represents only clauses in $P$ and $A$ is the query or the resolvent of another linear resolution. We suppose that literals in clauses are ordered and are chosen following this order during the resolution. A resolution proof for SLDNF can be represented as a sequence of clauses $\langle q,C_{1},C_{2},\dots,C_{n}\rangle$. If $C_{n}$ is the empty clause, the proof is a refutation. The substitution for the query $q$ is given by $\theta=\theta_{1}\theta_{2}\dots\theta_{n}$, where each $\theta_{i}$ is the substitution correspondent to clause $C_{i}$. Moreover, if $P$ is range restricted, $\theta$ is a grounding.

If variables appear for the first time in probabilistic facts, the query could still eventually be ground, but probabilistic facts will not be ground when called, and thus the semantics will be ill-defined.

Let us now extend Example 1 by introducing new clauses to obtain a program with an infinite covering set of explanations.

In the next section we introduce the syntax for hybrid probabilistic logic programs, i.e., programs with both discrete and continuous random variables.

When a probabilistic logic program contains both discrete and continuous random variables, it is called hybrid probabilistic logic program. Here, we also consider constraints involving continuous random variables’ values, obtaining probabilistic constraint logic programs [4, 13]. In this paper we use hybrid probabilistic logic program and probabilistic constraint logic program interchangeably, since usually in PLP the goal is to compute the probability of a query (and thus we always have constraints to define the range of the continuous random variables), rather than the joint probability density induced by the program.

A probabilistic constraint logic program is composed of a set of rules, a set of Boolean probabilistic facts, and a countable set of continuous random variables. The authors in [4] define $X=\{X_{1},X_{2},\dots\}$ the countable set of continuous random variables, each one associated with its range (that can be either $\mathbb{R}$ or $\mathbb{R}^{n}$), and $F$ the set containing discrete probabilistic facts. These discrete facts form a countable set of Boolean random variables $Y=\{Y_{1},Y_{2},\dots\}$. The sample space of the whole program ($W_{\mathcal{P}}$) is defined as the product of the spaces for continuous ($W_{X}$) and discrete ($W_{Y}$) random variables, i.e, $W_{\mathcal{P}}=W_{X}\times W_{Y}$.

The probabilistic facts associated with every random variable $Y_{i}$ set to 1, and the grounding of the rules (with the constraints removed) whose constraints are satisfied given a valuation of the continuous random variables, define a ground normal logic program. The probability of a query can be computed by considering a pairwise incompatible covering set of explanations. As before, an explanation for a query of a probabilistic constraint logic program is a set of worlds $\omega_{i}$ such that the query is true in every element of this set.

A concrete syntax for this type of programs is given by cplint hybrid programs [19]. In cplint hybrid programs, logical variables are partitioned into two disjoint sets: those that can assume terms as values and those that can assume continuous values. Let us call the first term variables and the latter continuous variables.

Continuous random variables are encoded with probabilistic facts of the form

where $A$ is an atom with a continuous variable $Var$ as argument and $Density$ is a special atom identifying a probability density on variable $Var$. For example,

p(X) : gaussian(X,0,1).

indicates that X in atom p(X) is a continuous variable that follows a Gaussian distribution with mean 0 and variance 1. Each predicate $p/n$ has a signature that specifies which arguments hold continuous values. Only these arguments can contain continuous variables. Continuous values (and variables) can appear inside a term built on a function symbol $f/n$. Each function symbol $f/n$ also has a signature that specifies which arguments hold continuous values. Again, only these arguments can contain continuous variables. While discrete random variables are identified by ground atoms (that form a countable set), continuous random variables are identified by predicates and by the ground terms present in atoms with arguments that can hold continuous random variables.

ProbLog probabilistic facts of the form $p::f$ can also be encoded as $f:p$ for uniformity with Logic Programs with Annotated Disjunctions [25] and CP-Logic [24].

Atoms in clauses and probabilistic facts can have both term and continuous variables. However, we impose the constraint that in every world of the program the values taken by term variables in a ground atom for a predicate $p/n$ that is true in the world uniquely determine the values taken by the continuous variables.

Continuous variables are introduced by probabilistic facts for continuous random variables and by the special predicate =:=/2 that is used to define a new variable based on a formula involving existing continuous variables (see Example 5). Constraints are represented by Prolog comparison predicates. The semantics assigns a probability of being true to any ground atom not having continuous values as arguments. Atoms with continuous values have probability 0, as the probability that a continuous random variable takes a specific value is 0. However, there is one special case when a continuous value is admitted as an argument. This will be discussed in Section 4.

Inference in cplint hybrid programs can be performed using MCINTYRE [2, 5, 20], an algorithm based on Monte Carlo sampling. cplint hybrid programs can also be translated into probabilistic constraint logic programs [13] by removing the continuous variables from the arguments of predicates and by replacing constraints with their probabilistic constraint logic program form.

Consider an extension to Example 2, where we also add a continuous random variable and clauses with constraints.

In the next Section, we illustrate more in detail the syntactic requirements that hybrid probabilistic logic programs, and thus probabilistic constraint logic programs, must follow to have a well-defined semantics.

To preserve the well-definedness, we require that the set of random variables must be countable. That is, every random variable must be associated with a ground logical atom. The discrete arguments of this logical atom can contain terms and cannot be real values. Let us now analyse several possible situations.

In the fourth clause of Example 3, (reported here for clarity)

pick(0,spades) :- spades(0), angle(0,V), V > 3.14.

the first argument of the continuous random variable angle is a constant. Similarly happens with the clauses with angle(s(X),V). Variable X appears in the head, so it is ground when angle(s(X),V) is called (during the recursion or by directly set a value for X in the query), and the continuous random variable V is associated with term s(X) by predicate angle/2. In both cases, s(X) is a ground logical term (integer in case of 0), so the semantics is well-defined.

Consider now Example 4: in this program there are two random variables, identified respectively by g(X) and h(X). Predicate mix/1 is composed of two clauses with the same head but different bodies, a situation that may lead to an ill-defined program where both clauses are true and the random variable X is defined by two different distributions. However, the two bodies are mutually exclusive: the discrete random variable h is used to discriminate between the two. When h is true, heads is true, and thus the first clause of mix/1 is considered. When it is false, the second mix/1 clause is considered. This mutual exclusivity guarantees the well-definedness of the program. Algorithmically, this property can be verified performing clause unfolding, obtaining two clauses with the same head with bodies mutually exclusive, since they contain at least one atom in common, but in one it is positive, in the other it is negated. The same happens for Example 5. This idea can be extended to the case where there are $n$ clauses with the same head defining $n$ different distributions for the same variable, provided that all the clauses are mutually exclusive.

To see a counterexample, if we modify the clauses for predicate mix/1 of Example 4 in this way:

mix(X) :- g(X).
mix(X) :- h(X).

the program is ill-defined, since the two clauses are not mutually exclusive, and there is not a single distribution for variable X.

Focus now on Example 6. Here, atom value/3 has a continuous random variable (M) as input. To keep the well-definedness, this input must be defined in another continuous probabilistic fact and must be used only as a parameter for another distribution. In fact, M is obtained from a Gaussian distribution and it is used as a parameter for the mean for another Gaussian distribution. In this way, variables M and X are specified by a joint density. Note that the first variable of value/3 is a term variable and can be associated with a ground atom (integer, for example), preserving the well-definedness: the value of the term variable uniquely identifies the value of the continuous random variable. In this way, the position in the sequence of random variables is exactly identified.

This situation can be straightforwardly extended to programs in which there are multiple continuous random variables as input: for instance, in Example 6, the variance for X in clause value/3 can be sampled from another distribution instead of being fixed to 2.

In other cases, when the value of a continuous random variable is used as variable for another term, but not as a parameter for a distribution, the semantics is ill-defined. Consider the following modification to Example 6:

value(X) : gaussian(X,1,5).
value(_,M) : gaussian(M,2,2).
res(M) :- value(X), value(X,M).

Here, X in clause res/1 is the value of a continuous random variable but it is not used as parameter for the distribution of M. The continuous random variable M cannot be associated with a term that uniquely identifies it, so the program is ill-defined. The difference with Example 6 is that in Example 6 the term variable used as index (I) can be associated with a ground logical term, while here it is associated with a real value (X). If in this last example the variable X is a discrete random variable rather than a continuous one, the program would be well-defined, since X is associated with a ground logical atom.

To see how to compute the probability in this situation, consider the following simple program (a simplification of Example 6, where Gaussian distribution are replaced by Uniform distributions identified by uniform_dens/3):

Here, the variable X in angle_b/1 follows a uniform distribution between 0 and 1. For variable Y in angle_a/1, its lower bound is sampled from another uniform distribution. The probability distribution defined by the two random variables can be considered as a joint distribution between the two, so they can be treated as one multivariate random variable in the sequence of random variables, indexed by the logical term unified with I. Their joint density function is given by

and thus the probability of the query success(0) is

As said in Section 2, the range-restrictedness property ensures that the answers of a query are always ground instantiations of it. However, there can be some exceptions. Consider the first three lines of Example 3, reported here for clarity:

1/3 :: spades(_).
1/2 :: clubs(_).
angle(_,X) : uniform_dens(X,0,6.28).

Both discrete and continuous probabilistic facts are not range restricted, since they contain an input variable (anonymous) that is not ground. To ensure that the answers of a query are always ground instantiations of it, we need to make sure that, when these types of facts are called, all the input variables are ground. We then impose that the arguments of probabilistic facts that are not ground must be variables that appear in previous literal in the body: the preceding calls will bind these variables, so the probabilistic facts will be called with all input arguments ground, and a probability value will be assigned to a ground query. The order of the terms is fundamental: the variables in a probabilistic fact must appear in a preceding literal, to ensure the well-definedness. Consider the following clarifying example:

a(1).
f(_,X) : uniform_dens(X,0,6).

g0(X):- a(X), f(X,V), V > 1.
g1(X):- f(X,V), V > 1, a(X).

For the query g0(X), when f(X,Y) is called, X has already been substituted with 1, and f/2 has a ground input variable. This does not hold for query g1(X) (even if the terms in the body are the same, they are in different order), since f/2 is called with the input variable not instantiated, thus violating the syntactic requirements.

To sum up, if we consider the following simple program:

ud(_,V) : uniform_dens(V,0,6).
1/2 :: a(_).
b(X,1):- a(X).
b(X,2):- \+a(X).
n(1).
f_0(X):- a(X).
f_1:- a(1).
f_2(X):- n(X), a(X).
f_3:- a(_).
f_4(X):- b(X,V), a(V),
f_5:- ud(1,V), V > 2.

the answers of the queries f_0(1), f_1, f_2(X), and f_5 are ground instantiations of them, since the input term variable for probabilistic facts a/1 and ud/2 is bounded to 1 in all the queries. Similarly happens for f_4(1), where V can unify with 1 or 2, depending on the truth value of a. On the contrary, the answers for f_0(_), f_3, and f_4(_) are not ground instantiations, since the term variable of the probabilistic fact a is not ground (for the first two queries) or the input variable X of b/2 is not ground (for the third query).

In this paper, following the semantics proposed in [4], we delineated a precise syntax and explained the necessary syntactic conditions to maintain the well-definedness for hybrid probabilistic logic programs. We covered several cases in which ill-definedness may arise, providing examples and counterexamples. As future work, we plan to develop algorithms to automatically check these properties as well as developing new inference algorithms that can manage infinite domains [6].