Lecture 08 · The five interfaces

Logic as an architecture.

The program is no longer a penalty outside the model. It is executed in the forward pass, its worlds are counted, and the answer is a distribution over the worlds it accepts.

9 sections 4 systems 1 exact-inference lab Self-paced
00 · Learning objectivesLecture 08 · Logic as architecture

By the end of this lecture

Four things you can do.

01

Read a distribution over worlds

Probabilistic facts, total choices, world weights, and a query probability that sums over worlds.

02

Open the four systems

Say what DeepProbLog, NeurASP, Scallop and ULLER each put inside the computation graph.

03

Price exact inference

Explain weighted model counting, the #P-hardness, and why compilation changes the cost but not the problem.

04

Separate loss from architecture

State the difference in one sentence and two equations, and name the gradient failure modes.

S/V · Lecture 08
00 · The hookLecture 08 · Logic as architecture

Three cells, three values

A classifier that votes. A program that decides.

Each cell returns a distribution over 1–3. The program says the row is a permutation. The model does not return three argmaxes; it returns one distribution over the six valid rows.

Cellp(1)p(2)p(3)
10.600.300.10
20.600.300.10
30.100.300.60
The prior's best row is (1, 1, 3) at 0.216 — and it is invalid. A penalty would keep it and make it expensive. The architecture gives it zero mass.
S/V · Lecture 08
00 · The hookLecture 08 · Logic as architecture

Exact enumeration

Six rows, one normalizer.

RowProduct of probabilitiesPosterior
(1, 2, 3)0.60 × 0.30 × 0.60 = 0.1080.108 / 0.258 = 0.4186
(2, 1, 3)0.30 × 0.60 × 0.60 = 0.1080.108 / 0.258 = 0.4186
(1, 3, 2)0.60 × 0.10 × 0.30 = 0.0180.018 / 0.258 = 0.0698
(3, 1, 2)0.10 × 0.60 × 0.30 = 0.0180.018 / 0.258 = 0.0698
(2, 3, 1)0.30 × 0.10 × 0.10 = 0.0030.003 / 0.258 = 0.0116
(3, 2, 1)0.10 × 0.30 × 0.10 = 0.0030.003 / 0.258 = 0.0116

Z = 0.108 + 0.108 + 0.018 + 0.018 + 0.003 + 0.003 = 0.258

Z is the prior probability that the constraint holds. The posterior MAP is a tie between (1,2,3) and (2,1,3); the prior MAP is gone.

S/V · Lecture 08
01 · Distribution semanticsLecture 08 · Logic as architecture
01 / 08

Worlds, weights, sums.

The program defines a distribution; inference is a weighted count of the worlds that satisfy the query.

S/V · Lecture 08
01 · Distribution semanticsLecture 08 · Logic as architecture

Distribution semantics

A world is a total choice plus its consequences.

Probabilistic fact. p::f. means f is true with probability p, independently of every other fact.

Total choice. Fix every fact as true or false. The ordinary logic program derives the rest.

World weight. Multiply p for each chosen fact and 1 − p for each rejected one.

abqWeight
TTT0.7 × 0.6 = 0.42
TFF0.7 × 0.4 = 0.28
FTF0.3 × 0.6 = 0.18
FFF0.3 × 0.4 = 0.12

Program: 0.7::a. 0.6::b. q :- a, b. The weights sum to 1.

The weights are a product over facts, not over derived atoms. The program says which atoms follow; the probability says how likely the choice was. That separation is what makes the next section possible.
S/V · Lecture 08
01 · Distribution semanticsLecture 08 · Logic as architecture

Inference

A query is a formula. Its probability is a weighted count.

P(q) = Σw ⊨ q P(w) = WMC(φq)

WMC(φ) = Σx ⊨ φ Πi wi(xi), with wi(1) = pi and wi(0) = 1 − pi.

01 · Formula

φq is true exactly on the worlds where q holds. Here q is a ∧ b.

02 · Weights

Each literal carries a weight. The product is the world's weight.

03 · Count

Sum the weights of the satisfying assignments. That is the query probability.

The count is #P-hard in general. Everything that follows is a way of making it smaller or avoiding it.
S/V · Lecture 08
01 · Distribution semanticsLecture 08 · Logic as architecture

ProbLog

The program is the distribution.

0.7::a.
0.6::b.
q :- a, b.
query(q).

0.42

The rule does not return a truth value. It defines which worlds satisfy q; the query sums their weights.

Ground the query-relevant part, rewrite it as a propositional formula, compile it to a circuit, and evaluate the circuit. That is the exact-inference recipe ProbLog introduced; §6 takes the circuit apart.

