Approximate weighted model counting for neural
probabilistic reasoning

Thomas Valentin, directed by Pierre Genevès, TYREX/Inria Grenoble

August 1, 2024

Abstract

Neural probabilistic reasoning is a neuro-symbolic artificial intelligence method that has shown promising results, especially with systems like Scallop which have achieved state-of-the-art results for various tasks, such as visual question answering. During the probabilistic reasoning part, the computation of logical provenance formula's probabilities is a major bottleneck. To address this problem, this work proposes a new approximation algorithm based on DPLL. Despite admitting an exponential complexity lower bound and being closely related to knowledge compilation methods commonly used, this algorithm performs better in practice. In addition, this algorithm makes it possible to avoid the complexity of the logical provenance computation phase, enabling new possibilities.

# 1 Introduction

## 1.1 Context

Classical algorithms and deep learning constitute two prevalent paradigms. Classical algorithms excel at precisely defined tasks, such as determining the consistency of a propositional logic formula. On the other hand, deep learning is well-suited for tasks where classical algorithms struggle, like detecting an object in an image. However, neural networks used in deep learning lack reliability and explainability and are often considered as black boxes. Furthermore, their reasoning abilities are inferior to those of classical algorithms when it comes to simple logical tasks.

Both paradigms are complementary, and many modern tasks require the capabilities of both: (Visual) Question Answering [18], Code Completion [4], mathematical problem solving [13]... Neuro-symbolic programming is an emerging approach that aims to combine the two. Among all neuro-symbolic methods, neural probabilistic reasoning is one of the most promising. After improvement in probabilistic logic reasoning especially with ProbLog [10], the idea of using neural network to produce probability distributions has been introduced by DeepProbLog [15]. Recently, Scallop [14] has overcome some scalability problems of DeepProbLog and accomplished state of the art result on a set of tasks such as Visual Question Answering [11] demonstrating the potential of the concept.
The method is based on a Datalog like program with a probabilistic semantics (see [10]). The probabilities of extensional predicates are given by neural networks (see [15]) and the probabilities of intentional predicates are computed using probabilistic symbolic reasoning over the Datalog program (see [10]). The final function giving the probability of intentional predicates w.r.t. the parameters of the neural networks is differentiable, which allows learning throughout the reasoning.

The bottleneck of this method is the probabilistic symbolic reasoning phase. Scallop and DeepProbLog perform it in two steps. Given a grounded intentional atom, the logical provenance of this predicate is first computed. The logic provenance is a propositional logic formula in which variables are the grounded extensional atoms. Intuitively, the logic provenance of an intentional atom is the condition over the extensional atoms for the intentional atom to be true. The second step is to compute the probability of this logic formula w.r.t. the probabilities of the ground extensional atoms given by the neural networks and the probabilistic semantics used. ProbLog, DeepProbLog and Scallop use the Sato's distribution semantics [20]. Each extensional grounded atom is considered a binary random variable, and all these variables are considered independent. With this semantics, determining the probability of a logic formula is a specific case of weighted model counting (WMC). Thus, the second step consists mainly in performing WMC.

The contribution of Scallop mainly concerns the computation of the logical provenance. First, they consider the probabilistic database defined by a Scallop program and reuse methods from the database literature to efficiently compute logical provenance. More precisely, they use semiring based methods for computing provenance in databases [22]. Each semiring defines a type of provenance. The semiring corresponding to the logic provenance computed by ProbLog and DeepProbLog is the DNF semiring (DNF formulas, $\vee$, $\bot$, $\wedge$, $\top$). Computing this semiring provenance is hard because of the potential exponential size of the DNF. To address this problem, Scallop used a semiring called the top $k$ proof semiring. This semiring is identical to the DNF semiring except that the number of clauses is bounded by $k$. During the computation, when the number of clauses exceeds the limit, only the $k$ most probable ones are kept. The final DNF formula is included in the real one, which means that its probability will be a lower bound of the real probability.

ProbLog, DeepProbLog and Scallop implementations use knowledge compilation methods for performing WMC. The logical formula is compiled into a language such as Binary Decision Diagram or Sequential Decision Diagram which allow WMC in polynomial time in their size [10] [7]. This choice was made by ProbLog and was justified at the time, but with the progress made by Scallop it should be questioned. First, the approximation methods used by Scallop rely on the probabilities. Hence, the approximated logical provenance and its probability should be recomputed at each iteration of a learning session. Therefore, the main advantage of knowledge compilation methods, which is to produce compiled structures that can be reused multiple times, is no longer useful. Second, usual knowledge compilation methods are exact methods. But computing the exact probability of an approximation is useless, especially if this approximation does not provide any guarantee of precision. Third, knowledge compilation structures, especially SDDs and OBDDs, have generally been conceived to have a unique normal form. Indeed, the purpose of knowledge compilation is beyond the bounds of just performing WMC. Therefore, they hold special properties and constraints that are not necessary for the WMC task alone.
As a result, Scallop has to use a very small $k$ in practice because of the difficulty of performing WMC with knowledge compilation so many times. This is problematic because it slows down the convergence of the neural networks and no guarantee on probabilities can be given resulting in a loss of reliability. Indeed, when the size of the program and the data size increase, a few clauses are not sufficient to approximate the real DNF provenance because it may contain up to millions of clauses. This lack of precision could mislead the neural networks which would then struggle to learn.

The aim of this work is to improve the computation of a formula probability with sato's distribution semantics in order to allow scaling with a controlled loss of precision. To fulfil this purpose, a new algorithm derived from DPLL is proposed for computing an approximate probability of a formula with a bounded error. In addition to the performance improvement, this new way of computing probabilities in the context of neural probabilistic reasoning makes it possible to avoid the computation of the provenance in clausal form opening new possibilities.

## 1.2 Specific objective

The initial objective of this internship was mainly to investigate the neural probabilistic reasoning on knowledge graphs for link prediction. However, as the problems described in the introduction were particularly highlighted in this context, the objective has been refined. The refined goal is to improve WMC in the context of neural probabilistic reasoning to improve scalability. More precisely, the aim is to perform approximate probability computation on small and medium-sized DNF and CNF produced by an approximate logical provenance query on a probabilistic database/knowledge graph. These instances have generally few clauses (up to thousands) but potentially large clauses. Moreover, variables are generally logically linked together, inducing logical schemes in these formulas. The result does not have to be reused since the computation is redone at each iteration. The final function must be differentiable to allow gradient descent.

# 2 Preliminaries

# 3 Definitions and Notations

In this work, $\mathbf{S} = (\Omega, \mathcal{F}, \mathbb{P})$ is a probability space and $\mathcal{X} = \{X_i|1 \le i \le N\}$ is a set of independent random binary variables over this space. Usual conventions over random variables such as $(X_i = x) := \{w \in \Omega|X_i(w) = x\}$ are conserved. A formula is a function $f: \{0,1\}^N \to \{0,1\}$ from the model space to the binary space. For clarity, $X_i$ is also defined as the function evaluating to 1 exactly on all models in which the $i^{th}$ component is set to 1. The usual binary operators $\wedge, \vee, \neg$ and the constant functions 1 and 0 are used. The probability of a formula $f$ is noted as $\mathbb{P}(f)$ and is defined as :

$$ \mathbb{P}(f(X_1, ..., X_N) = 1) = \sum_{f(x_1,...,x_n)=1} \prod_{i=1}^{N} \mathbb{P}(X_i = x_i) $$

The following properties are trivially verified :
$$ \bullet \forall \mathbf{S}, \mathcal{X}, f, g, \mathbb{P}(f \wedge g) = \mathbb{P}(f(X_1, \dots, X_n) = 1 \cap g(X_1, \dots, X_n) = 1) $$

$$ \bullet \forall \mathbf{S}, \mathcal{X}, f, g, \mathbb{P}(f \vee g) = \mathbb{P}(f(X_1, \dots, X_n) = 1 \cup g(X_1, \dots, X_n) = 1) $$

