Bayesian Logic

Origin. Multiple traditions: Bayesian networks (Pearl, 1988), Bayesian logic programs (Kersting, 2000), BLOG (Milch, 2005). Combines first-order logic with Bayesian probability. Uncertain relational domains. Foundation for probabilistic programming and statistical relational learning.

Models. Probability over relational structures. First-order logic: relations, quantifiers, certain truth. Bayesian: probability distributions, conditioning. Combined: distributions over possible worlds with relational structure. Query: P(φ | evidence).

Formalism.

Bayesian networks: DAG with nodes = random variables. Edges = direct dependencies. P(X₁,...,Xₙ) = ∏ᵢ P(Xᵢ | Parents(Xᵢ))

Bayesian Logic Programs (BLPs): Combine logic programs with Bayesian networks. Clauses with conditional probabilities. Ground to Bayesian network for inference.

BLOG (Bayesian Logic): First-order probabilistic language. Unknown number of objects (open-universe). type Person; origin(Person) ~ Poisson(10); random Boolean Friends(Person, Person) ~ Bernoulli(0.1);

Probabilistic relational models: Classes, attributes, relations with CPDs. Aggregation: how to combine evidence from multiple related objects.

Inference:

• Exact: variable elimination, junction trees
• Approximate: MCMC, importance sampling, variational
• Lifted: exploit symmetry, avoid grounding

Learning: Parameter learning: MLE, EM Structure learning: search over models

Symbols.

Metatheory. The graph and the distribution correspond exactly: a distribution factorizes along a DAG iff it satisfies the local Markov condition for that DAG, and Verma and Pearl (1988) proved d-separation sound and complete for the independences so entailed — every d-separation holds in every distribution factorizing along the graph, and every d-connection fails in some such distribution. Verma and Pearl (1990) then characterized when two DAGs entail the same independences: iff they have the same skeleton and the same v-structures, so the graph is identifiable only up to its Markov equivalence class. Inference is intractable in the exact and approximate cases alike. Cooper (1990) proved exact inference in a general Bayesian network NP-hard; Roth (1996) showed the counting version #P-complete; Dagum and Luby (1993) showed that even approximating a marginal to within a relative factor is NP-hard. Lauritzen and Spiegelhalter (1988) gave the junction tree algorithm, exact and linear in the network but exponential in the treewidth of the moralized graph.

Applies to. Knowledge graphs. Natural language understanding. Biological networks. Social network analysis. Robotics (SLAM). Citation analysis. Medical diagnosis.

Limitations. Because Markov equivalent graphs entail exactly the same independences, observational data cannot orient an edge within an equivalence class, so no amount of data distinguishes X → Y from Y → X in a two-node model; recovering direction requires intervention or an assumption outside the formalism. The inference from independences back to a graph also needs faithfulness — that the distribution exhibits no independence beyond those the graph entails — and faithfulness fails whenever two causal paths cancel, a set of parameter values that is measure zero but not empty. Acyclicity is required for the factorization to define a distribution at all, so feedback systems have no direct representation. Structure learning is NP-hard (Chickering, 1996), even with complete data and bounded in-degree. Open-universe languages such as BLOG can specify generative models whose recursion has no least fixed point, so a well-formed program need not determine a probability measure, and the conditions guaranteeing one must be checked separately.

© 2026 Lingenic LLC