DeepProbLog: Neural Predicates and the Gradient Semiring

📍 Where we are: Part II · Probabilistic Logic and Circuits — Chapter 7. Circuits compiled a query's formula into a smooth d-DNNF (deterministic decomposable negation normal form) that a single upward (+, ×) pass counts exactly; this chapter puts a neural network underneath the circuit's leaves and sends learning backward through that same pass.

Part II has assembled a pipeline in three moves: the distribution semantics turned a logic program with probabilistic facts into a distribution over possible worlds, weighted model counting (WMC) turned query probability into a sum over satisfying assignments, and knowledge compilation turned that #P-hard sum into one cheap pass over a circuit. One question has been quietly deferred the whole time: where do the probabilities on the facts come from? Writing 0.9::advises(alice, bob) by hand is fine for a textbook knowledge base and hopeless for perception. Nothing hand-written can assign a probability to "this photograph shows the digit 3" or "this document is about logic." DeepProbLog answers by letting a neural network write the probabilities: a neural predicate is a probabilistic fact whose probability is a network output, the program above it is ordinary ProbLog, and the whole stack trains end to end because exact inference itself is differentiable [1]. This chapter builds the mechanism in full: the annotated disjunction that a softmax head defines, the gradient semiring that makes one circuit pass return both the query probability and its exact gradient, and the payoff, distant supervision, where the logic program acts as the labeling function for a classifier that never sees a label.

The simple version

Imagine teaching a child to judge pairs of animal photos, saying only "same kind" or "different kind," never naming a single animal. To answer "same kind" at all, the child must privately decide what each photo shows; your same/different feedback reaches those private decisions through one rule, "same kind means both my private labels agree." Praise for a correct "same" strengthens whichever pair of matching private labels explained it; correction for a wrong "same" weakens them. After enough pairs the child sorts photos into kinds perfectly, though you never once said "cat." DeepProbLog is this loop made exact: the private decision is a softmax, the rule is a logic program, and the praise is a gradient routed backward through exact probabilistic inference.

What this chapter covers

• The architecture, formally: a linear-softmax classifier on 2-D document features becomes a neural annotated disjunction over topic(D, logic), topic(D, ml), topic(D, nesy); one Prolog rule defines relevance; and the query probability comes from Part II's exact pipeline: ground, compile, count.
• One categorical, not three coins: why a softmax head is a single mutually exclusive choice, how the companion encodes that exclusion in the worlds themselves, and the committed numbers showing the independent-coins misreading leaking almost half its probability mass onto impossible worlds.
• The gradient semiring, derived: differentiate the circuit evaluation of the previous chapter and watch the sum rule and the product rule assemble themselves into a semiring on pairs (value, gradient), with the associativity of ⊗ verified in full.
• One pass, both answers: the upward pass that returns $P(\text{query})$ and every $\partial P/\partial(\text{softmax output})$ simultaneously, certified against central finite differences to 2.7e-13, then chained by hand through the softmax Jacobian to the linear weights, certified again to 2.0e-11.
• Training by entailment: cross-entropy on the query probability against relevant/irrelevant pair labels alone drives the hidden topic classifier to 100% on the six documents; we read the committed trace and explain exactly why the credit lands on the right latent decisions.
• The scale ledger: exact grounding and compilation is the honest cost, with successor evaluations reporting the limit near four-digit MNIST addition, and the approximation lines (top-k proofs, derivation semantics) that trade exactness for reach.

The architecture: a network under the leaves

