A Combination of Active Learning and Semi-supervised Learning Starting with Positive and Unlabeled Examples for Word Sense Disambiguation: An Empirical Study on Japanese Web Search Query

Makoto Imamura, Yasuhiro Takayama, Nobuhiro Kaji, Masashi Toyoda, Masaru KitsuregawaACL 2009

TL;DR

This paper tackles the challenge of training Word Sense Disambiguation (WSD) models for web search queries, where manually labeling negative examples is costly and time-consuming. They propose a novel approach that combines active learning with semi-supervised learning, starting with only positive examples and intelligently generating "pseudo-negative" examples to bootstrap the learning process. This method achieves comparable accuracy to fully supervised approaches, significantly reducing the human effort required.

What Problem Does This Paper Address?

Word Sense Disambiguation (WSD) is crucial for accurately analyzing text, especially in web mining tasks like sentiment analysis. It involves determining the correct meaning of a word when it has multiple possible senses. For instance, the word "Loft" could refer to an attic, a golf club angle, a movie title, or a music club.

The main hurdle in building effective WSD systems is acquiring sufficient labeled training data. While it's relatively easy to gather "positive" examples (texts that clearly exhibit the desired sense of a word, often by augmenting queries with related terms), creating "negative" examples (texts that represent other senses) is much harder. This is particularly true for proper nouns, which often have many unexpected meanings on the web, and for languages like Japanese where capitalization doesn't help distinguish senses. Manually identifying and labeling these negative examples is a labor-intensive and time-consuming process, hindering the scalability of WSD for real-world web applications.

Methods

The authors propose a hybrid approach that cleverly sidesteps the need for extensive manual negative labeling. Their method combines:

  • Active Learning: This is a strategy where the model intelligently selects the most informative unlabeled data points for human annotation. In this case, it focuses on identifying the most "uncertain" examples.
  • Semi-Supervised Learning: This technique leverages a large amount of unlabeled data alongside a smaller set of labeled data to improve model performance.
  • "Pseudo-Negative" Example Generation: This is the core innovation. Instead of relying on human annotators to provide negative examples from scratch, the system uses a classifier trained on existing positive and unlabeled data to predict which unlabeled examples are most likely to be negative. These predicted examples are then treated as "pseudo-negative" training data.

Specifically, the algorithm starts with a set of positive examples and a large pool of unlabeled data. In each iteration:

  1. It uses a Naive Bayes classifier trained on current positive and unlabeled data to predict senses for the unlabeled examples.
  2. It identifies "pseudo-negative" examples by selecting unlabeled instances where the classifier's confidence score for a negative sense exceeds a certain threshold (τ).
  3. It then uses a semi-supervised learning method (EM algorithm) with these pseudo-negatives and the existing positive examples to refine the WSD classifier.
  4. Finally, it employs uncertainty sampling to select the single most uncertain example from the remaining unlabeled data for human labeling. This human-labeled example is then added to either the positive or negative training set, and the process repeats.

Datasets

The paper uses several Japanese web search query datasets for evaluation. The specific ambiguous words evaluated are:

  • Wega: (Product name, e.g., TV)
  • Loft: (Store name)
  • Honda: (Personal name, e.g., football player)
  • Tsubaki: (Product name, e.g., shampoo)

These datasets were crawled from Japanese blogs. The authors also mention that 90% of the data was used for training and 10% for testing, with labels being assigned by one person and 48.5% checked by a second person, achieving a high inter-annotator agreement of 99.0%.

Key Insights and Ideas

  • The Power of Pseudo-Negatives: The most significant insight is that generating "pseudo-negative" examples using a classifier's own predictions can effectively substitute for manually labeled negative data, especially in the early stages of training.
  • Bootstrapping Learning: This approach allows WSD systems to start learning from a very limited set of resources (only positive examples) and gradually build up a robust classifier by intelligently leveraging unlabeled data.
  • Reduced Annotation Cost: The proposed method significantly reduces the human effort required for WSD model development, making it more practical for real-world web mining applications where data is abundant but labeling is expensive.
  • Active Learning's Role: Uncertainty sampling is crucial for guiding the active learning process, ensuring that the human annotator's effort is focused on the most informative examples, further optimizing the learning curve.

Key Results

  • The proposed method (with-EM) achieves WSD accuracy comparable to approaches that use manually prepared negative examples.
  • The initial accuracy of the proposed approach (with-EM) is significantly higher than unsupervised clustering methods (b-clustering and m-clustering).
  • The accuracy of the proposed approach gradually increases as more hand-labeled examples are added, eventually converging with the performance of human-labeled approaches.
  • The method demonstrates that semi-supervised learning using unlabeled data is effective in improving WSD performance.
  • The authors show that their approach can reduce the labor cost of assigning correct labels by up to 30% of added points compared to fully supervised methods.

Limitations and Future Work

  • Threshold Dependency: The performance of the pseudo-negative generation is dependent on the threshold value (τ). The authors suggest that future work should investigate how to dynamically adjust this threshold based on the number of hand-labeled examples available during active learning iterations.
  • Generalization: The authors acknowledge that further evaluation is needed to confirm if these results can be generalized beyond the four specific proper noun examples used in their study.
  • Dynamic Threshold Control: A key future direction is to develop a mechanism for controlling the threshold τ dynamically as the active learning process progresses, optimizing the balance between pseudo-negative generation and human labeling.

Summary updated

BibTeX
@inproceedings{imamura2009combination,
  author = {Makoto Imamura and Yasuhiro Takayama and Nobuhiro Kaji and Masashi Toyoda and Masaru Kitsuregawa},
  title = {{A Combination of Active Learning and Semi-supervised Learning Starting with Positive and Unlabeled Examples for Word Sense Disambiguation: An Empirical Study on Japanese Web Search Query}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2009},
}
Figure