A Tree Search Algorithm for Sequence Labeling

Yadi Lao, Jun Xu, Yanyan Lan, Jiafeng Guo, Sheng Gao, Xueqi Cheng

Abstract

In this paper, we propose a novel reinforcement learning-based model for sequence tagging, referred to as MM-Tag. Inspired by the success and methodology of AlphaGo Zero, MM-Tag formalizes the problem of sequence tagging with a Monte Carlo tree search (MCTS) enhanced Markov decision process (MDP) model. In this framework, time steps correspond to the positions of words in a sentence from left to right, and each action corresponds to assigning a tag to a word. Two long short-term memory networks (LSTM) are used to summarize the past tag assignments and words in the sentence. Based on the outputs of LSTMs, the policy for guiding the tag assignment and the value for predicting the whole tagging accuracy of the whole sentence are produced. The policy and value are then strengthened with MCTS, which takes the produced raw policy and value as inputs, simulates and evaluates the possible tag assignments at the subsequent positions, and outputs a better search policy for assigning tags. Experimental results on a chunking benchmark show that MM-Tag outperformed the state-of-the-art sequence tagging baselines including CRF and CRF with LSTM.

Introduction

Sequence labeling tasks, such as Part-of-Speech (POS) tagging and Named Entity Recognition (NER), are fundamental to natural language processing. Traditionally, these tasks are approached using statistical models like Conditional Random Fields (CRFs) or deep learning architectures like BiLSTMs. However, these methods often struggle with balancing local decisions and global sequence optimization. Greedy models lack a "vision" of how current choices impact future labels, while CRFs, though globally optimized via Viterbi decoding, can be limited by feature engineering or label bias in small-data regimes.

This paper introduces MM-Tag, a model that treats sequence tagging as a strategic game of search and decision-making. By borrowing the lookahead mechanism from AlphaGo Zero, MM-Tag aims to bridge the gap between local decision-making and global optimization.

Methodology: The MM-Tag Model

The core innovation of MM-Tag is the formalization of sequence tagging as a Markov Decision Process (MDP) enhanced by Monte Carlo Tree Search (MCTS).

MDP Framework and Dual LSTMs

The tagging process is modeled as a sequence of states and actions. A state represents the words processed up to time $t$ and the tags assigned to them. To capture this context, the model employs two separate LSTMs:

  • $LSTM_X$: Summarizes the input word sequence.
  • $LSTM_Y$: Summarizes the sequence of tags assigned so far.

Policy and Value Networks

The outputs of these LSTMs feed into two specialized heads:

  • Policy Network: Generates a probability distribution over possible tags.
  • Value Network: Predicts the final accuracy of the entire sequence given the current state, allowing the model to estimate the "worth" of a state immediately without full rollouts.

MCTS Lookahead

The defining feature of MM-Tag is the MCTS integration. Instead of simple greedy selection, the model performs simulations at each step. It explores potential future tagging paths, evaluates them using the value function, and aggregates the results to produce a "strengthened" search policy. This exploratory mechanism allows the model to anticipate future constraints and avoid local optima.

Experimental Evaluation

The authors evaluated MM-Tag on the CoNLL 2000 chunking dataset. Due to the high computational cost of MCTS simulations, the experiments were conducted on a subset of 1,000 short sentences (maximum 13 words), using pre-trained 100-dimensional GloVe embeddings.

Results

MM-Tag demonstrated superior performance across all metrics—Precision, Recall, F1 Score, and Accuracy—compared to traditional and neural baselines.

Performance comparison of MM-Tag against baseline models on the CoNLL 2000 chunking subset.

The results indicate that the exploratory decision-making of MCTS provides a significant advantage. Interestingly, standard neural baselines (LSTM+CRF) underperformed relative to the traditional CRF on this small dataset, while MM-Tag maintained its lead, suggesting that the MCTS search provides a strong inductive bias that helps the model perform well even when data is scarce.

Conclusion

MM-Tag represents the first application of an MCTS-enhanced MDP model to the sequence tagging task. By incorporating a lookahead search, the model achieves higher accuracy than standard Viterbi-based or greedy approaches. While the computational intensity of MCTS currently limits its application to shorter sequences, the success of MM-Tag opens new avenues for applying reinforcement learning and search-based strategies to complex NLP tasks.

Summary updated

Abstract

In this paper we propose a novel reinforcement learning based model for sequence tagging, referred to as MM-Tag. Inspired by the success and methodology of the AlphaGo Zero, MM-Tag formalizes the problem of sequence tagging with a Monte Carlo tree search (MCTS) enhanced Markov decision process (MDP) model, in which the time steps correspond to the positions of words in a sentence from left to right, and each action corresponds to assign a tag to a word. Two long short-term memory networks (LSTM) are used to summarize the past tag assignments and words in the sentence. Based on the outputs of LSTMs, the policy for guiding the tag assignment and the value for predicting the whole tagging accuracy of the whole sentence are produced. The policy and value are then strengthened with MCTS, which takes the produced raw policy and value as inputs, simulates and evaluates the possible tag assignments at the subsequent positions, and outputs a better search policy for assigning tags. A reinforcement learning algorithm is proposed to train the model parameters. Our work is the first to apply the MCTS enhanced MDP model to the sequence tagging task. We show that MM-Tag can accurately predict the tags thanks to the exploratory decision making mechanism introduced by MCTS. Experimental results show based on a chunking benchmark showed that MM-Tag outperformed the state-of-the-art sequence tagging baselines including CRF and CRF with LSTM.
BibTeX
@misc{lao2018tree,
  author = {Yadi Lao and Jun Xu and Yanyan Lan and Jiafeng Guo and Sheng Gao and Xueqi Cheng},
  title = {{A Tree Search Algorithm for Sequence Labeling}},
  year = {2018},
  eprint = {1804.10911},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.10911},
}
Figure