Knowledge Bases (KBs) are becoming increasingly large, sparse and probabilistic. These KBs are typically used to perform query inferences and rule mining. But their efficacy is only as high as their completeness. Efficiently utilizing incomplete KBs remains a major challenge as the current KB completion techniques either do not take into account the inherent uncertainty associated with each KB tuple or do not scale to large KBs.

 Probabilistic rule learning not only considers the probability of every KB tuple but also tackles the problem of KB completion in an explainable way. For any given probabilistic KB, it learns probabilistic first-order rules from its relations to identify interesting patterns. But, the current probabilistic rule learning techniques perform grounding to do probabilistic inference for evaluation of candidate rules. It does not scale well to large KBs as the time complexity of inference using grounding is exponential over the size of the KB. In this paper, we present SafeLearner -- a scalable solution to probabilistic KB completion that performs probabilistic rule learning using lifted probabilistic inference -- as faster approach instead of grounding. 

 We compared SafeLearner to the state-of-the-art probabilistic rule learner ProbFOIL+ and to its deterministic contemporary AMIE+ on standard probabilistic KBs of NELL (Never-Ending Language Learner) and Yago. Our results demonstrate that SafeLearner scales as good as AMIE+ when learning simple rules and is also significantly faster than ProbFOIL+. There is an increasing tendency to construct knowledge bases and knowledge graphs by machine learning methods. As a result, knowledge bases are often incomplete and also uncertain. To cope with uncertainty, one often resorts to probabilistic databases and logics Suciu, 2017, De Raedt et al., 2016] , which take into account the probability of the tuples in the querying process. The most widely used probabilistic database semantics is based on the tuple-independent probabilistic databases model, which assumes that every tuple in every table of the database is independent of one another To cope with incomplete knowledge bases, various researchers have used machine learning techniques to learn a set of rules that can be used to infer new tuples from the existing ones, thereby completing the knowledge base BID2 . This traditional relational rule learning setting BID18 has been extended to probabilistic logics and databases by De Raedt et al. [2015] . However, the ProbFOIL approach of De Raedt et al. suffers from one key limitation: It does not scale well to large databases due to the grounding step, which results in an intractable probabilistic inference problem. The key contribution of this paper is the introduction of the SafeLearner system which performs two major tasks. 1) It uses lifted inference to avoid the grounding step and to improve scaling.2) It enhances a highly efficient rule generation system, AMIE+ BID11 ] to obtain deterministic candidate rules which are then made probabilistic using lifted inference.This paper is organized as follows. We introduce the background for this paper in Section 2. We define, in Section 3, the problem of learning a set of probabilistic rules. Sections 4 and 5 outline the idea behind the working of SafeLearner. Section 6 proposes the algorithm for SafeLearner. In Section 7, we present an experimental evaluation in the context of the NELL knowledge base BID2 ]. An overview of related work can be found in Section 8. Section 9 discusses future research directions and concludes. The work presented in this paper advances the works [De Raedt et al., 2015, Dylla and BID9 that also studied learning in the probabilistic database setting. 7 But compared with these previous works, we rely on lifted inference, which allows our approach to scale to much larger databases. Both of the previous approaches only use tuples from a given training set but do not take into account the behavior of the model on tuples not in the training set. This is problematic because, unless the training set is really large, these previous methods do not distinguish models that predict too many false positives (i.e. models that give too high probability to too many tuples outside the training set). This becomes an issue especially in sparse domains (and most real domains are indeed sparse). Our work is also closely related to the literature on learning from knowledge bases such as NELL within statistical relational learning (SRL), including works that use Markov logic networks BID20 , Bayesian logic programs BID19 and stochastic logic programs BID17 BID23 . A disadvantage of many of these methods is that the learned parameters of the models can not be interpreted easily, which is particularly an issue for Markov logic networks where the weight of a rule cannot be understood in isolation from the rest of the rules. In contrast, the learned weights of probabilistic rules in our work, and also in the other works relying on probabilistic databases [De Raedt et al., 2015, Dylla and BID9 , have a clear probabilistic interpretation.Parameter Learning with Different Losses Cross entropy is not the only loss function that may be considered for learning the parameters of probabilistic rules. Here, we discuss two additional loss functions that have already been used for the same or similar tasks in the literature: squared loss BID9 and a probabilistic extension of accuracy . Whereas cross entropy and squared loss belong among so-called proper scoring rules BID12 and, thus, reward estimates of probabilities that match the true probability, this is not the case for probabilistic accuracy. Moreover, each of these functions also relies on additional assumptions such as mutual independence of the examples' probabilities as well as mutual independence of the predictions, although this is not mentioned explicitly in the respective works BID9 Theobald, 2016, De Raedt et al., 2015] . Below, we briefly discuss squared loss and probabilistic accuracy.Squared Loss (Brier Score) As before, let p i denote the probability of the i-th example and q i the probability of the respective prediction. Then, the squared loss, which is a proper scoring rule, is: DISPLAYFORM0 2 which was among others used in BID9 for learning probabilities of tuples in PDBs. define probabilistic extension of accuracy and other measures of predictive quality such as precision and recall. Their version of probabilistic accuracy is Acc prob = 1− 1 |E| t i ,p i ∈E |p i − q i | . Unlike the other two discussed loss functions, probabilistic accuracy is not a proper scoring rule as the next example illus-7. Strictly speaking, the work was framed within the probabilistic logic programming setting. However, probabilistic logic programming systems, such as Problog BID10 , can be seen as generalizations of probabilistic databases. We proposed a probabilistic rule learning system, named SafeLearner, that supports lifted inference. It first performs structure learning by mining independent deterministic candidate rules using AMIE+ and later executes joint parameter learning over all the rule probabilities. SafeLearner extends ProbFOIL + by using lifted probabilistic inference (instead of using grounding). Therefore, it scales better than ProbFOIL + . In comparison with AMIE+, it is able to jointly learn probabilistic rules over a probabilistic KB unlike AMIE+ which only learns independent deterministic rules (with confidences) over a deterministic KB. We experimentally show that SafeLearner scales as good as AMIE+ when learning simple rules. Trying to learn complex rules leads to unsafe queries which are not suitable for lifted inference. But lifted inference helps SafeLearner in outperforming ProbFOIL + which does not scale to NELL Sports Database without the help of a declarative bias. A few limitations of SafeLearner are as follows: 1) It cannot learn complex rules that translate to an unsafe query. 2) It cannot use rules within the background theory. 3) It cannot learn rules on P DB with numeric data (without assuming them as discrete constants).The main contributions of SafeLearner are presented as follows. Firstly , it accomplishes probabilistic rule learning using a novel inference setting as it is the first approach that uses lifted inference for KB completion. Secondly , unlike ProbFOIL + , SafeLearner scales well on the full database of NELL with 233,000 tuples and 426 relations as well as on the standard subset of Yago 2.4 with 948,000 tuples and 33 relations. Thirdly , SafeLearner is faster than ProbFOIL + because of the following three factors: 1) it disintegrates longer complex queries to smaller simpler ones, 2) it caches the structure of queries before doing inference and 3) it uses lifted inference to infer on those simple queries. The first two factors of query disintegration and memoization are discussed in Appendix D in further detail.In future, this work could be advanced further to eliminate its shortcomings. In particular , a prominent direction of advancement would be to extend probabilistic rule learning to open-world setting of which the Lif t O R algorithm BID3 is capable.
Probabilistic Rule Learning system using Lifted Inference A model for probabilistic rule learning to automate the completion of probabilistic databases that uses AMIE+ and lifted inference to help computational efficiency.