Many solutions have been proposed for the entity matching problem. The classic example is a rule-based approach. The method clusters those that contain full or partial matches of attribute values or identical tokens that have been segmented into words (Jaro, 1989), (Cohen, et al., 2003), (Benjelloun, et al., 2009). Recently, a machine learning approach has been proposed. They use random forests (Gokhale, et al., 2014), (Das, et al., 2017), and metric learning (Peeters, et al., 2022), (Osawa, et al., 2021) to judge whether an entity pair is a match by calculating its similarity. These methods are simple and inexpensive but are vulnerable to orthographical variants of data.

Several studies have pointed out the limitations of entity matching using only computers without human intervention. (Takashi et al. 2019) identified low-precision results based on similarity using Okapi BM25 (Robertson, et al., 1995) and proposed a crowdsourcing-based method that allows for human interaction. (Das, et al., 2017) proposed the framework, Falcon. This method assumes that there is no training data, and a small portion of the target data is labelled by a human to prepare the training data. Other methods using human-in-the-loop have been proposed (Li, 2017), (Gokhale, et al., 2014), (Osawa, et al., 2021), (Eraheem, et al., 2014). Any methods are used to generate or modify data for quality of results and training of the computer, and the other methods are used in much the same way. In this study, we propose a human task from the perspective of obtaining efficient training data.

(Zhu et al., 2020) proposed a method using the transitivity of equivalence class. The method tries to find two matched pairs that share the same entity so that it can infer another match between other two entities, because the matching is done by crowdsourcing and requires a huge monetary cost. Our work is different from it in the way to use the transitivity of equivalence because we use it to detect errors in AI decisions assuming AI is the main matcher. Other methods (Li, et al., 2020), (Trabelsi, et al., 2022) use domain knowledge to improve accuracy in entity matching. Their approach is completely different from ours and complementary to each other.

In this section, we define the problem. Table 1 shows definitions of symbols in this paper.

We define a tuple of entities as 𝑥=(𝑠_𝑖,𝑠_𝑗), set of all possible tuple of entities as 𝒳={(𝑠_𝑖,𝑠_𝑗)∈𝒮²∣𝑖<𝑗}, a set of labels 𝒴={𝑀𝑎𝑡𝑐ℎ,𝑈𝑛𝑚𝑎𝑡𝑐ℎ}, and a set of all true data as Un=xi,yii=1n⊂X×Y, where n=sC2⋅Lm=xi,yii=1m⊆Un is the labelled training set with 𝑚 samples(We assume that humans give answers with the platform such as crowdsourcing ) (we give 𝑚 and 𝑚 ≪𝑛). Our main goal is to design a query strategy 𝒬: 𝒰^𝓃→ℒ^𝓂 to train an entity matching model (matcher) 𝑓∈ℱ, 𝑓:𝒳→𝒴. The optimization problem can be expressed as follows:

where δ is the indicator function. The intuition of Eq. (1) is that, for all pairs of entities in a dataset, it is beneficial for the matcher to answer a matching for a pair $x$ correctly, and the dataset ℒ^𝓂 contains the correct label for a pair 𝑥. We assume the model returns a probability of 𝑀𝑎𝑡𝑐ℎ or 𝑈𝑚𝑚𝑎𝑡𝑐ℎ, and we note the probability of 𝑀𝑎𝑡𝑐ℎ that the matching model gives to a tuple (𝑠_𝑖,) as 𝑃(𝑀𝑎𝑡𝑐ℎ|𝑠_𝑖,𝑠_𝑗).

Algorithm 1 implements the idea of inconsistency-driven sampling. It takes a set of entity pairs with match probabilities D̂={((𝑠_𝑖,𝑠_𝑗),𝑝)}⊂𝒳×[0,1] and outputs 𝑚 sample pairs taken from the given set. Note that the matching probability 𝑝=(𝑀𝑎𝑡𝑐ℎ|𝑠_𝑖,𝑠_𝑗). Note that the given set of entity pairs forms a graph, and that the triples that may cause the inconsistency in the graph are triangles. We define a set of triangles as

The flow of inconsistency-driven sampling is as follows: First, we apply the blocking method for the set of entities, then sort the triangles in descending order of , and lastly, sample the /3 triangles with the highest to sample pairs of entities.

We conducted an extensive set of experiments to address our research questions and evaluated the impact of sampling strategies on the f1 value of matchers on datasets from different domains.

Figure 3 overviews the overall experiment workflow. First, we apply a blocking technique to each of the three datasets for the experiment and generate training and evaluation datasets. Then, we execute human-in-the-loop entity matching iterations with each of the five sampling strategies. We explain the steps one by one.

For each of the three original datasets, we generated two data sets we use in the blocking phase and the human-in-the-loop entity matching iterations:

・ the training dataset for the blocking phase and the Bayesian inference, and

・ the evaluation dataset for evaluating sampling strategies to update the Bayesian inference.

The two datasets were constructed as follows and disjointed from each other.

