Learning to Bootstrap for Entity Set Expansion

Lingyong Yan, Xianpei Han, Le Sun, Ben He

Abstract

Entity Set Expansion (ESE) is a critical task in information extraction that aims to expand a small set of seed entities into a comprehensive collection of members belonging to the same semantic category. Traditional bootstrapping methods often suffer from "semantic drift," where the inclusion of noisy patterns leads the expansion process into incorrect categories over time. This paper introduces a novel framework that treats bootstrapping as a search problem, utilizing Monte Carlo Tree Search (MCTS) to perform multi-step lookahead. This allows the system to evaluate the long-term "delayed feedback" of patterns rather than relying solely on immediate results. Furthermore, a Pattern Mover Similarity Network (PMSN) is proposed to provide robust entity scoring by representing entities as distributions over context patterns. Experimental results on large-scale corpora demonstrate that this approach significantly outperforms existing state-of-the-art methods.

Introduction

Entity Set Expansion (ESE) involves taking a few "seed" entities (e.g., London, Paris, Beijing) and iteratively identifying more members of that category (e.g., Moscow, Tokyo). The standard approach is a bootstrapping cycle: use seeds to find patterns, use those patterns to extract new entities, and then add those entities back into the seed set for the next iteration.

The Challenge of Semantic Drift

Despite its popularity, bootstrapping faces the significant hurdle of semantic drift. A pattern might appear highly relevant in the short term but lead the system into a "noisy" neighborhood of the corpus in subsequent steps. For instance, a general pattern like "* is a big city" might initially extract valid capital cities but eventually pull in unrelated entities like companies or months, causing the expanded set to lose its categorical integrity.

Illustrations of semantic drift where short-term valid patterns lead to incorrect category expansion over multiple iterations.

Methodology

The proposed framework addresses these issues through two primary components: a lookahead search mechanism and an adaptive similarity network.

Instead of greedily selecting the best-performing pattern at each step, the system employs Monte Carlo Tree Search (MCTS). Much like AI systems designed for complex games, the model "simulates" several expansion steps into the future to observe where a specific pattern leads.

  • Selection & Expansion: A prior policy prunes low-quality patterns while exploring promising branches.
  • Evaluation & Backup: The system calculates a reward based on the quality and quantity of entities discovered at the end of a simulation. This reward is back-propagated to update the value of the initial pattern, allowing the system to prioritize patterns with high delayed feedback (long-term utility).
The proposed framework integrates MCTS into the traditional bootstrapping cycle to evaluate patterns based on future simulations.

2. Pattern Mover Similarity Network (PMSN)

To overcome the problem of sparse supervision, the authors developed the PMSN. This network represents entities as distributions over the patterns in which they appear. Inspired by the "Word Mover’s Distance," the Pattern Mover Similarity metric measures the similarity between entities by calculating the minimum cost to transform one pattern distribution into another. This adaptive representation allows for a more precise similarity measure tailored to the specific expansion task compared to static embeddings.

Experimental Results

The model was evaluated on three public datasets: Google Web 1T, APR (news sentences), and Wiki (Wikipedia subset).

  • Performance: On Google Web 1T, the full model achieved a 45% improvement in Mean Average Precision (MAP) compared to basic bootstrapping. It also outperformed competitive methods like COB and the state-of-the-art SetExpan on smaller datasets.
  • Ablation Study: Removing the MCTS component resulted in a 19% drop in P@100, confirming that lookahead search is vital for preventing semantic drift.

Conclusion

By framing bootstrapping as a search problem, this work provides a robust solution to the long-standing issue of semantic drift in Entity Set Expansion. The combination of MCTS-based lookahead and the Pattern Mover Similarity Network allows the system to navigate the corpus more strategically, ensuring that the expanded entity sets remain accurate over many iterations. Future work may extend this framework to other iterative tasks like relation extraction.

Summary updated

BibTeX
@inproceedings{yan2019learning,
  author = {Lingyong Yan and Xianpei Han and Le Sun and Ben He},
  title = {{Learning to Bootstrap for Entity Set Expansion}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  doi = {10.18653/v1/d19-1028},
}
Figure