S/V · Lecture 08
02 · DeepProbLogLecture 08 · Logic as architecture
02 / 08

Four ways to put a program inside.

Different languages, different counts. The same move: the symbolic executor becomes part of the forward pass.

S/V · Lecture 08
02 · DeepProbLogLecture 08 · Logic as architecture

A fact whose probability is a network

The neural predicate.

nn(digit, img_a, [0..9], A).
nn(digit, img_b, [0..9], B).
sum(S) :- digit(A), digit(B), S is A + B.
query(sum(8)).
01 · Network

m maps x to a normalized distribution over the finite domain D.

02 · Annotated disjunction

From the program's view, the predicate is a set of exclusive head atoms with probabilities.

03 · Grounding

The forward pass runs when the predicate is grounded; the logic sees probabilities, not logits.

Inside the graph: the CNN forward pass, the annotated-disjunction probabilities, the grounded formula, the circuit, and the gradient semiring.
S/V · Lecture 08
02 · DeepProbLogLecture 08 · Logic as architecture

Inference and gradients

Compile the query. Differentiate the circuit.

1. Ground the query and run a forward pass for each neural predicate.

2. Compile the propositional formula into an SDD.

3. Evaluate bottom-up: addition at OR nodes, multiplication at AND nodes.

4. Evaluate again with (probability, derivative) pairs; the gradient semiring returns ∂P(q)/∂p for every predicate output.

+ × × p(a)p(b) p(c)p(d) gradient semiring P(q) → → ∂P(q)/∂p Schematic. A decomposable, deterministic circuit makes the count linear in its size.
The catch: the SDD can be exponentially large, and grounding can blow up before compilation starts.
S/V · Lecture 08
02 · DeepProbLogLecture 08 · Logic as architecture

The guarantee

Exact, but conditional.

What it guarantees

The query probability is exact given the program and the predicates.

Every program-consistent world is counted once. Every inconsistent world gets zero. The normalizer is the total mass of the consistent worlds. The gradient is the exact derivative of that probability.

What it does not

That the digits are true, or the program is right.

A miscalibrated classifier produces an exact posterior for the wrong facts. A wrong program produces an exact posterior over the wrong worlds. The SDD can also be exponentially large.

The guarantee is semantic, not epistemic. It is a statement about the computation, not a certificate about the world.
S/V · Lecture 08
03 · NeurASPLecture 08 · Logic as architecture

Answer set programming

The stable models are the worlds.

nn(digit, cell, D).
1 { solved(C,D) : digit(D) } 1 :- cell(C).
:- solved(C1,D), solved(C2,D), C1 != C2.
% one value per cell; all-different
% each stable model is a world

The ASP program is deterministic given the neural choices. Each stable model is one way the program can be true.

Its weight is the product of the neural outputs that produce it. The probability of an atom is the sum of the weights of the models containing it, divided by Z.

P(a | x) = ΣM ⊨ a w(M) / Z(x),   w(M) = Πnn ∈ M p(y | x)

Inside the graph: the grounded ASP program and the stable-model enumeration. Guarantee: exact under stable-model semantics.
S/V · Lecture 08
03 · NeurASPLecture 08 · Logic as architecture

The Sudoku case

Eighty-one cells, one enumeration.

5 3 8 1 9 4 2 7 6 3 9 8 1 4 2 schematic · orange clues, teal filled

One CNN reads each cell; 81 neural atoms. Row, column and box constraints define the legal completions. The stable models are the completions; the enumeration is exact.

Training uses solution grids, not digit labels: the ASP rules supply the digit-level supervision. The worst case is still exponential; the constraints prune, but they do not make the count polynomial.

The price is the enumeration. Exactness buys a guarantee, not a budget.
S/V · Lecture 08
04 · ScallopLecture 08 · Logic as architecture

Differentiable Datalog

One program, several algebras.

path(X,Y) :- edge(X,Y).
path(X,Y) :- path(X,Z), edge(Z,Y).
% provenance tags on every tuple
Semiring⊕⊗Value
Booleanorandtrue / false
Probabilitya+b−aba·bP(path)
Min-plusmin+shortest
Top-kk-bestk-bestranked proofs

The provenance tag records how a tuple was derived; the semiring decides what the tag is worth. The same rules can answer a probability question, a shortest-path question, or a top-k question.

Inside the graph: the grounded relational algebra, the provenance tags, the retained proofs, and the semiring evaluation.
S/V · Lecture 08
04 · ScallopLecture 08 · Logic as architecture

The approximation

Top-k is a ranking, not a probability.

