Keyphrase Extraction from Online News Using Binary Integer Programming

Zhuoye Ding, Qi Zhang, Xuanjing HuangIJCNLP 2011 · OpenReview

Abstract

This paper presents a novel approach to keyphrase extraction from online news by framing it as a global optimization problem. Unlike traditional methods that rank phrases individually, the proposed method utilizes Binary Integer Programming (BIP) to select a set of phrases that collectively satisfy criteria of relevance, coverage, coherence, and conciseness. By incorporating constraints based on Latent Dirichlet Allocation (LDA) for topic coverage and Mutual Information (MI) for coherence, the model ensures a representative summary of news events. Experimental results on a custom news dataset demonstrate that the BIP-based approach significantly outperforms standard SVM and Ranking SVM baselines, achieving a peak F1-score of 72.53%.

Introduction

While keyphrases are essential for navigating the massive volume of daily online news, they are rarely provided by publishers. Traditional automatic extraction methods typically score and select phrases individually. This "local" approach often leads to redundant sets that miss minor but important aspects of a story (poor coverage) or feel disjointed (poor coherence). This research addresses these flaws by treating keyphrase extraction as a "set" problem, ensuring that the final selection satisfies four critical criteria: Relevance, Coverage, Coherence, and Conciseness.

Methodology

The researchers transform keyphrase extraction into a binary labeling problem: for every candidate word, the model decides whether it should be a keyphrase (1) or not (0). This is solved using Binary Integer Programming (BIP) to maximize an objective function subject to specific global constraints.

The Objective Function

The selection score for a word is a weighted combination of:

  • TF-IDF: Measuring the uniqueness and frequency of a word across the document group.
  • Locality: Providing "bonuses" to words appearing in high-signal areas like the news title or the first sentence.

Global Constraints

The BIP approach ensures the selected set is globally optimal through:

  • Coverage: Using Latent Dirichlet Allocation (LDA) to identify different "topics" within the news group, the model is constrained to select phrases that cover these topics above a certain threshold.
  • Coherence: Using Mutual Information (MI), the model identifies word pairs that frequently appear together. Constraints force the model to select these pairs together to ensure logical connection.
  • Quantity: A constraint limits the total number of phrases to a user-defined $K$ (e.g., 6 phrases).
Ablation study results showing the impact of individual features and constraints on extraction performance.

Experimental Setup

As no standard public dataset existed for multi-article news keyphrase extraction, the authors curated a dataset of 150 news groups (1,103 articles) from Google News. Three human annotators labeled the data, with a phrase considered "Golden" (ground truth) if at least two annotators agreed. The data was split into 50 groups for parameter tuning and 100 groups for final testing.

Key Results and Insights

The BIP-based method was compared against three baselines: a Title-only method, a standard SVM classifier, and a Ranking SVM. As shown in the performance comparison, the BIP method consistently outperformed all baselines across Precision, Recall, and F1-Score.

Performance comparison of the BIP-based method against Title-only, SVM, and Ranking SVM baselines.

The Power of Global Optimization

The ablation study (Figure 5) confirms that keyphrase extraction is fundamentally a set problem. Removing the "Coverage" constraint dropped the F1-score by over 4% (relative), proving that forcing the model to look at different aspects of a story significantly improves quality. Furthermore, the "InTitle" feature provided a massive boost (roughly 17% relative improvement), confirming that news titles remain the strongest signal for relevance.

Conclusion

By shifting from local ranking to global optimization via Binary Integer Programming, this method successfully captures the multifaceted nature of news stories. While the model requires careful parameter tuning and may face computational challenges with very large document sets, its ability to enforce coverage and coherence represents a significant step forward in automated news summarization.

Summary updated

BibTeX
@inproceedings{ding2011keyphrase,
  author = {Zhuoye Ding and Qi Zhang and Xuanjing Huang},
  title = {{Keyphrase Extraction from Online News Using Binary Integer Programming}},
  booktitle = {IJCNLP},
  year = {2011},
  url = {https://openreview.net/forum?id=tTAetg8VVN},
}
Figure