Similarity Score Computation

Imagine a training dataset for an AI model that contains thousands of text examples. Some of them may be copies of one another, or near-copies that differ only in a few words or spacing. Duplicate examples can quietly distort what a model learns, which is why deduplication is part of preparing data.

Before you can remove a duplicate, you need a way to find out which examples resemble each other. Pairwise comparison is one direct strategy for that search. It is a deduplication method that computes the similarity score of each example against every other example in the dataset. The question it answers is simple: how do you decide that two examples are similar enough to count as duplicates?

The key word in pairwise comparison is every. The method does not look for a single representative of a group, and it does not skip examples that seem unlikely to match. Each example takes a turn being the one under inspection, and it is scored against all of the other examples.

Consider four generated example rows, labeled A, B, C, and D. Start with A. It is scored against B, then against C, then against D. Now B is the one under inspection. Its pair with A has already been scored, so B only needs scores against C and D. Then C needs only its score against D. Each pair appears exactly once in the trace.

Notice that A is involved in three pairs, B in three, C in three, and D in three. Every example has one line leaving it for each of the other examples. Because a pair is scored once and covers both examples in it, the picture is the same no matter which example you start from. Nothing is left out, and nothing is repeated.

Two details are worth holding onto. First, the score is computed for a pair, so the similarity of A to B is the same kind of result as the similarity of B to A. Second, once each pair has a score, those scores can be used to decide which examples count as duplicates. The source describes the scoring step. How a high or low score is turned into a removal decision is a separate choice that depends on the score and the dataset.

Counting the pairs for four examples was simple, and the same logic applies to any number of examples. If a dataset has n examples, the number of distinct pairs that get scored is given by the formula below. The formula counts each pair once, which matches the trace above, where B paired with A was not scored a second time.

Each step adds one new example, and that example must be scored against all the examples already present. Adding the fifth example adds 4 new pairs, the sixth adds 5, and so on. The total grows faster than the number of examples because every new example joins every existing one.

Pairwise comparison describes where the scores come from, but it does not specify how each score is calculated. The source names four methods for computing the similarity score of a pair of examples. Each method answers the question of how alike two examples are in a slightly different way.

The source points to Chapter 3 for the details of these methods. The important point for this article is that the pairwise framework stays the same regardless of which method you choose. Every example is scored against every other example, and the chosen method determines the number that each pair receives. Changing the method changes the scores, but it does not change which pairs are scored or how many there are.

The main practical limitation of pairwise comparison is cost. The source notes that this approach can be expensive with large datasets. The formula from the earlier section shows why. The number of pairs grows with the square of the dataset size, so doubling the number of examples roughly quadruples the number of comparisons that must be computed.

Each example contributes a term to the total, but each term also depends on the number of other examples. Data grows linearly while the pair count grows with the square of the dataset size. That is why a method that is manageable for a few hundred rows can become costly for a training set of many thousands of rows.