Unsupervised Learning of Link Speci cations: Deterministic vs. Non-Deterministic

Abstract

Link Discovery has been shown to be of utter importance for the Linked Data Web. In previous works, several supervised approaches have been developed for learning link speci cations out of labelled data. Most recently, genetic programming has also been utilized to learn link speci cations in an unsupervised fashion by optimizing a parametrized pseudo-F-measure. The questions underlying this evaluation paper are twofold: First, how well do pseudo-F-measures predict the real accuracy of non-deterministic and deterministic approaches across di erent types of datasets? Second, how do deterministic approaches compare to non-deterministic approaches? To answer these questions, we evaluated linear and Boolean classi ers against classi ers computed by using genetic programming on six di erent data sets. We also studied the correlation between two di erent pseudo-F-measures and the real F-measures achieved by the classi ers at hand. Our evaluation suggests that pseudoF-measures behave di erently on the synthetic and real data sets.

-

Over the last years, the importance of Link Discovery (LD) as a research topic has increased signi cantly. This increase was upheld mainly by the ever-growing size of the Linked Data Web and the scalability and accuracy requirements it brings about. The creation of links between knowledge bases, one of the most important steps in the realization of the vision of the Linked Data Web has pro ted from this boost of research and seen the development of several LD frameworks and approaches [ 7, 2, 12, 11, 3 ]. Two main research focuses played a role so far: (1) the determination of time-e cient algorithms [ 3, 7, 6 ] for LD and (2) the development of approaches for the e cient computation of link speci cations (also called linkage rules) [ 8, 4, 10, 9 ]. In most cases, supervised machine learning approaches were used to tackle the second challenge of LD. Approaches developed so far include batch learning using genetic programming [ 3 ], the combination of active learning and of linear and Boolean classi ers [ 8 ] as well as the combination of active learning and genetic programming [ 9 ]. In addition, unsupervised approaches for learning link speci cations have been recently developed [ 10 ]. While all these approaches have been shown to achieve good results, unsupervised approaches obviously trump batch and active learning approaches as they do not require any feedback from the user and can still achieve remarkably good performance. In addition, genetic programming approaches yield the central advantage of being able to exploit the whole spectrum of the link specication grammar provided by the framework in which they were implemented. So far, unsupervised approaches to the discovery of link speci cations have only been tested with arti cially generated benchmark data and low-noise datasets. Moreover, no deterministic approach for the unsupervised discovery of link speci cations has been presented so far, although deterministic approaches such as those presented in [ 8 ] counterbalance their limitations in expressiveness by being clearly more time-e cient than approaches based on genetic programming.

The aim of this paper is to experimentally examine the unsupervised discovery of link speci cations with respect to two main questions: 1. Are deterministic approaches able to achieve results comparable to those of genetic approaches? To address this question, we extended the approach presented in [ 9 ] and devised an approach for the unsupervised learning of Boolean and linear classi ers which is loosely based on the RAVEN approach [ 8 ]. We refrained from reusing the approach presented in [ 10 ] as one of the pseudo-measures we rely on was designed especially to work well with this approach. Consequently, using it could have led to a bias in our results. 2. How well are pseudo-F-measures suited for unsupervised discovery performed on synthetic and real data sets? Here, we compared the results achieved by the approaches above on the three OAEI 2010 datasets1 and on three data sets extracted from real data2. In addition to the pseudo-F-measure described in [ 10 ] (which we dub Fu ), we devised a supplementary pseudo-Fmeasure Fd which relies more on the standard de nition of the F -measure. We performed a correlation analysis of the values of Fu , Fd and the F1 measure and detected a surprisingly di erent behaviour of these measures across our two groups of data sets.

The rest of this paper is structured as follows: We rst give an overview of the approaches and measures we used for our experiments. We then present the results of our experimental setup as well as the results of our experiments. For the sake of reproducibility, we chose to use freely available datasets and made the approaches presented herein freely available at the project website.3 We conclude with a summary of the implications of our results for the LD community. 2

Approaches