The whole construction is three layers, and the companion deepproblog_mini.py miniaturizes each one onto the academic world. The perception layer is a classifier: each of six documents presents a feature vector $\mathbf{x}_d \in \mathbb{R}^2$ (two real numbers per document, the stand-in for an image's pixels), and a linear layer plus softmax maps it to a probability vector over $K = 3$ topics, where $K$ is the number of topics. The documents are the three papers p1, p2, p3 of the running example, their hidden topics read from Volume 3's kg graph and never retyped, plus three new manuscripts m1, m2, m3 that complete each topic to a two-document cluster (deepproblog_mini.py lines 89–98). The logic layer is the two-line ProbLog program the module prints at startup:

  nn(m_topic, [D], [logic, ml, nesy]) ::
      topic(D, logic) ; topic(D, ml) ; topic(D, nesy).
  relevant(D1, D2) :- topic(D1, T), topic(D2, T).

The first statement is DeepProbLog's one new construct, the neural annotated disjunction (nAD) [1]. Decode it piece by piece. An annotated disjunction (AD) in ProbLog is a probabilistic choice among several heads: the annotation gives each head's probability, the probabilities sum to at most one, and any remaining mass goes to the outcome in which no listed head fires. The prefix nn(m_topic, [D], [logic, ml, nesy]) says those probabilities are not written by hand; they are the outputs of the network named m_topic applied to document D, one output per listed value. A softmax head is the saturated special case: it produces $K$ non-negative numbers summing to exactly one, leaving no mass for the no-head outcome, so the nAD declares them the probabilities of the $K$ mutually exclusive ground atoms topic(D, logic), topic(D, ml), topic(D, nesy), exactly one of which holds. The second statement is ordinary logic: two documents are relevant to each other when some topic T is the topic of both. The inference layer is Part II's exact pipeline unchanged: ground the query, compile the resulting propositional formula into a smooth deterministic decomposable circuit, and evaluate. In the journal source of record this pipeline, grounding, compilation to Sentential Decision Diagrams (SDDs), and semiring evaluation, is the entire system; the network is just another supplier of leaf weights [2].

The perception task is deliberately tiny so every number stays inspectable. Each topic owns a cluster center in the feature plane, and each document sits at its hidden topic's center plus Gaussian scatter (deepproblog_mini.py lines 96–110). The committed run prints the world:

      doc    x1      x2      hidden topic
      m1     0.044   2.154   logic
      m2     2.424  -1.163   ml
      m3    -2.387  -1.073   nesy
      p1     0.456   2.531   logic
      p2    -2.446  -1.643   nesy
      p3     1.982  -1.186   ml

The "hidden topic" column is the crucial fiction: it exists in the file only to generate pair labels and to score the final classifier. Training never sees it. What training sees is the label of each of the $\binom{6}{2} = 15$ document pairs (the binomial coefficient $\binom{6}{2}$ counts the unordered pairs of six items): $y = 1$ for the 3 pairs sharing a hidden topic, $y = 0$ for the other 12 (deepproblog_mini.py lines 118–120). This is distant supervision: the observable signal (relevance) is connected to the latent decision (topic) only through the logic program.

Grounding relevant(A, B) for a document pair unfolds the rule into a disjunction over the shared topic: it holds exactly when both documents chose logic, or both chose ml, or both chose nesy. The module compiles that formula once, with placeholder slots A and B, into a circuit over $2K = 6$ Boolean indicator variables topic(A,t), topic(B,t), and reuses the compiled circuit for every pair by rebinding the leaf weights (deepproblog_mini.py lines 128–166), the same compile-once-evaluate-often pattern the real system uses for its SDDs [2]. The compiler is the previous chapter's circuit.py; its structural guarantees are re-checked here as code, not assumed (deepproblog_mini.py lines 461–466):

      query            terms  vars  nodes  edges  pass-throughs
      relevant(A,B)        3     6     18     22        0
      irrelevant(A,B)      6     6     26     36        0
      structure: decomposable + deterministic (structural and all-64-assignment
      enumeration) + smooth as compiled — checked as code, PASS

The second row is a cross-check, not a training target: irrelevant(A, B) grounds the complement (A has exactly topic $t$, B exactly topic $u$, over the six ordered pairs with $t \ne u$; deepproblog_mini.py lines 147–151), and for every document pair the harness asserts that the two circuits partition the one-hot worlds, $P(\text{relevant}) + P(\text{irrelevant}) = 1$. The gradient half of that identity, checked once the machinery below exists, is subtler: because the leaf slots are treated as free parameters, the two gradients sum not to the zero vector but to the all-ones vector (with free slots, the sum $P(\text{relevant}) + P(\text{irrelevant})$ works out to the product of the two documents' total leaf masses, and the partial derivative of that product with respect to any one slot is the other document's total mass, exactly $1$ once the softmax normalizes each document's three slots to sum to one), and it is the softmax Jacobian derived later in this chapter that annihilates exactly that direction, so the cancellation does hold at the logit level (deepproblog_mini.py lines 483–497). Keep an eye on the last column too: once the leaves carry this chapter's categorical weights, a nonzero pass-through count would be a silent arithmetic error rather than a cosmetic detail, and the gradient-semiring section explains exactly why zero is required.

One structure, two directions: forward, a softmax fills the leaves of a compiled circuit and one pass computes P(relevant); backward, the same pass's gradient semiring routes credit through the logic to the softmax and its weights. Original diagram by the authors, created with AI assistance.

One categorical, not three coins

Before any gradient can flow, the encoding must be right, and there is a genuinely easy way to get it wrong. A softmax head over three topics is one random choice with three outcomes: a categorical distribution. It is not three independent yes/no facts. If we modeled topic(m1, logic), topic(m1, ml), topic(m1, nesy) as three independent probabilistic facts, three coins, the possible worlds for one document would be all $2^3 = 8$ subsets of the three atoms, including worlds where m1 has two topics and a world where it has none. The distribution the softmax actually defines has exactly $K = 3$ worlds per document: one per topic. The worlds must range over the $K$ choices, not the $2^K$ subsets.

The companion encodes this in the grounding itself. Each disjunct of relevant(A, B) is completed to a full one-hot world description: the term for topic $t$ asserts topic(A,t) true and the other two indicators false, and likewise for B, six signed literals per term (deepproblog_mini.py lines 132–144):

def _one_hot(slot: str, t: str) -> dict[str, bool]:
    """The indicator literals saying slot's document has EXACTLY topic t:
    topic(slot,t) true, topic(slot,t') false for both other topics.  This is
    how the nAD's mutual exclusion enters the worlds — a document never
    carries two topics or none in any model of the formula."""
    return {f"topic({slot},{u})": (u == t) for u in TOPICS}


def relevant_dnf() -> list[dict[str, bool]]:
    """Ground relevant(A,B) = ∨_T (topic(A,T) ∧ topic(B,T)), each disjunct
    completed to a full one-hot world description (6 signed literals):
    the T-th term says "A has exactly T and B has exactly T"."""
    return [{**_one_hot("A", t), **_one_hot("B", t)} for t in TOPICS]

The weights complete the encoding: a positive indicator topic(S,t) is weighted by the softmax output $\pi_t$, and a negated indicator is weighted by the constant $1$, not by $1 - \pi_t$ (deepproblog_mini.py lines 195–213). This is the standard categorical indicator encoding, and the constant $1$ is the point: the world "A has exactly topic logic" should carry mass $\pi_{\text{logic}}$, full stop, and the two negated literals in its description are bookkeeping that must not tax it. With one-hot terms and these weights, each legal world's weight is the product of the softmax entries it chose, every illegal world satisfies no term, and the count over the circuit is exactly

$$P(\text{relevant}(A,B)) \;=\; \sum_{t \in \{\text{logic, ml, nesy}\}} \pi_{A,t}\, \pi_{B,t},$$

where the summation symbol $\sum_t$ says: for each of the three topics $t$ in turn, form the product of the two documents' probabilities for that topic, then add the three products up. The harness asserts this sum against the circuit to $10^{-12}$ for all 15 pairs (deepproblog_mini.py lines 483–488). Recall from the circuits chapter why determinism mattered: an OR whose children can be true together double counts under $\oplus$, the semiring addition an OR node performs. Circuit-level determinism is the compiler's guarantee: the Shannon expansion makes every OR a decision on one variable, whatever the input formula. What the one-hot encoding buys is semantic. It makes the formula's models exactly the legal one-hot worlds, so the three disjuncts of relevant are pairwise disjoint events and summing their probabilities is honest.

The module keeps the wrong reading alive as an exhibit, coins_dnf(): bare two-literal terms with Bernoulli weights $w(x) = \pi$, $w(\lnot x) = 1 - \pi$ (deepproblog_mini.py lines 154–160). On the untrained network, for the logic-cluster pair (m1, p1):

[4] the nAD is ONE categorical, not 3 independent coins (pair m1, p1)
      correct (one-hot worlds) P(relevant) = 0.470735  = sum_t pi_A,t pi_B,t
      3-coin reading           P(relevant) = 0.421794  = 1 - prod_t (1 - pi_A,t pi_B,t)
      coin mass on legal exactly-one worlds for one document: 0.501081
      (the rest sits on impossible worlds: a document with two topics or none)

The two readings disagree by almost five points of probability ($0.470735 - 0.421794 = 0.048941$), and the last line is the diagnosis: under independent coins, the probability that m1 has exactly one topic is $\sum_t \pi_t \prod_{t' \ne t} (1 - \pi_{t'}) = 0.501081$, where the product symbol $\prod_{t' \ne t}$ multiplies one factor $(1 - \pi_{t'})$ for each of the other two topics $t'$, so each term reads: topic $t$'s coin lands heads and both other coins land tails. That total is barely half, so almost half the coin model's mass sits on worlds the softmax says are impossible. The coin formula $1 - \prod_t (1 - \pi_{A,t}\pi_{B,t})$ is the probability of a union of three independent events, computed as one minus the probability that no topic matches; the union arithmetic is needed precisely because under coins the events "both have topic $t$" can overlap (documents may carry two topics at once), while the categorical formula is a clean sum over disjoint worlds. Both are computed by correct circuits; the coin version answers a different, wrong question. The companion asserts the visible disagreement and the mass leak (deepproblog_mini.py lines 508–514). One more sanity anchor: in the one-hot limit of the softmax (leaf probabilities set to exact 0/1, values the softmax itself can only approach) the semiring pass degenerates to Boolean logic and returns exactly $1.0$ when the two topics match and exactly $0.0$ otherwise, verified for all $9$ combinations (deepproblog_mini.py lines 371–387). Crisp logic sits inside this machinery as the crisp limit, the recurring soundness anchor of this volume.