$$ \bullet \forall \mathbf{S}, \mathcal{X}, f, \mathbb{P}(\neg f) = 1 - \mathbb{P}(f) $$

The terminology of approximations in [9] is conserved here. All algorithm described will be computing weak-approximations. Given $0 \le \epsilon$, an algorithm $A$ computes a $\epsilon$-weak-approximation if and only if:

$$ \forall f, \mathbb{P}(f) - \epsilon \le A(f) \le \mathbb{P}(f) + \epsilon $$

## 3.1 Existing approximation methods

A first approach would be to search for approximate knowledge compilation methods. However, this subject is not really treated in the literature because the objectives of knowledge compilation are numerous and are generally exact tasks by nature such as determining entailment. At the beginning of the internship, attempts of approximate knowledge compilation methods with SDD were not found promising.

On the other hand, model counting (#SAT) is very close to WMC and is more studied in the literature. Today, state-of-the-art approximate model counters are probabilistic methods where the model space is sampled using a particular family of hashing functions and rely on a polynomial number of calls to a SAT solver [3]. Sampling the model space seems really promising, and it is in fact already done by Scallop in another way. With the semiring abstraction, Scallop has been able to develop numerous different logical provenance semirings in addition to the top k semiring. One of these semirings is the sampled k proof semiring. It is identical to the top k except that the k clauses kept are chosen randomly. Studying how to randomly sample the clause of the provenance DNF in order to obtain probabilistic guarantees is a good idea to explore. But it is first possible to learn from these methods without introducing probabilistic results. Indeed, the real power of these approximation methods is not the sampling but the calls to SAT solvers. Without efficient SAT solvers in practice, these algorithms would not be faster than knowledge compilation methods for model counting. Since SAT is really close to model counting and WMC, this suggests it is perhaps possible to implement an efficient algorithm performing WMC by taking inspiration from what SAT solvers are doing. This idea is not new and some knowledge compilation compilers are already inspired by SAT solvers with good results [16].

## 3.2 DPLL and ProbDPLL

The Davis-Putnam-Logemann-Loveland (DPLL) algorithm (alg.1) [8] is one of the most famous algorithms and it is the basis of the majority of SAT solvers. One advantage of this algorithm is that it can be easily modified to compute the probability of f (alg.2). At a first glance, this algorithm is not better than the other methods based on knowledge compilation, but its interest lies in all the literature and known properties about it. This algorithm has been successfully modified to treat formulas of industrial scale, especially by using conflict-driven clause learning (CDCL). It is easy to understand and visualize what is going on during its execution. That is why it is a good basis for creating an approximation algorithm.
**Algorithm 1 DPLL**

**Require:** $f$ a formula in CNF form ($f = \bigwedge_{i} \vee L_{k_{i,j}}$ where $L_{k_{i,j}} = X_{k_{i,j}}$ or $\neg X_{k_{i,j}}$)

**Ensure:** Return true if and only if $f$ is satisfiable

if $f$ is empty **then**

return True

else if $f$ contains the empty clause **then**

return False

else

Choose a variable $X$ that appears in $f$

$$f_0 \leftarrow f(X = 0)$$

▷ $f$ where $X$ is replaced by 0 and simplified

$$f_1 \leftarrow f(X = 1)$$

▷ $f$ where $X$ is replaced by 1 and simplified

return DPLL($f_0$) or DPLL($f_1$)

end if

**Algorithm 2 PROBDPLL**

**Require:** $f$ a formula in CNF form ($f = \bigwedge_{i} \vee L_{k_{i,j}}$ where $L_{k_{i,j}} = X_{k_{i,j}}$ or $\neg X_{k_{i,j}}$)

**Ensure:** Return $\mathbb{P}(f)$

if $f$ is empty **then**

return 1

else if $f$ contains the empty clause **then**

return 0

else

Choose a variable $X$ that appears in $f$

$$f_0 \leftarrow f(X = 0)$$

▷ $f$ where $X$ is replaced by 0 and simplified

$$f_1 \leftarrow f(X = 1)$$

▷ $f$ where $X$ is replaced by 1 and simplified

return $\mathbb{P}(X = 0) \times \text{PROBDPLL}(f_0) + \mathbb{P}(X = 1) \times \text{PROBDPLL}(f_1)$

end if

# 4 ApproxProbDPLL

## 4.1 ApproxProbDPLL

The main idea behind ApproxProbDPLL is to take advantage of the probability distribution over the models. For example, if there are 10 variables and for all $i$, $\mathbb{P}(X_i = 1) = 0.999999$. It is clear that if $f(1, ..., 1) = 1$ then $\mathbb{P}(f) \approx 1$ and on the contrary, if $f(1, ..., 1) = 0$, $\mathbb{P}(f) \approx 0$. In other words, there is no need to know $f$ on the models that are not probable. DPLL explores a tree of partial assignments. Therefore, it is possible to know if a branch leads to probable models or not and to cut it if it is not necessary to count them. Given $\epsilon$ an amount of approximation, the idea behind ApproxProbDPLL is to distribute this approximation quantity over the searching branches of DPLL. If the amount of approximation allowed is sufficiently high compared to the probability of the branch, it is possible to cut the branch. Intuitively, it is desirable to be precise in branches that are probable and to allow greater
approximation in branches that are less probable.

ApproxProbDPLL (alg.3) is similar to ProbDPLL but is taking $\epsilon$ an upper bound of its allowed approximation and is distributing this approximation over its recursive call considering the probability of X. $\alpha$ is a parameter that can be chosen w.r.t. $f_0$ and $f_1$ to distribute the approximation between the two. This way, it is possible to get a higher approximation upper bound for formulas that are likely to have a lot of models and a lower approximation upper bound for formulas that are likely to have few models. This way, the approximation is counterbalancing the fact that ProbDPLL is less efficient on formulas with a lot of models.

It is, however, difficult to analyze the impact on complexity of some heuristics choosing $X$ and $\alpha$. A complexity study with a simplified situation (variables are chosen in a fixed order, and $\alpha = 1/2$) is done in section 9. The conclusion of this study is that the complexity is $O(n^{2+C(\epsilon,n,p)})$ where $n$ is the number of variables of the formula, $0 < p \le 1/2$ is a real such that for all variable $X$, $0 \le \mathbb{P}(X = 1) \le p$ or $1-p \le \mathbb{P}(X = 1) \le 1$ and $C(\epsilon, n, p) := |(\log_2(\epsilon) - n)/\log_2(p)|$. This means that the smaller the $p$ the faster the algorithm. If we consider $p$ fixed and $\epsilon$ fixed, this is a worse upper bound than $O(n2^n)$ though. Without surprise, the complexity lower bound is exponential in $n$. Explanations about it are given later, when the link with knowledge compilation is done.

<caption>**Algorithm 3 APPROXPROBDPLL**</caption>

**Require:** $f$ a formula in CNF form ($f = \bigwedge_i \vee L_{k_{i,j}}$ where $L_{k_{i,j}} = X_{k_{i,j}}$ or $\neg X_{k_{i,j}}$)
**Require:** $0 \le \epsilon$ an amount of approximation
**Ensure:** Return an interval $[low, up]$ such that $\mathbb{P}(f) \in [low, up]$ and $up - low \le \epsilon$
    **if** $f$ is empty **then**
        **return** $[1, 1]$
    **else if** $f$ contains the empty clause **then**
        **return** $[0, 0]$
    **else if** $1 \le \epsilon$ **then**
        **return** $[0, 1]$
    **else**
        Choose a variable $X$ that appears in $f$
        $f_0 \leftarrow f(X = 0)$ \quad $\triangleright f$ where $X$ is replaced by 0 and simplified
        $f_1 \leftarrow f(X = 1)$ \quad $\triangleright f$ where $X$ is replaced by 1 and simplified
        Choose an $\alpha \in [0, 1]$
        $\epsilon_0 \leftarrow \alpha \cdot \epsilon / \mathbb{P}(X = 0)$
        $\epsilon_1 \leftarrow (1 - \alpha) \cdot \epsilon / \mathbb{P}(X = 1)$
        $[low_0, up_0] \leftarrow \text{APPROXPROBDPLL}(f_0, \epsilon_0)$
        $[low_1, up_1] \leftarrow \text{APPROXPROBDPLL}(f_1, \epsilon_1)$
        $low \leftarrow \mathbb{P}(X = 0) \times low_0 + \mathbb{P}(X = 1) \times low_1$
        $up \leftarrow \mathbb{P}(X = 0) \times up_0 + \mathbb{P}(X = 1) \times up_1$
        **return** $[low, up]$
**end if**
## 4.2 ApproxProbDPLLCache

ApproxProbDPLL is a good algorithm to understand the concept of approximation and is interesting in theory. But as such, it does not profit from all the previous advances made, especially advances for the #DPLL algorithm (a version of DPLL that counts the number of models, which is equivalent to computing the probability with a uniform distribution).

It would be interesting to study how conflict-driven clause learning could speed up the algorithm since it is the most important improvement of SAT solvers. It is very efficient when there are few models because conflicts are numerous. However, the kinds of instances that will mainly be encountered in neural probabilistic reasoning will rather be composed of few but potentially big clauses. This means that the models of this kind of instance are numerous in general. Fortunately, this also means that these instances contain a lot of redundancies and/or disjoint information. To take advantage of this, [1] proposed a modified version of #DPLL using components caching and splitting that has an upper bound of complexity that is exponential in the tree-width of the CNF input formula. Tree-width is a lower bound of the number of variables so this is a tighter upper bound than usual. Moreover, tree-width is intuitively smaller when disjoint information are given in a formula (see [1]) and component caching allows handling redundant information more efficiently. This means that their algorithm is fit for the majority of instances that will be encountered in our case. ApproxProbDPLLCache (alg.7) is a direct fusion of their algorithm with ApproxProbDPLL. In addition, ApproxProbDPLLCache uses unit propagation to further improve the efficiency of the algorithm. The details about ApproxProbDPLLCache are given in Section 7.

## 4.3 Link with knowledge compilation and lower bound of complexity

Even if DPLL seems really different from knowledge compilation, the link between the two is very tight. In [12], Jinbo Huang and Adnan Darwiche have shown how each variation of DPLL corresponds to a knowledge compilation language (OBDD, FBDD, d-DNNF). The trace of the algorithm corresponds almost exactly to the graph of a knowledge compilation form. In other words, it is possible to slightly modify any variation of DPLL to make it produce a compiled form. When $\epsilon$ is set to 0, which is the exact version of ApproxProbD-PLLCache, the execution tree graph matches with a Decision-DNNF graph (Decision-DNNF are described in [17]). Decision-DNNF is a strict superset of BDDs. It follows fewer constraints, which allows it to be a more compact representation of a formula. However, it is a strict subset of d-DNNFs which have been shown to have an exponential lower bound of size in the number of variable for a family of formula [2]. ApproxProbDPLLCache corresponds to an $\epsilon$-weak-approximation d-DNNF of the formula according to the terminology in [9]. Unfortunately, [9] have shown that for every $0 \le \epsilon < 1/2$ there exist a family of formulas on which $\epsilon$-weak-approximation d-DNNFs have exponential size in the number of variables. This means that ApproxProbDPLLCache has a worst-case complexity lower bound that is exponential in the number of variables. ApproxProbDPLL corresponds to an $\epsilon$-weak-approximation BDD of the formula therefore the same lower bound applies.
## 4.4 Generalization

DPLL also works on non-clausal formulas (a version of ApproxProbDPLLCache for non-clausal formulas is given in section 7). Works found in [21] have shown that efficient SAT solving was possible and even desirable on non-clausal formulas by simply adapting what is done by usual SAT solvers. It is clearly possible to do the same for our algorithms. This is particularly interesting because computing the logical provenance in DNF or CNF using the semiring provenance abstraction is expensive. This is because operations in these semirings are done in polynomial time while operations in the non-clausal formula semiring are possible in constant time. When the saturation procedure of the logic program has a known maximum number of iterations, like in the case of a non-recursive program or a transitivity closure query, it is then possible to compute directly the non-clausal logic provenance formula. The complexity of computing the probability is then totally transferred to our algorithm.

# 5 Experimental results

## 5.1 Experimental setup

All the experiments are conducted on a MacBook Air (M2, 2022) with an Apple M2 processor and 24 Go of RAM. The source code is in Python. The comparison with Scallop and ProbLog is made using their Python libraries. The code is executed in PyCharm with a virtual Python environment. Proofs of termination and correctness of ApproxProbDPLL are given in section 8. An additional test-based verification of implementations is done through systematic comparisons with brute force methods on random CNF, DNF and non-clausal formulas (1000 random formulas containing up to 20 variables are tested before an experiment for each implementation used).

## 5.2 Experiment 1: Graph transitive closure request

Transitive closure is a simple recursive Datalog program, but it is already a difficult program for Scallop. Indeed, the number of paths from an entity $x$ to an entity $y$ could be huge and each path could be very long. Since a path $R(x_0, x_1), R(x_1, x_2), \dots, R(x_{n-1}, x_n)$ corresponds to a clause of the logic provenance DNF, the exact logic provenance DNF could contain a lot of clauses with numerous atoms. That is to say, numerous clauses with a small probability. Therefore, bounding the number of clauses of the approximation, as in the top $k$ proofs semiring, could produce a result close to 0 while the real probability could be close to 1.

$$ 
\begin{align*}
T(X,Y) &:- R(X,Y) \\
T(X,Y) &:- T(X,Z), T(X,Y) \\
?-T(X,Y)
\end{align*}
$$

The relation $R$ corresponds to a graph. For different $n$, a random sparse graph with $n$ nodes where each edge $R(x, y)$ has $2/n$ chances to have a non-zero probability is generated. The query is then evaluated on this graph using the following methods :
* ProbLog uses a SLD-resolution variation to compute the logical provenance CNFs and then compiles these CNFs into d-DNNFs to compute probabilities.

* Scallop with the top $k$ proofs semiring where $k = 100$. Top $k$ proofs provenance DNFs are then compiled into SDDs to compute probabilities.

* A first implementation (impl.1) computes the top $k$ proofs provenance DNFs with $k = 100$ and then uses ApproxProbDPLLCache with $\epsilon = 0.01$ to compute probabilities.

* A second implementation (impl.2) computes non-clausal provenance formulas with $\log_2(n) + 1$ iteration of the saturation procedure (the minimum number of iterations required to produce a correct logic provenance) and then uses a version of ApproxProb-DPLLCache adapted to non-clausal formulas with $\epsilon = 0.01$ to compute probabilities.

A comparison of the result probabilities has been done on small examples ($n = 5$) where the top $k$ proofs semiring with $k = 100$ produces exact logic provenance. The result probabilities of (impl.1) and (impl.2) correspond to those of ProbLog. However, Scallop sometimes produces different results. The results of the experiment are shown in fig. 1. The time measured takes into account the logical provenance computation for all the links $T(x, y)$ and the probability computation for each of these logic provenance formulas. However, while the bottleneck of Scallop and ProbLog is mainly due to the probability computation, the bottleneck of (impl.1) is mainly the provenance computation because we used a naive and not optimized implementation of the top $k$ semiring. It is not the case for (impl.2) since the provenance semiring of the non-clausal formulas has constant time operations. An important observation is that all the executions of Scallop and ProbLog done on instances of size greater than 16 lasted for more than 2h before we interrupted them. While (impl.2) terminated in 1 min on some instances of size 50 and in less than 1 hour for most of these instances. The main problem of (impl.1) is the provenance computation. However, by using $T(X,Y) : -R(X,Z), T(X,Y)$ instead of $T(X,Y) : -T(X,Z), T(X,Y)$ which produces equivalent results. The provenance computation is faster and (impl.1) is able to treat graphs of size 100 in less than 20 min.

## 5.3 Experiment 2: Impact of the probability distribution over variables on the complexity

Even if the distribution is impacting the complexity in theory, to what extent is that the case in practice? To study this, we parameterize each distribution by a parameter $p \in [0, 1/2]$. A distribution $U_p$ is a distribution where for all variable $X$, $\mathbb{P}(X = 1) \in [0, p] \cup [1-p, 1]$. We generate random CNF on $n$ variables for different $n$. Each CNF has $n$ clauses of size 3 to 5 because this proportion produces CNF that are likely to be difficult for WMC since they have a more balanced proportion of models and invalidating valuations. As usual, $\epsilon$ is fixed to 0.01 except for a witness to compare with the algorithm without approximation. The results (see Fig. 1) show that it is not necessary to have a small $p$ for a huge speed-up as previously suggested by the theory. In practice, without restriction on the distribution ($p = 0.5$) the approximation is around 5 to 10 times faster than the exact algorithm. Moreover, with $p$ fixed around 0.1 or 0.2 the approximation algorithm is 100 times faster than the exact
one. Furthermore, curves suggest that this factor continues to increase with the number of variables. This could be really interesting during a learning procedure. At the beginning of the learning process, neural networks have not learned anything, therefore they produce a random distribution of probability. But over time, their results converge toward more precise probabilities, with probabilities closer to 1 and 0. Hence, the more the neural networks learn, the faster the process is.

<figure><img src="image_1.png" /><figcaption>Figure 1: Time comparison on a graph transitivity query with different graph size and a 10min of timeout</figcaption></figure>

# 6 Conclusion and perspectives

This work proposed ApproxProbDPLL and ApproxProbDPLLCache, new approximate algorithms for computing the probability of logical formulas with Sato's semantics for neural probabilistic reasoning. Beyond achieving better results than the current state-of-the-art in a difficult probabilistic reasoning task, experimental results suggest that the efficiency of the algorithm might increase during a learning procedure. Further studying the integration of the proposed algorithms in a complete neuro-symbolic learning procedure constitutes an interesting perspective for further work. Experiments also show promising results when computing the provenance in non-clausal form allowing faster logical provenance computation. Furthermore, DPLL-based algorithms work on every logical representation for which partial valuation is possible. It is therefore possible to imagine a specific representation of
<figure><img src="image_2.png" /><figcaption>Figure 2: Time of ApproxProbDPLLCache for different CNF size and different values of *p*</figcaption></figure>

a logic program on which a DPLL-based algorithm can directly operate without any logic provenance computation.

## References

[1] Fahiem Bacchus, Shannon Dalmao, and Toniann Pitassi. “Algorithms and complexity results for# SAT and Bayesian inference”. In: *44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings*. IEEE. 2003, pp. 340–351.

[2] Simone Bova et al. “Knowledge Compilation Meets Communication Complexity.” In: *IJCAI*. Vol. 16. 2016, pp. 1008–1014.

[3] Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi. *A Scalable Approximate Model Counter*. 2013. arXiv: 1306.5726 [cs.LO]. URL: https://arxiv.org/abs/1306.5726.

[4] Mark Chen et al. *Evaluating Large Language Models Trained on Code*. 2021. arXiv: 2107.03374 [cs.LG]. URL: https://arxiv.org/abs/2107.03374.

[5] Eugene Dantsin. “Probabilistic logic programs and their semantics”. In: *Logic Programming*. Ed. by A. Voronkov. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992, pp. 152–164.

[6] Adnan Darwiche. “Decomposable negation normal form”. In: *IJCAI*. Vol. 48. 2001, pp. 608–647.
[7] Adnan Darwiche. "SDD: A new canonical representation of propositional knowledge bases". In: *Twenty-Second International Joint Conference on Artificial Intelligence*. 2011.

[8] Martin Davis, George Logemann, and Donald Loveland. "A machine program for theorem-proving". In: *Communications of the ACM* 5.7 (1962), pp. 394–397.

[9] Alexis De Colnet and Stefan Mengel. "Lower bounds for approximate knowledge compilation". In: *arXiv preprint arXiv:2011.13721* (2020).

[10] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. *ProbLog: A probabilistic Prolog and its application in link discovery*. eng. 2007-01-01.

[11] Jiani Huang et al. "Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning". In: *Advances in Neural Information Processing Systems*. Ed. by A. Beygelzimer et al. 2021. URL: https://openreview.net/forum?id=ngdcA1tlDvj.

[12] Jinbo Huang and Adnan Darwiche. "DPLL with a trace: From SAT to knowledge compilation". In: *IJCAI*. Vol. 5. 2005, pp. 156–162.

[13] Aitor Lewkowycz et al. "Solving quantitative reasoning problems with language models". In: *Advances in Neural Information Processing Systems* 35 (2022), pp. 3843–3857.

[14] Ziyang Li, Jiani Huang, and Mayur Naik. *Scallop: A Language for Neurosymbolic Programming*. 2023. arXiv: 2304.04812.

[15] Robin Manhaeve et al. *DeepProbLog: Neural Probabilistic Logic Programming*. 2018. arXiv: 1805.10872.

[16] Umut Oztok and Adnan Darwiche. "A top-down compiler for sentential decision diagrams". In: *Twenty-Fourth International Joint Conference on Artificial Intelligence*. 2015.

[17] Umut Oztok and Adnan Darwiche. "On compiling CNF into decision-DNNF". In: *International Conference on Principles and Practice of Constraint Programming*. Springer. 2014, pp. 42–57.

[18] Pranav Rajpurkar et al. "Squad: 100,000+ questions for machine comprehension of text". In: *arXiv preprint arXiv:1606.05250* (2016).

[19] Tian Sang et al. "Combining Component Caching and Clause Learning for Effective Model Counting". In: *SAT* 4 (2004), 7th.

[20] Taisuke Sato. "A Statistical Learning Method for Logic Programs with Distribution Semantics". In: *Logic Programming: The 12th International Conference on Logic Programming*. 1995, pp. 715–729.

[21] Christian Thiffault, Fahiem Bacchus, and Toby Walsh. "Solving non-clausal formulas with DPLL search". In: *International Conference on Principles and Practice of Constraint Programming*. Springer. 2004, pp. 663–678.

[22] Val Tannen Todd J. Green Grigoris Karvounarakis. *Provenance Semirings*. eng. 2007-06-11.
[23] Timothy Van Bremen et al. "Symmetric component caching for model counting on combinatorial instances". In: *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 35. 5. 2021, pp. 3922-3930.
# 7 Algorithms

## 7.1 Unit propagation

<caption>**Algorithm 4 UNITPROPAGATION**</caption>

**Require:** $f$ a formula in CNF form ($f = \bigwedge_i \bigvee_j L_{k_{i,j}}$ where $L_{k_{i,j}} = X_{k_{i,j}}$ or $\neg X_{k_{i,j}}$)

**Ensure:** At the end $f$ does not contains any unit clause

**Ensure:** Return $p = \Pi_i \mathbb{P}(Y_i = y_i)$ where $Y_i$ are the variables of the initial $f$ that has been fixed to $y_i$ during the execution

$$p \leftarrow 1$$

**while** $f$ contains a unit clause with a literal $L$ **do**

if $L = Y$ then

$$f \leftarrow f(Y = 1)$$

$$p \leftarrow p.\mathbb{P}(Y = 1)$$

else if $L = \neg Y$ then

$$f \leftarrow f(Y = 0)$$

$$p \leftarrow p.\mathbb{P}(Y = 0)$$

end if

end while

## 7.2 ApproxProbDPLLCache

ApproxProbDPLLCache (alg.7) combines component caching and formula splitting with the approximation method of ApproxProbDPLL. When the formula contains two set of clauses with disjoint variables each set can be treated independently. In other words we can split the formula in two. When this occurs, $\alpha$ is chosen to distribute properly the approximation and $\epsilon'$ is fixed with respect to $\alpha$ and $\epsilon$ to maintain the approximation invariant. Adapting the component caching was a bit more tricky because computing 2 times the probability of the same $f$ during the execution does not mean it is with the same $\epsilon$ so if a probability interval has already been computed for $f$ we have to check that the approximation invariant is valid for the current $\epsilon$ if it is not we have to recompute. The algorithm is trying to avoid this kind of situation by greedily computing first the branch where $\epsilon$ is the smaller. By lack of time we were not able to implement a version using clause learning [19] and component caching symmetry [23] to see DPLL with its full power. About the choice of $\alpha$ and $X$, $X$ is the variable which is the most present in the formula and $\alpha = \sigma(7.(\frac{size(f_0)}{size(f_0)+size(f_1)} - 0.5))$ where $\sigma$ is the sigmoid and $size(f)$ is the size of the tree representing $f$.
**Algorithm 5 APPROXPROBDPLLCACHE**

**Require:** $f$ a formula in CNF form ($f = \bigwedge_i \bigvee_j L_{k_{i,j}}$ where $L_{k_{i,j}} = X_{k_{i,j}}$ or $\neg X_{k_{i,j}}$)

**Require:** $0 \le \epsilon$ an amount of approximation

**Require:** $C$ a cache mapping known components to an interval of probability (at the beginning $C$ is empty)

**Ensure:** Return an interval $[low, up]$ such that $\mathbb{P}(f) \in [low, up]$ and $up - low \le \epsilon$

if $f$ is empty **then**

return $[1, 1]$

else if $f$ contains the empty clause **then**

return $[0, 0]$

else if $1 \le \epsilon$ **then**

return $[0, 1]$

else

if $f \in C$ such that $C[f] = [low, up]$ and $up - low \le \epsilon$ **then**

return $[low, up]$

else if $f$ contains unit clauses **then**

$p \leftarrow \text{UNITPROPAGATION}(f) \quad \triangleright f$ is implicitly modified here

$[low, up] \leftarrow \text{APPROXPROBDPLLCACHE}(f, \epsilon/p, C)$

return $[p.low, p.up]$

else if $f$ can be split in 2 non empty CNF $f_l, f_r$ with disjoint set of variable **then**

Choose $\alpha \in ]0, 1[$

$\epsilon' \leftarrow \frac{\sqrt{1+4\alpha(1-\alpha)\epsilon-1}}{2\alpha(1-\alpha)}$

$[low_l, up_l] \leftarrow \text{APPROXPROBDPLLCACHE}(f_l, \alpha\epsilon', C)$

$[low_r, up_r] \leftarrow \text{APPROXPROBDPLLCACHE}(f_r, (1-\alpha)\epsilon', C)$

$C[f] \leftarrow [low_l.low_r, up_l.up_r]$

return $[low_l.low_r, up_l.up_r]$

else

Choose a variable $X$ that appears in $f$

$f_0 \leftarrow f(X = 0) \quad \triangleright f$ where $X$ is replaced by 0 and simplified

$f_1 \leftarrow f(X = 1) \quad \triangleright f$ where $X$ is replaced by 1 and simplified

Choose an $\alpha \in [0, 1]$

$\epsilon_0 \leftarrow \alpha.\epsilon/\mathbb{P}(X = 0)$

$\epsilon_1 \leftarrow (1 - \alpha).\epsilon/\mathbb{P}(X = 1)$

if $\epsilon_0 < \epsilon_1$ **then**

$[low_0, up_0] \leftarrow \text{APPROXPROBDPLLCACHE}(f_0, \epsilon_0, C)$

$[low_1, up_1] \leftarrow \text{APPROXPROBDPLLCACHE}(f_1, \epsilon_1, C)$

else

$[low_1, up_1] \leftarrow \text{APPROXPROBDPLLCACHE}(f_1, \epsilon_1, C)$

$[low_0, up_0] \leftarrow \text{APPROXPROBDPLLCACHE}(f_0, \epsilon_0, C)$

end if

$low \leftarrow \mathbb{P}(X = 0) \times low_0 + \mathbb{P}(X = 1) \times low_1$

$up \leftarrow \mathbb{P}(X = 0) \times up_0 + \mathbb{P}(X = 1) \times up_1$

$C[f] \leftarrow [low, up]$

return $[low, up]$

end if

end if
## 7.3 Unit propagation on a non clausal formula

**Algorithm 6 NONCLAUSALUNITPROPAGATION**

**Require:** $f$ a formula in Negation Normal Form (negation is pushed down to the literals)

**Ensure:** At the end, if $f$ is the conjunction this conjunction does not contains literal.

**Ensure:** Return $p = \Pi_i \mathbb{P}(Y_i = y_i)$ where $Y_i$ are the variables of the initial $f$ that has been fixed to $y_i$ during the execution

$$p \leftarrow 1$$

while $f$ is a conjunction which contains a literal $L$ do

if $L = Y$ then

$$f \leftarrow f(Y = 1)$$

$$p \leftarrow p.\mathbb{P}(Y = 1)$$

else if $L = \neg Y$ then

$$f \leftarrow f(Y = 0)$$

$$p \leftarrow p.\mathbb{P}(Y = 0)$$

end if

end while

## 7.4 ApproxProbDPLLCache on non clausal formula

This algorithm is identical to ApproxProbDPLLCache except that it works on non clausal formulas. The main differences are hidden in the partial valuation of a formula. It is necessary to use simplification rule in order to obtain $\top$ or $\bot$ when the partial valuation make the formula true of false. The partial valuation is propagated in a bottom up manner using simple rules :

* $\top$ (resp. $\bot$) children of a $\land$ (resp. $\lor$) node are removed from the children of this node

* If a $\land$ (resp. $\lor$) node has a $\bot$ (resp. $\top$) child, this node is replaced by $\bot$ (resp. $\top$)

* If a node has only one child, this node is replaced by its child
**Algorithm 7 NONCLAUSALAPPROXPROBDPLLCACHE**

**Require:** *f* a formula in Negation Normal Form

**Require:** $0 \le \epsilon$ an amount of approximation

**Require:** *C* a cache mapping known components to an interval of probability (at the beginning *C* is empty)

**Ensure:** Return an interval [*low*, *up*] such that $\mathbb{P}(f) \in [low, up]$ and $up - low \le \epsilon$

if *f* is ⊤ then

return [1, 1]

else if *f* is ⊥ then

return [0, 0]

else if $1 \le \epsilon$ then

return [0, 1]

else

if $f \in C$ such that $C[f] = [low, up]$ and $up - low \le \epsilon$ then

return [low, up]

else if *f* is a conjunction which contains a literal **then**

$p \leftarrow \text{NONCLAUSALUNITPROPAGATION}(f) \quad \triangleright f$ is implicitly modified here

$[low, up] \leftarrow \text{NONCLAUSALAPPROXPROBDPLLCACHE}(f, \epsilon/p, C)$

return [p.low, p.up]

else if $f = f_l \wedge f_r$ where $f_l, f_r$ have disjoint set of variable **then**

Choose $\alpha \in ]0, 1[$

$$ \epsilon' \leftarrow \frac{\sqrt{1+4\alpha(1-\alpha)\epsilon-1}}{2\alpha(1-\alpha)} $$

$[low_l, up_l] \leftarrow \text{NONCLAUSALAPPROXPROBDPLLCACHE}(f_l, \alpha\epsilon', C)$

$[low_r, up_r] \leftarrow \text{NONCLAUSALAPPROXPROBDPLLCACHE}(f_r, (1 - \alpha)\epsilon', C)$

$C[f] \leftarrow [low_l.low_r, up_l.up_r]$

return [low_l.low_r, up_l.up_r]

else

Choose a variable *X* that appears in *f*

$f_0 \leftarrow f(X = 0) \quad \triangleright f$ where *X* is replaced by 0 and simplified

$f_1 \leftarrow f(X = 1) \quad \triangleright f$ where *X* is replaced by 1 and simplified

Choose an $\alpha \in [0, 1]$

$$ \epsilon_0 \leftarrow \alpha \cdot \epsilon / \mathbb{P}(X = 0) $$

$$ \epsilon_1 \leftarrow (1 - \alpha) \cdot \epsilon / \mathbb{P}(X = 1) $$

if $\epsilon_0 < \epsilon_1$ then

$[low_0, up_0] \leftarrow \text{NONCLAUSALAPPROXPROBDPLLCACHE}(f_0, \epsilon_0, C)$

$[low_1, up_1] \leftarrow \text{NONCLAUSALAPPROXPROBDPLLCACHE}(f_1, \epsilon_1, C)$

else

$[low_1, up_1] \leftarrow \text{NONCLAUSALAPPROXPROBDPLLCACHE}(f_1, \epsilon_1, C)$

$[low_0, up_0] \leftarrow \text{NONCLAUSALAPPROXPROBDPLLCACHE}(f_0, \epsilon_0, C)$

end if

$$ low \leftarrow \mathbb{P}(X = 0) \times low_0 + \mathbb{P}(X = 1) \times low_1 $$

$$ up \leftarrow \mathbb{P}(X = 0) \times up_0 + \mathbb{P}(X = 1) \times up_1 $$

$C[f] \leftarrow [low, up]$

return [low, up]

end if

end if
# 8 Proofs

## 8.1 Proof of ProbDPLL

* ProbDPLL terminate since DPLL terminate

* The proof of correctness is done by recurrence over the number of variables

- If $f$ has no variable, it contains no close or the empty clause. If $f$ contains no clause $f = 1$ so $\mathbb{P}(f) = \mathbb{P}(1) = 1$ else it contains the empty clause so $f = 0$ therefore $\mathbb{P}(f) = \mathbb{P}(0) = 0$.

- If $f$ has a $N + 1$ variables. If $f$ contains the empty clause it is the same case as before. Else, lets get $X$ chosen in the algorithm and note $X_1, ..., X_N$ the other variables. According to the recurrence hypothesis :

$$ \text{PROBDPLL}(f_0) = \mathbb{P}(f_0) = \mathbb{P}(f(0, X_1, ..., X_n) = 1) $$

$$ \text{PROBDPLL}(f_1) = \mathbb{P}(f_1) = \mathbb{P}(f(1, X_1, ..., X_n) = 1) $$

Because $f_0$ and $f_1$ are $f$ where $X$ has taken the value 0 or 1 and on the other hand ($X = 0$) and ($X = 1$) form a partition of $\Omega$

$$ \mathbb{P}(f) = \mathbb{P}(f(X, X_1, ..., X_n) = 1 \cap (X = 0)) + \mathbb{P}(f(X, X_1, ..., X_n) = 1 \cap (X = 1)) $$

$$ \mathbb{P}(f) = \mathbb{P}(f(0, X_1, ..., X_n) = 1 \cap (X = 0)) + \mathbb{P}(f(1, X_1, ..., X_n) = 1 \cap (X = 1)) $$

Finally, $X$ is independent of $X_1, ..., X_n$ therefore $X$ is independent of $f(0, X_1, ..., X_n)$ and $f(1, X_1, ..., X_n)$

$$ \mathbb{P}(f) = \mathbb{P}(f(0, X_1, ..., X_n) = 1) \times \mathbb{P}(X = 0) + \mathbb{P}(f(1, X_1, ..., X_n) = 1) \times \mathbb{P}(X = 1) $$

$$ \mathbb{P}(f) = \mathbb{P}(X = 0) \times \text{PROBDPLL}(f_0) + \mathbb{P}(X = 1) \times \text{PROBDPLL}(f_1) $$

## 8.2 Proof of ApproxProbDPLL

* The termination of the algorithm is naturally implied by the termination of ProbDPLL

* The proof of correctness is identical to the proof of ProbDPLL except for the approximation part. Therefore only approximation are treated here :

- If $f$ is empty then $\mathbb{P}(f) = \mathbb{P}(1) = 1 \in [1, 1]$ and $1 - 1 = 0 \le \epsilon$

- If $f$ contains the empty clause then $\mathbb{P}(f) = \mathbb{P}(0) = 0 \in [0, 0]$ and $0 - 0 = 0 \le \epsilon$

- If $1 \le \epsilon$, then $\mathbb{P}(f) \in [0, 1]$ always hold and $1 - 0 = 1 \le \epsilon$ by hypothesis

- Else $f$ has $N + 1$ variables and we suppose the recursive calls on $f_0$ and $f_1$ which have $N$ variables are correct, this means

$$ (H0) : low_0 \le \mathbb{P}(f_0) \le up_0 \text{ and } up_0 - low_0 \le \epsilon_0 $$

$$ (H1) : low_1 \le \mathbb{P}(f_1) \le up_1 \text{ and } up_1 - low_1 \le \epsilon_1 $$

Combining the inequalities, we obtain
$$ 
\begin{aligned}
low &= \mathbb{P}(X = 0) \times low_0 + \mathbb{P}(X = 1) \times low_1 \le \\
    &\mathbb{P}(X = 0) \times \mathbb{P}(f_0) + \mathbb{P}(X = 1) \times \mathbb{P}(f_1) \\
    &\le \mathbb{P}(X = 0) \times up_0 + \mathbb{P}(X = 1) \times up_1 = up
\end{aligned}
$$

But as proved in the proof of ProbDPLL, $\mathbb{P}(X = 0) \times \mathbb{P}(f_0) + \mathbb{P}(X = 1) \times \mathbb{P}(f_1) = \mathbb{P}(f)$

$$ low \le \mathbb{P}(f) \le up $$

Lets now prove that $up - low \le \epsilon$

$$ 
\begin{aligned}
up - low &= \mathbb{P}(X = 0).(up_0 - low_0) + \mathbb{P}(X = 1).(up_1 - low_1) \\
up - low &\le \mathbb{P}(X = 0).\epsilon_0 + \mathbb{P}(X = 1).\epsilon_1 \\
up - low &\le \alpha.\epsilon + (1 - \alpha).\epsilon = \epsilon
\end{aligned}
$$

In conclusion, the interval returned verify the specifications.

# 9 Complexity analysis of ApproxProbDPLL

## 9.1 Visualisation

To simplify the analysis, we consider the worst case of ProbDPLL where the probability is equal to 1 and all the branch of the tree search must be visited to compute it because $f$ does not evaluate to false under any variable assignment. To continue simplifying, we suppose that we choose the variables in a fixed order ($X_1, ..., X_N$) and that $\alpha$ is fixed to $1/2$ (this is a default value that is good in practice). The trace of the ProbDPLL will correspond to a decision tree (by convention right child is where the variable is evaluated to 1 and left to 0). Here is an example with 4 variables.

<figure><img src="image_3.png" /></figure>

We now observe the corresponding trace of ApproxProbDPLL noting the value of $\epsilon$ in each node. For the example we suppose that $\forall i, \mathbb{P}(X_i = 1) = 3/4$
<figure><img src="image_4.png" /></figure>

Intuitively, the less probable is the partial assignment of a branch the greater is $\epsilon$ in this branch.

## 9.2 Formalization

Consider a formula a base formula $F$ and $0 < E$. For each call of ApproxProbDPLL, consider $v = [(X_1 = x_1), ..., (X_k = x_k)]$ and $B = [\beta_1, ..., \beta_k]$ where $v$ is the partial assignment done before such that

$$f = F(X_1 = x_1, ..., X_k = x_k)$$

and $B$ is the list of all the $\alpha$ and $(1 - \alpha)$ coefficient chosen by the algorithm before such that

$$\epsilon = (\prod_{i=1}^{k} \frac{\beta_i}{\mathbb{P}(X_i = x_i)}).E$$

A execution tree of ApproxProbDPLL is a tree where each node correspond to a call to ApproxProbDPLL annotated by $f$, $\epsilon$, $v$ and $B$ and where the parent of a node $c$ is the ApproxProbDPLL call node $p$ that recursively called $c$.

## 9.3 First study

To simplify the situation, suppose that variables are always chosen in the order $X_1, ..., X_N$, that $\alpha$ is always fixed to $1/2$ and even if it means replacing $X_i$ by $\neg X_i$ in $F$ suppose that $\mathbb{P}(X_i = 1) \le 1/2$. To continue the simplification suppose there exist a $p$ such that $\mathbb{P}(X_i = 1) \le p < 1/2$ for all $i$.

Let $T$ be the execution tree of ApproxProbDPLL($F$, $E$). Let $T'$ be $T$ completed with all the node that would have been part of it if the algorithm would not stop its execution before having made a full assignment of the $N$ variables. $T'$ is complete, contains $2^N - 1$ nodes and contains $T$. Let $M$ be the number of node of $T'$ where $\epsilon < 1$. $2M$ is an upper bound of the number of node of $T$ because each node that makes 2 recursive call in $T$ has $\epsilon < 1$ and is therefore counted in $M$. Hence, the complexity of ApproxProbDPLL($F$, $E$) is an $\Omega(M)$.

For each node $(f, \epsilon, v, B)$ in $T'$. Let $z = x_1 + ... + x_k$. Since $E = \epsilon \cdot 2^k \cdot (\prod_{i=1}^{k} \mathbb{P}(X_i = x_i))$

$$E \le \epsilon \cdot 2^k \cdot p^z \text{ then } E/(2^k \cdot p^z) \le \epsilon$$
Because if $x_i = 0$, $\mathbb{P}(X_i = x_i) \le 1$ and if $x_i = 1$, $\mathbb{P}(X_i = x_i) \le p$. For $0 \le k \le N-1$, let $M_k$ be the number of node of M of depth k in the execution tree. Let $\delta_\phi$ be the Kronecker delta over the condition $\phi$ ($\delta_\phi = 1$ if $\phi$ hold, $\delta_\phi = 0$ else). If $1 \le E/(2^k \cdot p^z) \le \epsilon$, then the node is not counted in M. Equivalently, if the node is counted then $E/(2^k \cdot p^z) < 1$. This means

$$M_k \le \sum_{z=0}^{k} \binom{k}{z} \delta_{E/(2^k \cdot p^z)} < 1$$

Because there is $\binom{k}{z}$ ($x_1, ..., x_k \in \{0, 1\}^k$ such that $z = x_1 + ... + x_k$. But $E/(2^k \cdot p^z) < 1$ means that

$$\log_2(E) - k - z \log_2(p) < 0 \\ z < (\log_2(E) - k)/\log_2(p) \quad (p < 1/2 \text{ then } \log_2(p) < -1)$$

Let

$$C(E, p, k) := \lceil (\log_2(E) - k) / \log_2(p) \rceil$$

This implies that

$$M = \sum_{k=0}^{N} M_k \le \sum_{z=0}^{k} \binom{k}{z} \delta_{E/(2^k \cdot p^z)} < 1 \le \sum_{k=0}^{N} \sum_{z=0}^{\min(C(E,p,k),k)} \binom{k}{z} = \sum_{k=0}^{N} \sum_{z=0}^{\min(C(E,p,k),k)} O(N^z)$$

But since $\log_2(p) < -1$, $\min(C(E, p, k), k)$ is an increasing function in k. Therefore

$$M \le \sum_{k=0}^{N} \sum_{z=0}^{\min(C(E,p,k),k)} O(N^{\min(C(E,p,k),k)}) \\ M \le O(N^{2+\min(C(E,p,N),N)})$$

Finally the complexity of the algorithm is a $O(n^{2+C(E,p,N)})$ where n is the number of variable. This is a large upper bound of the algorithm and if p and E are fixed $C(E, p, N) = \Omega(n)$. But this upper bound allows us to study the impact of p which represents the information we have about the probabilities over the variables. Given $m \ge 1$, E and N it is always possible to find a p enough small such that $C(E, p, N) \le m$. Indeed, $(\log_2(E) - N)/\log_2(p) \xrightarrow{p \to 0} 0$. More precisely, $(\log_2(E) - N)/\log_2(p) \le m$ implies $p \cdot E^{-1/m} \le 2^{-N/m}$.

# 10 Basic concepts

## 10.1 Logic

Before defining the context of this work, we briefly summarize basic logic programming concepts. We will follow the Prolog and Datalog convention :

* Atoms are expressions of the form $q(t_1, ..., t_n)$ where q is a predicate (of arity n) and the $t_i$ are terms.

* A literal is an atom or the negation $\neg q(t_1, ..., t_n)$ of an atom.

* A term t is either a constant c, a variable V, or a structured term of the form $f(u_1, ..., u_k)$ where f is a functor.
* According to the Prolog convention, constants start with a lower case character and variables with an upper case. Expressions that do not contain any variables are called ground.

* A substitution $\theta = \{V_1 = t_1, ..., V_n = t_n\}$ is an assignment of terms $t_i$ to variables $V_i$. When applying a substitution $\theta$ to an expression $e$ we simultaneously replace all occurrences of $V_i$ by $t_i$ and denote the resulting expression as $e\theta$.

* A rule is an expression of the form $h \leftarrow b_1, ..., b_n$ where $h$ is an atom and forms the head of the rule and the $b_i$ are literals and form the body of the rule. The meaning of such a rule is that $h$ holds whenever the conjunction of the $b_i$ holds. Thus ($\leftarrow$) represents logical implication ($\Leftarrow$), and the comma ($,$) represents conjunction ($\wedge$).

## 10.2 ProbLog : Probability logic

In order, to establish a link between reasoning and neural networks, DeepProbLog and its successor Scallop [14] are inspired by ProbLog [10] which is a natural probabilistic extension of the Prolog programming language. There is different ways of defining the probabilities over logic [5] and it would be very interesting to explore what kind of probability semantic better match neural networks needs in the learning but this is not the subject here.

A ProbLog program is a set $T = \{(c_i, p_i)|1 \le i \le N\}$ of rules and facts $c_i$ annotated by a probability $p_i$ which defines the probabilistic space $(\Omega, Pr, \mathcal{P}(\Omega))$ where :

* $\Omega = \{w_L | L \subset T\}$ where $w_L = \{w \in \Omega | w \models L \subset T\}$ is the set of all the models that satisfy the rules and facts of $L$ a subset of $T$.

* $Pr$ follows the distribution $Pr(\{w_L\}) = \prod_{(c_i, p_i) \in L} p_i \prod_{(c_j, p_j) \in T \setminus L} (1 - p_j)$

* For any assumption $f$, $Pr(f)$ is defined as $Pr(\{w_L|L \vdash f\})$

It is interesting to note that this definition suppose the $c_i$ to be independent. Moreover, the only information about the real probability distribution over the models comes from the probability annotations, that is why it is impossible to differentiate two models satisfying the exactly the same rules and facts of $T$. It implies that it is not possible to compute the probability of an assumption over the models but only over the possible combination of $c_i$. With the definition given, $Pr(f) \le$ the probability of $f$ to be true over the possible models, and the difference between the two depends of $T$.

## 10.3 DeepProbLog : Neural probabilistic reasoning

A DeepProbLog program is really similar to a ProbLog program but some $p_i$ are unknown and the objective is to train some neural network to predict them. In other words, we dispose of an incomplete database about the real world and the objective is to approximate it with neural networks by using known facts and rules to train them. More formally a DeepProbLog program is a quadruplet $D = (E, N, C, R)$ where :

* $E = \{e_i|1 \le i \le n\}$ is a set of entities.
* $N = \{(P_i, \mathbf{p}_i)|1 \le i \le k\}$ is set of predicates $P_i$ annotated by their probability function $\mathbf{p}_i : E^{arity}(p_i) \to [0, 1]$. Depending of $\mathbf{p}_i$ which could be a known function or a neural network, $P_i$ is called a probabilistic or a neural predicate.

* $C = \{C_i|1 \le i \le m\}$ is a set of predicates. A predicate of $C$ is a classic predicate.

* $R$ is a Prolog program over the predicates of $N$ and $C$.

This naturally define a ProbLog program $T = N' \cup R'$ where :

* $N' = \{(P(e_1, ..., e_{arity(P)}), \mathbf{p}(e_1, ..., e_{arity(P)})) | e_1, ..., e_{arity(P)} \in E \text{ and } (P, \mathbf{p}) \in N\}$ is the set of grounded atoms over the predicates of $N$ annotated by the corresponding probability.

* $R' = \{(r, 1)|r \in R\}$

Thus, it is possible to define probabilities over a DeepProbLog program as it is done for a ProbLog program and to use the same procedures to answer queries. Moreover, given a dataset of assumption $f$ with a known probability $p_f$, it is possible to train the neural networks of the neural predicates to match this probabilities using back-propagation through the logic reasoning. Indeed, $Pr(f)$ is always a sum of product of constant values and outputs of neural networks, therefore the loss function $L(Pr(f), p_f)$ is differentiable.

## 10.4 Probability computation

In a ProbLog program $T$, for any assumption $f$, $Pr(f) = \sum_{L \vdash f} \prod_{(c_i, p_i) \in L} p_i \prod_{(c_j, p_j) \in T \setminus L} (1 - p_j)$. A naive approach to compute this value would be to enumerate all the possible $L$ such that $L \vdash f$ and sum the product of the probabilities. But this is clearly infeasible, even for small programs since the number of subset of $T$ is exponential in the size of $T$. Instead, ProbLog and DeepProbLog proceed in two step :

* Firstly, the set $\mathbf{L} = \{L \subset T | L \vdash f\}$ is computed in the form of a formula of propositional logic where variables are the elements of $T$. If $T = \{(c_i, p_i)|1 \le i \le N\}$, a logic formula $F(c_1, ..., c_N)$ such that $L \vdash f \Leftrightarrow F(c_i \in L = \top, c_i \notin L = \bot)$ is computed. This allow to represent $\mathbf{L}$ in a compressed way. ProbLog do this through an adaptation of the SLD-resolution used by Prolog which compute $F$ in disjunctive normal form (DNF). Actually, this procedure is a particular case of provenance computation in database [22], $F$ is said to be the logic provenance of $f$

* Computing $Pr(f)$ is equivalent to computing the probability of $F$ where the probability of a model $m: T \to \{0, 1\}$ is $\prod_{m(c_i)=1} p_i \prod_{m(c_j)=0} (1-p_j)$. This problem is known as the weighted model counting problem (WMC) and is NP-hard. However, some graphical representation of logic formula such as Binary Decision Diagram allow to compute WMC in linear time in their size [10]. More generally, a set of structure from the knowledge compilation allow WMC to be computed in linear time in their size such as Sequential Decision Diagram [7] and deterministic Decomposable Negation Normal
Form which is a super set of all the forms cited above [6]. Another advantage of this solutions is that the computation of the compiled form (for example the Binary Decision Diagram) need to be done only once and can be reused for any probability distribution over the program.

## 10.5 Computing the gradient

During the learning phase in DeepProbLog, computing the gradient is necessary in order to perform gradient descent or one of its variation. Once an expression of $Pr(f)$ is known there two main way of computing gradient of the parameter for the loss function :

* Back propagation using automatic differentiation : This method use a computation graph to represent operations over data and use neighborhood relation to propagate the gradient through the graph. It is widely used by neural network library (pytorch, tensorflow ...) and is generally more efficient when the input space dimension is larger than the output space dimension (which is almost always the case in deep learning).

* Forward propagation which is easier to compute using dual number but generally it is less efficient when the input space dimension is larger than the output space dimension.

The solution adopted by DeepProbLog and Scallop is mixed. The gradient of the outputs of the neural networks is computed using dual number when computing the probability of assumptions and the loss. The gradient is then back propagated to the parameter of the neural networks by the automatic differentiation engine of the neural network library used (for example pytorch). This is not the object of this paper but it could be interesting to evaluate the gain of a full back propagation procedure. And to study which method of probability computation allow speedup of the gradient computing phase.

## 10.6 Example

Lets see an example of the working of DeepProbLog. Consider a set of entity $E := \{A, B, C, D, E\}$ and a neural probabilistic predicate $P$ over this set of entity with its probability function $p$ partially known (for example some edge are known to be absent or present but some edge are unknown). This relation could be represented as a probabilistic graph :
<figure><img src="image_5.png" /></figure>

This example is purely artificial and very small so it is possible to simply store the values of $\mathbf{p}(A, B), \dots, \mathbf{p}(E, F)$ directly. But in practice the entity set could be much larger then each entity would have an embedding (a vector representation) and $\mathbf{p}$ would be a neural network taking in input two embedding and returning a probability.

Assume information about the transitive closure of this relation are known. For example it is known that there is no path from $B$ to $F$. In order to use this kind of information to complete knowledge about $P$. The DeepProbLog program would have a classic relation $P^+$ representing the transitivity closure thanks to the rules :

$$P^+(X, Y) \leftarrow P(X, Y) \\ P^+(X, Z) \leftarrow P^+(X, Y), P(Y, Z)$$

It is known that $\neg P^+(B, F)$ hold. This mean that in our program $Pr(P^+(B, F))$ must be equal to 0. Hence DeepProbLog compute this probability using the two step described before.

First, it computes the logic provenance of $P^+(B, F)$ using the modified SLD-resolution of ProbLog. In this particular case of graph relation transitivity closure it correspond to find the paths from $B$ to $F$. The following formula is obtained $F := (P(B, C) \land P(C, F)) \lor (P(B, E) \land P(E, F))$.

Secondly, DeepProbLog compute WMC($F$) by firstly compiling $F$ into a BDD (fig. 3) and using algorithm (alg. 8). After simplification due to the fact that $\mathbf{p}(B, C)$ and $\mathbf{p}(B, E)$ are equal to 1, the following formula is obtained :

$$Pr(P^+(B, E)) = \mathbf{p}(E, F) + (1 - \mathbf{p}(E, F)).\mathbf{p}(C, F)$$
<figure><img src="image_6.png" /><figcaption>Figure 3: BDD of F</figcaption></figure>

The Loss := (Pr(P<sup>+</sup>(B, E)) − 0)² is then minimized with gradient descent algorithm leading p(E, F) and p(C, F) to be fixed to 0.

**Algorithm 8 PROBABILITY :** Calculating the probability of a BDD

**Require:** BDD node *n*

**Ensure:** Return the probability of the formula represented by *n*

If *n* is the 1-terminal then return 1

If *n* is the 0-terminal then return 0

let *h* and *l* be the yes and no children of *n*

prob(*h*) := call PROBABILITY(*h*)

prob(*l*) := call PROBABILITY(*l*)

return $p_n \cdot \text{prob}(h) + (1 - p_n) \cdot \text{prob}(l)$