TL;DR
This paper introduces a novel semi-supervised feature clustering algorithm designed to tackle the challenge of dimensionality reduction in Word Sense Disambiguation (WSD). By effectively leveraging both labeled and unlabeled data, their method achieves state-of-the-art WSD accuracy while significantly reducing feature space complexity, outperforming traditional dimensionality reduction techniques.
What Problem Does This Paper Address?
Word Sense Disambiguation (WSD) is the task of assigning the correct meaning to a word in a given context. Many WSD approaches rely on statistical methods that represent contexts as high-dimensional, sparse feature vectors. This high dimensionality poses significant computational challenges, requiring substantial memory and processing power, which hinders scalability and integration into larger natural language processing systems. Existing dimensionality reduction techniques often fall into two categories: supervised methods that require labeled data and unsupervised methods that only use unlabeled data. This leaves a gap for methods that can effectively utilize both types of data to improve feature clustering and, consequently, WSD performance.
Methods
The core contribution is a Semi-Supervised Feature Clustering (SemiFC) algorithm. Unlike traditional supervised feature clustering, which struggles with features not present in labeled data ("unseen features"), SemiFC addresses this by:
- Inducing Class Labels for Unseen Features: It first estimates "hard labels" for unseen features by leveraging the similarity between seen and unseen features, using a classifier like the Label Propagation (LP) algorithm.
- Clustering All Features: Once all features (both seen and unseen) have estimated class labels, they are clustered together. This is achieved by first creating a soft label matrix for all features and then applying a clustering algorithm like Sequential Information Bottleneck (SIB).
- Leveraging Label Propagation and Local/Global Consistency: The algorithm uses Label Propagation (LP) to infer initial hard labels for unseen features and then employs a Local and Global Consistency (LGC) based semi-supervised learning approach to smooth these labels. This is crucial because labeled data is often scarce, making direct estimation difficult. The LGC approach assumes that good classifications change slowly on the underlying data structure, making it robust to noise.
For dimensionality reduction, the paper compares their SemiFC with other methods like Supervised Feature Clustering (SuFC), Iterative Double Clustering (IDC), Supervised Feature Selection (SuFS), and Latent Semantic Indexing (LSI).
Datasets
The experiments were conducted on the SENSEVAL-3 English Lexical Sample (ELS) task. This dataset includes 57 ambiguous English words. The authors used two experimental setups:
- Full SENSEVAL-3 Data: The entire training set was used as labeled data, and the test set was treated as unlabeled data.
- Sampled SENSEVAL-3 Data: To investigate performance with limited labeled data, a small percentage (10%) of the training data was sampled as labeled, with the rest of the training data and the test set serving as unlabeled data.
Key Insights and Ideas
- Bridging the Gap: The most significant insight is the successful development of a feature clustering method that effectively utilizes both labeled and unlabeled data. This is crucial for scenarios where labeled data is scarce but unlabeled data is abundant.
- Robustness to Noise: The semi-supervised approach, particularly the use of LGC for smoothing, makes the algorithm robust to noise in small labeled datasets, a common issue in WSD.
- Unseen Features are Key: The ability to infer labels for and cluster unseen features is a critical advantage over purely supervised methods, allowing for a more comprehensive feature space reduction.
- Label Information Matters: Supervised and semi-supervised dimensionality reduction techniques (SuFC, IDC, SuFS, SemiFC) consistently outperform unsupervised methods like LSI, highlighting the value of incorporating label information into the reduction process.
Key Results
- State-of-the-Art Accuracy: On the full SENSEVAL-3 dataset, their SemiFC combined with an LP classifier achieved an accuracy of 69.0%, competitive with the best results.
- Significant Dimensionality Reduction: Feature clustering (SemiFC) was shown to aggressively reduce the feature space while losing only about 1.0% accuracy compared to no reduction.
- SemiFC Outperforms Others: When combined with a semi-supervised WSD algorithm (LP), SemiFC outperformed other dimensionality reduction techniques, including supervised ones like SuFC and SuFS.
- Robustness Demonstrated: On sampled SENSEVAL-3 data (limited labeled examples), SemiFC showed significantly better performance than SuFC and SuFS, demonstrating its robustness to noise and scarcity of labeled data. The accuracy achieved was 54.1% (SemiFC + LPjs), with only a 0.8% loss compared to no dimensionality reduction.
- LP Superiority: The LP algorithm generally performed better than SVM when combined with dimensionality reduction, suggesting that leveraging unlabeled data during disambiguation is beneficial.
Limitations and Future Work
- Computational Cost of IDC: The paper notes that IDC was too computationally expensive to run over 20 trials for the sampled data experiments.
- Future Work: The authors suggest extending their work to more datasets to empirically evaluate the algorithm. They also propose that the semi-supervised feature clustering framework is generalizable and can be applied to other NLP tasks, such as text categorization.
Summary updated