Active Learning of Equivalence Relations by Minimizing the Expected Loss Using Constraint Inference

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.