The gradient semiring, derived

Now the heart of the chapter. The previous chapter's evaluator walks the circuit bottom-up: each leaf carries a weight, each AND node multiplies its children, each OR node adds them, and the root value is $P(q)$ (circuit.py lines 336–366). Training needs one more thing: the derivative of that root with respect to every network output. Collect the six softmax outputs feeding the leaves into a vector $\mathbf{v} \in \mathbb{R}^6$ ("$\mathbb{R}^6$" is the space of lists of six real numbers, one slot per indicator variable), and ask for the gradient $\nabla P = (\partial P/\partial v_1, \ldots, \partial P/\partial v_6)$, the vector of all six partial derivatives. We could run the circuit six extra times with nudged weights, but there is something better: differentiate the pass itself.

Suppose that at some node we know both the node's value $a_1$ and its gradient $\vec{a}_2 = \nabla a_1$, the derivative of that value with respect to all six leaf parameters, and likewise $(b_1, \vec{b}_2)$ for a sibling. What does the parent know?

At an OR node, the value is $a_1 + b_1$. Differentiation is linear: for each slot $s$, $\frac{\partial}{\partial v_s}(a_1 + b_1) = \frac{\partial a_1}{\partial v_s} + \frac{\partial b_1}{\partial v_s}$, so the parent's gradient is $\vec{a}_2 + \vec{b}_2$. That is the sum rule.

At an AND node, the value is $a_1 b_1$. The product rule gives, slot by slot, $\frac{\partial}{\partial v_s}(a_1 b_1) = b_1 \frac{\partial a_1}{\partial v_s} + a_1 \frac{\partial b_1}{\partial v_s}$, so the parent's gradient is $b_1 \vec{a}_2 + a_1 \vec{b}_2$.

Both rules consume only the two pairs and produce a pair. So define a new number system whose elements are pairs $(a_1, \vec{a}_2)$ with $a_1 \in \mathbb{R}$ and $\vec{a}_2 \in \mathbb{R}^6$, and install the two rules as its operations:

