ProbLog

Origin. De Raedt, Kimmig and Toivonen, "ProbLog: A Probabilistic Prolog and Its Application in Link Discovery" (IJCAI 2007). The semantics is Sato's distribution semantics, introduced for PRISM in 1995, and shared with Poole's Independent Choice Logic (1997); ProbLog's contribution was to compute with it by knowledge compilation to binary decision diagrams rather than by enumerating proofs. ProbLog2 (Fierens et al., TPLP 2015) recast inference as weighted model counting and extended the language with stratified negation, evidence and annotated disjunctions.

Models. Randomness lives only in the facts; the rules are deterministic. A program is a set of probabilistic facts p::f, each an independent Bernoulli switch, together with a definite logic program. A total choice — a subset of the ground probabilistic facts — turns the program into an ordinary one with a unique least Herbrand model, and the probability of a query is the total probability of the choices whose least model entails it. Conditioning on evidence renormalizes over the choices consistent with it. Logical structure and uncertainty are thus kept apart: the program says what follows from what, the facts say what is uncertain.

Formalism.

Probabilistic facts: p::f (fact f holds with probability p) Example: 0.3::earthquake.

Logic program: Definite clauses over probabilistic facts. alarm :- earthquake. alarm :- burglary.

Distribution semantics: Each probabilistic fact: independent Bernoulli. Total choice σ ⊆ F, the set of ground probabilistic facts. World w = LM(σ ∪ R), the least Herbrand model of the chosen facts and the rules. P(w) = ∏{pf | f ∈ σ} · ∏{1-pf | f ∉ σ}

Query probability: P(q) = ∑{P(w) | w ⊨ q} Sum over worlds where query holds. Not the sum over proofs: proofs share facts, so their events overlap (the disjoint-sum problem).

Conditioning: P(q | e) = P(q ∧ e) / P(e). Evidence restricts to the total choices whose least model satisfies e. Undefined when P(e) = 0.

Example: 0.1::burglary. 0.2::earthquake. alarm :- burglary. alarm :- earthquake. P(alarm) = P(burglary ∨ earthquake) = 0.1 + 0.2 - 0.02 = 0.28

Inference: Ground the relevant part of the program. Convert to a propositional formula over the probabilistic facts (Clark completion for stratified negation). P(q) = weighted model count of that formula, weights pf and 1−pf. Exact: compile to BDD, d-DNNF or SDD; counting is then linear in circuit size. Approximate: sampling, or bounds from partial proof enumeration.

Learning: Parameter learning: learn probabilities. Structure learning: learn rules. LFI: learning from interpretations.

Extensions: Annotated disjunctions: p₁::a₁; ...; pₙ::aₙ. Continuous distributions (DC-ProbLog).

Symbols.

Symbol	Unicode	Name	Meaning
p::f	—	Probabilistic fact	Fact f holds independently with probability p
::	—	Double colon	Attaches a probability to a fact
:-	—	Neck	Definite clause, "if"
P(q)	—	Query probability	Marginal probability of the query
⊨	U+22A8	True / Double turnstile	World satisfies the query
σ	U+03C3	Greek small sigma	A total choice, a subset of the facts
F	—	Fact set	The ground probabilistic facts
R	—	Rules	The definite clauses
LM	—	Least model	Least Herbrand model of a total choice
w	—	World	A least model, one per total choice
e	—	Evidence	The conditioning observation
∏	U+220F	N-ary product	Product over chosen and unchosen facts
∑	U+2211	N-ary summation	Sum over worlds entailing the query
⊆	U+2286	Subset	A total choice inside the fact set
∈	U+2208	Element of	Fact selected by the total choice
∉	U+2209	Not an element of	Fact left out of the total choice
∨	U+2228	Logical or	Disjunction in the worked example
∧	U+2227	Logical and	Conjunction of query and evidence
;	U+003B	Semicolon	Separator in an annotated disjunction
\|	—	Vertical line / Given	Conditioning bar, and set-builder separator

Metatheory. Sato (1995) proved the distribution semantics well-defined even with countably many probabilistic facts: the product measure on total choices extends from the cylinder sets by Kolmogorov's extension theorem, and since each total choice yields a definite program with a unique least Herbrand model, every query receives exactly one probability. Poole's Independent Choice Logic and PRISM are the same semantics under different syntax, and annotated disjunctions are definable from independent facts, so the language extensions add convenience rather than expressive power. Fierens et al. (2015) showed exact inference is weighted model counting on the Clark completion of the relevant ground program, which is where the complexity sits: the problem is #P-hard, by reduction from counting satisfying assignments, and it is #P-hard already for the propositional case because summing over proofs double-counts shared facts. Approximation is better behaved than the exact problem for definite programs, where P(q) is the probability of a monotone DNF over the facts and Karp and Luby's (1983) estimator gives a fully polynomial randomized approximation scheme.

Applies to. Probabilistic reasoning. Bioinformatics. NLP. Probabilistic databases. Neuro-symbolic AI.

Limitations. Independence is not an assumption that can be relaxed but the source of the distribution: every dependence must be manufactured by rules over independent switches, and a correlated pair of facts has no direct expression. The unique-model guarantee comes from restricting to definite and stratified programs; allow loops through negation and a total choice may yield several stable models or none, at which point probability mass is split by stipulation or left unassigned, and the semantics has to be replaced rather than extended. Inference is not lifted: the program is grounded first, so a clause with k variables produces a formula of size polynomial in the domain to the k, and the compiled circuit can be exponential in that even when the query is simple — the disjoint-sum problem leaves no proof-by-proof shortcut. Continuous variables break the construction outright, since the space of total choices becomes uncountable and weighted model counting gives way to weighted model integration, whose tractability depends on the integrals admitting closed form. Conditioning on evidence of probability zero is undefined, which for continuous extensions is the normal case.