s a b t 0.9 0.9 0.8 0.8 two edge-disjoint paths
SettingKeptValue
Exactboth proofs0.9316
Top-2both proofs0.9316
Top-1best proof0.8100

Exact: 1 − (1 − 0.81)(1 − 0.64) = 0.9316. Top-1 keeps only 0.81, and its gradient follows only that path.

With k below the number of proofs, the value and the gradient are approximations. Exactness is recovered only when k covers every proof.
S/V · Lecture 08
05 · ULLERLecture 08 · Logic as architecture

A unified language

One language, several semantics.

ULLER is a first-order language for knowledge and learning. Functions are interpreted as conditional probability distributions; a neural network is just a function.

There is no dedicated neural syntax. The semantics is an argument: classical, fuzzy, probabilistic, or sampling.

A statement binding composes functions and delimits scope: x := f(T, …)(F).

Why it matters

The same program can be compared across semantics.

A result under classical logic, a degree under fuzzy logic, a probability under WMC, and an estimate under sampling are different objects. ULLER makes the choice explicit instead of hiding it in the engine.

Inside the graph: the grounded statements, the function applications — including networks — and the semantics operators. Guarantee: exact relative to the chosen semantics.
S/V · Lecture 08
05 · ULLERLecture 08 · Logic as architecture

The semantics table

The same program, four values.

SemanticsConnectivesFunction applicationWhat the value means
Classicalmin / maxthe modetruth value in {0, 1}
Fuzzyt-norm / t-conorma value in [0, 1]degree of satisfaction
Probabilisticproduct / expectationa sum over valuesprobability by WMC
Samplingclassical after drawsa drawMonte Carlo estimate

Probabilistic evaluation agrees with WMC for closed, statement-free, finite-domain formulas. It is generally exponential; compilation can help, but no general tractability is claimed.

Two limits: the fuzzy semantics is defined for finite domains only, and sampling is an estimate, not a guarantee.
S/V · Lecture 08
06 · Exact inferenceLecture 08 · Logic as architecture
06 / 08

The count has a price.

Weighted model counting is #P-hard. Compilation moves the exponential into the circuit; it does not remove it.

S/V · Lecture 08
06 · Exact inferenceLecture 08 · Logic as architecture

Weighted model counting

Counting is #P-hard.

WMC(φ) = Σx ⊨ φ Πi wi(xi)

φ is the query's formula; the weights are literal weights. The count is over assignments, not over proofs.

d-DNNF

Decomposable and deterministic: AND children share no variables, OR children are exclusive.

SDD

A canonical circuit form. Evaluation is a bottom-up sum-product, linear in the circuit.

Compilation

The circuit can be exponentially large. The exponential has moved, not vanished.

The practical question is not “is it hard?” but “which structure makes the count small?”
S/V · Lecture 08
06 · Exact inferenceLecture 08 · Logic as architecture

Tractability

Where the exponential lives.

Small

Structure that compiles well.

Shared subgoals let the circuit reuse work. Determinate programs avoid multiple stable models. Bounded treewidth gives a compact circuit. Few independent choices mean few worlds to multiply.

Large

Structure that blows up.

Many independent choices multiply. Grounding creates the atoms before counting. Recursion can generate unboundedly many proofs. Negation and aggregation add non-monotonic structure that defeats simple decompositions.

Numerical care is part of the cost. Z can underflow before the posterior is computed; log-space or a scaled semiring is a requirement, not an optimization.
S/V · Lecture 08
07 · Buys & costsLecture 08 · Logic as architecture

The line

A loss changes the cost. An architecture changes the answers.

Loss: minθ Ldata(θ) + λ · Rφ(fθ(x))

Architecture: pθ(y | x) = Σσ ⊨P y Πi pi(σi | x) / Z(x)

01 · Support

The loss leaves the output space unchanged; the architecture removes every world the program rejects.

02 · Normalizer

The loss has a weight λ. The architecture has a partition function Z and an inference procedure.

03 · Guarantee

The loss guarantees nothing at inference; the architecture is exact relative to its program.

S/V · Lecture 08
07 · Buys & costsLecture 08 · Logic as architecture

The four systems, side by side

What is inside, and what is promised.

SystemInside the graphInferenceGuarantee
DeepProbLogCNN + nADs + grounded formula + SDD + gradient semiringSDD evaluationExact given the nADs
NeurASPGrounded ASP + stable models + weighted sumEnumerationExact under stable models
ScallopRelational algebra + provenance + retained proofsFixpoint + WMCExact if not top-k
ULLERGrounded statements + function applications + semantics operatorsSemantic evaluationExact relative to the semantics