$$(a_1, \vec{a}_2) \oplus (b_1, \vec{b}_2) = (a_1 + b_1,\; \vec{a}_2 + \vec{b}_2), \qquad (a_1, \vec{a}_2) \otimes (b_1, \vec{b}_2) = (a_1 b_1,\; b_1 \vec{a}_2 + a_1 \vec{b}_2).$$

This is the gradient semiring, and the claim is that it is a commutative semiring, so the previous chapter's evaluator can run over it unchanged. The aProbLog (algebraic ProbLog) framework generalized circuit-based inference from probabilities to arbitrary commutative semirings, under conditions on the leaf labels that are needed exactly where a circuit branch skips a variable [3]; the smoothness discussion below shows that this chapter's one-hot encoding compiles with zero pass-throughs, so no branch ever skips one and those conditions are never invoked. The axioms are therefore not pedantry; they are the license to reuse the machinery. Check them. Addition $\oplus$ is componentwise, so it is associative and commutative with neutral element $e^{\oplus} = (0, \vec{0})$, where $\vec{0}$ is the all-zeros vector. Multiplication $\otimes$ is commutative by inspection: $a_1 b_1 = b_1 a_1$ and $b_1\vec{a}_2 + a_1\vec{b}_2$ is symmetric in the two pairs. Its neutral element is $e^{\otimes} = (1, \vec{0})$: indeed $(1, \vec{0}) \otimes (b_1, \vec{b}_2) = (1 \cdot b_1,\; b_1 \cdot \vec{0} + 1 \cdot \vec{b}_2) = (b_1, \vec{b}_2)$. The annihilator works too: $(0, \vec{0}) \otimes (b_1, \vec{b}_2) = (0,\; b_1 \vec{0} + 0 \cdot \vec{b}_2) = (0, \vec{0})$.

Associativity of $\otimes$ deserves the full computation, because it is the axiom that could plausibly fail. Take three pairs $a, b, c$ and expand both groupings. Left grouping first:

$$(a \otimes b) \otimes c = (a_1 b_1,\; b_1 \vec{a}_2 + a_1 \vec{b}_2) \otimes (c_1, \vec{c}_2) = \big( (a_1 b_1) c_1,\; c_1 (b_1 \vec{a}_2 + a_1 \vec{b}_2) + (a_1 b_1)\, \vec{c}_2 \big),$$

and distributing $c_1$ through the parenthesis, the gradient slot is $b_1 c_1 \vec{a}_2 + a_1 c_1 \vec{b}_2 + a_1 b_1 \vec{c}_2$. Right grouping:

$$a \otimes (b \otimes c) = (a_1, \vec{a}_2) \otimes (b_1 c_1,\; c_1 \vec{b}_2 + b_1 \vec{c}_2) = \big( a_1 (b_1 c_1),\; (b_1 c_1)\, \vec{a}_2 + a_1 (c_1 \vec{b}_2 + b_1 \vec{c}_2) \big),$$

whose gradient slot distributes to the same $b_1 c_1 \vec{a}_2 + a_1 c_1 \vec{b}_2 + a_1 b_1 \vec{c}_2$. The two groupings agree, and the common value is no accident: it is the product rule for a triple product, $\nabla(abc) = bc\,\nabla a + ac\,\nabla b + ab\,\nabla c$, which is symmetric in $a, b, c$. Associativity holds precisely because differentiating a product does not care how the product was parenthesized. Finally, distributivity of $\otimes$ over $\oplus$:

$$a \otimes (b \oplus c) = \big( a_1(b_1 + c_1),\; (b_1 + c_1)\,\vec{a}_2 + a_1(\vec{b}_2 + \vec{c}_2) \big) = \big( a_1 b_1 + a_1 c_1,\; (b_1 \vec{a}_2 + a_1 \vec{b}_2) + (c_1 \vec{a}_2 + a_1 \vec{c}_2) \big),$$

which is exactly $(a \otimes b) \oplus (a \otimes c)$. All axioms pass. This pair construction is old and honorable: it is the expectation semiring of probabilistic finite-state transducers, invented to push expected counts through their sum-product recursions [4], rediscovered here as forward-mode differentiation of weighted model counting. The full semiring menu of Part II now reads:

semiring	element	⊕	⊗	$e^{\oplus}$	$e^{\otimes}$	root computes
Boolean	true/false	∨	∧	false	true	satisfiability
probability	$p \in [0,1]$	$+$	$\times$	$0$	$1$	$P(q)$ (WMC)
max-product	$p \in [0,1]$	max	$\times$	$0$	$1$	most probable explanation
gradient	$(p, \nabla p)$	add both slots	product rule	$(0, \vec{0})$	$(1, \vec{0})$	$\big(P(q),\; \nabla P(q)\big)$

Leaf labels complete the definition. A constant probabilistic fact with probability $p$ does not depend on the network, so its derivative in every slot is zero: label $(p, \vec{0})$. The indicator for the $j$-th softmax output is the $j$-th parameter, so its derivative is $1$ in slot $j$ and $0$ elsewhere: label $(\pi_j, \mathbf{e}_j)$, where $\mathbf{e}_j$ is the $j$-th standard basis vector, the vector with a single $1$ in position $j$. The negated indicators of the categorical encoding are the constant $1$: label $(1, \vec{0})$. In the companion this is six lines (deepproblog_mini.py lines 184–189):

    return Semiring(
        f"gradient (p, dp/dx) over R^{n}",
        (0.0, np.zeros(n)),
        (1.0, np.zeros(n)),
        lambda a, b: (a[0] + b[0], a[1] + b[1]),
        lambda a, b: (a[0] * b[0], b[0] * a[1] + a[0] * b[1]))

