Textual Membership Queries

Jonathan Zarecki, Shaul MarkovitchIJCAI 2020 · DOI

TL;DR

This paper introduces a novel framework for generating "membership queries" (MQs) in the textual domain, allowing machine learning models to actively request labels for synthesized, highly informative examples. This approach addresses the limitations of traditional active learning by enabling query generation directly within the instance space, making them understandable to human labelers and overcoming issues with data scarcity or vast unlabeled pools.

What Problem Does This Paper Address?

Machine learning models thrive on data, but collecting labeled data is often expensive and time-consuming. Active learning (AL) aims to mitigate this by having the learning algorithm intelligently request labels for the most useful instances. The "membership query" (MQ) model is a powerful theoretical framework within AL where the learner can generate any instance and ask for its label. However, this model faces a significant practical hurdle: when learners generate queries in the form of feature vectors (e.g., numerical representations of text), these vectors often don't directly translate back into human-understandable instances (like sentences). This makes it impossible for a human to label them. Furthermore, traditional feature representations can be non-surjective (multiple feature vectors map to the same instance) and non-injective (a single feature vector can map to multiple instances), complicating the generation of meaningful queries. This paper tackles the challenge of making MQ-based active learning practical for the textual domain.

Methods

The core contribution is a framework for synthesizing membership queries directly in the instance space, rather than the feature space. This ensures generated queries are understandable to humans. The framework relies on:

  • Core Set: A small set of initially labeled instances.
  • Modification Operators: Functions that take an instance and modify it to create a new, related instance. These operators are designed to be applied sequentially.
  • Search Space: The instance space is treated as a search space where modification operators are the "actions."
  • Evaluation Function: A heuristic function (e.g., uncertainty sampling) is used to guide the search towards the most informative instances.

Two synthesis algorithms are proposed:

  1. Stochastic Query Synthesis: Randomly applies modification operators to instances from the core set or previously generated instances.
  2. Search-based Query Synthesis: Employs heuristic search algorithms (like greedy best-first or beam search) to actively explore the instance space and find informative queries, guided by an evaluation function.

For the textual domain, the authors define the instance space as all syntactically and semantically legal English sentences. Modification operators are built upon a semantic distance function (specifically, Dependency Word2vec) to replace words with semantically related ones, aiming to create "near-misses" – examples that are only slightly different from existing ones and might cross the classification boundary.

Datasets

The paper evaluates its framework on five publicly available binary sentence classification datasets:

  • CMR: Cornell sentiment polarity dataset.
  • SST: Stanford sentiment treebank (sentence sentiment analysis).
  • KS: Kaggle short sentence sentiment analysis dataset.
  • HS: Hate speech and offensive language classification dataset.
  • SUBJ: Cornell sentence subjective/objective dataset.

The authors also conducted a human evaluation on generated sentences, comparing them to original sentences and those generated by an RNN-LM.

Key Insights and Ideas

  • Instance-Space Queries are Key: The fundamental insight is that for practical MQ-based AL in domains like text, queries must be generated and understood within the instance space itself, not just as abstract feature vectors.
  • Near-Misses are Powerful: The framework's ability to generate "near-misses" (examples that are very similar to existing ones but have a different label) is highlighted as a crucial factor in improving classifier performance, especially for complex decision boundaries.
  • Semantic Neighborhood for Text: Using semantic distance and neighborhood concepts (like Dependency Word2vec) is essential for creating meaningful textual modifications that preserve sentence quality and relevance.
  • Search Outperforms Randomness: The search-based synthesis algorithm, guided by an evaluation function, consistently outperforms the purely stochastic approach, demonstrating the value of actively seeking informative queries.
  • Textual Quality is Achievable: The framework successfully generates syntactically and semantically coherent sentences, a significant challenge in text generation for AL.

Key Results

  • The proposed MQ synthesis framework, particularly the search-based approach (US-BS-MQ), achieved significant accuracy gains across all five tested datasets compared to baseline methods like random sampling (IDEAL-RAND) and WordNet-based augmentation (WNA).
  • The search-based methods (US-HC-MQ and US-BS-MQ) were shown to generate a higher percentage of "switched instances" (near-misses) compared to simpler stochastic methods, reinforcing their effectiveness.
  • In a human evaluation, generated sentences from the US-BS-MQ method were rated as "comprehensible" by 95% of evaluators, comparable to original sentences (96%) and vastly superior to sentences generated by an RNN-LM (21%).
  • The framework's ability to generate a large pool of instances is theoretically unlimited, unlike methods relying on limited synonym sets.

Limitations and Future Work

  • Simulated Oracle: The experiments used a simulated human oracle (a trained classification model) for labeling. While efforts were made to validate this setup, real human labeling might introduce different dynamics.
  • Textual Granularity: The current work focuses on sentence-level classification and modification. The authors plan to extend their approach to larger textual components like noun phrases and verb phrases, which will require developing methods for generating syntactically and semantically well-structured phrases.
  • Multi-Sense Embeddings: The paper notes that switching words multiple times can sometimes harm sentence quality. They suggest using multi-sense embeddings to better handle words with different meanings in different contexts.
  • Data Augmentation: The framework can be adapted for data augmentation by restricting modification operators to synonyms, thus preserving class labels.
  • Enriching Pools: The authors propose using heuristic-guided local search to enrich existing pools of unlabeled instances for pool-based AL methods.

Summary updated

BibTeX
@inproceedings{zarecki2020textual,
  author = {Jonathan Zarecki and Shaul Markovitch},
  title = {{Textual Membership Queries}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/369},
}
Figure