TensorLog: A Probabilistic Database Implemented Using Deep-Learning Infrastructure

William W. Cohen, Fan Yang, Kathryn MazaitisJAIR 2020 · OpenReview

TL;DR

This paper introduces TensorLog, a system that bridges the gap between probabilistic first-order logic and deep learning frameworks like TensorFlow. By compiling logical queries into differentiable functions, TensorLog allows for efficient, GPU-accelerated learning of probabilistic logic parameters, enabling scalable reasoning over large knowledge bases.

What Problem Does This Paper Address?

Traditional probabilistic first-order logic systems often require specialized learners and struggle to integrate with the powerful, GPU-accelerated infrastructure of modern deep learning. This limits the ability to leverage deep learning's optimization capabilities for probabilistic reasoning and to incorporate complex logical knowledge into deep learning models. The authors aim to create a system that seamlessly integrates probabilistic logic with deep learning, allowing for efficient inference and learning on large-scale problems.

Methods

The core of TensorLog's approach is to compile probabilistic logic programs into differentiable functions that can be executed within deep learning frameworks. They achieve this by:

  • Polytree-Limited Stochastic Deductive Knowledge Graphs (ptree-SDKGs): Identifying a tractable subset of probabilistic logic that is still expressive.
  • Dynamic Programming for Inference: Developing an efficient algorithm based on belief propagation on factor graphs, which can be "unrolled" into a series of differentiable matrix operations.
  • TensorFlow/Theano Integration: Compiling these operations into computation graphs compatible with popular deep learning frameworks, enabling GPU acceleration and automatic differentiation.
  • Sparse Matrix Representation: Utilizing sparse matrices to efficiently represent knowledge bases, crucial for scalability.

Datasets

The paper uses several datasets for evaluation:

  • Artificial Graphs: For scalability experiments, including "friends and smokers" and "grid transitive closure" problems, generated with varying sizes up to 2 million facts.
  • Grid Navigation Task: A synthetic dataset designed to test learning performance on recursive tasks.
  • WikiMovies Dataset: A real-world dataset for question-answering against a knowledge base, containing over 420k tuples.
  • Relational Learning Benchmarks: Standard tasks like CORA, UMLS, WordNet, Hypernym, and Hyponym.

Key Insights and Ideas

  • Bridging Logic and Deep Learning: The fundamental insight is that by representing logical inference as differentiable functions, we can leverage the entire deep learning ecosystem (GPUs, optimizers, automatic differentiation) for probabilistic logic.
  • Scalability through Compilation: Compiling logic into differentiable operations, rather than relying on traditional theorem provers, is key to achieving scalability on large knowledge bases.
  • Tractability is Key: The authors emphasize that for practical integration with neural networks, probabilistic logics must be computationally tractable (ideally polynomial time). #P-hard problems are unlikely to be incorporated effectively.
  • Flexibility of Integration: TensorLog allows for bidirectional integration: probabilistic logic can be embedded within deep learning models, and neural network components can be used within the logic.

Key Results

  • Scalability: TensorLog demonstrates impressive scalability, handling knowledge bases with hundreds of thousands of triples and tens of thousands of examples. For instance, learning on a KB of 420,000 tuples took around 200 seconds per epoch on a desktop GPU.
  • Efficiency: Inference times are significantly faster than traditional probabilistic logic systems, often by orders of magnitude, especially on larger datasets. For example, on a 25x25 grid, GPU acceleration made learning over 500 times faster than the SciPy backend.
  • Accuracy: TensorLog achieves competitive or superior accuracy on various tasks, including relational learning and question-answering, often outperforming existing methods like ProPPR. For the WikiMovies task, it achieved 95.0% accuracy with 10,000 training examples.
  • GPU Acceleration: The integration with deep learning frameworks allows for substantial speedups through GPU utilization, particularly for learning tasks where inference is repeated many times.

Limitations and Future Work

  • Restricted Logic: The current implementation of TensorLog is limited to a specific subset of first-order logic (ptree-SDKGs). While expressive, it does not cover all possible logical constructs.
  • Tractability Assumption: The authors argue that #P-hard logics are unlikely to be practically incorporated into neural networks, suggesting future work should focus on tractable extensions.
  • Hyperparameter Tuning: While TensorFlow's optimizers are more robust, hyperparameter tuning is still necessary for optimal performance.
  • Future Work: The authors suggest exploring more stable optimization techniques (e.g., gradient clipping), better debugging support, and extending TensorLog to handle more complex logical structures and non-binary predicates. They also highlight the potential for learning programs in TensorLog and integrating it with more complex non-logical models like dialog agents.

Summary updated

Abstract

We present an implementation of a probabilistic first-order logic called TensorLog, in which classes of logical queries are compiled into differentiable functions in a neural-network infrastructure such as Tensorflow or Theano. This leads to a close integration of probabilistic logical reasoning with deep-learning infrastructure: in particular, it enables high-performance deep learning frameworks to be used for tuning the parameters of a probabilistic logic. The integration with these frameworks enables use of GPU-based parallel processors for inference and learning, making TensorLog the first highly parallellizable probabilistic logic. Experimental results show that TensorLog scales to problems involving hundreds of thousands of knowledge-base triples and tens of thousands of examples.
BibTeX
@article{cohen2020tensorlog,
  author = {William W. Cohen and Fan Yang and Kathryn Mazaitis},
  title = {{TensorLog: A Probabilistic Database Implemented Using Deep-Learning Infrastructure}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=-_b-bgHVMC},
}
Figure