Learning statistical models from relational data
Published 12 June 2011
Lise Getoor, Lilyana Mihalkova
Citations121
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This survey will provide an introduction to SRL, describe some of the distinguishing characteristics of SRL systems, including relational feature construction and collective classification, and discuss connections between SRL methods and existing database research such as probabilistic databases.
Abstract
Statistical Relational Learning (SRL) is a subarea of machine learning which combines elements from statistical and probabilistic modeling with languages which support structured data representations. In this survey, we will: 1) provide an introduction to SRL, 2) describe some of the distinguishing characteristics of SRL systems, including relational feature construction and collective classification, 3) describe three SRL systems in detail, 4) discuss applications of SRL techniques to important data management problems such as entity resolution, selectivity estimation, and information integration, and 5) discuss connections between SRL methods and existing database research such as probabilistic databases.
Keywords
Computer ScienceDecision Sciences
AI MagazineCollective Classification in Network Data
3,287 Citations2008Prithviraj Sen, Galileo Namata +4 more
This article introduces four of the most widely used inference algorithms for classifying networked data and empirically compare them on both synthetic and real-world data.
Machine LearningMarkov logic networks
2,678 Citations2006Matthew Richardson, Pedro Domingos
Experiments with a real-world database and knowledge base in a university domain illustrate the promise of this approach to combining first-order logic and probabilistic graphical models in a single representation.
Learning Probabilistic Relational Models
941 Citations2001Lise Getoor, Nir Friedman +2 more
New Generation ComputingInductive logic programming
932 Citations1991Stephen Muggleton
A discussion of the feasibility of extending the RLGG framework to allow for the invention of new predicates and the possible relationship between Algorithmic Complexity theory and Probably-Approximately-Correct Learning is discussed.
Inductive Logic Programming: Techniques and Applications
767 Citations1993Nada Lavrač, Sašo Džeroski
Applications of inductive logic programming: learning rules for early diagnosis of rheumatic diseases finite element mesh design an overview of selected ILP applications.
The Kluwer international series on advances in database systemsManaging and Mining Graph Data
586 Citations2010Charų C. Aggarwal, Haixun Wang
This is the first comprehensive survey book in the emerging topic of graph data processing and contains extensive surveys on important graph topics such as graph languages, indexing, clustering, data generation, pattern mining, classification, keyword search, pattern matching, and privacy.
First-order probabilistic inference
420 Citations2003David Poole
This paper presents an algorithm to reason about multiple individuals, where the authors may know particular facts about some of them, but want to treat the others as a group.
Synthesis lectures on artificial intelligence and machine learningMarkov Logic: An Interface Layer for Artificial Intelligence
319 Citations2009Pedro Domingos, Daniel Lowd
Lecture notes in computer scienceProbabilistic Inductive Logic Programming
314 Citations2008Luc De Raedt, Kristian Kersting
This chapter outlines three classical settings for inductive logic programming, namely learning from entailment, learning from interpretations, and learning from proofs or traces, and shows how they can be adapted to cover state-of-the-art statistical relational learning approaches.
Iterative Classification in Relational Data
306 Citations2000Jennifer Neville, David Jensen
An iterative classification approach that uses simple Bayesian classifiers in an iterative fashion, dynamically upd ating the attributes of some objects as inferences are made about related ob jects.
The MIT Press eBooksLifted First-Order Probabilistic Inference
282 Citations2007Rodrigo de Salvo Braz, Eyal Amir +1 more
This paper presents the first exact inference algorithm that operates directly on a first- order level, and that can be applied to any first-order model (specified in a language that generalizes undirected graphical models).
Probabilistic frame-based systems
269 Citations1998Daphne Koller, Avi Pfeffer
This paper provides a language that cleanly integrates frame-based representation systems and Bayesian networks, and describes an implemented system that allows most of the main frame systems in existence today to annotate their knowledge bases with Probabilistic information, and to use that information in answering probabilistic queries.
Selectivity estimation using probabilistic models
265 Citations2001Lise Getoor, Benjamin Taskar +1 more
The approach produces more accurate estimates than standard approaches to selectivity estimation, using comparable space and time for both single-table multi-attribute queries and a general class of select-join queries.
Learning probabilistic models of link structure
239 Citations2003Lisa Getoor, Nir Friedman +2 more
This paper proposes two mechanisms for representing a probabilistic distribution over link structures: reference uncertainty and existence uncertainty, and describes the appropriate conditions for using each model and present learning algorithms for each.
Lifted first-order belief propagation
218 Citations2008Parag Singla, Pedro Domingos
This paper proposes the first lifted version of a scalable probabilistic inference algorithm, belief propagation, based on first constructing a lifted network, where each node represents a set of ground atoms that all pass the same messages during belief propagation.
DSpace@MIT (Massachusetts Institute of Technology)Lifted probabilistic inference with counting formulas
179 Citations2008Brian Milch, Luke Zettlemoyer +3 more
This paper presents a new lifted inference algorithm, C-FOVE, that not only handles counting formulas in its input, but also creates counting formulas for use in intermediate potentials, and achieves asymptotic speed improvements compared to FOVE.
arXiv (Cornell University)Counting Belief Propagation
149 Citations2012Kristian Kersting, Babak Ahmadi +1 more
The experiments show that counting BP is applicable to a variety of important AI tasks such as (dynamic) relational models and boolean model counting, and that significant efficiency gains are obtainable, often by orders of magnitude.
arXiv (Cornell University)Probabilistic Similarity Logic
127 Citations2012Matthias Bröcheler, Lilyana Mihalkova +1 more
Probabilistic similarity logic (PSL) is introduced, a general-purpose framework for joint reasoning about similarity in relational domains that incorporates probabilistic reasoning about similarities and relational structure in a principled way.
The MIT Press eBooksPredicting Structured Data (Neural Information Processing)
97 Citations2007Gükhan H. Bakir, Thomas Hofmann +4 more
arXiv (Cornell University)Relational Bayesian Networks
93 Citations2013Manfred Jaeger
A new method is developed to represent probabilistic relations on multiple random events by using a powerful way of specifying conditional probability distributions in these networks, which provides for constraints on equalities of events and allows to define complex, nested combination functions.
Journal of Machine Learning ResearchLearning probabilistic models of link structure
87 Citations2003GetoorLisa, FriedmanNir +2 more
Proceedings of the VLDB EndowmentExploiting shared correlations in probabilistic databases
80 Citations2008Prithviraj Sen, Amol Deshpande +1 more
This work shows how data characteristics can be leveraged to make the query evaluation process more efficient, and introduces a new data structure, called the random variable elimination graph (rv-elim graph) that can be built from the PGM obtained from query evaluation.
Probabilistic Models of Text and Link Structure for Hypertext Classification
77 Citations2001Lise Getoor, Eran Segal +2 more
This work proposes a unified probabilistic model for both the textual content and the link structure of a document collection based on the recently introduced framework of Probabilistic Relational Models (PRMs), which allows us to capture correlations between linked documents.
Lecture notes in computer scienceProbabilistic Inductive Logic Programming
70 Citations2004Luc De Raedt, Kristian Kersting
MPE and partial inversion in lifted probabilistic variable elimination
59 Citations2006Rodrigo de Salvo Braz, Eyal Amir +1 more
A significantly more general lifted variable elimination algorithm, FOVE-P, that covers many cases where atoms share logical variables and the notion of lifted assignments, a distribution of values to a set of random variables rather than to each individual one is introduced.
arXiv (Cornell University)Bisimulation-based Approximate Lifted Inference
48 Citations2012Prithviraj Sen, Amol Deshpande +1 more
arXiv (Cornell University)Template Based Inference in Symmetric Relational Markov Random Fields
41 Citations2012Ariel Jaimovich, Ofer Meshi +1 more
Statistical Relational Learning
23 Citations2017Lise Getoor
This tutorial will overview the field of statistical relational learning (SRL) and survey common approaches, make connections to work in probabilistic databases, and highlight commonalities and differences among them.
Lecture notes in computer scienceTutorial on Statistical Relational Learning
17 Citations2005Lise Getoor
Relational learning often involves instances that are heterogeneous, where the result of learning is a set of multiple components (classifiers, probability distributions, etc.) that predict labels of objects and logical relationships between objects.
Lecture notes in computer scienceSRL without Tears: An ILP Perspective
1 Citations2008Kristian Kersting
This tutorial provides an gentle introduction to and an overview of the state-of-the-art in statistical relational learning, starting from classical settings for inductive logic programming and showing how they can be extended with probabilistic methods.