In general, a link speci cation is a classi er C that assigns each element of the set S T to one of the classes of Y = f+1; 1g, where S is called the set of source 1 Freely available at http://oaei.ontologymatching.org/2010/. 2 Freely available at http://dbs.uni-leipzig.de/en/research/projects/object_ matching/fever/benchmark_datasets_for_entity_resolution. 3 http://saim.sf.net instances, while T is the set of target instances. (s; t) 2 S T is considered by C to be a correct link when C(s; t) = +1. Otherwise, (s; t) is considered not be a potential link. We will assume that the classi er C relies on a complex similarity function which consists of a combination of atomic similarity measure i. Each of the atomic similarity measures is associated with a parameter !i, which is used in main cases as threshold or weight for i. Supervised approaches to the computation of link speci cations use labelled training data L S T Y to maximize an objective function such as the distance from the labelled data items to the boundary of the classi er in the case of Support Vector Machines [ 1 ]. The idea behind unsupervised approaches to learning link speci cations is that they do not to utilize any training data (i.e., L = ;). Instead, they aim to optimize an objective function F . In the following, we present the non-deterministic and the deterministic approaches we utilized in our experiments. We then present two di erent objective functions that are based on the well-know F -measure. These functions build the basis for our evaluation. 2.1

Non-Deterministic Approach

Algorithm 1 EAGLE

Require: Sets of instances S and T , size of population, number of iterations Get property mapping (S, T ) Generate initial population repeat

Compute F for all individuals.

Apply genetic operators to population until Number of iterations is reached return Overall ttest individual

The non-deterministic approach we evaluated is based on the EAGLE approach presented in [ 9 ] and implemented in the LIMES framework [ 8 ]. The approach was modi ed as described in Algorithm 1. We begin by generating a random population of n individuals. Let Gt be the population at the iteration t. To evolve a population to the generation Gt+1, the tness of each individuals gt 2 Gt is computed. For this purpose, the mapping M (gt) generated by gt is evaluated and the value F (M (gt)) is assigned to gt. These tness values build the basis for selecting individuals for the genetic operator reproduction. EAGLE uses a tournament setting between two selected individuals to decide which one is copied to the next generation gt+1. On randomly selected individuals the operator mutation is applied according to a probability called the mutation rate. A mutation can a ect an individual in three di erent ways: First, it can alter the thresholds used by the individual. Second, a mutation can alter the property values that are compared by one of the atomic measures on which the classi er relies. Finally, mutations can modify the measures included in the The postprocessed mapping is nally returned. individuals. The third genetic operator, crossover, operates on two parent individuals and builds a new o spring by swapping two random sub-trees of the parent genotypes. The application of these operators is carried out iteratively until a maximal number of iterations is reached. The result of this process is the mapping M that is returned by the best individual. M is postprocessed as follows: Each s 2 S such that 9t 2 T : (s; t) 2 M is mapped to arg max (s; t). t2T 2.2

Deterministic Approaches

Algorithm 2 EUCLID

