Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS

By Feng Niu, Christopher R'e, AnHai Doan, Jude W. Shavlik. Proceedings of the VLDB Endowment, 2011

306 citations recorded by the source corpus.

Markov Logic Networks (MLNs) have emerged as a powerful framework that combines statistical and logical reasoning; they have been applied to many data intensive problems including information extraction, entity resolution, and text mining. Current implementations of MLNs do not scale to large real-world data sets, which is preventing their widespread adoption. We present Tuffy that achieves scalability via three novel contributions: (1) a bottom-up approach to grounding that allows us to leverage the full power of the relational optimizer, (2) a novel hybrid architecture that allows us to perform AI-style local search efficiently using an RDBMS, and (3) a theoretical insight that shows when one can (exponentially) improve the efficiency of stochastic local search. We leverage (3) to build novel partitioning, loading, and parallel algorithms. We show that our approach outperforms state-of-the-art implementations in both quality and speed on several publicly available datasets.

Subfields: Artificial Intelligence, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/3afdfe832950d012f2fa14a067bb332de1172c7e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Christopher R'e
2. Mohit Bansal
3. Li Fei-Fei
4. Stefano Ermon
5. Percy Liang
6. Yoshua Bengio
7. Sergey Levine
8. Quoc V. Le

In Information Systems

1. Christopher R'e
2. Xu Chu
3. Ce Zhang
4. Ihab F. Ilyas
5. Christopher D. Manning
6. Theodoros Rekatsinas
7. Neha Nayak Kennard
8. Gabor Angeli

In Signal Processing

1. Christopher R'e
2. Ce Zhang
3. Yang Song
4. Alexander J. Ratner
5. Stefano Ermon
6. Christopher De Sa
7. Chenlin Meng
8. Sen Wu

Citations in the corpus

• Incremental Knowledge Base Construction Using DeepDive (2015, methodology): “From a machine learning perspective, DeepDive’s language is based on Markov Logic [16,35]: DeepDive’s language inherits Markov Logic Networks’ (MLN’s) formal semantics.”
• A user-guided approach to program analysis (2015, background): “Given the variety of solvers that already exist [8,14,26,33,34,37], and the ongoing active research in this area, we expect the running times to improve further.”
• News events prediction using Markov logic networks (2018, methodology): “In this article, we employed the MLN interface engine Tuffy [62], which leverages time-tested relational data-base management system (RDBMS) infrastructure for joins to achieve high performance at scale.”
• Building a Large-scale Multimodal Knowledge Base for Visual Question Answering (2015, background): “A number of recent advances have been made in the database community to shed light on how to build a largescale knowledge base (KB) [6, 8, 25].”
• Probabilistic programming (2014, background): “Probabilistic logic languages include BLOG [40], Alchemy [31], and Tuffy [43].”
• Building a Large-scale Multimodal Knowledge Base System for Answering Visual Queries (2015, background): “A number of recent advances have been made in the database community to shed light on how to build a large-scale KB [12, 13, 34].”
• Combining Natural Logic and Shallow Reasoning for Question Answering (2016, background): “…proof theory that aims to capture a subset of logical inferences by appealing directly to the structure of language, without needing either an abstract logical language (e.g., Markov Logic Networks; Richardson and Domingos (2006)) or denotations (e.g., semantic parsing; Liang and Potts (2015)).”
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving (2020, methodology): “Jacobi-type iterations are also used in message passing algorithms for probabilistic graphical models (Elidan et al., 2012; Niu et al., 2011) and graph neural networks (GNNs, Scarselli et al.”
• DeepDive: Web-scale Knowledge-base Construction using Statistical Learning and Inference (2012, methodology): “A Markov logic program (aka Markov logic network, or simply MLN) specifies what (evidence) data are available, what predictions to make, and what constraints and correlations there are [10].”
• DeepDive: Declarative Knowledge Base Construction (2016, methodology): “In addition to specifying sets of classifiers, DeepDive inherits Markov Logic’s ability to specify rich correlations between entities via weighted rules.”
• HoloClean: Holistic Data Repairs with Probabilistic Inference (2017, background): “Recent works have introduced general-purpose systems for specifying probabilistic models and running probabilistic inference [6, 41, 46].”