and the labels are attached in grad_weights (deepproblog_mini.py lines 207–212):

    for s, pi in (("A", pi_a), ("B", pi_b)):
        for t in TOPICS:
            var = f"topic({s},{t})"
            e = np.zeros(N_SLOTS)
            e[SLOT[var]] = 1.0
            w[var] = ((float(pi[T_ID[t]]), e), (1.0, np.zeros(N_SLOTS)))

Correctness follows by structural induction up the circuit. At every leaf the pair is (value, gradient of that value) by construction. If every child of a node carries the correct pair, the OR case is the sum rule and the AND case is the product rule, so the parent's pair is correct too. At the root, the first slot is the same number the probability semiring computes, $P(q)$, and the second slot is $\nabla P(q)$, exactly. Note what the induction needed. Determinism and decomposability (last chapter) make the value slot the true probability, and one further condition does quiet work under the categorical weights: the smoothness identity $w(x) + w(\lnot x) = 1$ fails here, because $w(\lnot x) = 1$ makes the sum $\pi + 1$, so a smoothing pass-through $(v \vee \lnot v)$ inserted by the compiler would multiply its branch by $\pi + 1$ and corrupt both slots. The encoding is safe only because the full one-hot terms compile smooth as-is, with zero pass-throughs; that is what the pass-throughs column of the structure report above certifies, and the companion enforces it as an assert before anything else runs (deepproblog_mini.py lines 457–466). With the value slot correct for every $\mathbf{v}$, the gradient slot comes free, because differentiating a computation that is correct everywhere yields a computation of its derivative. The cost accounting is equally clean: each $\otimes$ or $\oplus$ now touches a length-6 vector, so the pass costs one vector operation per circuit edge, 22 edges for relevant(A,B), and returns all seven numbers, the probability and six partials, in that single sweep. Six re-evaluations would have cost six times the circuit; forward-mode pairs cost one circuit at six times the width.

One pass, both answers

The companion runs the pass through the same evaluate entry point the probability semiring used (circuit.py lines 369–374), wrapped in query_prob_grad (deepproblog_mini.py lines 223–228):

def query_prob_grad(circ, pi_a: np.ndarray, pi_b: np.ndarray,
                    ) -> tuple[float, np.ndarray]:
    """One gradient-semiring WMC pass over the compiled circuit:
    returns (P, ∇P) where ∇P has the 6 slots (A×3 topics, then B×3)."""
    p, g = evaluate(circ, grad_weights(pi_a, pi_b), GRAD)
    return float(p), g

Trust, then verify. The central finite difference is the definition of the derivative made numerical: nudge one slot up by a small step $h$, down by $h$, and divide the change in $P$ by $2h$, so $\partial P/\partial v_s \approx \big(P(\mathbf{v} + h\,\mathbf{e}_s) - P(\mathbf{v} - h\,\mathbf{e}_s)\big)/(2h)$. Because the circuit's polynomial is multilinear in the leaf weights (each world multiplies each variable's weight at most once, so no slot ever appears squared), the central difference is exact up to floating-point rounding, which makes it a merciless oracle. The check fd_check_circuit compares every semiring slot against it, using plain probability-semiring evaluations at the perturbed weights (deepproblog_mini.py lines 294–315). The committed run, on the untrained network and the pair (m1, p1):

[3] the gradient semiring, certified against central finite
    differences on the untrained net (pair m1, p1)
      slot            semiring dP/dpi   finite diff       |diff|
      topic(A,logic)      0.563591122   0.563591122   5.1e-14
      topic(A,ml)         0.038147531   0.038147531   4.8e-14
      topic(A,nesy)       0.398261347   0.398261347   2.7e-13
      topic(B,logic)      0.562658408   0.562658408   2.0e-13
      topic(B,ml)         0.057065962   0.057065962   2.3e-13
      topic(B,nesy)       0.380275630   0.380275630   1.4e-13
      max |semiring - FD| on the circuit : 2.67e-13  (tolerance 1e-06)

and the harness enforces the chapter's contract as an assert (deepproblog_mini.py lines 503–504):

    assert fd_circ <= FD_TOL, f"semiring vs FD on the circuit: {fd_circ:.2e}"
    assert fd_par <= FD_TOL, f"chained param gradient vs FD: {fd_par:.2e}"

You can read the table's numbers off the closed form as a spot check. Since $P = \sum_t \pi_{A,t}\pi_{B,t}$, the partial derivative with respect to $\pi_{A,t}$ is simply $\pi_{B,t}$, the other document's softmax entry. The printed slot for topic(A,logic), $0.563591$, is p1's untrained probability of logic; the slot for topic(B,logic), $0.562658$, is m1's. Multiply the paired slots and sum: $0.562658 \times 0.563591 + 0.057066 \times 0.038148 + 0.380276 \times 0.398261 = 0.317109 + 0.002177 + 0.151449 = 0.470735$, which is exactly the coins exhibit's printed $P(\text{relevant}) = 0.470735$ for this pair. The semiring, the finite differences, and the hand algebra tell one story.

