Link discovery plays a key role in the integration and use of data across RDF knowledge graphs. Active learning approaches are a common family of solutions to address the problem of learning how to compute links from users. So far, only active learning from perfect oracles has been considered in the literature. However, real oracles are often far from perfect (e.g., in crowdsourcing). We hence study the problem of learning how to compute links across knowledge graphs from noisy oracles, i.e., oracles that are not guaranteed to return correct classification results. We present a novel approach for link discovery based on a probabilistic model, with which we estimate the joint odds of the oracles' guesses. We combine this approach with an iterative learning approach based on refinements. The resulting method, Ligon, is evaluated on 11 benchmark datasets. Our results suggest that Ligon achieves more than 95% of the F-measure achieved by state-of-the-art algorithms trained with a perfect oracle.
The provision of links between knowledge graphs in RDF 3 is of central importance for numerous tasks on the Semantic Web, including federated queries, question answering and data fusion. While links can be created manually for small knowledge bases, the sheer size and number of knowledge bases commonly used in modern applications (e.g., DBpedia with more than 3 × 10 6 resources) demands the use of automated link discovery mechanisms. In this work, we focus on active learning for link discovery. State-of-the-art approaches that rely on active learning [3,12,8] assume that the oracle they rely upon is perfect. Formally, this means that given an oracle ω, the probability of the oracle returning a wrong result (i.e., returning false when an example is to be classified as true) is exactly 0. While these approaches show pertinent results in evaluation scenarios, within which the need for a perfect oracle can be fulfilled, this need is difficult if not impossible to uphold in real-world settings (e.g., when crowdsourcing training data). No previous work has addressed link discovery based on oracles that are not perfect.
We address this research gap by presenting a novel approach for learning link specifications (LS) from noisy oracles, i.e., oracles that are not guaranteed to return correct classifications. This approach is motivated by the problem of learning LS using crowdsourcing. Previous works have shown that agents in real crowdsourcing scenarios are often not fully reliable (e.g., [19]). We model these agents as noisy oracles, which provides erroneous answers to questions with a fixed probability. We address the problem of learning from such oracles by using a probabilistic model, which approximates the odds of the answer of a set of oracles being correct. Our approach, dubbed Ligon, assumes that the underlying oracles are independent, i.e., that the probability distributions underlying oracles are pairwise independent. Moreover, we assume that the oracles have a static behavior, i.e., that the probability of them generating correct/incorrect answers is constant over time.
The contributions of this paper are as follows: (1) We present a formalization of the problem of learning LS from noisy oracles. We derive a probabilistic model for learning from such oracles. (2) We develop the first learning algorithm dedicated to learning LS from noisy data. The approach combines iterative operators for LS with an entropy-based approach for selecting most informative training examples. In addition, it uses cumulative evidence to approximate the probability distribution underlying the noisy oracles that provide it with training data. Finally, (3) we present a thorough evaluation of Ligon and show that it is robust against noise, scales well and converges with 10 learning iterations to more than 95% of the average F-measure achieved by Wombat-a state-of-the-art approach for learning LS-provided with a perfect oracle.
Knowledge graphs (also called knowledge bases) in RDF are defined as sets of triples K ⊆ (R ∪ B) × P × (R ∪ B ∪ L), where R is the set of all resources, i.e., of all objects in the domain of discourse (e.g., persons and publications); P ⊆ R is the set of all predicates, i.e., of binary relations (e.g., author); B is the set of all blank nodes, which basically stand for resources whose existence is known but whose identity is not relevant to the model and L is the set of all literals, i.e., of values associated to datatypes (e.g., integers). 4 The elements of K are referred to as facts or triples. We call the elements of R entities or resources.
The link discovery task on RDF knowledge graphs is defined as follows: Let S and T be two sets of resources, i.e., S ⊆ R and T ⊆ R. Moreover, let r ∈ P be a predicate. The aim of link discovery is to compute the set M = {(s, t) ∈ S ×T : r(s, t)}. We call M a mapping. In many cases, M cannot be computed directly and is thus approximated by a mapping M . To find the set M , declarative
link discovery frameworks rely on link specifications (LS), which describe the conditions under which r(s, t) can be assumed to hold for a pair (s, t) ∈ S × T . Several formal models have been used for describing LS in previous works [8].
We adopt a formal approach derived from [17] and first describe the syntax and then the semantics of LS. LS consist of two types of atomic components: similarity measures m, which allow the comparing of property values of input resources and operators op, which can be used to combine LS to more complex LS. Without loss of generality, we define a similarity measure m as a function m : S × P × T × P → [0, 1]. An example of a similarity measure is the edit similarity dubbed edit5 which allows computing the similarity of a pair (s, t) ∈ S × T w.r.t. the values of a pair of properties (p s , p t ) for s resp. t. An atomic LS is a pair (m, θ). A complex LS is the result of combining two LS L 1 and L 2 through an operator that allows merging the results of L 1 and L 2 . Here, we use the operators , and \ as they are complete w.r.t. the Boolean algebra and frequently used to define LS. An example of a complex LS is given in Figure 1.
We define the semantics
We model oracles Ω for r as black boxes with a characteristic function ω : S × T → {true, false}. The characteristic function ω i of the oracle Ω i returns true iff the oracle Ω i assumes that r(s, t) holds. Otherwise, it returns false.
For ease of notation, we define LC = S × T and call the elements of LC link candidates. For l ∈ LC, we write l ≡ to signify that r(l) holds, i.e., r(s, t) is true for l = (s, t). Otherwise, we write l ≡ ⊥. We now assume a learning situation typical for crowdsourcing, where n oracles are presented with a link candidate l and asked whether l ≡ holds. We can describe each oracle Ω i by the following four probabilities: 1 p(ω i (l) = true|l ≡ ), i.e., the probability of the oracle Ω i generating true positives. This value is exactly 1 for a perfect oracle. 2 p(ω i (l) = false|l ≡ ), the probability of false negatives (0 for a perfect oracle). 3 p(ω i (l) = true|l ≡ ⊥), i.e., the probability of false positives, (0 for a perfect oracle), and 4 p(ω i (l) = false|l ≡ ⊥), the probability of true negatives (1 for a perfect oracle). Given that p(A|B) + p(¬A|B) = 1, the sum of the first two and last two probabilities is always 1.
Example 1. A noisy oracle can have the following description:
For compactness, we use the following vector notation in the rest of the formal model: − → ω refers to the vector of characteristic functions over all oracles.
We write − → ω (l) = − → x to signify that the ith oracle returned the x i for the link candidate l. Let us assume that the probabilities underlying all oracles Ω i are known (we discuss ways to initialize and update these probabilities in the subsequent section). Recalling that we assume that our oracles are independent, we can now approximate the probability that l ≡ y (with y ∈ { , ⊥}) for any given link candidate l using the following Bayesian model:
Recall that the odds of an event A occurring are defined as odds(A) = p(A)/P (¬A). For example, the odds of any link candidate being a correct link (denoted o + ) are given by
o + is independent of l and stands for the odds that an element of LC chosen randomly would be a link. Given feedback from our oracles, we can approximate the odds of a link candidate l being a correct link by computing the following:
A key idea behind our model is that a link candidate l can be considered to be a correct link if odds(l
Computing the odds for a link now boils down to (1) approximating the four probabilities which characterize our oracles and (2) computing o + . As known from previous works on probabilistic models [7], o + is hard to compute directly as it requires knowing the set of links M , which is exactly what we are trying to compute. Several strategies can be used to approximate o + . In this work, we consider the following three:
1. Ignore strategy: We can assume the probabilities p(l = ) and p(l = ⊥) to be equally unknown and hence use o + = 1 . This reduces Equation 3to [13]). Hence,
3. Approximate strategy: We approximate o + by using our learning approach. We select the mapping [[L * ]] computed using the best specification L * learned by Ligon (see the subsequent Section) as our best current approximation of the mapping we are trying to learn. o + is then computed as follows:
We quantify the effect of these strategies on our learning algorithm in our experiments.
Ligon is an active learning algorithm designed to learn LS from noisy oracles. An overview of the approach is given in Algorithm 1 and explained in the sections below.
Confusion Matrices. We begin by assuming that we are given an initial set E 0 ⊆ LC of positive and negative examples for links. In the first step, we aim to compute the initial approximations of the conditional probabilities which describe each of the oracles Ω i . To this end, each oracle is assigned a confusion matrix C i of dimension 2 × 2 (see lines 2-3 of Algorithm 1). Each entry of the matrix is initialized with 1 2 to account for potential sampling biases due to high disparities between conditional probabilities. The first and second row of each C i contains counts for links where the oracle returned true resp. false. The first and second column of C i contain counts for positive resp. negative examples. Hence, C 11 basically contains counts for positive examples that were rightly classified as by the oracle. In each learning iteration, we update the confusion matrix by presenting the oracle with unseen link candidates and incrementing the entries of C (see lines 4-8 of Algorithm 1). We discuss the computation of the training examples in the subsequent section. Based on the confusion matrix, we can approximate all conditional probabilities necessary to describe the oracle by computing the 2 × 2 matrix D with d ij = c ij /(c 1j + c 2j ). For example, d 11 ≈ p(ω i (l) = true|l ≡ ). We call D the characteristic matrix of Ω. .
Updating the Characteristic Matrices. Updating the probabilities is done via the confusion matrices. In each learning iteration, we present all oracles with the link candidates deemed to be most informative. Based on the answers of the oracles, we compute the odds for each of these link candidates. Link candidates l with odds in [0, 1/k] and [k, +∞[ are considered to be false respectively true. The new classifications are subsequently used to update the counts in the confusion matrices and therewith also the characteristic matrix of each of the oracles.
Active Learning Approach. So far, we have assumed the existence of an active learning solution for link discovery. Several active learning approaches have been developed over recent years [8]. Of these approaches, solely those based on genetic programming can generate specifications of arbitrary complexity. However, genetic programming approaches are not deterministic and are thus difficult to use in practical applications. Newer approaches based on iterative operators such as Wombat [17] have been shown to perform well in classical link discovery tasks. Therefore, we implemented a generic interface to apply Ligon to several active learning algorithms, where we used the Wombat algorithm as the default active learning algorithm for Ligon. See our last set of experiments for results of applying Ligon to other state-of-the-art active learning approaches.
Selecting the Most Informative Examples. Given an active learning algorithm, we denote the set of the m best LS generated in a given iteration i as B i . The most informative examples are those link candidates l, which maximize the decision entropy across the elements of B i [12]. Formally, let [[B i ]] be the union of the set of link candidates generated by all LS b ∈ B i . Then, the most informative link candidates are the l ∈ B i which maximize the entropy function e(l, B i ), which is defined as follows: Let p(l, B i ) be the probability that a link candidate belongs to [[b]] for b ∈ B i . Then, e(l, B i ) = −p(l, B i ) log 2 p(l, B i ).
We aimed to answer 6 research questions with our experimental evaluation: Q 1 . Which combination of strategies for computing odds and the threshold k leads to the best performance?, Q 2 . How does Ligon behave when provided with an increasing number of noisy oracles?, Q 3 . How well does Ligon learn from noisy oracles?, Q 4 . How well does Ligon scale?, Q 5 . How well does Ligon perform compare to batch learning approaches trained with a similar number of examples? and Q 6 . How general is Ligon, i.e., can Ligon be applied to problems outside the link discovery domain? and does Ligon depend on the underlying active learning algorithm?
Experimantal Setup. All experiments were carried out on a 64-core 2.3 GHz PC running OpenJDK 64-Bit Server 1.8.0 151 on Ubuntu 16.04.3 LTS. Each experiment was assigned 20 GB RAM. We evaluated Ligon using 8 link discovery benchmark datasets. Five of these benchmarks were real-world datasets [6] while three were synthetic from the OAEI 2010 benchmark. 6 We used the paradigm proposed by [5] and measured the performance of algorithms using the best Fmeasure they achieved. As this measure fails to capture the average behaviour of algorithm over several iterations, we also report the normalized average area under the F-measure curve, which we denote AUC. We initialized Ligon with 10 positive examples (ergo, |E 0 | = 10). We fixed the number of the most informative examples to be labeled by the noisy oracles at each iteration to 10. For labeling the most informative examples, we use n = 2, 4, 8 and 16 noisy oracles which were all initialized with random confusion matrices. We set the size of B to 10. All experiments were repeated 10 times and we report average values. The characteristic matrices C of our noisy oracles were generated at random. To this end we generated the true positive and true negative probabilities using a uniform distribution between 0.5 and 1, i.e. p(ω i (l) = true|l ≡ ) ∈ [0.5, 1] and p(ω i (l) = true|l ≡ ) ∈ [0.5, 1]. The other probabilities were set accordingly, as they are complementary to the former two. Fig. 2 Parameter Estimation. Our first series of experiments aimed to answer Q 1 . We ran Ligon with k = 2, 4, 8 and 16. These settings were used in combination with all three strategies for computing o + aforementioned. A first observation is that the AUC achieved by Ligon does not depend much on the value of k nor on the strategy used. This is a highly positive feature of our algorithm as it suggests that our approach is robust w.r.t. to how it is initialized. Interestingly, this experiment already suggests that Ligon achieves more than 95% of the performance of the original Wombat algorithm trained with a perfect oracle.
We chose to run the remainder of our experiments with the setting k = 16 combined with the equivalent strategy as this combination achieved the highest average F-measure of 0.86.
Comparison with Perfect Oracle. In our second set of experiments, we answered Q 2 by measuring how well Ligon performed when provided with an increasing number of oracles. In this series of experiments, we used 2, 4, 8, and 16 oracles which were initialized randomly. k was set to 16 and we used the Equivalent strategy. Once more, the robustness of our approach became evident as its performance was not majorly perturbed by a variation in the number of oracles. In all settings Ligon achieves an average AUC close to 0.86 with no statistical difference. We can hence conclude that the performance of our approach depends mostly on the initial set of examples E 0 being accurate, which leads to our prior-i.e., the evaluation of the initial confusion matrix of the oracles-being sufficient. This sufficient approximation means that our Bayesian model is able to distinguish between erroneous classifications well enough to find most informative examples accurately and generalize over them. In other words, even a small balanced set containing 5 positive and 5 negative examples seems sufficient to approximate the confusion matrix of the oracles sufficiently well to detect positive and negative examples consistently in the subsequent steps. This answers Q 2 . Figures 2 and 3 show the detailed results of running Ligon for 10 iterations for each of our 8 benchmark datasets.
To answer Q 3 , we also ran our approach in combination with a perfect oracle (i.e., an oracle which knew and returned the perfect classification for all pairs from (S, T )). The detailed results are provided in Figures 3 and 2. Combining our approach with a perfect oracle can be regarded as providing an upper bound to our learning algorithm. Over all datasets, Ligon achieved 95% of the AUC achieved with the perfect oracle (min = 88% on DBpedia-LMDB, max = 100% on Restaurants) of the AUC achieved with the perfect oracle. This answers Q 3 and demonstrates that Ligon can learn LS with an accuracy close to that of an approach provided with perfect answers. Runtime. In our third set of experiments, we were interested in knowing how well our approach scales. To this end, we measured the runtime of our algorithm while running the experiments carried out to answer Q 2 and Q 3 . In our experiments, Wombat, the machine learning approach used within Ligon, makes up for more than 99% of Ligon's runtime. for more detailed results see Table 2. This shows that the Bayesian framework used to re-evaluate the characteristic matrices of the oracles is clearly fast enough to be used in interactive scenarios, which answers Q 4 . Our approach completes a learning iteration in less than 10 seconds on most datasets, which we consider acceptable even for interac- Comparison with Batch Learning. While active learning commonly requires a small number of training examples to achieve good F-measures, other techniques such as pessimistic and re-weighted batch learning have also been designed to achieve this goal [5]. In addition, the positive-only learning algorithm Wombat has also been shown to perform well with a small number of training examples. In our final set of experiments, we compared the best F-measure achieved by Ligon when trained with 16 noisy oracles, k = 16 and the equivalent strategy with the pessimistic and re-weighted models proposed in [5] as well as the two versions of the Wombat approach [17]. All approaches were trained with 2% of the reference data (i.e., with a perfect oracle) as suggested by [5]. The results of these experiments are shown in Table 3. Note that, we did not consider the datasets Persons 1, Persons 2 and Restaurant because 2% of the training data accounts to less than 10 examples, which Ligon requires as initial training dataset E 0 . Our results answer Q 5 clearly by showing that Ligon outperforms previous batch learning algorithms even when trained with noisy oracles. On average, Ligon is more than 40% better in F-measure. This clearly demonstrates that our active learning strategy for selecting training examples is superior to batch learning.
Generalization of Ligon. In our last set of experiment, we implemented a generalization of Ligon for binary classification tasks behind link discovery. We thus used the active learning framework JCLAL [15] to wrap WEKA [2] classifiers and implemented Ligon as a custom oracle. We selected three well known binary classification datasets (i.e., Diabetes, breast-cancer and Ionosphere) from the WEKA distribution on which we applied two state-of-the-art classification algorithms, namely GBDT and Random Forests [20]. Based on our previous experiments, we used 4 noisy oracles, k was set to 16 and we used the Ignore strategy, since all the other strategies are specific to the link discovery domain. We executed two sets of experiments for noisy oracles with true positive/negative probabilities drawn from the two uniform distributions in [0.5, 1] and [0.75, 1]. On average, Ligon achieves 75% and 89% of the learning accuracy for noisy oracles drawn from [0.5, 1] and [0.75, 1] respectively. These results indicate that Ligon is not only applicable to problems outside the link discovery domain but also independent from the underlying active learning algorithm is able to achieve F-measures near to the ones scored using a perfect oracle, which answers Q 6 .
Link Discovery for RDF knowledge graphs has been an active research area for nearly a decade, with the first frameworks for link discovery [4,9] appearing at the beginning of the decade. Raven [10] was the first active learning approach for link discovery and used perception learning to detect accurate LS. Other approaches were subsequently developed to learn LS within the active learning setting [3,11,12]. Unsupervised learning approaches for monogamous relations [11][12][13] rely on different pseudo-F-measures to detect links without any training data. Positive-only learning algorithms [17] address the open-world characteristic of the Semantic Web by using generalization algorithms to detect LS. The work presented by [14] proposes an active learning approach for link prediction in knowledge graphs. Ligon differs from the state of the art in that it does not assume that it deals with perfect oracles. Rather, it uses several noisy oracles to achieve an F-measures close to those achieved with perfect oracles. An active learning approach with uncertain labeling knowledge is proposed by [1], where the authors used diversity density to characterize the uncertainty of the knowledge. A probabilistic model of active learning with multiple noisy oracles was introduced by [18] to label the data based on the most perfect oracle. For Crowdsourcing scenarios, [16] propose a supervised learning algorithm for multiple annotators (oracles), where the oracles' diverse reliabilities were treated as a latent variables.
We presented Ligon, an active learning approach designed to deal with noisy oracles, i.e., oracles that are not guaranteed to return correct classification results. Ligon relies on a probabilistic model to estimate the joint odds of link candidates based on the oracles' guesses. Our experiments showed that Ligon achieves 95% of the learning accuracy of approaches learning with perfect oracles in the link discovery setting. Moreover, we showed that Ligon is (1) not dependent on the underlying active learning algorithm and (2) able to deal with other classification problems. In future work, we will evaluate Ligon within real crowdsourcing scenarios. A limitation of our approach is that it assumes that the confusion matrix of the oracles is static. While this assumption is valid with the small number of iterations necessary for our approach to converge, we will extend our model so as to deal with oracles which change dynamically. Furthermore, we will extend Ligon to handle n-ary classification problems and evaluate it on more stat-of-the-art approaches from the deep learning domain.
Acknowledgments. This work has been supported by the EU H2020 project Know-Graphs (GA no. 860801) as well as the BMVI projects LIMBO (GA no. 19F2029C) and OPAL (GA no. 19F2028A).