Every guarantee in the last column is conditional on two things: the program is the right one, and the neural predicate distributions are the right probabilities.

Exactness is a property of the computation, not a certificate about the world.
S/V · Lecture 08
07 · Buys & costsLecture 08 · Logic as architecture

Gradient quality

Exact gradients, not necessarily useful ones.

Saturation

A confident wrong posterior is hard to move.

When the query probability is near 0 or 1, the gradient of the negative log-likelihood can be tiny or huge. The normalizer amplifies the saturation.

Piecewise

The support can jump.

The set of stable models or retained proofs can change discontinuously. The gradient is exact on each piece and undefined at the boundary.

Top-k bias

The truncated sum has a biased gradient.

Only the retained proofs receive signal. That can be right for a ranking loss and wrong for a probability.

Calibration

The logic cannot repair a probability.

A miscalibrated network yields an exact posterior for the wrong numbers. Classical semantics yields a zero gradient almost everywhere.

Evaluate the gradient, not just the loss. Exactness of the value does not imply that the parameters move in the right direction.
S/V · Lecture 08
07 · Buys & costsLecture 08 · Logic as architecture

The bill

What the interface buys, and what it costs.

BuysCosts
A hard constraint by constructionWMC is #P-hard in general
An exact posterior relative to the programRestricted fragments, grounding, finite domains
Compositional structure from the programIndependence assumptions on facts and predicates
Weak supervision at the query levelCalibration errors propagate into the posterior
Inspectable worlds, proofs and derivationsGradients can saturate, and top-k can bias them
Use it when the constraint is hard, the program is stable, and the query is countable. Use a loss for soft knowledge, and a verifier when the guarantee must be about the final answer.
S/V · Lecture 08
07 · Buys & costsLecture 08 · Logic as architecture

Interactive · the constraint is a switch

Move the constraint.

Three cells, three values, six valid rows. The constraint is the only thing that changes; the priors stay fixed.

Z · normalizer—
P(all-different)—
MAP row—
MAP posterior—

Toggle the constraint and watch Z and the posterior renormalize.

#RowPrior weightPosterior
prior marginalposterior marginal
S/V · Lecture 08
08 · Cases & recapLecture 08 · Logic as architecture

Read each along the tuple

Four systems, one anatomy.

DeepProbLog · exact

CNNs → nADs → SDD → gradient semiring

Digits in, sum out. The query probability is exact given the neural predicates; the circuit is the cost.

NeurASP · exact

NN atoms → ASP → stable-model enumeration

Sudoku is the canonical case. The rules supervise perception; the stable models are the worlds.

Scallop · exact or top-k

Datalog → provenance → semiring

Recursion and aggregation, with a choice of algebra. Top-k trades exactness for tractability.

ULLER · semantics-dependent

Statements → semantics function

One language, several semantics. The probabilistic value is WMC; the guarantee is relative to the choice.

Read the guarantee before the benchmark. “Exact” without “relative to what?” is a slogan.
S/V · Lecture 08
08 · Cases & recapLecture 08 · Logic as architecture

The design question

Choose the interface.

Architecture

Hard constraint, stable program, countable query.

You need zero mass on invalid worlds, and you can afford the count.

Loss

Soft knowledge, unconstrained output, tight budget.

You want a prior, not a guarantee, and the output space must stay open.

Verifier or search

A guarantee on the answer, or an unknown program.

Check the output after the fact, or search for the program instead of assuming it.

The interfaces are not exclusive. A deployed system can use an architecture for the hard constraint, a loss for a soft preference, and a verifier on the final answer.

The first question is the constraint: is a violation unacceptable, or merely expensive?
S/V · Lecture 08
08 · Cases & recapLecture 08 · Logic as architecture

The four moves

What to carry forward.

01 · Worlds

Probabilistic facts and rules define a distribution over worlds; a query is a weighted sum.

02 · Posterior

Π neural probabilities × the constraint indicator, divided by Z.

03 · Systems

DeepProbLog, NeurASP, Scallop, ULLER: different counts, the same architectural move.

04 · Ledger

Exact relative to the program; #P-hard; gradients can saturate or be biased.

Exact relative to the program.

S/V · Lecture 08
08 · Cases & recapLecture 08 · Logic as architecture

Next · hands-on

Open the enumeration.

The lab is the four-cell version of the hook: twenty-four valid rows, an exact posterior, a noise slider, and a constraint toggle.

The guide derives the same number twice: by enumeration in §0, and by conditioning in §7. The lab is the third derivation, with the controls in your hands.

Lab 08 · exact posterior → open the lab

S/V · Lecture 08
Speaker notes