  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.
