Current web-scale knowledge bases (KBs) incorporate a substantial amount of information in a structured format. Availability of this readily machine-digestible data has made KBs a desirable resource for other applications. This has motivated many to explore learning on KBs. Graph embeddings and inference rule learning are examples such methods. This paper concerns the later, mostly because rules provide great inference power and are also easily understandable. Most recent work focuses only on normal rules (where all the predicates only support variables). We explore more general type of rules: conditional inference rules. These rules are a class of logical rules which allow predicates with constants, thus having more expressive power. We show their effectiveness in knowledge expansion by comparing them to normal rules’ number of predictions and precision. However, due to the larger search space, mining conditional rules is much more time-consuming compared to mining normal rules. Current state-of-the-art rule mining methods adapted to mine conditional rules are infeasibly slow on medium/large KBs. To aid with this shortcoming, we introduce a scalable conditional rule mining algorithm. Our algorithm makes it possible to mine conditional rules from web-scale KBs.
Our Approach
We aim to mine conditional rules shown below on large knowledge bases and explore the application of conditional rules in knowledge expansion
wasBornIn(x, Munich) => isCitizenOf(x,Germany)
hasWonPrize(x, OrderOfCanada) => isCitizenOf(x, Canada)
These type of logical rules not only enable us to expand KBs in a straight-forward and interpretable way but also contribute to our understanding of the KB.
Hybrid Confidence
In order to obtain high-quality rules, we need scoring metrics to rank them and review them here given the following rule:
Support. The support of a rule is defined to be the number of correct predictions the rule makes.
Standard Confidence. Confidence measures how confident we are about the predictions of a rule. Standard confidence assumes the closed world assumption by regarding predictions out of the KB as false, thus it is defined as the ratio of a rule’s predictions in the knowledge base
PCA Confidence. Due to the incompleteness of KBs, predictions that are not in the KB are not necessarily false, because they might just be missing from the KB. Thus, a more relaxed assumption is employed in Partial Closed-world Assumption (PCA) confidence by assuming that the KB is locally complete for (pred, sub) pairs existing in the KB.
For predictions where the (predicate, subject) pair does not exist in the KB, PCA simply regards them as unknown and ignores them in the confidence computation. The PCA confidence is formally defined as the following:
Hybrid Confidence. While PCA confidence tries to deal with the incompleteness and has been demonstrated to be useful especially for (quasi) functional predicates, PCA is still a strong assumption and can fail in cases where the unknown is simply wrong for uncommon predicates. For example, in YAGO2 the predicate “hasWonPrize” is actually a rare attribute for person, film or music albums. Since KBs usually do not contain negative triples, PCA would simply ignore unknown predictions containing this rare attribute and severely overestimate the quality of those rules. In those cases, standard confidence is a closer estimate for rules with rare predicates as the head. Motivated by this observation, we propose a hybrid confidence metric:
Relational Model
We utilize the relational model from ProbKB [https://dsr.cise.ufl.edu/projects/probkb-web-scale-probabilistic-knowledge-base/] for mining conditional rules in batches. Our mining algorithm can be written in one SQL sentence per rule type:
However, directly executing the SQL sentence would be infeasible due to the large KB sizes and multiple self joins on the KBs. Instead we implement the algorithm in Spark with a number of optimization techniques.
Experiments
We empirically validate our approach in terms of mining performance and prediction accuracy of conditional rules. We conduct two groups of experiments: in the first group we compare our approach against state-of-the-art mining system Amie+[link] which is capable of mining rules with constants; in the second group of experiments, we explore the prediction accuracy of conditional rules with normal rules and our hybrid metric. We use YAGO and Freebase datasets in our experiments, the statistics are shown below.
Performance Comparison
We compare our mining algorithm with the state-of-art rule mining system Amie+. The running times are shown below. We see that our algorithm (CRM) performs consistently better than Amie+ on medium to large KBs, demonstrating the scalability of our approach.
Link Prediction
To explore how conditional rules can be useful, we evaluate the conditional rules in the link prediction task. Previous work has demonstrated that normal rules can be useful in predicting new facts. Here we compare the predicting ability of normal rules with that of conditional rules, using two different evaluation methods: cross-validation and predictions beyond the KB.
Cross-validation
Figure 1 and Figure 2 compare the predictive ability of conditional rules and normal rules, respectively. We can see that conditional rules achieves higher precision that normal rules consistently.
Beyond the KB (Hybrid Confidence)
We compare different confidence metrics for conditional rules and evaluate their prediction precision beyond the KB. We see in the figure below that PCA confidence works better than standard confidence on link prediction beyond the KB with conditional rules. However, our hybrid confidence consistently outperforms PCA confidence considerably by around 0.1. This justifies our observation that PCA fails to appropriately handle rare predicates in the head of rules and can be fixed by falling back to using standard confidence. For KBs with a small schema and heuristic annotation, we can boost the prediction accuracy
This paper has been included in the Ph.D. thesis and is currently under submission.