Solving Sequential Text Classification as Board-Game Playing

Chen Qian, Fuli Feng, Lijie Wen, Zhenpeng Chen, Li Lin, Yanan Zheng, Tat-Seng Chua

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.

Comparison of successive labeling (top) and jump labeling (bottom) for a cooking recipe instruction.

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:

  1. Representation: A BERT backbone provides initial embeddings, followed by a BiLSTM to capture local contextual information.
  2. Prior Knowledge: A Multi-Layer Perceptron (MLP) generates preliminary label probabilities for each fragment.
  3. 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."
  4. 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

Abstract

Sequential Text Classification (STC) aims to classify a sequence of text fragments (e.g., words in a sentence or sentences in a document) into a sequence of labels. In addition to the intra-fragment text contents, considering the inter-fragment context dependencies is also important for STC. Previous sequence labeling approaches largely generate a sequence of labels in left-to-right reading order. However, the need for context information in making decisions varies across different fragments and is not strictly organized in a left-to-right order. Therefore, it is appealing to label the fragments that need less consideration of context information first before labeling the fragments that need more. In this paper, we propose a novel model that labels a sequence of fragments in jumping order. Specifically, we devise a dedicated board-game to develop a correspondence between solving STC and board-game playing. By defining proper game rules and devising a game state evaluator in which context clues are injected, at each round, each player is effectively pushed to find the optimal move without position restrictions via considering the current game state, which corresponds to producing a label for an unlabeled fragment jumpily with the consideration of the contexts clues. The final game-end state is viewed as the optimal label sequence. Extensive results on three representative datasets show that the proposed approach outperforms the state-of-the-art methods with statistical significance.
BibTeX
@inproceedings{qian2020solving,
  author = {Chen Qian and Fuli Feng and Lijie Wen and Zhenpeng Chen and Li Lin and Yanan Zheng and Tat-Seng Chua},
  title = {{Solving Sequential Text Classification as Board-Game Playing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i05.6388},
}
Figure