Learning First-Order Logic Embeddings via Matrix Factorization

William Yang Wang, William W. CohenIJCAI 2016 · OpenReview

Abstract

Many complex reasoning tasks in Artificial Intelligence (including relation extraction, knowledge base completion, and information integration) can be formulated as inference problems using a probabilistic first-order logic. However, due to the discrete nature of logical facts and predicates, it is challenging to generalize symbolic representations and represent first-order logic formulas in probabilistic relational models. In this work, we take a rather radical approach: we aim at learning continuous low-dimensional embeddings for first-order logic from scratch. In particular, we first consider a structural gradient based structure learning approach to generate plausible inference formulas from facts; then, we build grounded proof graphs using background facts, training examples, and these inference formulas. To learn embeddings for formulas, we map the training examples into the rows of a binary matrix, and inference formulas into the columns. Using a scalable matrix factorization approach, we then learn the latent continuous representations of examples and logical formulas via a low-rank approximation method. In experiments, we demonstrate the effectiveness of reasoning with first-order logic embeddings by comparing with several state-of-the-art baselines on two datasets in the task of knowledge base completion.

Introduction

Traditional symbolic AI relies on discrete logical rules, which are powerful for reasoning but brittle when handling uncertainty or "fuzzy" similarities between entities. Conversely, modern embedding methods represent entities as continuous vectors, scaling well to massive datasets but often lacking interpretable reasoning structures. This work addresses the challenge of Statistical Relational Learning (SRL) by combining the formal rigor of first-order logic with the flexibility of latent vector embeddings.

Methodology

The proposed pipeline transforms logical reasoning into a recommendation-style matrix factorization problem through several stages:

  1. Structure Learning: A structural gradient approach automatically generates candidate Horn clauses from existing knowledge base facts.
  2. Proof Graph Construction: Using the ProPPR probabilistic logic framework, proof graphs are generated for training examples, identifying which formulas are "activated" to reach a conclusion.
  3. Matrix Formulation: A large binary matrix $F$ is constructed where rows represent training examples (queries) and columns represent candidate logical formulas. A cell is '1' if the formula was used in the proof for that example.
  4. Low-Rank Approximation: This matrix is factorized into lower-dimensional matrices representing latent embeddings for examples and formulas.
  5. Integration: Learned formula embeddings are converted back into scalar weights to parameterize the ProPPR engine for final inference.
Transformation from ProPPR proof graphs to a binary logical matrix for factorization.

Experimental Evaluation

The approach was evaluated on two standard knowledge base completion benchmarks:

  • WordNet: A lexical database with ~40,000 entities and 18 relations.
  • FB15K (Freebase): A subset of a large-scale knowledge graph with ~15,000 entities and over 1,300 relation types.

Key Insights

A significant finding was the effectiveness of treating logic as a "user-item" problem. Matrix factorization allows the system to discover latent similarities between different logical rules. Furthermore, the choice of loss function proved critical. The authors found that Pairwise Log Loss (specifically Row Pairwise Log Loss) performed best, as it explicitly learns to rank "activated" rules higher than "unused" ones, effectively modeling the absence of evidence.

Comparison of different loss functions, showing the superior performance of Row Pairwise Log Loss.

Results

The proposed method, ProPPR+MF, outperformed several state-of-the-art embedding-only models and standard symbolic ProPPR:

  • WordNet: Achieved a 94.1% Hits@10 score, a significant jump from the standard ProPPR's 83.0% and TransR's 79.8%.
  • FB15K: Achieved 61.0% Hits@10, outperforming PTransE (51.8%) and standard ProPPR (59.0%).
  • Dimensionality: Small embedding sizes (k=4 or k=8) were sufficient to capture the necessary logic, ensuring computational efficiency.

Conclusion

By bridging symbolic logic and vector embeddings, this work demonstrates that low-dimensional representations can significantly enhance automated reasoning on large-scale knowledge bases. Future work will explore performing inference directly in the embedding space and jointly learning embeddings for entities, relations, and formulas.

Summary updated

Abstract

Many complex reasoning tasks in Artificial Intelligence (including relation extraction, knowledge base completion, and information integration) can be formulated as inference problems using a probabilistic first-order logic. However, due to the discrete nature of logical facts and predicates, it is challenging to generalize symbolic representations and represent first-order logic formulas in probabilistic relational models. In this work, we take a rather radical approach: we aim at learning continuous low-dimensional embeddings for first-order logic from scratch. In particular, we first consider a structural gradient based structure learning approach to generate plausible inference formulas from facts; then, we build grounded proof graphs using background facts, training examples, and these inference formulas. To learn embeddings for formulas, we map the training examples into the rows of a binary matrix, and inference formulas into the columns. Using a scalable matrix factorization approach, we then learn the latent continuous representations of examples and logical formulas via a low-rank approximation method. In experiments, we demonstrate the effectiveness of reasoning with first-order logic embeddings by comparing with several state-of-the-art baselines on two datasets in the task of knowledge base completion.
BibTeX
@inproceedings{wang2016learning,
  author = {William Yang Wang and William W. Cohen},
  title = {{Learning First-Order Logic Embeddings via Matrix Factorization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=B14vT4zO-B},
}
Figure