Title
Active Learning of Equivalence Relations by Minimizing the Expected Loss Using Constraint Inference
Abstract
Selecting promising queries is the key to effective active learning. In this paper, we investigate selection techniques for the task of learning an equivalence relation where the queries are about pairs of objects. As the target relation satisfies the axioms of transitivity, from one queried pair additional constraints can be inferred. We derive both the upper and lower bound on the number of queries needed to converge to the optimal solution. Besides restricting the set of possible solutions, constraints can be used as training data for learning a similarity measure. For selecting queries that result in a large number of meaningful constraints, we present an approximative optimal selection technique that greedily minimizes the expected loss in each round of active learning. This technique makes use of inference of expected constraints. Besides the theoretical results, an extensive evaluation for the application of record linkage shows empirically that the proposed selection method leads to both interesting and a high number of constraints.
Year
DOI
Venue
2008
10.1109/ICDM.2008.41
ICDM
Keywords
Field
DocType
selection technique,expected constraint,expected loss,equivalence relation,active learning,effective active learning,equivalence relations,high number,constraint inference,large number,proposed selection method,approximative optimal selection technique,data mining,minimization,upper and lower bounds,couplings,learning artificial intelligence,record linkage,probability density function
Data mining,Similarity measure,Computer science,Upper and lower bounds,Artificial intelligence,Transitive relation,Constraint inference,Expected loss,Equivalence relation,Mathematical optimization,Active learning,Inference,Machine learning
Conference
ISSN
Citations 
PageRank 
1550-4786
4
0.45
References 
Authors
11
2
Name
Order
Citations
PageRank
Steffen Rendle1196370.68
Lars Schmidt-Thieme23802216.58