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.
Introduction
Sequence labeling tasks, such as Part-of-Speech (POS) tagging or Named Entity Recognition (NER), are fundamental to Natural Language Processing (NLP). These tasks require assigning a label to every word in a sentence. Traditionally, this is addressed using Conditional Random Fields (CRFs) or Bi-directional Long Short-Term Memory (BiLSTM) networks.
A significant challenge in sequence tagging is that a tag choice for a word early in a sentence can drastically affect the validity of tags later on. While CRFs provide a global view, they often rely on hand-crafted features or struggle with complex, long-range dependencies. Many deep learning models are "greedy" or only look at local context, effectively making decisions without considering how those choices might impact future states. This paper introduces MM-Tag, a reinforcement learning framework that brings the "lookahead" power of game-playing AIs like AlphaGo Zero to sequence labeling.
Methodology
The authors formalize sequence tagging as a Markov Decision Process (MDP) and solve it using a Policy-Value Network strengthened by Monte Carlo Tree Search (MCTS).
Architecture
The model utilizes a Dual-LSTM Architecture to represent the current state. One LSTM summarizes the words processed so far, while the other summarizes the tags assigned so far. Based on these representations, the model produces two outputs:
- Policy ($p$): A probability distribution over possible tags for the current word.
- Value ($V$): A prediction of the final accuracy of the entire sentence based on the current state.
MCTS Lookahead
The primary innovation is the integration of MCTS. Instead of greedily picking the tag with the highest probability from the raw policy, the model runs simulations (lookaheads) to explore various tagging paths. It uses the value function to estimate which paths lead to the highest overall sentence accuracy. These simulations generate a "strengthened" search policy ($\pi$), which is more robust than the initial LSTM output.
Training
The model is trained via Reinforcement Learning. The loss function is designed to force the raw policy to match the MCTS search results and the value function to accurately predict the final tagging success.
Experimental Setup
The model was evaluated on the CoNLL 2000 chunking dataset. Due to the computational expense of MCTS, the authors focused on a "short sentence subset" of 1,000 sentences (900 for training, 100 for testing) with a maximum length of 13 words. Word representations were initialized using pre-trained GloVe 100-dimensional embeddings.
Results
MM-Tag was compared against several strong baselines, including standard CRFs, LSTM+CRF, and BiLSTM+CRF.
As shown in the results, MM-Tag achieved the highest scores across all metrics, including Precision, Recall, F1 Score, and Accuracy. Interestingly, on this specific small/short-sentence dataset, the standard BiLSTM+CRF underperformed the basic CRF, likely due to insufficient data to train complex neural parameters. However, MM-Tag's search mechanism allowed it to overcome this data scarcity and outperform both.
Discussion and Conclusion
MM-Tag represents a shift from reactive to proactive sequence labeling. By treating a sentence like a game board, the model can evaluate if a currently "likely" tag might lead to an ungrammatical structure later. The value function acts as a global critic, providing a "gut feeling" for whether a partial tagging sequence is on the right track.
While successful, the approach has limitations. MCTS is computationally intensive, making it slower than standard BiLSTM-CRF models, especially for long sentences. Future work will focus on optimizing the search process to handle longer sequences and applying the framework to more complex tasks like NER. This work is a pioneering step in adapting the AlphaGo Zero methodology to the discrete, linear structure of NLP tasks.
Summary updated