From softmax outputs to the weights, by hand

The circuit's gradient stops at the softmax outputs; the network's parameters live behind them. DeepProbLog hands $\partial P/\partial \pi$ to the deep-learning framework's automatic differentiation at exactly this seam [2]; the companion writes the remaining chain by hand so nothing is hidden. Three links remain. First, the loss. For a pair with target $y \in \{0, 1\}$ and inferred $p = P(\text{relevant})$, the cross-entropy is $L = -y \ln p - (1-y)\ln(1-p)$, where $\ln$ is the natural logarithm (the logarithm to base $e \approx 2.718$), and differentiating term by term,

$$\frac{\partial L}{\partial p} = -\frac{y}{p} + \frac{1-y}{1-p} = \frac{-y(1-p) + (1-y)p}{p(1-p)} = \frac{-y + yp + p - yp}{p(1-p)} = \frac{p - y}{p(1-p)}.$$

Second, the softmax Jacobian. For one document, $\pi_t = e^{z_t} / \sum_u e^{z_u}$, where $z$ is the vector of $K$ logits (pre-softmax scores), the exponential $e^{z_t}$ raises $e$ to the logit and so turns any real score into a positive number, and the index letters $t, s, u$ range over the three topics. Volume 3's attention chapter derived, by the quotient rule, $\partial \pi_t / \partial z_s = \pi_t(\delta_{ts} - \pi_s)$, where $\delta_{ts}$ is the Kronecker delta, equal to $1$ when $t = s$ and $0$ otherwise. Collected over all $t, s$ this Jacobian is the matrix $\operatorname{diag}(\boldsymbol{\pi}) - \boldsymbol{\pi}\boldsymbol{\pi}^{\top}$: here $\operatorname{diag}(\boldsymbol{\pi})$ places the entries of $\boldsymbol{\pi}$ on the diagonal of an otherwise-zero matrix, the superscript $\top$ marks the transpose (a column vector laid on its side as a row), and the outer product $\boldsymbol{\pi}\boldsymbol{\pi}^{\top}$ is the $K \times K$ matrix whose entry in row $t$, column $s$ is $\pi_t \pi_s$. Applying it to the incoming row vector $u_t = \partial L/\partial \pi_t$ by the chain rule:

$$\frac{\partial L}{\partial z_s} = \sum_t u_t\, \pi_t(\delta_{ts} - \pi_s) = u_s \pi_s - \pi_s \sum_t u_t \pi_t = \pi_s \Big( u_s - \sum_t u_t \pi_t \Big),$$

where the first equality split the sum at the delta (only $t = s$ survives the $\delta_{ts}$ term). Third, the linear layer: $z_d = W \mathbf{x}_d + \mathbf{b}$ for document $d$, where $W$ is the $K \times 2$ weight matrix (one row per topic, one column per feature) and $\mathbf{b}$ is the length-$K$ bias vector. Written entry by entry, with $c$ indexing the two feature columns, the topic-$t$ logit is $z_{d,t} = \sum_{c} W_{tc}\, x_{d,c} + b_t$. The weight entry $W_{tc}$ appears in exactly one place per document, that document's topic-$t$ logit, and there $\partial z_{d,t}/\partial W_{tc} = x_{d,c}$, so the chain rule adds one contribution per document: $\partial L/\partial W_{tc} = \sum_d (\partial L/\partial z_{d,t})\, x_{d,c}$. Collecting the entries over all $t, c$ into a matrix gives $\partial L/\partial W = \sum_d (\partial L/\partial z_d)\, \mathbf{x}_d^{\top}$, a sum of outer products, and the bias is the same argument with $\partial z_{d,t}/\partial b_t = 1$, so $\partial L/\partial \mathbf{b} = \sum_d \partial L/\partial z_d$. All three links are the committed code, comment for comment (deepproblog_mini.py lines 268–285):

        p, g = query_prob_grad(REL_C, pi[i], pi[j])
        ...
        dl_dp = (p - y) / (p * (1.0 - p))
        dl_dpi[i] += dl_dp * g[:K]
        dl_dpi[j] += dl_dp * g[K:]
    ...
    dl_dz = pi * (dl_dpi - np.sum(dl_dpi * pi, axis=1, keepdims=True))
    dw = dl_dz.T @ X
    db = dl_dz.sum(axis=0)

The two dl_dpi lines route the semiring's six slots to the right documents: slots 1–3 belong to the document bound to A, slots 4–6 to B. And the whole chain, semiring pass included, is certified a second time by central differences on the full-batch loss, one nudge per parameter, all nine of them (six weights, three biases): the committed maximum discrepancy is $1.96 \times 10^{-11}$ against the same $10^{-6}$ tolerance (deepproblog_mini.py lines 318–341). The gradient this system trains on is not an approximation of anything; it is the derivative of exact inference.

Training by entailment: the logic is the labeling function

Training is now the plainest loop in this volume: full-batch gradient descent, $\theta \leftarrow \theta - \eta\, \partial L/\partial \theta$, where $\theta$ is the vector collecting all nine parameters (the six entries of $W$ and the three of $\mathbf{b}$), with learning rate $\eta = 2.0$ for $400$ epochs over the 15 pairs (deepproblog_mini.py lines 416–444). The loss is what DeepProbLog calls learning from entailment: the training example is a query and its target probability, here relevant(a, b) against the pair label, and never a label for any topic atom [1]. The committed trace:

