A loss asks the model to prefer the constraint. An architecture makes the constraint part of the model. This lecture is about the second move — why it is a different object, what it guarantees, and what it costs. The short version: the program becomes a logic program inside the forward pass; its worlds are enumerated, compiled, or counted; and the answer is a normalized distribution over those worlds. The program is not a penalty on the side. It is the hypothesis space.
00 / The hookA classifier that votes, a program that decides.
A digit classifier looks at four cells. For each cell it returns a distribution over the values 1–4. A logic program says the four cells form a permutation: every value appears exactly once. The model does not return four independent argmaxes. It returns one distribution over the twenty-four rows that satisfy the program. The classifier supplies the numbers; the program decides which combinations of numbers are possible at all.
Make the arithmetic small enough to do by hand. Three cells, three values. The classifier's distributions are:
Without the program, the most likely assignment is (1, 1, 3), with weight 0.60 × 0.60 × 0.60 = 0.216. It is invalid: the value 1 appears twice. A loss that penalizes duplicates would keep this assignment in play and make it expensive. An architecture that executes the program gives it probability zero and renormalizes the rest.
There are six valid rows. Each has an unnormalized weight equal to the product of its three per-cell probabilities. The posterior is the weight divided by the sum of the six weights:
| Row (cell 1, 2, 3) | Product of probabilities | Posterior |
|---|---|---|
| (1, 2, 3) | 0.60 × 0.30 × 0.60 = 0.108 | 0.108 / 0.258 = 0.4186 |
| (2, 1, 3) | 0.30 × 0.60 × 0.60 = 0.108 | 0.108 / 0.258 = 0.4186 |
| (1, 3, 2) | 0.60 × 0.10 × 0.30 = 0.018 | 0.018 / 0.258 = 0.0698 |
| (3, 1, 2) | 0.10 × 0.60 × 0.30 = 0.018 | 0.018 / 0.258 = 0.0698 |
| (2, 3, 1) | 0.30 × 0.10 × 0.10 = 0.003 | 0.003 / 0.258 = 0.0116 |
| (3, 2, 1) | 0.10 × 0.30 × 0.10 = 0.003 | 0.003 / 0.258 = 0.0116 |
The normalizer is
Three observations matter. First, Z is the prior probability that the constraint holds: under the independent distributions, 25.8% of the mass is on all-different rows, and conditioning divides by exactly that number. Second, the prior's single most likely row is more probable than any individual valid row, so conditioning removes it and splits the mass between (1, 2, 3) and (2, 1, 3). Third, the constraint changes the ranking: the posterior MAP is not the prior MAP.
A loss changes the cost of a mistake. An architecture changes the set of possible answers.
That is the whole lecture in one example. The rest is the machinery that makes it work at scale, and the bill that comes with it. The general form is a sum over worlds:
Here σ is a complete assignment to the cells, pi is the neural distribution for cell i, I[·] is the indicator that the assignment satisfies the constraint, and Z(x) = Στ ⊨ C Πi pi(τi | x). The numerator is a product of local probabilities and a hard logical test. The denominator is the sum of those products over every assignment the program accepts. Nothing is approximated in the formula; the approximation, when it appears, is in how the sum is computed.
The example assumes the four per-cell distributions are independent and correct. Neither is guaranteed. A real classifier is correlated across cells, and its probabilities may be miscalibrated. The program is also assumed to be the right constraint. Exactness is conditional on both assumptions; §7 returns to this. The lab lets you vary the confidence of the per-cell distributions with a noise slider, but it cannot repair the program or make the cells dependent.
01 / Distribution semanticsWorlds, weights, and a sum.
The formal bridge between logic and probability is the distribution semantics, introduced by Sato in 1995 for logic programs with probabilistic facts. The idea is simple enough to state in one sentence: a probabilistic logic program describes a distribution over semantic objects, and the probability of a query is the total weight of the objects that satisfy it.
Start with a set of probabilistic facts, each written p::f., meaning that the ground atom f is true with probability p and false with probability 1 − p, independently of the others. A total choice selects a truth value for every probabilistic fact. Given a total choice, the ordinary logic program — the rules — determines which atoms are true. For a definite program (no negation, no disjunction in the head), the least model is unique. A possible world is the set of atoms true under one total choice. Its probability is the product of the probabilities of the selected facts and the complements of the unselected ones.
The ground terms form the Herbrand universe, and the ground atoms form the Herbrand base; with n probabilistic facts there are 2n total choices, so the naive world space is exponential. The logic program is what makes the distribution interesting: it collapses many choices into the same derived atoms and rules out combinations that violate its rules.
Let F be a finite set of independent probabilistic facts with probabilities pf, and let P be a logic program. For a total choice w ⊆ F, the world is the least model of P ∪ w (or a stable model, when P is non-monotonic). The probability of the world is Πf ∈ w pf · Πf ∉ w (1 − pf). The probability of a query q is the sum of the probabilities of the worlds in which q is true.
A concrete ProbLog program makes the accounting visible. The syntax is Prolog-like: facts, rules, and a query. The probabilities attach to facts, not to rules.
There are four total choices. The program's only rule says that q is true exactly when both a and b are true. The worlds and their weights are:
| a | b | q | Weight |
|---|---|---|---|
| true | true | true | 0.7 × 0.6 = 0.42 |
| true | false | false | 0.7 × 0.4 = 0.28 |
| false | true | false | 0.3 × 0.6 = 0.18 |
| false | false | false | 0.3 × 0.4 = 0.12 |
The query probability is a sum over the worlds that satisfy the query: P(q) = 0.42. This is already a weighted model count. Let φq be the Boolean formula that is true exactly on the worlds where q holds; here φq = a ∧ b. Give each literal a weight: w(a = 1) = 0.7, w(a = 0) = 0.3, and similarly for b. Then
and P(q) = WMC(φq) / WMC(true) = 0.42 / 1. The denominator is 1 because the weights of each variable sum to 1. If the program contains a constraint that some worlds violate, the denominator is the mass of the worlds that satisfy the constraint — exactly the Z of the all-different example. This is the sense in which a probabilistic logic program is a satisfiability problem with weights: the query is a formula, and inference is a weighted count of its models.
Three assumptions are doing work here, and each can fail. The probabilistic facts are assumed independent. The program is assumed to have a unique model per total choice; definite programs do, but negation or disjunction may yield several stable models. And the program is interpreted under a closed-world assumption: atoms not derived are false. ProbLog is a closed-world language, and that closure is what makes the world finite.
ProbLog's original inference method grounds the query-relevant part of the program, rewrites it as a propositional formula, compiles that formula into a d-DNNF circuit, and evaluates the circuit. The compilation step is where the cost lives; §6 takes it apart. For now the important point is structural: the logic program is not a black box that returns a truth value. It is a specification of a distribution over models, and the probability of a query is a sum over those models.
The distribution semantics is due to Sato, “A Statistical Learning Method for Logic Programs with Distribution Semantics” (ICLP 1995). ProbLog is De Raedt, Kimmig and Toivonen, “ProbLog: A Probabilistic Prolog and Its Application in Link Discovery” (IJCAI 2007). The weighted-model-counting view is developed in Fierens et al., “Inference and Learning in Probabilistic Logic Programs Using Weighted Boolean Formulas” (Theory and Practice of Logic Programming, 2015). These are cited by author, title, venue and year; none has an arXiv identifier in the course's source list.
02 / DeepProbLogNeural predicates and a circuit.
ProbLog gives the logic a distribution. DeepProbLog gives the distribution a perception. The extension is a new kind of fact, the neural predicate, written nn(m, x, D, y): a neural network m maps an input x to a distribution over a finite domain D, and y ranges over that domain. The network's output layer is normalized, typically by a softmax, so the scores become probabilities. From the logic program's point of view, the neural predicate is an ordinary annotated disjunction: a set of mutually exclusive head atoms with probabilities that happen to be computed by a network.
A ground neural predicate nn(m, x, D, y) selects the alternative y with probability pθ(y | x), where pθ is the network's normalized output over D. The probabilities of the alternatives sum to 1. The logic program sees an annotated disjunction whose head probabilities are supplied at grounding time by a forward pass of the network.
The query probability keeps ProbLog's possible-world semantics. During grounding, DeepProbLog runs a forward pass for every neural predicate it encounters; the normalized scores become the probabilities of that predicate's alternatives. The query-relevant program is then rewritten into a propositional formula and compiled into a Sentential Decision Diagram (SDD). The SDD is evaluated bottom-up: addition at OR nodes, multiplication at AND nodes. The result is the exact probability of the query under the program and the current network outputs.
The gradient is the elegant part. DeepProbLog uses a gradient semiring: each value in the circuit is a pair (probability, derivative), and the semiring operations propagate both. Addition at an OR node adds probabilities and derivatives; multiplication at an AND node applies the product rule. One evaluation of the circuit yields the query probability and its derivative with respect to every neural predicate output. The logic side hands that derivative to the network, and ordinary backpropagation carries it through the layers. The pipeline is differentiable end to end, but the differentiation is a structured pass over the circuit, not a generic autodiff over a discrete search.
A worked example is the MNIST addition task. Two images, two digit classifiers, one program:
The program says that the sum is the arithmetic sum of the two recognized digits. For the query sum(8), only the nine pairs (0, 8), (1, 7), …, (8, 0) satisfy the body; the other ninety-one pairs contribute zero. If both classifiers are uniform over ten digits, each pair has probability 0.01 and the query has probability 0.09. The program has removed 91% of the hypothesis space for this query. Training with only the sum label — no digit labels — backpropagates through the circuit and raises the probability of the nine consistent pairs. No accuracy number is quoted because the point is the mechanism, not a benchmark.
What is inside the computation graph? The network forward passes, the normalized annotated-disjunction probabilities, the grounded query formula, the SDD, and the gradient semiring. What guarantee does it give? The query probability is exact with respect to the program and the current neural predicate distributions: every program-consistent world is counted once, every inconsistent world gets zero, and the normalizer is the total mass of the consistent worlds. It is not a guarantee that the digit facts are true; a wrong classifier produces an exact probability for the wrong facts.
DeepProbLog's inference is exact for the compiled query, but the SDD can be exponentially large, and grounding can blow up before compilation begins. The paper's guarantee is about the semantics, not about the runtime. A program that is easy to write can still be impossible to compile at the scale you need.
03 / NeurASPStable models, enumerated.
NeurASP (Yang, Ishay and Lee, IJCAI 2020) takes a different route to the same destination. Instead of probabilistic facts inside a probabilistic logic program, it embeds neural networks into answer set programming (ASP). The neural predicate is written nn(m, x, y): the network m maps input x to a distribution over the possible values of y. The ASP program uses y like any other atom. The program has no probabilities of its own; the uncertainty comes from the network's choices, while ASP supplies the non-monotonic semantics.
The semantics is an enumeration over stable models. Fix a total choice of neural outputs. The ASP program — rules, constraints, negation, aggregates — has a set of stable models. Each stable model is a possible world. Its weight is the product of the probabilities of the neural choices that produced it. The probability of an atom is the sum of the weights of the stable models that contain it. If several choice combinations produce the same stable model, their weights add. If a choice combination produces no stable model, that combination has probability zero: the program has rejected it.
For a neural input x and an atom a, let S(x) be the stable models of the ASP program under the neural outputs for x. For a stable model M, let w(M) = Πnn ∈ M pθ(y | x) be the product of the chosen outputs' probabilities. Then P(a | x) = ΣM ∈ S(x), a ∈ M w(M) / Z(x), with Z(x) = ΣM w(M).
The running example is a four-cell row with an all-different constraint. Each cell has a neural predicate over 1–4; the ASP program says the four values are a permutation. There are twenty-four stable models before any clues; with clues, the models that conflict are removed. The lab is exactly this calculation. NeurASP's Sudoku experiment is the same calculation at 9 × 9, with row, column and box constraints adding many more stable models — and pruning enough of them to make enumeration practical.
Training is gradient descent on the negative log-likelihood of the observed atoms. Because the probability is a sum of products, the gradient with respect to each neural output is exact for the current enumeration. The discrete part — which stable models exist — receives no gradient; it changes only when the neural choices cross a boundary that makes a model appear or disappear. The function is smooth in the probabilities and discontinuous in the support.
What is inside the graph? The grounded ASP program, the stable-model enumeration, and the weighted sum. What guarantee? Exactness under the stable-model semantics, conditional on the ASP program and the neural distributions. What cost? The number of stable models and the size of the grounding. ASP's constraints are powerful, and they can prune the enumeration dramatically, but the worst case is exponential and the solver is doing real search, not a table lookup.
Yang, Ishay and Lee, “NeurASP: Embracing Neural Networks into Answer Set Programming” (IJCAI 2020; arXiv:2307.07700). The paper's Sudoku experiment trains a digit classifier from solution grids using the ASP rules as the only source of digit-level supervision. The claim is exact inference under the stable-model semantics, not a polynomial-time algorithm.
04 / ScallopProvenance, not just probability.
DeepProbLog and NeurASP both answer the same question: what is the probability of this query? Scallop (Li, Huang and Naik, PLDI 2023) generalizes the question. Its language is a typed Datalog with recursion, stratified negation, and stratified aggregation. Every derived tuple carries a provenance tag: a description of how the tuple was derived. The tag is combined with a semiring, and different semirings give different notions of inference from the same program.
The idea is old and good: a proof is a structured object, and evaluating it in different algebras gives different questions. In the Boolean semiring, a tuple is true or false. In the probability semiring, disjunction is a + b − a·b (for independent proofs) and conjunction is a·b. In the min-plus semiring, disjunction is minimum and conjunction is addition. In a top-k semiring, a tuple keeps the k best proofs. One engine, many inference notions.
Scallop compiles a program to a relational algebra and evaluates it to a fixpoint. Each tuple's tag is propagated through the algebra: union combines disjunction, join combines conjunction, difference handles negation, and aggregation applies an aggregator such as count, sum, max, or exists. The provenance is the derivation structure, and the semiring is the interpretation. The same program can express exact probabilistic inference and approximate top-k inference without changing a rule.
Differentiation works on the semiring values. A differentiable provenance uses dual numbers: each input probability becomes a pair (r, e) of value and derivative, and every operation propagates both. An external interface maps the neural network's outputs into the semiring's input values and recovers the output probabilities, so gradients flow from the query back to the neural inputs. The gradient is exact for the computation that was actually performed; the question is whether that computation was the full sum or a truncation.
Consider two parallel paths from s to t. Path 1 has edges with probabilities 0.9 and 0.9, so its probability is 0.81. Path 2 has edges with probabilities 0.8 and 0.8, so its probability is 0.64. The paths are edge-disjoint, so the probability that at least one path exists is
This is the exact sum over all proofs. A top-1 provenance keeps only the best proof, 0.81, and reports that as the probability. The number is not wrong as a ranking of the best path; it is wrong as the probability of reachability. Top-2 would recover 0.9316 here, because there are only two proofs. In a graph with many paths, the gap between top-k and the exact sum is the approximation you chose to make.
| Setting | What is kept | Value | What the value means |
|---|---|---|---|
| Exact (sum-product) | All proofs | 0.9316 | Probability that some path exists |
| Top-2 | The two best proofs | 0.9316 | Exact here; approximate in general |
| Top-1 | The best proof | 0.8100 | Probability of the best path, not of reachability |
What is inside the graph? The grounded relational algebra, the provenance tags, the retained proofs, and the semiring evaluation. What guarantee? Exactness for the chosen semiring if the provenance is not truncated. With top-k, the value is an approximation and the gradient is the gradient of the approximation: it flows only through the retained proofs, so paths outside the top-k get no signal. What cost? The number of proofs, the cost of the semiring operations, and the weighted model count at the end. Scallop's paper notes that weighted model counting is #P-complete, so increasing k buys accuracy at a real price.
“Differentiable Datalog” is not one semantics. A probabilistic semiring, a top-k semiring, and a min-plus semiring answer different questions from the same rules. A result that is exact under one provenance can be an approximation under another. When you read a Scallop paper, look for the provenance and the value of k before you compare it with a probabilistic logic program.
05 / ULLEROne language, several semantics.
The previous three systems each commit to a language and a semantics. DeepProbLog is probabilistic logic programming; NeurASP is answer set programming with neural choices; Scallop is Datalog with provenance semirings. ULLER (van Krieken, Badreddine, Manhaeve and Giunchiglia, 2024) asks a different question: can one declarative language express the knowledge base, and let the user choose the semantics afterwards?
ULLER is a neurosymbolic first-order language. It has quantifiers over domains, Boolean connectives, predicates, terms with arithmetic and property access, and function application. The distinctive syntactic form is the statement binding x := f(T, …)(F), which composes data and neural functions while delimiting variable scope and memoization. There is no dedicated neural syntax: a neural network is simply a function, and the language does not care whether the function is a table, a closed-form expression, or a network.
The semantics is model-theoretic. An interpretation assigns domains, Boolean predicates, constants, and functions. Functions are interpreted as conditional probability distributions, with deterministic functions as a special case. A neurosymbolic structure adds a variable assignment and a semantics function. Because the semantics function is a parameter, the same program can be evaluated under several regimes:
| Semantics | Boolean connectives | Function application | What the value means |
|---|---|---|---|
| Classical | Minimum and maximum | The mode of the distribution | A truth value in {0, 1} |
| Fuzzy | t-norms and t-conorms | A value in [0, 1] | A degree of satisfaction |
| Probabilistic | Product and expectation | A sum over values | A probability, computed by weighted model counting |
| Sampling | Classical after draws | A draw from the distribution | A Monte Carlo estimate |
The probabilistic semantics is the one that connects to this lecture. For a closed, statement-free, finite-domain formula, it agrees with weighted model counting. Probabilistic evaluation is generally exponential; compiling formulas into tractable representations can accelerate it but is not guaranteed. The fuzzy semantics is defined for finite domains only. The sampling semantics is an approximation, useful when exact counting is out of reach.
What is inside the graph? The grounded statements, the function applications — including neural networks — and the semantics operators for the chosen regime. A quantifier expands over its domain; a conjunction applies the semantics' conjunction; a function application evaluates a conditional distribution. What guarantee? Exactness relative to the chosen semantics, not across semantics. The probabilistic value is exact when the count is exact; the sampling value is an estimate; the classical value is exact but piecewise constant, which matters for gradients. What cost? The size of the grounded formula and the cost of evaluation. ULLER defines evaluation, not a compilation pipeline; the engineering is left to the implementation.
The value of ULLER is comparative. It makes the semantics an explicit argument, so two systems that disagree can be compared on the same program rather than on two different encodings. It also makes the cost of a semantic choice visible: classical logic gives no gradient, fuzzy logic a graded value, probabilistic logic a count, sampling an estimate. The price is that ULLER is a language and a semantics framework, not a turnkey solver; it does not remove the need for grounding, compilation, or a tractable fragment.
ULLER is van Krieken, Badreddine, Manhaeve and Giunchiglia, “ULLER: A Unified Language for Learning and Reasoning” (arXiv:2405.00532, 2024).
06 / Exact inferenceThe cost of counting.
In their probabilistic semantics, all four systems reduce to a weighted count. The count is exact in DeepProbLog and NeurASP (for the compiled or enumerated objects), conditional in Scallop (on the provenance and k), and semantic in ULLER (on the chosen semantics). The cost is the same in each case: the number of objects that have to be counted, and the size of the representation that makes counting efficient.
Weighted model counting is #P-hard in general. This is not a claim about a particular solver; it is a statement about the problem. Counting the satisfying assignments of a propositional formula is #P-complete, and WMC generalizes it. A polynomial-time algorithm would imply P = #P, which is not expected. The practical response is knowledge compilation: compile the formula into a representation where the count is linear in the size of the representation. A d-DNNF circuit is decomposable (the children of an AND node share no variables) and deterministic (the children of an OR node are mutually exclusive). Those two properties make the weighted count a bottom-up sum-product evaluation. An SDD is a canonical form with the same property.
The cost of each system is the cost of its compiled object:
| System | Inside the graph | Inference | Guarantee | Cost |
|---|---|---|---|---|
| DeepProbLog | Network forwards, annotated-disjunction probabilities, grounded formula, SDD, gradient semiring | Compile the query, evaluate the SDD, differentiate the circuit | Exact query probability given the neural predicates | SDD size, grounding, one forward pass per predicate |
| NeurASP | Grounded ASP program, stable-model enumeration, weighted sum | Enumerate stable models, sum their weights, backpropagate | Exact under stable-model semantics | Number of stable models, grounding, solver time |
| Scallop | Grounded relational algebra, provenance tags, retained proofs, semiring evaluation | Fixpoint over the algebra, then WMC over the retained proofs | Exact for the semiring if not truncated; approximate for top-k | Proof count, WMC, the value of k |
| ULLER | Grounded statements, function applications, semantics operators | Semantic evaluation; WMC for the probabilistic semantics | Exact relative to the chosen semantics | Formula size; exponential in general; compilation optional |
The practical question is not “is this #P-hard?” — everything interesting is. The question is which structure makes the count small. Many independent choices multiply the count. Shared subgoals let the circuit reuse work. A determinate program avoids the extra blow-up of multiple stable models. Bounded treewidth admits a compact circuit. Recursion is cheap when the grounding is finite and the provenance is shared, and expensive when it generates infinitely many proofs. Aggregation and negation add non-monotonic structure that can defeat the simple decompositions.
Numerical care is part of the cost. Z can be exponentially small; a naive product underflows before the posterior is computed. Log-space evaluation, or a scaled semiring, is not an optimization; it is a requirement for deep programs. The lab uses twenty-four rows and ordinary floating point, which is safe. A real program with hundreds of independent choices is not.
07 / What it buys and costsThe ledger, and the line between loss and architecture.
It is worth stating the difference between the two interfaces precisely, because the words “loss” and “architecture” are often used as if they were two strengths of the same thing. They are not. A loss is a term in an objective; an architecture is a constraint on the model class. The difference is visible in the equations.
In (8.6), the model's output space is unchanged. Rφ is a differentiable penalty that is small when the output satisfies the constraint and large when it does not. The weight λ decides how much the penalty matters. At inference, the model can still output an invalid assignment; the penalty has made that assignment expensive during training, not impossible. The guarantee is empirical, and the gradient is the gradient of the penalty, not of a semantics.
In (8.7), the model's output space is the set of assignments that satisfy the program. The indicator is inside the sum, so an inconsistent assignment contributes zero. The denominator Z(x) redistributes the mass over the consistent assignments. The gradient flows through the normalizer as well as the numerator, which is why the model learns to make the consistent set probable rather than merely to avoid a penalty. The guarantee is semantic: the output is the exact posterior under the program and the neural distributions. It is not a guarantee that the program is true, or that the neural distributions are calibrated.
A loss changes the cost of a mistake; an architecture changes the set of possible answers. The loss has a weight λ; the architecture has a normalizer Z. The loss can be added to any model; the architecture requires an inference procedure. The loss guarantees nothing at inference; the architecture guarantees exactness relative to its program.
The ledger follows from the equations.
| What it buys | What it costs |
|---|---|
| A hard constraint by construction: invalid worlds get zero mass | Inference is #P-hard in general; exactness can be exponentially expensive |
| An exact posterior relative to the program and the neural predicates | The program must fit the engine's fragment: grounding, stratification, finite domains |
| Compositional structure: the program defines how local percepts combine | Independence assumptions: probabilistic facts and neural predicates are independent unless modeled otherwise |
| Weak supervision at the query level: learn perception from symbolic labels | Calibration: a miscalibrated network yields an exact posterior for the wrong probabilities |
| Inspectable worlds, proofs, and derivations | Gradient quality: exact gradients can saturate, and top-k or classical semantics can bias them |
| End-to-end training through the symbolic executor | Engineering: compilers, solvers, memory, and debugging are part of the product |
Gradient quality is not the same as gradient existence
All four frameworks can produce a gradient for some semantics. That does not mean the gradient is useful. The probability of a query is a polynomial in the neural predicate probabilities, so it is differentiable wherever the set of worlds is fixed. But several things can go wrong.
Saturation. If the query probability is near 0 or 1, the gradient of the negative log-likelihood can be tiny or huge. A confident and wrong network is hard to move, because the posterior has collapsed onto a world and the others receive almost no weight. This is a saturated softmax, amplified by the normalizer.
Piecewise structure. The set of stable models, the set of retained proofs, and the support of the posterior can change discontinuously as the parameters move. The gradient is exact on each piece and undefined at the boundary. NeurASP's enumeration and Scallop's top-k selection are both piecewise: the value is smooth in the probabilities, but which probabilities are summed is a discrete choice.
Top-k bias. A top-k provenance differentiates the truncated sum, not the full one. The gradient points toward improving the retained proofs, which can be right for a ranking loss and wrong for a probability. The bias is controlled by k, and the cost grows with it.
Classical semantics and calibration. Under a classical semantics the value is 0 or 1 almost everywhere, so the gradient is zero almost everywhere; ULLER can express classical logic but cannot make it trainable by gradient descent alone. And the architecture treats neural outputs as probabilities: if they are miscalibrated, the posterior is exact for the wrong numbers. The logic cannot repair a probability it was handed.
The practical rule is to evaluate the gradient, not just the loss: measure whether the neural parameters move in the direction that improves the end task, and whether the posterior is sharp for the right reason. An exact posterior over the wrong worlds is still wrong.
When to use this interface
Use logic as an architecture when the constraint is hard, the program is stable, and the query is small enough to count or compile. Use a loss when the constraint is soft background knowledge, the output space must stay unconstrained, or the cost of exact inference is prohibitive. Use a verifier when the guarantee you need is about the final answer rather than the model's distribution. Use search when the program itself is unknown; the architecture assumes the program is given. These are not exclusive: a system can use an architecture for the hard constraint, a loss for a soft preference, and a verifier for the deployed output.
The weakest claim in this lecture is the one that sounds strongest: “exact semantics.” It is exact relative to a program and a set of neural distributions, both of which can be wrong. The caveat belongs on the same page as the claim, and it is the reason the lab reports Z and the prior as well as the posterior. Exactness is a property of the computation, not a certificate about the world.
08 / Cases and recapRead the system, then the guarantee.
Four systems, one anatomy. Each has a language, an object inside the computation graph, an inference procedure, a guarantee, and a cost. Read them along the same tuple and the differences become design choices rather than brand names.
DeepProbLog
A neural predicate is an annotated disjunction whose probabilities come from a network. The query is compiled to an SDD and differentiated with a gradient semiring. Inside the graph: network forwards, the grounded formula, the circuit, and the derivative.
NeurASP
Neural outputs become atoms in an ASP program. The stable models are the worlds; each is weighted by the neural choices that produce it. Inside the graph: the grounded program and the enumeration. The Sudoku experiment trains perception from solution grids.
Scallop
A Datalog program with provenance tags, evaluated in a semiring. The same rules can answer probabilistic, shortest-path, or top-k questions. Inside the graph: the grounded relational algebra, the retained proofs, and the semiring evaluation. Top-k is an approximation.
ULLER
One first-order language; functions are conditional distributions; the semantics is an argument. Classical, fuzzy, probabilistic, and sampling evaluations share the same program. Inside the graph: grounded statements and semantics operators. The probabilistic value is WMC; the guarantee is relative to the semantics.
Two comparisons are worth carrying away. DeepProbLog and NeurASP both give exact inference, but they count different objects: DeepProbLog counts worlds through a compiled circuit, while NeurASP enumerates stable models of an ASP program. Scallop and ULLER generalize the semantics rather than the solver: Scallop with provenance semirings inside Datalog, ULLER with a semantics parameter over a first-order language. None makes the exponential disappear; each chooses where to put it.
The lab is a four-cell all-different row. Four per-cell distributions over 1–4, twenty-four valid permutations, and an exact posterior computed by enumerating all twenty-four. The controls are a noise slider and a constraint toggle. Turn the constraint off and the posterior is the prior; turn it on and the mass is renormalized over the valid rows. The Z display is the probability that the constraint holds under the prior. No sampling, no libraries, no network.
Define distribution semantics: probabilistic facts, total choices, worlds, and a query probability that sums over the worlds.
Write the posterior as a normalized product of neural probabilities and a constraint indicator, and identify Z.
Explain what DeepProbLog puts inside the graph: neural predicates, the grounded formula, the SDD, and the gradient semiring.
Explain NeurASP's stable-model enumeration and why its exactness is conditional on the ASP program.
Distinguish Scallop's exact semiring from its top-k approximation, and say what the gradient loses in each case.
State the loss-versus-architecture distinction in one sentence and in two equations.
Exercises
- Verify the hook. Recompute Table 0.1 from the distributions in (8.1). Confirm Z = 0.258 and the two MAP rows. Then change
p3to (0.05, 0.85, 0.10) and recompute. Which two rows tie for the MAP, and why? - Turn the constraint off. In the lab, switch the constraint off. Explain why Z = 1 and why the displayed MAP can be invalid. Switch it on and explain where the invalid mass went.
- Uniform noise. Set the noise to 100%. Show that the posterior over the twenty-four rows is uniform and that every posterior marginal is 0.25. What did the logic contribute? What did it not contribute?
- A ProbLog program. Write a program with three probabilistic facts and a query that is true when at least two facts are true. Enumerate the eight worlds and compute the query probability by hand. Check it with the WMC formula.
- DeepProbLog versus NeurASP. Take the four-cell all-different row. Describe what DeepProbLog would compile and what NeurASP would enumerate. Which is smaller for this example, and which is easier to extend to 9 × 9 Sudoku?
- Top-k. In the two-path example, compute the exact probability and the top-1 value. Construct a third path with probability 0.5 and show how top-2 and exact diverge.
- The support argument. Write the loss form and the architecture form for the all-different row. Explain why the loss can assign positive probability to
(1, 1, 3)and the architecture cannot. - Design review. Choose a task with a hard constraint (a schedule, a medical code, a robot safety rule). State the program, the neural predicates, the independence assumptions, the inference cost, and the calibration check you would run.
Check your understanding
Ten questions, with explanations. The score is not the point; the questions you cannot answer are the reading list.
Reading list
The first five are the spine of this lecture. The rest are the next layer.
DeepProbLog: Neural Probabilistic Logic Programming
Manhaeve et al. · NeurIPS 2018 · neural predicates and the gradient semiring
NeurASP: Embracing Neural Networks into Answer Set Programming
Yang, Ishay & Lee · IJCAI 2020 · stable models and the Sudoku case
Scallop: A Language for Neurosymbolic Programming
Li, Huang & Naik · PLDI 2023 · Datalog, provenance semirings, top-k
ULLER: A Unified Language for Learning and Reasoning
van Krieken et al. · 2024 · one language, several semantics
Sato, “A Statistical Learning Method for Logic Programs with Distribution Semantics”
ICLP 1995 · the origin of the distribution semantics
De Raedt, Kimmig & Toivonen, “ProbLog: A Probabilistic Prolog and Its Application in Link Discovery”
IJCAI 2007 · probabilistic facts and exact inference
Fierens et al., “Inference and Learning in Probabilistic Logic Programs Using Weighted Boolean Formulas”
Theory and Practice of Logic Programming, 2015 · WMC as the inference engine
Darwiche & Marquis, “A Knowledge Compilation Map”
Journal of Artificial Intelligence Research, 2002 · d-DNNF and the tractability landscape
From Statistical Relational to Neuro-Symbolic Artificial Intelligence
Marra et al. · 2020 · where the architecture interface sits
Neural-Symbolic Computing: An Effective Methodology for Principled Integration of Machine Learning and Reasoning
Garcez et al. · 2019 · the integration agenda
Every number in this guide is computed from a stated toy distribution: the six-row all-different table, the two-fact ProbLog worlds, the two-path reachability, and the DeepProbLog uniform-digit example. No benchmark accuracy, runtime, or dataset statistic is claimed. The system descriptions follow the cited papers; the figures are schematics, not reproductions.