Training dataset 𝐷^𝑡: For each original dataset, we randomly choose a set of 15,000 positive pairs (the two cluster labels are the same) and 15,000 negative pairs (the labels are different from each other) from all pairs of entities in the original dataset. Then, every entity pair and their label form a triple contained in 𝐷^𝑡.

Evaluation Dataset 𝐷^e: First, we randomly select clusters from each of the original datasets until each dataset contains about 2000 entities in total. Then, we generate a set of entity pairs with labels from the clusters.

Then, we constructed the dataset by applying a standard blocking technique based on metric learning to all pairs of the selected entities. The blocking technique chose only pairs of entities that were closer than the threshold after metric learning on the distance among entities with the training dataset.

Table 3 shows the statistics of the evaluation datasets constructed this way. Note that the blocking does not work in favour of the inconsistency-driven sampling because the blocking is done based on the metric learning result, and it removed some of the potentially matched pairs that can affect the inconsistency-based sampling (i.e., the recall of the matches is less than 1).

Algorithm 2 gives the concrete steps in the human-in-the-loop entity matching iterations in the experiment workflow. First, we conduct the Bayesian inference with ^{} for ^{} . Then, in the iteration, it chooses samples for which it obtains human labels and uses the obtained result to update the inference. We chose Bayesian inference because it is a simple matcher that satisfies the requirement for the application of our inconsistency-driven sampling: it outputs a matching probability for a pair of entities. Note that our research question is not the performance of a particular matcher, and we can use this Bayesian inference matcher without loss of generality.

Prior distribution for Bayesian inference. The prior distribution was set to (𝑀𝑎𝑡𝑐ℎ) = 0.1 and (𝑈𝑛𝑚𝑎𝑡𝑐ℎ) = 0.9.

Batch sampling. We adopted a batch sampling scheme to reduce the number of inference updates; in each iteration, we choose $m$ samples (instead of choosing one sample) and obtain their human labels before each inference update. We set = 300. We need to be careful when dealing with inconsistency-driven sampling in the batch because we may obtain more than one human label for the same pair if it appears in different sets of inconsistent triangles. We solved the duplication by majority vote.

Languages and libraries. These algorithms were implemented by Python3, using the modules Tensorflow (Abadi et al., 2015) for metric learner construction, Cupy (Okuta et al., 2017) and Faiss (Johnson et al., 2019) for blocking and indexing, and Scipy (Virtanen, et al., 2020) and Scikit-Learn (Pedregosa, et al., 2011) for Bayesian inference probability density function manipulation.

Fig. 5 shows how different the five sampling strategies are from each other in terms of chosen samples. The horizontal axis represents the match probability determined by the inference, where the closer the match probability is to 1, the more likely the pair is to be matched, while the closer it is to 0, the more unlikely. The vertical axis represents the number of chosen pairs in the sampling strategy (in the log scale). The higher orange intensity means that they are chosen in earlier iterations.

The result clearly shows that the strategies are remarkably different in terms of chosen samples. Inconsistency-driven sampling tends to choose pairs that are highly likely or unlikely to be positive, while uncertainty sampling constantly chooses pairs in the middle. Query-by-committee, diversity, and random sampling choose pairs from a wide range.

Fig. 6 shows the effects of each sampling strategy on the matcher performance in the iterations. The X-axis is the number of iterations. The Y-axis is the F1 value for the output of Bayesian Inference and human labels after each iteration for the evaluation dataset. Each line represents a sampling strategy.

The aim of seeing the figure is to identify the sweet spots of each sampling strategy. Note that the performance of matchers (to be used with sampling strategies) for Persons, Bibliorecords, and Music are very different (very high, moderate, and very low, respectively). The result suggests the following. First, inconsistency-driven sampling is effective when the f1 value of the matcher is high (i.e., higher than 0.8), while uncertainty sampling performs the best, especially for lower-quality matchers. Second, when the f1 value is high, the performance inconsistency-driven is stable, while other sampling strategies are directly influenced when the accuracy of human labels becomes lower. The results are reasonable for the following reasons: if the f1 value of matchers is not high, it is difficult to identify inconsistency correctly. Third, the inconsistency-driven approach can identify inconsistencies even for newly obtained human labels, while other strategies take human inputs as oracles, even if they are incorrect.

The results so far showed that (1) the inconsistency-based sampling works better when the inference f1 value is high while uncertainty sampling works better otherwise and that (2) the chosen pairs of the strategies are completely different to each other. They suggest that it is worth considering a hybrid strategy. Since it is difficult to set the threshold to switch strategies, we considered a simple hybrid strategy that switches uncertainty and inconsistency-driven strategies in each iteration.

Fig. 7 shows the results of applying the hybrid strategy to the three datasets with 90%-accurate human labels. The result shows that the hybrid strategy performs well when the inference f1 value is moderate or higher, which covers many practical situations. On the other hand, uncertainty sampling still works better with the inference with an extremely low f1 value.