[6] training from pair labels alone (full-batch GD, lr=2.0, 400 epochs)
      epoch    loss      pair acc   hidden-topic acc
          1   0.425199    86.67%       66.67%
         25   0.004551   100.00%      100.00%
        100   0.001134   100.00%      100.00%
        200   0.000571   100.00%      100.00%
        400   0.000287   100.00%      100.00%

Read the first row carefully: the untrained net's 86.67% pair accuracy is mostly base rate. Fourteen of the fifteen initial probabilities sit below the $0.5$ threshold, so the net calls nearly everything irrelevant and is right on the 12 truly irrelevant pairs plus the one true pair, (m3, p2), that happens to start above threshold at $0.5530$. The number that matters is the last column. Hidden-topic accuracy scores the softmax argmax against the hidden topics that training never saw, maximized over the $3! = 6$ relabelings of the three classes, since pair labels are invariant under renaming the topics and can pin the clustering down only up to a permutation, the standard label-switching symmetry of distant supervision (deepproblog_mini.py lines 392–405). By epoch 25 it is 100% and stays there. The centerpiece of the committed output:

      m1      0.9996    0.0002    0.0002   class0 -> logic     logic  ok
      m2      0.0001    0.0000    0.9999   class2 -> ml        ml     ok
      m3      0.0002    0.9997    0.0001   class1 -> nesy      nesy   ok
      p1      0.9999    0.0000    0.0001   class0 -> logic     logic  ok
      p2      0.0000    0.9999    0.0001   class1 -> nesy      nesy   ok
      p3      0.0002    0.0002    0.9996   class2 -> ml        ml     ok
      hidden-topic accuracy: 100% — no topic label was ever shown to training

A three-way document classifier, confident and correct on all six documents, trained by a supervisor who only ever said "these two go together" or "these two do not." The trained pair probabilities bracket cleanly: the minimum over the 3 true pairs is $0.9994$ and the maximum over the 12 false pairs is $0.0004$, both asserted along with the perfect topic recovery (deepproblog_mini.py lines 531–535).

Why does the credit land on the right latent decisions? The circuit says exactly. The gradient slot for $\pi_{A,t}$ is $\pi_{B,t}$: for a relevant pair, $\partial L/\partial p$ is negative (the derivation above gives $(p-y)/(p(1-p))$ with $y=1$ and $p$ below 1), so descent raises each $\pi_{A,t}$ in proportion to how much the partner already believes topic $t$; the two documents pull each other toward whichever topic currently explains their agreement best, and the softmax normalization converts "raise one entry" into "lower the others." For an irrelevant pair the sign flips and agreement on any topic is taxed, again in proportion to the partner's belief. Worlds that explain the observed label get their softmax entries reinforced; worlds that contradict it get suppressed; and atoms outside the ground pair, the other four documents' topic indicators, never appear as leaves of the pair's circuit, so their softmax outputs receive exactly zero gradient. Distant supervision works here because the logic program routes each pair label to precisely the latent choices that could have produced it. The logic is the labeling function, and exact inference is what keeps its bookkeeping honest.

The MNIST-addition touchstone

Our miniature is a scale model of the field's canonical demonstration. In the original experiment, the perception is a convolutional network over MNIST (the Modified National Institute of Standards and Technology handwritten-digit set), the nAD is a ten-way softmax per image, nn(m_digit, [X], [0..9]) :: digit(X, 0); ...; digit(X, 9), the program is one line, addition(X, Y, Z) :- digit(X, X2), digit(Y, Y2), Z is X2 + Y2, and the supervision is a pair of images with their sum, never a digit label [1]. The structure maps onto ours term for term: image → document features, digit classifier → topic classifier, sum label → relevance label, and the numbers reported in the journal version's tables make the phenomenon concrete: from 30,000 sum-labeled pairs the pipeline reaches 97.2% test accuracy on single-digit addition, ahead of the 93.5% of a convolutional baseline trained to map the two images directly to one of the 19 possible sums, with the sum label distributing credit across the $10 \times 10$ joint digit choices exactly as our pair label distributes it across the $3 \times 3$ topic choices [2]. The demonstration made the point that stuck: a logic program can convert cheap, task-level supervision into precise, symbol-level training signal, provided inference in the middle is differentiable.

The scale ledger

The honesty this volume owes: everything above is exact, and exactness is the cost center. Each training step grounds the query, compiles the ground formula, and evaluates; compilation is the same knowledge-compilation step whose worst case is exponential, and grounding itself multiplies out the program's choice space. Our circuit has 6 variables and 22 edges. Two-digit MNIST addition already has a $10^4$ joint choice space per example; the journal source of record reports grounding and compilation, not the neural network, as the cost that dominates and grows with problem size, so that exact inference becomes prohibitively expensive for large problems [2], and successor evaluations locate the wall concretely: the exact pipeline times out near MNIST addition with numbers of about four digits [5][6]. The ledger of escapes, each trading something:

line	what it keeps	what it gives up
exact (this chapter)	the true $P(q)$ and its true gradient	scale: grounding + compilation blow up
top-k proofs	only the $k$ most probable proofs enter the circuit	mass in the dropped proofs; the gradient is of a lower bound
approximate / amortized inference	scale, minibatch-friendly evaluation	exactness and its guarantees
derivation semantics (DeepStochLog)	one pass over a derivation forest, parser-style speed [5]	the possible-worlds reading: probabilities attach to derivations, not worlds

