Abstract
Traditional document similarity measures often rely on tf-idf weighting schemes designed for keyword-based information retrieval. However, these assumptions can fail in "query-by-example" tasks where the query is a full document. This paper introduces Sp, a data-dependent probabilistic similarity measure for bag-of-words representations. Sp evaluates similarity based on the distribution of term frequencies across a collection, avoiding explicit weighting and providing more intuitive results. Empirical evaluations across ten benchmark datasets demonstrate that Sp is highly competitive, consistent, and robust compared to state-of-the-art measures like BM25 and cosine similarity.
Introduction
Measuring inter-document similarity is a cornerstone of text mining, essential for tasks such as clustering, classification, and information retrieval. For decades, the combination of cosine similarity and tf-idf (term frequency-inverse document frequency) weighting has served as the standard approach.
Despite its success, tf-idf has inherent limitations when applied to "query-by-example" (QBE) scenarios. In QBE, the "query" is an entire document rather than a few keywords. The core assumptions of tf-idf—that higher term frequency always implies higher relevance and that rare words are universally more important—can lead to counter-intuitive results. For example, if a query document contains a specific term once, a document containing it fifty times might be considered more similar by tf-idf than one containing it once, despite the latter being a closer match in terms of topical focus.
The Sp Similarity Measure
To address these issues, the authors propose Sp, a measure that leverages the global distribution of term frequencies. Instead of assigning static weights to terms, Sp calculates similarity based on the "gap" between term frequencies in two documents relative to the rest of the collection.
Methodology
The fundamental intuition behind Sp is that two documents are similar with respect to a term if few other documents in the collection have a frequency count falling between them. If the interval between the frequency of a word in document A and document B is sparsely populated, the two documents are considered more similar for that term.
Mathematically, Sp is defined as: $$s_{sp}(\mathbf{x}, \mathbf{y}) = \frac{1}{|T_{\mathbf{x}} \cup T_{\mathbf{y}}|} \sum_{t_i \in T_{\mathbf{x}} \cap T_{\mathbf{y}}} \log \frac{N}{|\{z \in D : \min(x_i, y_i) \leq z_i \leq \max(x_i, y_i)\}|}$$
This approach offers several technical advantages:
- Data-Dependency: It automatically adapts to the specific characteristics of the dataset without requiring manual tuning of tf-idf variants.
- Scale Invariance: The measure is invariant to monotonic scaling of frequency values.
- Efficiency: With preprocessing, Sp operates in $O(M)$ time, maintaining the speed of standard cosine similarity.
Addressing the IDF Blind Spot
Traditional IDF can fail to capture significant similarity signals. For instance, if a term appears in every document, its IDF weight becomes zero, effectively ignoring it. However, if a query and a candidate document share a specific, high frequency for that term while others do not, this is a strong indicator of similarity that Sp naturally captures.
Comparison of Assumptions
The Sp approach fundamentally differs from tf-idf in its underlying assumptions regarding term importance and document ranking.
While tf-idf assumes a linear or logarithmic relationship between frequency and relevance, Sp treats similarity as the inverse of the probability of finding a document between two frequency points. This density-based approach is more robust against the outliers and skewed distributions common in natural language data.
Experimental Evaluation
The authors evaluated Sp across ten diverse benchmark datasets, including TREC (Fbis, La1s, La2s, New3s), 20 Newsgroups (Ng20), Ohsumed (Ohscal), Reuters (R8, R52), Yahoo (Wap), and University Web Pages (Webkb).
Key Results
Performance was measured using Mean Average Precision (MAP@25) against BM25 and various cosine similarity weighting schemes:
- Binary Representation: Sp significantly outperformed existing measures in binary scenarios (presence/absence of words), effectively "learning" an optimal weighting scheme from the data distribution.
- Consistency: Unlike cosine similarity, which shows high variance depending on the chosen tf-idf variant, Sp provided consistently high performance across all ten datasets.
- Robustness: Sp avoids the "negative weight" issue present in BM25, where extremely common terms can paradoxically decrease similarity scores.
Conclusion and Future Work
Sp represents a simple yet effective shift in how we measure document similarity. By moving from static term weighting to a data-dependent probabilistic model, it provides more intuitive results for query-by-example tasks.
Currently, Sp is limited to the Bag-of-Words model and does not account for semantic relationships or word order. Future research could explore extending this density-based similarity approach to other data types, such as categorical or numerical features in broader machine learning applications. Additionally, optimizing updates for dynamic, non-static collections remains an area for further development.
Summary updated