TL;DR
This paper argues that in document retrieval, the order of results is often more important than the exact similarity scores. They introduce formal definitions of equivalence between similarity measures, showing that many measures can be grouped into classes that produce identical result rankings. This insight simplifies the selection of similarity measures and has implications for how retrieval systems are evaluated and designed.
What Problem Does This Paper Address?
In document and image retrieval systems, a core task is to compare a user's query (e.g., an example image) against a database of documents or images. This comparison is done using similarity measures, which assign a score indicating how well each document matches the query. The system then ranks the documents based on these scores, presenting the most similar ones first.
The challenge arises because there are numerous similarity measures available, and it's often unclear which one to choose. The authors observe that users typically focus on the order of the retrieved documents, not the specific numerical similarity values. This is also reflected in common evaluation metrics like precision and recall, which depend on the ranking of relevant items, not their precise scores. The paper aims to understand if this focus on order allows for a simplification in choosing and understanding similarity measures.
Methods
The paper introduces formal definitions of equivalence between similarity measures. The key idea is that two measures are considered equivalent if they produce the same ranking of documents for any given query. They define three types of equivalence:
- Equivalent in Order: Two measures $S_a$ and $S_b$ are equivalent in order if for any two sets of features $(X, Y, Z)$ and $(X', Y', Z')$, the condition $S_a(X, Y, Z) \leq S_a(X', Y', Z')$ implies $S_b(X, Y, Z) \leq S_b(X', Y', Z')$. This means they preserve the relative order of any two comparisons.
- Equivalent by Function: Two measures $S_a$ and $S_b$ are equivalent by function if there exists a strictly increasing function $f$ such that $S_b = f \circ S_a$. This implies that one measure's output can be transformed into the other's through a monotonic function.
- Equivalent in Level-Sets: Two measures $S_a$ and $S_b$ are equivalent in level-sets if for any similarity level $\beta$ in the range of $S_b$, there is a unique similarity level $\alpha$ in the range of $S_a$ such that their level sets are identical.
The authors demonstrate that these definitions lead to the same notion of equivalence, particularly for continuous measures. They then apply these definitions to Tversky's ratio model, a family of similarity measures parameterized by $\alpha$ and $\beta$. They show that within this model, measures are equivalent if their parameters $(\alpha, \beta)$ have the same ratio, effectively reducing the choice of parameters to a single value $k$.
Datasets
Not discussed in the paper. The paper focuses on theoretical definitions and uses illustrative examples with generic queries and image databases (e.g., "Washington Groundtruth" mentioned in Section 2.4).
Key Insights and Ideas
- Order is King: The core insight is that for many practical applications of document retrieval, the exact similarity score is less important than the relative order of the results. This observation simplifies the problem of choosing between numerous similarity measures.
- Equivalence Classes: Similarity measures can be grouped into "equivalence classes" where all measures within a class produce the same ranking for any query. This significantly reduces the search space for selecting an appropriate measure.
- Predictability: If two measures are equivalent, the outcome of procedures relying on similarity values (like thresholding or aggregation) can be predicted. Even if a system uses specific similarity values, if an equivalent measure is used, the results can be understood or transformed.
- Tversky's Ratio Model Simplification: The paper shows that Tversky's ratio model, which has two parameters $(\alpha, \beta)$, can be simplified. Equivalence within this model depends only on the ratio $\alpha/\beta$, meaning the choice of parameters can be reduced to a single parameter $k$, simplifying its application.
Key Results
- The paper formally defines three types of equivalence for similarity measures (order, function, level-sets) and shows they are equivalent.
- It demonstrates that measures like Jaccard, Dice, and Fermi-Dirac belong to the same equivalence class, while Ochiai's measure belongs to a different one. Figure 2 visually supports this by showing a clear functional relationship between Jaccard and Dice, but not between Jaccard and Ochiai.
- For Tversky's ratio model, equivalence is established when the ratio of parameters $\alpha/\beta$ is the same. This allows for a single parameter $k$ to characterize equivalence classes within this model.
- The paper argues that for procedures like recall/precision evaluation or best-matching algorithms, only the order matters, making equivalent measures interchangeable.
Limitations and Future Work
- Focus on Order: While the paper emphasizes that order is often paramount, it acknowledges that in some "value-based procedures" (like thresholding), the actual similarity values do matter. The paper shows how to predict these values using equivalent measures, but the initial assumption of order-dominance might not hold universally.
- Theoretical Framework: The paper provides a theoretical framework for understanding similarity measure equivalence. Applying this framework to a wider range of similarity measures and real-world retrieval systems could be a future direction.
- Image Representation: The paper mentions that the choice of image representation (e.g., global histograms vs. regional features) is separate from the similarity measure itself. Further research could explore how similarity measure equivalence interacts with different image representation techniques.
- Parameter Selection: While the paper simplifies parameter selection for Tversky's model, determining the "best" value for the single parameter $k$ for a specific application might still require empirical study.
Summary updated