The top-k line is where the Scallop chapter picks up: keep the semiring, keep the differentiability, but cap the provenance at the $k$ best explanations and accept a principled approximation. The derivation-semantics line, DeepStochLog, changes the semantics itself: probabilities attach to stochastic-grammar derivations rather than to possible worlds, which buys substantially faster inference at the price of a different (and sometimes less natural) probabilistic reading [5]. What no line on the ledger changes is the architecture of this chapter: a network proposing weights for symbols, a program composing them, and a semiring carrying gradients back through whatever inference survives the budget.

The unsolved part

The training loss is entirely about queries: cross-entropy on $P(\text{relevant})$, never on $P(\text{topic})$. The perfect confusion table above is therefore a fortunate consequence, not a certified one. The optimizer is free to find any softmax behavior that makes the query probabilities right, and on richer programs than ours there can be many such behaviors: predicates can absorb each other's roles, two wrongs can multiply into a right, and the latent classifier can be systematically miscalibrated while every training query sits at its target. Nothing in the gradient semiring, which is exact, prevents this; exactness guarantees the gradient of the query loss, not the meaning of the intermediate symbols. Our miniature dodges the problem by construction (the label-switching permutation is the only residual freedom, and the module measures it), but the general phenomenon, models right for the wrong internal reasons, is real, and it has a name and a literature waiting in Volume 5's reasoning-shortcuts chapter. A second open front is engineering rather than semantics: exact inference resists batching. A GPU (graphics processing unit) wants ten thousand identical dense operations; a compiled circuit is an irregular sparse DAG (directed acyclic graph), different per query, and the field is only now building layouts that evaluate many circuits at once on accelerators. That thread resumes with KLay in the GPU-native chapter.

Why it matters

This chapter is the volume's thesis in its cleanest form. Part I asked for logic a gradient can cross; Part II built the exact machinery: worlds, counts, circuits. DeepProbLog is the demonstration that the machinery actually closes the loop, that a perception network and a logic program can share one training signal without either surrendering its nature. The logic stays crisp (the program, the grounding, the circuit are all exact; set the probabilities to 0/1 and Boolean logic reappears, as the crisp-limit check verifies), the network stays a network (a softmax trained by gradient descent), and the interface between them is one algebraic idea, a semiring whose multiplication is the product rule. The pattern generalizes far past this instance: the same pair trick differentiates any structure evaluated by real sums and products, provenance polynomials included, which is why it will reappear when those polynomials meet Datalog in Scallop and when circuits become loss functions in the next chapter. And the payoff it purchased, task-level labels training symbol-level classifiers through exact inference, is precisely the kind of claim Volume 5 will demand receipts for: trust in the answer requires knowing why the answer is right, and this chapter's finite-difference certificates and world-level accounting are what those receipts look like at miniature scale.

Key terms

• Neural predicate / neural annotated disjunction (nAD): a probabilistic fact family whose probabilities are a network's outputs; a softmax head declared as a mutually exclusive choice among ground atoms, the AD's sum-to-one special case, so exactly one atom holds.
• Annotated disjunction (AD): ProbLog's construct for a probabilistic choice among several heads; the head probabilities sum to at most one, with any remainder on the outcome that no head fires.
• Categorical indicator encoding: one Boolean indicator per choice, one-hot world descriptions, positive literals weighted by the class probability and negated literals by the constant 1, so each legal world carries exactly its softmax mass.
• Gradient semiring: the commutative semiring on pairs $(p, \nabla p)$ with $\oplus$ adding both slots and $(a_1, \vec{a}_2) \otimes (b_1, \vec{b}_2) = (a_1 b_1, b_1\vec{a}_2 + a_1\vec{b}_2)$; one circuit pass returns the query probability and its exact gradient.
• Expectation semiring: the same pair construction in its original habitat, pushing expected counts through sum-product recursions for parameter estimation.
• Learning from entailment: training on (query, target probability) examples, with cross-entropy on $P(q)$; the program's intermediate atoms receive no direct supervision.
• Distant supervision: labels attached to an observable consequence (relevance, a sum) training a latent decision (topic, digit) through the rules that connect them.
• Label-switching symmetry: the residual freedom distant supervision cannot remove; here, pair labels determine the topic clustering only up to a permutation of topic names.
• Central finite difference: the numerical derivative $\big(f(x+h) - f(x-h)\big)/(2h)$; exact for multilinear functions up to rounding, used here as the oracle certifying both gradient stages.

Where this leads

DeepProbLog puts the program in charge: the network fills in leaf probabilities, and the logic defines the task. The next chapter inverts the relationship. In Semantic Loss and Constraint Layers, the network is in charge of the prediction and the logic becomes a regularizer: a constraint compiled to a circuit, evaluated on the network's own output probabilities, whose negative log-probability of satisfaction is added to the loss. Same worlds, same weighted model counting, same compiled circuits, pointed in the opposite direction: not "learn perception so the program's answers come out right" but "learn predictions that keep the constraint satisfied."

---

Companion code: examples/integration/deepproblog_mini.py implements the neural predicate, the one-hot grounding, the gradient semiring, both finite-difference certifications, and the distant-supervision training loop, on top of the circuit compiler in examples/integration/circuit.py. Run python3 examples/integration/deepproblog_mini.py to reproduce every number in this chapter; the run is deterministic and every claim is guarded by an assert.