Probabilistic Logic

Origin. Nils Nilsson introduced probabilistic logic for AI (1986). Combines first-order logic with probability assignments to formulas. Halpern's work on probabilistic reasoning about knowledge (1990s). Markov Logic Networks (Richardson & Domingos, 2006) combine first-order logic and probabilistic graphical models. Multiple traditions: logical, AI, statistical.

Models. Assigning probabilities to logical formulas. Classical logic: formulas are true or false. Probabilistic logic: formulas have probabilities. "P(Flies(x) | Bird(x)) = 0.9" — birds probably fly. Combines logical structure with uncertainty quantification.

Formalism.

Probability on formulas: Given a set of possible worlds W, probability P: W → [0,1] with Σ P(w) = 1. P(φ) = Σ{P(w) : w ⊨ φ}

Probabilistic sentences: w(φ) ≥ r — "probability of φ is at least r" w(φ) = r — "probability of φ is exactly r"

Nilsson's probabilistic logic:

Logical constraints (FOL sentences)
Probabilistic constraints: linear inequalities on P(φᵢ)
Entailment: determine bounds on query probabilities

Example: Given: P(Bird) = 0.3, P(Flies|Bird) = 0.9, P(Flies|¬Bird) = 0.01 Query: P(Bird|Flies) = ? (Bayes' theorem applies)

Markov Logic Networks (MLNs): First-order formulas as soft constraints with weights.

Formula φᵢ with weight wᵢ
Probability of world: P(w) ∝ exp(Σᵢ wᵢ · nᵢ(w)) where nᵢ(w) = number of true groundings of φᵢ in w

Hard constraint: infinite weight (must be satisfied). Soft constraint: finite weight (preference, not requirement).

Inference:

MAP inference: find most probable world
Marginal inference: compute P(φ)
Weight learning: learn wᵢ from data

Probabilistic databases: Tuples with probabilities; query answering under uncertainty.

Symbols.

Symbol	Unicode	Name	Meaning
P(φ)	—	Probability	Probability of φ
P(φ\|ψ)	—	Conditional	P of φ given ψ
w(φ)	—	Weight function	Probability assignment
≥, ≤, =	—	Constraints	Probability bounds
wᵢ	—	Weight	Formula weight (MLN)
⊗	U+2297	Combination	Product in network
∝	U+221D	Proportional	Unnormalized probability

Metatheory. Probabilistic satisfiability is NP-complete. MLN inference is #P-hard in general. Lifted inference exploits symmetry for tractable cases. Maximum entropy: among consistent probability distributions, prefer maximum entropy. Probabilistic logic subsumes classical logic (certainty = probability 1).

Applies to. Uncertain reasoning in AI. Knowledge base uncertainty. Statistical relational learning. Information extraction. Social network analysis. Natural language understanding. Combining logic and machine learning.

Limitations. Inference is computationally hard. Probability assignment (priors) is often subjective. MLN weight learning requires data. Scaling to large knowledge bases is challenging. Exact inference rarely tractable; approximations needed. Different frameworks (Nilsson, MLN, Bayesian logic programs) have different trade-offs. Open-world vs closed-world probability assumptions matter.