Multiple Similarity Measures and Source-Pair Information in Story Link Detection

Francine Chen, Ayman Farahat, Thorsten BrantsNAACL 2004

TL;DR

This paper tackles the challenge of accurately identifying when different news stories are about the same event. They significantly improve upon standard methods by combining multiple similarity measures between stories and incorporating source-pair specific statistical information, leading to the best-performing system at the TDT-2002 competition.

What Problem Does This Paper Address?

The core problem is story link detection, a crucial task in Topic Detection and Tracking (TDT). Imagine sifting through a massive stream of news from various sources – how do you automatically group stories that report on the same specific event (e.g., a particular tornado in Kansas) versus those that are just about a similar topic (e.g., all tornado stories)? This is tricky because events happen at specific times and places, and simply looking at keyword overlap isn't enough. Existing systems often rely on a single similarity measure (like cosine similarity) between document term vectors. However, this can be insufficient, especially given the dynamic nature of news, where new events and vocabulary emerge constantly. The authors aim to improve the accuracy and robustness of these systems.

Methods

The paper introduces a multi-faceted approach to enhance story link detection:

  • Multiple Similarity Measures: Instead of relying on a single similarity metric, they explore and combine several:
  • Cosine Similarity: A standard measure of vector similarity.
  • Hellinger Similarity: A probabilistic measure that captures differences in word distributions.
  • Tanimoto Similarity: Measures the ratio of shared terms to the total terms in a pair of documents.
  • Clarity: A measure that assesses how much a document's word distribution deviates from "general English," aiming to identify topicality.
  • Normalized Cosine: A variation of cosine similarity, normalized by the running median of similarity values for specific source pairs.
  • Source-Pair Specific Statistical Information: This is a key innovation. The authors hypothesize that the similarity between two stories is influenced by their sources (e.g., language, modality like broadcast vs. newswire). They compute statistics (mean, median, variance) of similarity scores for different source-pair combinations from training data. This information is used to "inform" the system about the expected similarity for a given pair of sources.
  • Machine Learning for Combination: To effectively integrate the multiple similarity measures and source-pair statistics, they employ machine learning classifiers:
  • Support Vector Machines (SVMs): Used as the primary method for combining features. They found SVMs to be highly effective, especially when using both similarity scores and source-pair statistics as input.
  • Decision Trees (C4.5): Explored as an alternative, though they treated source-pair statistics more as categorical features.
  • Majority Voting: A simpler combination method that was found to be less effective.

The core idea is to move beyond simple similarity scores and use a richer set of features, including contextual information about the story sources, to make a more informed link detection decision.

Datasets

The research utilizes corpora developed by the Linguistic Data Consortium (LDC) for the Topic Detection and Tracking (TDT) tasks.

  • Training Data:
    • TDT3 corpus (40,000 news articles and broadcast stories with 120 labeled events) was used for initializing document term counts and document counts.
  • TDT3pub partition of the TDT2001 story pairs was used for training the "post-processing" system (SVMs, decision trees).
  • TDT2002 dry run test set was used to compute source-pair statistics.
  • Testing Data:
    • TDT3unp partition of the TDT2001 test story pairs was used for evaluating the system's performance.

The paper does not introduce new benchmarks but rather evaluates its system on existing TDT datasets, comparing its performance against prior work.

Key Insights and Ideas

  • Source Matters: The most significant insight is that the source of news stories provides crucial information for link detection. Simply looking at story content in isolation is less effective than considering where the story came from (e.g., English broadcast vs. Mandarin newswire).
  • Combination is Key, but How Matters: Combining multiple similarity measures generally improves performance, but the method of combination is critical. SVMs, especially when fed a rich set of features including source-pair statistics, significantly outperform simpler methods like voting.
  • Statistics Over Raw Features: Using source-pair statistics (mean, median, variance of similarity scores) as input features to a machine learning model proved more effective than just using raw term vectors for the SVM. This suggests that higher-level, aggregated information is more robust for this task.
  • Clarity's Potential: The Clarity similarity measure, when used with source-pair specific information, showed strong performance, even outperforming some combinations of other measures. This highlights its ability to capture topical differences effectively.
  • Incremental TF-IDF Advantage: The use of an incremental TF-IDF model is beneficial for TDT tasks because it can adapt to new vocabulary introduced by new events, unlike static TF-IDF models that ignore unseen terms.

Key Results

  • The proposed system, which combines multiple similarity measures with source-pair specific statistics using an SVM, achieved the best performance at the TDT-2002 competition.
  • The use of source-pair specific statistics was found to have a larger effect in improving performance than the specific set of similarity measures used.
  • SVMs provided the best performance among the combination methods evaluated (SVMs, decision trees, majority voting).
  • Compared to a baseline normalized cosine similarity system (min DET cost of 0.2732), their best system achieved a min DET cost of 0.2342 on the TDT2001 test data.
  • The use of source-pair specific statistics with similarity measures consistently led to significant improvements (p < .005) across various similarity measures.

Limitations and Future Work

  • Limited Data for SVM Training: The paper notes that attempts to directly apply SVMs to TDT tasks have sometimes been unsuccessful due to a lack of sufficient training data. Their approach mitigates this by using similarity scores and source-pair statistics as input, which are more general features.
  • Generalization to Other Collections: The current experiments were conducted on a collection drawn from broadcast news and newswire in three languages. The authors suggest that experiments on a wider variety of collections would be beneficial for more general assessment.
  • Topic-Specific Models: The authors mention that their post-processing method can be used to enhance other approaches, such as topic-specific models, suggesting future work in integrating these techniques for even better performance.
  • Categorical Treatment of Statistics by Decision Trees: The paper notes that decision trees treated source-pair statistics as categorical features, which might limit their effectiveness compared to SVMs that can leverage them more directly. This suggests exploring how decision trees could better utilize these statistics.

Summary updated

BibTeX
@inproceedings{chen2004multiple,
  author = {Francine Chen and Ayman Farahat and Thorsten Brants},
  title = {{Multiple Similarity Measures and Source-Pair Information in Story Link Detection}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2004},
}
Figure