A Graph-based Semi-Supervised Learning for Question-Answering

Asli Celikyilmaz, Marcus Thint, Zhiheng HuangACL 2009

Introduction

In the field of open-domain Question-Answering (QA), the final stage of the pipeline involves ranking candidate sentences to identify the most accurate answer. A common approach for this ranking is Textual Entailment (TE), which determines if a candidate sentence logically supports the truth of a given question. However, developing high-performance ranking models typically requires large volumes of manually labeled data, which is both expensive and time-consuming to acquire.

While Semi-Supervised Learning (SSL) offers a potential solution by leveraging unlabeled data, traditional graph-based SSL methods suffer from high computational complexity—often $O(n^2)$ or $O(n^3)$. This makes them impractical for datasets containing hundreds of thousands of unlabeled points. This paper proposes a novel graph-based SSL framework that utilizes linguistic feature engineering and a "graph summarization" technique to achieve state-of-the-art performance with minimal labeled data.

Linguistic Feature Engineering

To effectively represent the relationship between questions and candidate answers, the authors extract several high-level linguistic features:

  • Question-Type Category Features (QTCF): These match the expected answer type (e.g., "HUMAN", "LOCATION") with Named Entities found in the candidate sentence.
  • Question Component Matching (QComp): This involves aligning semantic components such as subjects, objects, and modifiers between the question and the answer.
  • Lexico-Syntactic Alignment (LexSem): Using WordNet, the model identifies synonyms and entailment relations to bridge lexical gaps.
  • Hybrid Structural Modeling: The researchers observed that 98% of "affirmed" questions utilize copula (linking) verbs (e.g., "is", "was"). By building separate models for copula and non-copula sentences, the system better captures the distinct structural nuances of different sentence types.

Graph Summarization for Scalability

The core technical innovation is a graph summarization algorithm designed to handle over 100,000 unlabeled data points. Instead of constructing a graph where every individual data point is a node, the algorithm groups highly similar points into representative vertices.

Visual representation of the graph summarization process, showing the transition from original data (a) to a compressed graph of representative points (d).

To ensure the model does not lose the underlying spatial distribution of the data during this compression, the authors introduce a local density constraint ($\delta$). This constraint acts as a weight for the representative nodes, informing the model of how many original data points each summary node represents. This weight is integrated into the Laplacian matrix, allowing the SSL model to maintain the statistical significance of the original clusters while operating on a much smaller, computationally feasible graph.

Algorithm 1: The formal procedure for generating a graph summary of a large dataset.

Experimental Setup and Datasets

The framework was evaluated using a combination of labeled and unlabeled datasets:

  • Labeled Data: Approximately 7,600 question-answer pairs derived from TREC-99-03 and the Recognizing Textual Entailment (RTE) challenges.
  • Unlabeled Data: A massive pool of ~100,000 document headlines from a newswire corpus. The authors employed a clever heuristic: assuming the first sentence of a news article likely entails its headline, they created a large-scale "pseudo-q/a" dataset.
  • Evaluation: Testing was conducted on 202 questions from TREC-04, comprising 4,037 manually labeled test pairs.

Key Results and Performance

The system was evaluated using Mean Reciprocal Rank (MRR), Top-1, and Top-5 accuracy. The results highlighted several key strengths of the proposed approach:

  1. Efficiency in Low-Data Scenarios: When using only 1% of the available labeled data, the "Hybrid gSum SSL" model achieved an MRR of 59.7%. This significantly outperformed a standard supervised Support Vector Machine (SVM), which achieved only 45.2% under the same conditions.
  2. Effective Scaling: Performance improved consistently as the volume of unlabeled data increased from 25,000 to 100,000 samples, validating the summarization technique's ability to extract meaningful patterns from raw text.
  3. State-of-the-Art Benchmarks: The hybrid SVM/SSL configurations eventually surpassed previous state-of-the-art results on the TREC-04 dataset, reaching MRRs as high as 67.6%.

Conclusion

The proposed graph-based SSL framework demonstrates that graph summarization is a viable path for scaling semi-supervised learning to large-scale NLP tasks. By combining structural linguistic insights with a density-aware graph compression algorithm, the model achieves high accuracy even when human-labeled data is scarce. Future work may involve refining the distance measures between question-answer pairs and exploring more diverse sources for unlabeled data beyond newswire headlines.

Summary updated

BibTeX
@inproceedings{celikyilmaz2009graph,
  author = {Asli Celikyilmaz and Marcus Thint and Zhiheng Huang},
  title = {{A Graph-based Semi-Supervised Learning for Question-Answering}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2009},
}
Figure