Abstract
Knowledge bases (KBs) are often greatly incomplete, necessitating a demand for KB completion. A promising approach is to embed KBs into latent spaces and make inferences by learning and operating on latent representations. Such embedding models, however, do not make use of any rules during inference and hence have limited accuracy. This paper proposes a novel approach which incorporates rules seamlessly into embedding models for KB completion. It formulates inference as an integer linear programming (ILP) problem, with the objective function generated from embedding models and the constraints translated from rules. Solving the ILP problem results in a number of facts which 1) are the most preferred by the embedding models, and 2) comply with all the rules. By incorporating rules, our approach can greatly reduce the solution space and significantly improve the inference accuracy of embedding models. We further provide a slacking technique to handle noise in KBs, by explicitly modeling the noise with slack variables. Experimental results on two publicly available data sets show that our approach significantly and consistently outperforms state-of-the-art embedding models in KB completion. Moreover, the slacking technique is effective in identifying erroneous facts and ambiguous entities, with a precision higher than 90%.
Introduction
Knowledge Bases (KBs) like Freebase or WordNet are massive but notoriously incomplete. To fill the gaps, researchers usually turn to embedding models, which represent entities and relations as vectors in a latent space to predict missing links.
However, these models are purely data-driven; they "learn" patterns but ignore common sense or logical constraints. For example, an embedding model might predict that a person has two different birthplaces or that a city is located in a country that doesn't match its state. Conversely, rule-based systems are logically sound but struggle to capture the nuanced, "unobservable" properties of data that embeddings handle so well. This paper aims to bridge this gap by combining statistical intuition with symbolic logic.
Methods
The authors propose a framework that treats KB completion as a constrained optimization problem using Integer Linear Programming (ILP).
The process involves three main components:
- Embedding Plausibility: Standard models (RESCAL, TRESCAL, and TransE) calculate a "plausibility score" for every candidate fact, forming the objective function of the ILP.
- Rule Integration: Four types of rules are translated into linear constraints:
- Noisy Observation: Acknowledges that existing facts might be wrong.
- Argument Type Expectation: Ensures relations link the right types of entities.
- At-most-one Restraint: Enforces functional constraints (e.g., a city can only be the capital of one country).
- Simple Implication: Logical deductions (e.g., if A is the wife of B, then A is a spouse of B).
- Slacking Technique: To handle noise, they introduce slack variables (ε). If the ILP solver decides a "known" fact is actually false to satisfy other rules and maximize the objective, the slack variable for that fact is triggered. This allows the model to "disagree" with the input data if the evidence against it is strong enough.
Datasets
The researchers evaluated their approach on two datasets derived from NELL (Never-Ending Language Learner):
- Location: 195 entities and 231 triples involving relations like
CityLocatedInCountryandStateHasCapital. - Sport: 477 entities and 710 triples involving relations like
AthletePlaysForTeamandCoachesTeam.
These datasets were specifically chosen because they contain clear hierarchical and functional constraints that test the effectiveness of the rules.
Key Insights
- Rules as Search Space Reducers: Embedding models often struggle because the "solution space" is astronomical. Rules act as a massive filter, allowing the embedding model to focus only on physically and logically possible candidates.
- The Power of "Slacking": Most KBC models assume the training data is "Ground Truth." By adding slack variables, this model treats the KB as a "noisy observation," enabling it to clean the KB while completing it.
- Model Agnostic: The ILP framework acts as a wrapper that can enhance any scoring-based model, including RESCAL and TransE.
Key Results
The results show that adding rules (denoted as "r-models") leads to a dramatic performance boost across different base models.
- Accuracy Gains: On the Location dataset, the base RESCAL model achieved a measly 14.11% accuracy. The rule-enhanced version (r-RESCAL) jumped to 67.27%. Similar massive gains were seen for TRESCAL and TransE.
- Noise Detection: The slacking technique identified 22 suspicious triples in the Location dataset with over 90% precision, catching factual errors like "Los Angeles is in Nevada."
- Qualitative Success: Case studies showed the model correctly demoted "wrong but plausible" embedding predictions (like a city being a capital of two countries) in favor of logically correct answers.
Limitations and Future Work
- Relationship Types: The current ILP formulation handles 1-to-1, 1-to-Many, and Many-to-1 relations well, but struggles with Many-to-Many relations.
- Scalability: Solving ILP problems is NP-hard. While a "divide-and-conquer" strategy is suggested, scaling to billions of triples remains a challenge.
- Integration Timing: Incorporating rules during the embedding training phase, rather than just post-hoc, might yield even more accurate latent representations.
Summary updated