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.
Methodology
The proposed framework addresses these issues through two primary components: a lookahead search mechanism and an adaptive similarity network.
1. MCTS for Lookahead Search
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).
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