Abstract
Sequential Text Classification (STC) is a fundamental task in NLP where the label of a text fragment often depends on its neighbors. Traditional models process text in a fixed left-to-right order, which can neglect important "backward" context clues. We introduce GuGo, a novel framework that treats STC as a board game. By using Monte Carlo Tree Search (MCTS), GuGo performs "jump labeling," identifying the most certain fragments first to provide bidirectional context for harder ones. Experimental results on word, clause, and sentence-level datasets show that GuGo significantly outperforms traditional sequential models.
Introduction
In tasks such as part-of-speech tagging or dialogue act recognition, the context surrounding a fragment is crucial for accurate classification. Most existing models rely on "successive labeling," moving strictly from left to right. This approach is limited by the Markov assumption, where the current state depends only on previous states. However, human understanding often works differently; we might identify a clear "condition" at the end of a sentence to help classify an ambiguous "action" at the beginning.
The challenge in allowing arbitrary labeling orders is the "state space explosion"—the number of possible labeling sequences grows factorially with the number of fragments. GuGo addresses this by framing the problem as a game and using efficient search algorithms to find the optimal path.
Methodology
GuGo maps the STC problem onto a board game where text fragments are board squares and labels are game pieces. "Playing the game" involves placing labels on the board until it is full.
Architecture
The model uses a multi-stage architecture:
- Representation: A BERT backbone provides initial embeddings, followed by a BiLSTM to capture local contextual information.
- Prior Knowledge: A Multi-Layer Perceptron (MLP) generates preliminary label probabilities for each fragment.
- Search Engine (MCTS): To navigate the vast space of labeling orders, GuGo employs Monte Carlo Tree Search. It simulates various labeling "games" to identify sequences that maximize a global "bonus."
- Linguistic Bonus: The evaluation function considers emission features (label-fragment fit) and transition features (label-label fit, including high-order dependencies). Framing classification as a game also allows the model to utilize the Minimax principle to find robust global label sequences.
Optimization
To maintain efficiency, the authors introduced heuristic strategies such as only expanding nodes that have at least one labeled neighbor and using memory-augmented MCTS to avoid redundant calculations.
Experiments and Results
The model was evaluated on three distinct datasets: MAM (Maintenance Manuals, word-level), COR (Cooking Recipes, clause-level), and WeBis (Customer Reviews, sentence-level).
Performance
GuGo consistently outperformed state-of-the-art baselines like BiLCRF and CNNDAC. On the MAM dataset, GuGo achieved a Macro-F1 of 0.764, a significant improvement over CNNDAC's 0.694.
The Power of "Jumping"
A key finding was the comparison between "jump" labeling and "successive" (L2R or R2L) labeling. Models restricted to a fixed direction performed significantly worse, confirming that the flexibility to choose the labeling order is a primary driver of GuGo's performance.
Efficiency
While MCTS is more computationally intensive than a single linear pass, GuGo's speedup strategies reduced runtime by approximately 75%. This makes the model roughly 2-3 times slower than linear models, a manageable trade-off for the significant gains in accuracy.
Conclusion
GuGo demonstrates that treating sequential classification as a non-linear search problem can overcome the limitations of traditional Markovian models. By "jumping" to label easy fragments first, the model builds a richer context for complex classification tasks. Future work will focus on further optimizing computational overhead and applying jump labeling to other sequential domains like video analysis.
Summary updated