Require: Speci cation of the datasets S and T Require: ! 2]0; 1[ Require: > 1, > 0 with ( ; ) 2 N2

Get property mapping (S, T ) bestClassi er = (1, . . . , 1)

= ; for k = 0 ! b1= !c do

= [ f1 k !g end for for i = 1 ! n do imax = arg max F ( i !2 ; i2

!), !imin = 0, !imax = 1 end for for it=erja!timioanxs !=im1in!j

do C = argnmax F (!imin + ki )

i=1 if F (C) > F (bestClassi er) then

C = bestClassi er else

bestClassi er = C end if for j = 1 ! n do

!jmin = max(0; j ), !jmax = min(1; j ) end for end for return bestClassi er

Linear and Boolean classi ers have been shown in previous work [ 8 ] to also achieve good results on the task of LD. Both types of classi ers can be characterized by a similarity function which depends on similarity measures i and parameters !i. Linear classi ers L classify (s; t) as belonging to +1 i n n P !i i(s; t) 1. For Boolean classi ers B, the inequality V i(s; t) !i must i=1 i=1 be ful lled by the pair (s; t) for it belong to +1. In both cases, a classi er can be encoded by the vector = (!1; : : : ; !n). Determining the best L or B would require testing all possible combinations of values !i 2 [0; 1], which would be impracticable. The idea behind our algorithm EUCLID (E cient and Unsupervised Classi cation for Link Discovery) is to reduce the number of con gurations that must be tested by applying a search within the search space whose granularity increases gradually as described in Algorithm 2: We rst begin by detecting the right similarity measure for each pair of properties. To achieve this goal, we use the similarity imax = arg max F ( i !) for each pair of properties, where !2 ; i2 F ( i !) is the value of the pseudo-F-measure (PFM) of the classi er C0 such that C0(s; t) = +1 () i(s; t) !, = f! > 0 with 9k 2 N : ! = 1 k !g is a set of threshold values and is the set of similarity measures implemented by the framework at hand. Note that ! is the rst of the three parameters required by EUCLID.

In a second step, we compute the actual link speci cation. Given two parameters > 1 and > 0, !imin and !imax are set to 0 and 1 respectively for each of the similarities i. Then the interval !imin and !imax is split into intervals of the same size = (j!imax !iminj= . For each of the possible parametrization !i = !imin + k , k 2 f0; : : : ; g, EUCLID simply runs all of the resulting classi ers C and compute their tness F (C). The current overall best classi er C = ( 1; : : : ; n) is used as new reference point. !miin is set to maxf0; i g and !miax to minf i + ; 1g while := =2. This procedure is repeated times and the best overall classi er w.r.t. F is returned. 3

Pseudo-F-measures

We considered two di erent PFMs for the automatic discovery of link speci cations. The rst PFM, dubbed Fu , was proposed by [ 10 ] and is based on the F measure. Consequently, it is de ned as Let M S T be a mapping generated by an algorithm, S be the set of source instances and T be the set of target instances. Pu is de ned as

Fu = (1 + 2

PuRu ) 2Pu + Ru

: Pu(M ) = jfsj9t : (s; t) 2 M gj ;

P jft : (s; t) 2 M gj s Ru(M ) =

jM j min(jSj; jT j) : (1) (2) (3) while Ru is computed as follows: Note that Ru(M ) can be larger than 1 as jM j can be larger than min(jSj; jT j). While this does not occur in the setup proposed by [ 10 ], it seems rather counterintuitive that a recall measure can lead to values beyond 1. We thus speci ed the following novel pseudo-recall dubbed Rd:

Rd(M ) = jfsj9t : (s; t) 2 M gj + jftj9s : (s; t) 2 M gj : jSj + jT j (4) This pseudo-recall computes the ratio how well all source and target instances are covered by the Mapping M . Thus, Rd(M ) = 1 if every s 2 S is mapped to at least one t 2 T and vice versa. We would argue that it is therewith more in line with the original de nition of precision and recall. Our pseudo-F-measure Fd is thus de ned as

Fd (M ) = (1 + 2

Pd(M )Rd(M ) ) 2Pd(M ) + Rd(M ) with Pd = Pu: (5) 4

Experiments and Results

The goal of our experiments was twofold. First, we wanted to know how deterministic approaches perform in comparison to non-deterministic approaches for the discovery of link speci cations. The basic intuition here was that if deterministic approaches can achieve F-scores similar to those of non-deterministic approaches, they should be preferred as they are usually more time-e cient. We thus compared the maximal F-measure achieved by each of our approaches on the six di erent data sets at hand. Moreover, we wanted to measure how well PFM can predict the real performance of classi ers. Especially, we were interested in knowing whether the predictive power of pseudo-F-measures is as reliable on real data as it has been shown to be on synthetic data. Within this context, we were also interested in knowing which setting of led to the best real F-measure across the di erent datasets that we used, as = 0:1 was suggested in the past [ 10 ]. We thus ran our evaluation using both Fu and Fd for -values between 0.1 and 2.0 using a 0.1 increment. We used two di erent measures to evaluate the correlation between PFM and F1. In the following, we present the data, algorithmic parameters and correlation measures used for our experiments. We then present our results and discuss their implications for the next steps of research on link discovery. 4.1

Experimental Setup

In all experiments, we assumed that we knew the perfect mapping between the properties. Each experiment was ran on a single thread of an Ubuntu Linux server running JDK1.7 and was allocated maximally 2GB of RAM. The processors were 2.0GHz quadcore Opterons.

Data We ran our experiments on three synthetic and three real datasets. The synthetic datasets consisted of widely used and well-known Persons1, Persons2 and Restaurant datasets from the OAEI2010 set of benchmark data sets. The real datasets consisted of the ACM-DBLP, Amazon-Google and Abt-Buy datasets that were extracted from websites or databases and for which a gold standard was created manually as reported in [ 5 ]. The ACM-DBLP dataset consists of 2,617 source and 2,295 target publications (gold standard: 2,224 links). The AmazonGoogle dataset links 1,363 to 3,226 products (gold standard: 1,300 links). Finally, the Abt-Buy dataset links 1,081 to 1,092 products via 1,097 correct links. All non-RDF datasets were transformed into RDF and all attribute values were set to lower case. Apart from this preprocessing, no other preprocessing step was carried out.

Parametrization of the algorithms Four parameters need to be set to run

EAGLE: the number of iterations, the size of the population, the crossover rate and the mutation rate. Similarly to [ 10 ], we used 20 iterations with a population of 100 individuals. The crossover and mutation rates were set to 0.6. Given that this approach is not deterministic, we ran the experiments 5 times and present the average values in Section 4.2. Note that the standard deviations for the Fmeasures were always under 5% of the average value. For EUCLID, we used ! = 0:1, = 4, = 10.

Correlation Measures To measure the accuracy of the algorithms, we used the standard F1-measure. We were interested in determining whether the pseudo-Fmeasures Fu and Fd can be used practically to predict the F1 measure achieved by an algorithm and which setting of was the best to achieve this goal. Thus, we measured the correlation of Fu and Fd with F1 across di erent values of . We used two di erent correlation measures: The Pearson and the Spearman correlation. We used the Pearson correlation to ensure the comparability of our approach with other correlation studies as this correlation is one of the most commonly used. The main drawback of the Pearson correlation is that it is most reliable at detecting linear correlations between distributions. As there was no reason for assuming a linear relationship between our measures, we opted to also use another correlation measure that do not make any assumption upon the type of correlation between the input distributions. We used the Spearman correlation [ 13 ], which assesses how well a monotonic function can describe the relationship between the input distributions by comparing the ranks of the values in the two input distribution. For both correlations, we used a 2-tailed signi cance test with a con dence threshold of 95%. 4.2

Results

We rst measured the F1-scores achieved by our approaches when relying on Fd (see Figure 1) and Fu (see Figure 2). Our results indicate that EUCLID is in general slightly superior to EAGLE. Note that the linear classi er in combination with Fd even outperforms the supervised approaches presented in [ 5 ] and [ 9 ] on the ACM-DBLP data set. In addition the linear model leads to better results than the Boolean model in most cases (expect on the Restaurant dataset). Our

Fd . The y-axis shows the di erent F-values. Note that \FdPseudo" stands erent classi ers while \FdReal" stands results suggest that Fd is better suited for EUCLID while Fu and Fd tie for EAGLE. With respect to runtime, EUCLID requires between 2.5 and 30s and is therewith between 1 and 2 orders of magnitude faster than EAGLE. Given the signi cant di erent in runtimes we observed within our experiments, we suggest 2 . 0 0 . 0

2 . 0 2 . 0 0 . 0 0 . 5 1 . 5

2 . 0

FFFFFF dddddd PRPPRR ssseee eeeaaa uuulll LBG ddd i onoooe oeBLGn laieeone rtaoeni c nlaee rta i c n

FFFFFF dddddd PRRPPR ssseee eeeaaa uuulll GBL ddd i onoeoo oeGnBL laeieone rtaoeni c nlaee rta i c n

0 . 5 (d) 1 . 0 ACM-DBLP 1 . 5 (f )

FFFFFF dddddd RPPRPR ssseee eeeaaa uuulll LBG ddd i onoooe oeLBGn laieeone rtaoeni c nlaee rta i c n

1 . 0

Abt-Buy 0 . 9 0 . 8 0 . 7 0 . 6 0 . 5 0 . 4 0 . 3 0 . 2 0 . 5 1 . 0 0 0 . 9 0 0 . 3 0 . 2 that the development of speci c algorithms for classi ers of a given type can lead to algorithms for the discovery

of link speci cations that are both timee

cient and highly accurate. The insight we gain is thus a clear answer to our rst question: unsupervised deterministic approaches can perform as well as unsupervised approaches on both synthetic and real data.

Linear

To answer our second question, we rst computed the algorithm-independent correlation of Fd and the F1 measure as well as the correlation of Fu and the F1 measure (see Figure 3). In our experiments, the correlations varied signi cantly across the di erent values of , yet remained positive and signi cant in 97.5% of the cases (the 2 lowest correlation scores of the Pearson correlation for Fu were not signi cant). This means that optimizing Fu and Fd for one particular setting of is a sensible approach towards nding the best classi er for that particular setting of . We then computed the Pearson and Spearman correlation (see Table 2) between Fu, Fd and the F1 measure achieved by the di erent approaches across di erent values of . Our results were somewhat surprising as we detected both signi cant positive and negative correlations across the di erent datasets and for both correlations. Interestingly, while the number of signi cant positive and negative correlations were relatively balanced for the synthetic data sets, negative correlations seemed to dominate the set of real datasets, thus hinting towards Fu and Fd behaving di erently depending on the type of data they are confronted with. The negative correlation values suggest that to detect the best values of for a real dataset automatically, the mapping M which leads to the smallest best value of Fd across the di erent values of should be chosen. This seems rather counter-intuitive and is a hypothesis that requires ampler testing on a larger number of real datasets. Overall, our results show clearly that no -value achieves a maximal F1-measure across our data sets. Still, for real datasets, Fd seems to perform well for 2 [0:8; 1:2]. Stating such an interval for Fu is more di cult as the set of -values that lead to the best mapping is very heterogeneous across the di erent datasets. Interestingly, this conclusion diverges from that proposed in previous work. The answer to our second question is still clearly that while the predictive power of Fu and Fd is su cient for the results to be used in practical settings, signi cant e ort still needs to investigated to create a generic non-parametric PFM that can be used across di erent datasets and algorithms to predict the F1-measure reliably . 5

Conclusion

In this paper, we present a rst series of experiments to determine how well standard classi er models such as linear and Boolean classi ers perform in comparison to classi ers generated by the means of genetic programming in an unsupervised learning setting based on maximizing a PFM. Overall, our results indicate that we are still at the beginning of the search towards the \holy grail" of PFMs. Especially on real data, the maximal PFM achieved by algorithms across di erent values of is often negatively correlated with the value of the F1. The magnitude of this e ect is signi cantly reduced on synthetic data. This di erence suggest that there is still a need for benchmark generation methods that allow creating benchmark data sets which re ect real data in a more holistic way. Moreover, our evaluation shows that deterministic classi ers perform as well as or better than non-deterministic approaches while still bearing the main advantage of being signi cantly more time-e cient. Thus, nding more efcient extension of EUCLID or similar approaches should allow providing users of LD frameworks with accurate link speci cations within an interactive setting. Detecting the right parametrization for PFM yet remains an unsolved problem.

References

1. Nello Cristianini and Elisa Ricci . Support vector machines . In Encyclopedia of Algorithms . 2008 .

2. Aidan Hogan , Axel Polleres, Jrgen Umbrich, and Antoine Zimmermann . Some entities are more equal than others: statistical methods to consolidate linked data . In Workshop on New Forms of Reasoning for the Semantic Web: Scalable & Dynamic (NeFoRS2010) , 2010 .

3. R. Isele , A. Jentzsch , and C. Bizer . E cient Multidimensional Blocking for Link Discovery without losing Recall . In WebDB, 2011 .

4. Robert Isele and Christian Bizer . Learning Linkage Rules using Genetic Programming . In Sixth International Ontology Matching Workshop , 2011 .

5. Hanna Kopcke, Andreas Thor, and Erhard Rahm . Comparative evaluation of entity resolution approaches with fever . Proc. VLDB Endow ., 2 ( 2 ): 1574 { 1577 , 2009 .

6. Axel-Cyrille Ngonga Ngomo . A time-e cient hybrid approach to link discovery . In Proceedings of OM@ISWC , 2011 .

7. Axel-Cyrille Ngonga Ngomo and Soren Auer. Limes - a time-e cient approach for large-scale link discovery on the web of data . In Proceedings of IJCAI , 2011 .

8. Axel-Cyrille Ngonga Ngomo , Jens Lehmann, Soren Auer, and Konrad Ho ner. Raven: Active learning of link speci cations . In Proceedings of the Ontology Matching Workshop (co-located with ISWC) , 2011 .

9. Axel-Cyrille Ngonga Ngomo and Klaus Lyko . Eagle: E cient active learning of link speci cations using genetic programming . In Proceedings of ESWC , 2012 .

10. Andriy Nikolov , Mathieu D'Aquin , and Enrico Motta . Unsupervised learning of data linking con guration . In Proceedings of ESWC , 2012 .

11. George Papadakis , Ekaterini Ioannou, Claudia Niedere, Themis Palpanasz, and Wolfgang Nejdl . Eliminating the redundancy in blocking-based entity resolution methods . In JCDL , 2011 .

12. Jennifer Sleeman and Tim Finin . Computing foaf co-reference relations with rules and machine learning . In Proceedings of the Third International Workshop on Social Data on the Web , 2010 .

13. C. Spearman. The proof and measurement of association between two things . The American journal of psychology , 15 : 72 { 101 , 1904 .