Statistical relational learning
25 Nov 2019 Logic Probability LearningStatistical relational learning (Koller et al., 2007) is a branch of artificial intelligence (AI) devoted to integrate research in probability theory, statistics, logics and relational learning. Its main purpose is to develop learning models that handle uncertain information extracted from real world scenarios, and produce structured representations that describe objects, attributes and their relations.
Relational structures are able to provide complex models that describe objects in terms of attributes and relations. However, treatment of noisy, erroneous, duplicate and missing information is a common problem for relational learning systems due to their crisp representation of the domain.
During recent years, the machine learning (ML) community focused on statistical techniques (e.g. decision trees, support vector machines, neural networks, clustering, dimentionality reduction, reinforcement learning, and so on) that provided high prediction accuracy in many domains such as economics, bioinformatics, game playing, advertising, computer vision, speech recognition, natural language processing, recommendation systems just to name a few. These statistical models are inherently capable of dealing with uncertain information, though often at the expense of an interpretable model of the domain’s concepts.
Among the strong motivations for using a relational model is its ability to model dependencies between related instances. Intuitively, we would like to use our information about one object to help us reach conclusions about other, related objects. For example, in web data, we should be able to propagate information about the topic of a document to documents it has links to and documents that link to it.
Common problems
There are some classical problems in statistical relational learning systems (Koller et al., 2007):
- Relational feature construction between a model’s random variables and statistical predicate invention.
- Relational feature aggregation: because describing the influence of neightbors towards an object might be infeasible, aggregates provide a solution for defining relational neightborhood.
- Structural uncertainty: when there are many logical interpretation for the set of random variables. Namely, when the identity, attributes or domain itself are uncertain.
Existing work
Some approaches in the literature include (Koller et al., 2007):
- Inductive logic programming (ILP): learning logical rules from set of examples and background knowledge (Muggleton & De Raedt, 1994).
- Conditional random fields (CRF): (Sutton et al., 2012).
- Frame-based approaches:
- Probabilistic relational models (PRM): (Getoor et al., 2007).
- Relational markov networks (RMN): (Taskar et al., 2007).
- Probabilistic entity-relation models (PER) (Heckerman et al., 2004).
- Relational dependency networks (RDN): (Neville & Jensen, 2007).
- Logic-based approaches:
- Probabilistic knowledge bases.
- Probabilistic logic programming.
- Bayesian logic programming (BLP).
- Stochastic logic programming (SLP).
- Markov logic networks (MLN).
- Bayesian logic (BLOG) system, a language that defines probability distributions over outcomes with varying sets of objects. Which does not make the assumptions of unique names, requiring that the symbols or terms of the language all refer to distinct objects, and domain closure, requiring that no objects exist besides the ones referred to by terms in the language.
- Integrated Bayesian Agent Language (IBAL) system: a functional programming language for probabilistic AI.
- Lifted First-Order Probabilistic Inference.
- Structured generalized linear regression (SGLR).
- Reinforcement Learning in Relational Domains.
Canonical tasks
A number of canonical tasks are associated with statistical relational learning, the most common ones being:
- Collective classification, i.e. the (simultaneous) prediction of the class of several objects given objects’ attributes and their relations.
- Link prediction, i.e. predicting whether or not two or more objects are related.
- Link-based clustering, i.e. the grouping of similar objects, where similarity is determined according to the links of an object, and the related task of collaborative filtering, i.e. the filtering for information that is relevant to an entity (where a piece of information is considered relevant to an entity if it is known to be relevant to a similar entity).
- Social network modelling.
- Object identification/entity resolution/record linkage, i.e. the identification of equivalent entries in two or more separate databases/datasets.
References
- Koller, D., Friedman, N., Džeroski, S., Sutton, C., McCallum, A., Pfeffer, A., Abbeel, P., Wong, M.-F., Heckerman, D., Meek, C., & others. (2007). Introduction to statistical relational learning. MIT press.
- Raedt, L. D., & Kersting, K. (2010). Statistical relational learning. Encyclopedia of Machine Learning, 916–924.
- Muggleton, S., & De Raedt, L. (1994). Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19, 629–679.
- Sutton, C., McCallum, A., & others. (2012). An introduction to conditional random fields. Foundations and Trends Ⓡ in Machine Learning, 4(4), 267–373.
- Getoor, L., Friedman, N., Koller, D., Pfeffer, A., & Taskar, B. (2007). Probabilistic relational models. Introduction to Statistical Relational Learning, 8.
- Taskar, B., Abbeel, P., Wong, M.-F., & Koller, D. (2007). Relational markov networks. Introduction to Statistical Relational Learning, 175–200.
- Heckerman, D., Meek, C., & Koller, D. (2004). Probabilistic models for relational data. Technical Report MSR-TR-2004-30, Microsoft Research.
- Neville, J., & Jensen, D. (2007). Relational dependency networks. Journal of Machine Learning Research, 8(Mar), 653–692.