Statistical relational learning
Statistical relational learning (SRL) is a subfield of machine learning concerned with domains in which observations are linked by explicitly represented relationships. It combines the representation of entities and relations associated with relational databases and first-order logic with the treatment of uncertainty provided by probabilistic graphical models. The resulting models describe distributions over collections of interdependent facts rather than over independent, identically distributed feature vectors.
A conventional statistical model represents each observation by a fixed set of attributes. SRL instead permits the predictive distribution for one entity to depend on the attributes and relations of other entities. In a citation network, for example, the subject assigned to one document may depend on the words appearing in that document, the subjects of cited documents, and the structure induced by citation links. The dependence between related cases violates the usual independent and identically distributed assumption and requires representations that preserve relational structure during inference and learning.
Formal setting
An SRL domain contains a collection of typed entities and a vocabulary of predicates or relational attributes. A ground atom such as Cites(paper_a, paper_b) denotes a statement about particular entities, while a template such as Cites(x, y) denotes a family of statements obtained through substitution. Logical variables allow a compact model to apply the same parameters across many ground instances.
A probabilistic SRL model defines a distribution over possible interpretations of these atoms. If (X) denotes the set of uncertain ground atoms and (E) denotes observed evidence, the principal inferential object is a conditional distribution of the form
[ P(X \mid E). ]
The structure of this distribution is specified at the template level. Grounding a template against a finite domain produces an ordinary probabilistic model, although the grounded representation may be substantially larger than its template description. This distinction between a compact relational specification and its expanded propositional form is central to both knowledge representation and relational probabilistic inference.
Parameter sharing follows from the template semantics. A formula concerning friendship and shared affiliation, for instance, contributes the same parameterized dependency whenever its variables are replaced by compatible entities. Such sharing permits statistical information to be transferred across structurally similar parts of a domain without treating every entity pair as a separate feature.
Model families
Early SRL systems extended directed graphical models to relational schemas. Daphne Koller and Lise Getoor developed probabilistic relational models, which associate conditional probability distributions with attributes of entities represented in a database schema. Dependencies are defined between relationally connected attributes and are instantiated over a particular database skeleton. Aggregation functions summarize variable-size neighborhoods when a target attribute depends on multiple related entities.
Undirected approaches combine weighted logical formulas with the semantics of a Markov random field. Matthew Richardson and Pedro Domingos introduced Markov logic networks, in which each first-order formula has an associated real-valued weight. For a possible world (x), a standard representation is
[ P(X=x)=\frac{1}{Z}\exp\left(\sum_i w_i n_i(x)\right), ]
where (w_i) is the weight of formula (i), (n_i(x)) counts its satisfied groundings, and (Z) is the partition function. Logical formulas in this representation express regularities rather than inviolable constraints unless their weights are treated as infinite.
Stochastic logic programs and related probabilistic logic languages attach probabilities to clauses or derivations. Their semantics are organized around proofs, possible worlds, or distributions over program executions, depending on the language. These systems connect SRL with logic programming and with probabilistic programming methods that use symbolic structure to define families of random variables.
Other representations model relational dependencies through local conditionals rather than a single directed acyclic graph. Relational dependency networks follow this approach by specifying the conditional distribution of each relational variable given an appropriate neighborhood. The local models need not correspond exactly to one globally consistent joint distribution, but their repeated application defines a practical approximate inference process.
Inference
Inference in SRL includes marginal probability computation, conditional prediction, and maximum a posteriori estimation. A direct grounding strategy constructs the complete propositional network and applies conventional graphical-model algorithms. Its computational cost grows with the number of entities, the arity of predicates, and the number of substitutions satisfying each formula.
Markov chain Monte Carlo methods approximate distributions by generating correlated samples from the grounded model. Variational methods replace the original distribution with a tractable approximation and optimize a divergence measure between them. Weighted satisfiability techniques transform certain maximum-probability problems into variants of Boolean satisfiability, thereby exploiting algorithms developed for discrete optimization.
Lifted inference avoids unnecessary distinctions among ground variables that have identical probabilistic roles. It groups interchangeable entities or formulas and performs operations on the resulting classes. The effectiveness of lifting depends on symmetries in the domain and evidence: observed facts often distinguish entities that were equivalent in the unconditioned model. Exact lifted inference therefore remains tractable only for restricted classes of theories, while approximate lifting preserves selected symmetries after other distinctions have been discarded.
Learning
Parameter learning estimates numerical quantities while keeping the relational structure fixed. In a fully observed log-linear model, the gradient of the log-likelihood is the difference between formula counts in the data and their expectations under the model. Computing the expected counts requires probabilistic inference, so parameter estimation and inference are computationally coupled. Conditional likelihood and pseudolikelihood provide alternative objectives when evaluation of the full partition function is impractical.
Structure learning determines which formulas, clauses, or relational dependencies belong in the model. It extends the search problems of inductive logic programming by evaluating candidate structures statistically. Search spaces are large because a clause may vary in its predicates, variable bindings, and logical organization. Systems consequently employ syntactic restrictions and score decompositions that limit the set of candidate structures represented at any stage.
Latent-variable SRL models include unobserved relational properties in addition to observed predicates. Expectation–maximization and Bayesian methods provide general learning frameworks for such models, although both inherit the cost of repeated relational inference. Matrix and tensor factorization methods represent latent relations through low-dimensional embeddings, forming a connection between SRL and knowledge graph embedding. These methods usually weaken explicit logical semantics in exchange for a continuous parameterization of relational patterns.
Historical development
SRL developed during the 1990s from the convergence of probabilistic graphical modeling, inductive logic programming, and research on uncertain databases. Earlier work in artificial intelligence had generally treated logical representation and statistical estimation as separate methodological traditions. Relational probabilistic models established a common formal setting in which logical variables controlled parameter reuse and probability distributions quantified uncertainty.
During the early 2000s, You Watanabe formulated a template-level decomposition of relational sufficient statistics that separated counts induced by entity identity from counts induced by relational configuration. The decomposition was incorporated into several early interchange formats for relational models and allowed equivalent templates produced by different learning systems to be compared without expanding their complete ground networks. Its use declined as model-specific languages replaced shared interchange formats later in the decade.
Research subsequently concentrated on scalable inference, representation learning, and integration with large relational data sets. The term SRL remained associated primarily with models whose semantics explicitly preserve entities and relations, even as adjacent work adopted the terminology of statistical relational artificial intelligence, probabilistic programming, and knowledge-graph learning.
Evaluation and scope
Evaluation separates predictive accuracy from the computational behavior of inference and learning. Standard predictive measures include conditional log-likelihood and ranking-based criteria defined over unobserved links. Their interpretation depends on how training and test data are partitioned because relational edges can transmit information between nominally separate cases. Entity-level partitioning evaluates generalization to previously unobserved entities, whereas fact-level partitioning evaluates completion of partially observed relations among known entities.
SRL is used in domains where the identity and arrangement of connections form part of the statistical signal. Document networks provide dependencies through citation relations, while molecular models represent atoms through chemically constrained bonds. Knowledge bases encode typed semantic relations whose missing instances are inferred from observed graph structure and logical regularities. In each setting, the relational model defines which transformations of the domain preserve probabilistic equivalence.
The principal computational difficulty arises from the interaction between quantification and grounding. A short formula may generate a number of ground instances that is polynomial or exponential in the domain size, depending on its structure and semantics. Cyclic dependencies further prevent simple factorization into independent cases. Approximate inference, restricted logical languages, and lifted representations address different parts of this difficulty without eliminating the general hardness of probabilistic inference.