TL;DR
This paper tackles the challenge of organizing vast, automatically generated paraphrase databases by word sense, which currently lump all meanings together. They introduce and evaluate novel graph-based clustering methods, leveraging various similarity metrics and semantic features, to create sense-specific paraphrase clusters, significantly improving resource utility.
What Problem Does This Paper Address?
Automatically generated paraphrase databases, like the Paraphrase Database (PPDB), are incredibly useful due to their sheer scale, offering far more coverage than manually curated resources like WordNet. However, a major drawback is that for polysemous words (words with multiple meanings), all paraphrases, regardless of sense, are grouped together. This makes it difficult for downstream NLP tasks to select the most appropriate paraphrase for a given context. For instance, paraphrases for "bug" might include terms related to insects, software glitches, and listening devices, all mixed into one list. This paper aims to solve this by clustering these paraphrases into distinct sense groups, mirroring WordNet's synset structure but on a much larger scale.
Methods
The authors employ two advanced graph clustering algorithms:
- Hierarchical Graph Factorization Clustering (HGFC): This method probabilistically partitions data into hierarchical clusters, allowing for varying levels of granularity. It factorizes an adjacency matrix into a bipartite graph representing paraphrases and senses.
- Self-Tuning Spectral Clustering: This algorithm produces a flat clustering with a user-specified number of clusters. It works by computing eigenvectors of a normalized Laplacian matrix derived from the similarity matrix.
A key aspect of their work is the systematic exploration of various similarity measures to populate the input adjacency matrix for these algorithms. These include:
- PPDB Scores: Direct paraphrase probabilities from PPDB.
- Second-Order Paraphrase Scores: Similarity calculated by comparing the sets of paraphrases for two words (using cosine similarity or Jensen-Shannon divergence on their paraphrase feature vectors).
- Foreign Word Alignments: Similarity based on shared foreign translations of English words.
- Monolingual Distributional Similarity: Using Word2Vec embeddings for paraphrases.
- Entailment Relations: Incorporating automatically predicted semantic entailment relationships (e.g., "fault" entails "failure") to boost similarity for related senses and decrease it for unrelated ones.
Datasets
- Paraphrase Database (PPDB): The primary source of paraphrases, specifically PPDB 2.0 XXL entries.
- WordNet: Used as a reference for evaluation, specifically for a subset of polysemous words and their immediate hyponyms/hypernyms.
- SEMEVAL 2007 Lexical Substitution test data: Used to select query words for evaluation.
- CrowdClusters: A newly created benchmark dataset where paraphrase sets from PPDB were manually clustered with the help of crowd workers on Amazon Mechanical Turk.
Key Insights and Ideas
- The need for sense-aware paraphrases: The paper strongly argues that simply having a large list of paraphrases is insufficient for many NLP tasks; sense disambiguation is crucial for effective paraphrase selection.
- Graph-based clustering is effective: Both HGFC and Spectral Clustering, when properly configured, significantly outperform simpler baselines in organizing paraphrases by sense.
- Entailment relations are powerful signals: Incorporating predicted entailment relationships (like "fault" entails "failure") provides a significant boost to clustering quality, indicating that semantic relationships are strong indicators of shared senses.
- No single similarity metric reigns supreme: Different similarity metrics excel on different evaluation metrics (F-Score vs. V-Measure) and datasets, suggesting that a combination or careful selection is often best.
- Second-order comparisons offer potential but don't always beat direct scores: While comparing paraphrase sets (second-order) is an interesting idea, it didn't consistently outperform direct PPDB scores in their experiments.
Key Results
- Significant performance gains: Spectral Clustering achieved a 64% relative improvement in F-Score over the closest baseline on the WordNet+ dataset, while HGFC achieved a 50% improvement.
- Entailment impact: Adding entailment information improved F-Score by an average of 0.014 and V-Measure by 0.020 across experiments.
- HGFC and Spectral outperform baselines: Both advanced clustering methods significantly outperformed Most Frequent Sense (MFS), One Cluster per Paraphrase (1C1PAR), Random (RAND), and SEMCLUST baselines, except for 1C1PAR's V-Measure score (which is biased towards many small clusters).
- PPDB scores are strong contenders: The direct PPDB 2.0 Score similarity metric performed well, often outperforming other metrics, especially in terms of F-Score.
Limitations and Future Work
- WordNet's fine granularity: WordNet synsets are very fine-grained, which can make direct comparison challenging for tasks that benefit from coarser sense distinctions.
- Crowdsourcing effort: Creating the CrowdClusters benchmark was a significant undertaking.
- Future work: The authors suggest exploring applications of these sense-clustered paraphrases, particularly in lexical substitution tasks. They also propose more complex methods for choosing the best cluster for a given context, such as using pseudo-word approaches. They also mention releasing their code and paraphrase clusters.
Summary updated