A New Concept of Deep Reinforcement Learning based Augmented General Sequence Tagging System
Yu Wang Abhishek Patel Hongxia Jin

Studying the Plasticity in Deep Convolutional Neural Networks using Random Pruning

    Deepak Mittal Shweta Bhardwaj Mitesh M. KhapraBalaraman Ravindran 

    Received: date / Accepted: date
===================================================================================


In this paper, a new deep reinforcement learning based augmented general sequence tagging system is proposed. The new system contains two parts: a deep neural network (DNN) based sequence tagging model and a deep reinforcement learning (DRL) based augmented tagger. The augmented tagger helps improve system performance by modeling the data with minority tags. The new system is evaluated on SLU and NLU sequence tagging tasks using ATIS and CoNLL-2003 benchmark datasets, to demonstrate the new system's outstanding performance on general tagging tasks. Evaluated by F1 scores, it shows that the new system outperforms the current state-of-the-art model on ATIS dataset by 1.9 % and that on CoNLL-2003 dataset by 1.4 %.





§ INTRODUCTION


    
    
    
      
This work is licensed under a Creative Commons Attribution 4.0 International License. License details: http://creativecommons.org/licenses/by/4.0/

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

Sequence tagging/labeling is one of the general techniques required for implementing different natural/spoken language understanding (NLU/SLU) tasks, such as: Named-entity recognition (NER), Part-of-speech (POS) Tagging in NLU, or Slot filling in SLU. Though the purpose of the tasks and their sequence labels are different, most of the state-of-the-art results for these tasks are generated using neural network based architectures. For example, Ma et al. demonstrates that their BLSTM-CNN-CRF model <cit.> can achieve state-of-the-art performance for the NER task (without using extra features) on CoNLL-2003 dataset; Liu et al. gives an attention-based bi-directional LSTM model <cit.> for the slot-filling task, which also gives the best performance on the popular ATIS dataset <cit.> for SLU tasks (This result is obtained by intial paper submission, a better result is published later by Yu et al. <cit.>). The details of these related works will be given in next background section. The solution for general sequence tagging tasks (like NER/Slot filling) should mainly contain two properties: the first one is that the model can handle the language sequence in a word/token level manner, i.e., it can read in the sequence word by word and outputs their corresponding labels; the second property is that the model should capture the contextual information/constraints which helps understand the word/token's tags, either as named-entity or simply slot tags. In<cit.>, the authors use a conditional random filed (CRF) to assist their basic bidirectional LSTM model to capture the contextual constraints in NER task. Similarly, Liu et al. uses an attention based mechanism to take advantages of the weighted collective information from the hidden states of all words in an utterance. 

Due to the imbalance of data distribution under different labels, normally the evaluations for different models will be based on their precision and recall, or simply the F1 scores. It can be observed that, though the neural network based models are becoming more and more complicated, it becomes harder to make further improvement on these tagging tasks by using more advanced network structures. The main reasons are from two aspects:

1. Though the tagging models are designed to be more and more complicated, they also becomes more likely to be over-fitting by using more layers, hidden nodes or advance recurrent neural network structures (like bidirectional LSTM). A model's performance may easily reach a bottom-neck by simply tuning hyper-parameters or changing network structures.

2. Considering the fact that the numbers of words/tokens under some wrongly labeled tags may be quite small, it may not give us more improvement if we still use the same group of training data by simply changing the model. Normally a model will focus on finding the pattern of the data under majority tags instead of minority. Sometimes, even a new model can improve the performance on minority tags' classes, at the cost of degrading the model's performance on the majority tags with more training data, which is a common issue resulting from the imbalanced data distribution under different tags <cit.>.

Weighted sampling is one general solution to resolve the imbalanced data issue by giving more weights to minority tags and fewer to the majority ones <cit.>. The technique, however, gives the issue of distorting the original tagging distribution, which may adversely affect model's performance on majority tags. Similar approach, like adaptive synthetic sampling <cit.>,  also suffers from the same problem.

This gives us the dilemma on dealing with imbalanced tagged data (either for slot filling or NER task): On the one hand, it is a non-trivial task to re-organizing/sampling the data under different tags without any distortion of information; on the other hand, the improvement by changing models has an upper bound which is mainly decided by the data pattern itself instead of the model structure. Due to these two reasons, in this paper, a new concept of augmented tagging system based on deep reinforcement learning is proposed to furture improve the performances of sequence labeling tasks without sacrificing their original data distributions. This novel system will use a deep reinforcement learning based compensatory model to capture the wrong labeled tags and learn their correct labels, hence it can improve the whole model system performance without affecting the original correctly labeled tags. Detailed experiments will be further conducted on two sequence labeling tasks in the domain of SLU/NLU, as NER and slot filling, using public datasets.

The paper is organized as following: In section 2, a brief overview of two common NLP/SLU tagging tasks, i.e. NER and Slot filling, are given. Their current state-of-the-art models will also be explained briefly. Section 3 gives a background of deep reinforcement learning (DRL) first, then illustrates our DRL based augmented general tagging system (DAT) in detail. In section 4, two different tagging tasks on different datasets are given, One is a slot filling task performed on the ATIS benchmark dataset. The other is a named-entity recognition (NER) task, tested on the CoNLL-2003 benchmark dataset. Both experiments will compare our new algorithm with their current best-performed models with state-of-the-art results.




§ BACKGROUND

In this section, a brief background overview on the models for two sequence labeling tasks will be given. Their state-of-the-art neural network structures will also be discussed for further comparison purpose.



 §.§ Slot filling in SLU


Slot filling task is one of the fundamental tasks in spoken language understanding. It sequentially labels the words in an utterance using the pre-defined types of attributes or slot tags. The most straight-forward approach for this task is by using a single recurrent neural network (RNN) to generate sequential tags by reading an input sentence word by word. The current state-of-the-art result on ATIS is an attention based bidirectional LSTM model <cit.>. A brief overview about this approach is given for a better illustration of our new algorithm. The model introduced in <cit.> covers both of the intent detection and slot filling tasks. Considering the focus of this paper, we will only discuss the slot filling part of the model. The structure of the attention based BLSTM model for slot filling task is as shown in Figure <ref>. 



As shown in the figure, a contextual vector c_i(·) is defined using the attention of hidden states h_j:

    c_i=∑_j=1^Lα_i,jh_j

where α_i,j is the attention coefficient defined as:

    α_i,j   =e^e_i,j∑_k=1^L e^e_i,k
    
    e_i,k   =ϕ(s_i-1,h_k)

where ϕ(·) is a feed-forward neural network and s_i-1 is the decoder hidden state.

This model consists of tw0 main properties: 

1. It uses the Bi-direction LSTM (BLSTM) structure to capture the long-term dependencies in both directions.

2. The attention vector c_i gives additional contextual information, for which cannot be captured by the hidden states in BLSTM.


The model gives the state-of-the-art slot filling performance on ATIS dataset. In this paper, we will also use this model as a baseline for comparison purpose. Also, this attention based model is chosen as the DNN part of our new system, i.e.f_dnn, to generate the filtered input data to the deep reinforcement learning based augmented tagger (DAT) sub-model of the system.




 §.§ Named-entity recognition in NLU


Another very common NLU sequence labeling task is named-entity recognition (NER), which seeks to locate and classify entities into some pre-defined named labels. In this section, a brief overview about the neural network based NER model as in <cit.> will be given. The model gives the state-of-the-art performance on CoNLL-2003 dataset (without lexicon features). 

The structure contains a convolutional neural network for generating character-level representations, which is used as an input to a bidirectional LSTM network followed by a conditional random field layer. The conditional random field layer is designed to capture the strong dependency across the labels, which can be formulated as:

    s(X,y)   =∑_i=0^nA_y_i,y_i+1+∑_i=0^nP_i,y_i
    
    p(y|X)   =e^s(X,y)∑_ỹ∈ Y_xe^s(X,ỹ)

where s(X,y) is the score defined a predicted labeling sequence y given X. A_y_i,y_j represents transition score from the tag y_i to tag y_j, and P_i,y_i is the probability of the y_i output tag of the i^th input word generated by the bidirectional LSTM. Y_X represents all possible tag sequences for an input sentence X, and p(y|X) is the predicted output y's tagging probability giving an input words sequence X={ x_1, x_2, ⋯, x_n }.

The model shown above gives the state-of-the-art result on the English NER task with an F1 score of 91.2 on CoNLL-2003 dataset (without extra features).

Though decent experimental results are obtained by using deep learning models on the slot filling and NER tagging tasks, the potentials of these models are still limited by the imbalanced data distribution, since most of the tokens don't have any entity names (labeled as 'O'). The model can easily cover the majority tags but not the minority ones. Table <ref> gives a summary of minority tags (each tag has less than 1% of entire data) and majority tags on ATIS and CoNLL-2003 datasets, and their corresponding occurrence ratio among the wrongly labeled data in test dataset.


In Table <ref>, it shows that about 92% of the wrongly labeled data are from minority tags in ATIS dataset and 78% in CoNLL03 dataset. This gives us an indication that, in order to further improve the model performance, the new model needs to figure out how to better label the minority tags and wrongly labeled tags without sacrificing the model performance on majority tags.



§ DEEP REINFORCEMENT LEARNING

In this section, a novel deep reinforcement learning (DRL) based augmented tagging system is proposed to address the issue as described earlier. The system contains two parts: one is the original deep neural network(NN) based tagger (f_dnn) as in section <ref> for slot filling and section <ref> for NER, the second part is a deep reinforcement learning (DRL) based augmented tagger (f_dat), which can be trained to learn the correct tags that are labeled wrongly by the deep learning based tagger, such that it can compensate the weakness of the original single tagger. 



 §.§ Reinforcement Learning and Deep Q Network (DQN)


Reinforcement learning (RL) is a bit different from the supervised learning and unsupervised learning algorithm. Formulated as a markov decision process (MDP) , an RL based model mainly contains several key elements: state (s_t), action (a_t), rewards (r_t) and policy (π). In a given a state of a stochastic environment, an agent is seeking its best action to perform in order to maximize its expected rewards to be obtained, by following some policy. The main target of a RL based model is to seek the best policy, hence the corresponding action, for an agent to perform. There are mainly three types of reinforcement learning algorithms: value-based, policy gradient and actor-critic. In our scenario, due to the necessity to define rewards at each state and small discrete action space, a value-based model design using Q-learning  is proposed for our problem. Its optimal action-value function Q^π, which is also the maximum expected reward obtained by selecting the best policy π, is defined as:










    Q^π(s_t,a_t)=max_π𝔼[R_t | a_t,s_t,π]
 

One well-known issue of applying reinforcement learning in real problems is that, in order to compute this optimal action-value function Q^π, it is necessary to store all of the Q values for each state action pair (s_t,a_t) in a table, which is not very practical if the state or action space is large. This problem is described as “the curse of dimensionality" by Bellman <cit.>. One approach to overcome it is by training a deep neural network based estimator Q(s_t,a_t|θ_t) to estimate Q^π(s_t,a_t) at time t. However, these types of estimators tend to be unstable since the convergence cannot be fully guaranteed. Recently, the deep Q network (DQN) <cit.> demonstrates much better convergence performance on large state space, by taking advantage of a novel training technique called “experience replay”. In this paper, we will use DQN as our selected deep reinforcement learning structure to satisfy the model requirement due to large state space.

In DQN structure, the optimal action-value function Q^π(s_t,a_t) is estimated by a neural network based estimator Q(s_t,a_t|θ_t), i.e.

    Q(s_t,a_t|θ_t)∼ Q^π(s_t,a_t)

where θ_t is the neural network parameter, and the state s_t serves as the input of the network. In next section we will describe how to use the techniques in DQN to build our augmented tagger from a system perspective. Also, the states, actions and rewards of the DRL based tagger are also going to be carefully designed next.



 §.§ DRL based Augmented Tagger (DAT) System

The design of DRL based augmented tagging (DAT) system is as given in Figure <ref> and Figure <ref>. Due to the differences of using augmented tagger in training and inference, we discuss these two parts separately. 





  §.§.§ Training DAT System

In order to train the entire tagging system, one may need to first pre-train a deep NN based tagger f_dnn, this tagger will follow the design as discussed in section <ref> for slot filling task or section <ref> for the NER task. Once f_dnn is fully trained, the output labels of f_dnn using training input x_train are stored as y_predict with a probability distribution P_y_predict=[p_1, p_2,⋯, p_w], where w is the total number of tags in the entire training dataset. Following is the DRL  based design of our new DAT structure:

States (s_t): The DAT model's state s_t is shown in Figure <ref>. The state is defined by each word/token w_i in sentences, it mainly contains two parts: the first part contains the word level information represented by an n-gram (n is odd) averaged vector v_i, and the other part is a given label l_i of w_i. During the generation of training states, l_i uses all possible tags for the word/token w_i. v_i is defined as the average of the vector of word sequences from w_i-(n-1)/2 to w_i+(n-1)/2, where w_j is the center of this sequence:

    v_i=1n∑_j=i-(n-1)/2^j=i+(n-1)/2 w_j

Remarks: The reason to use an n-gram vector v_i to substitute w_i as a word level information in a state is due to that we want to better capture the contextual information compared to that using a single word vector. When n=1, v_i is the same as word vector w_i. Also, the average of fewer words/tokens can be used if the index of word sequences is out of the boundary of an input sentence.


Actions (a_t): The DAT model's action a_t at time step t is defined as in Figure <ref>. The action gives a transition signal such that the state will change from its current label l_i to its next label l_j by keep the same n-gram vector v_i. Simply speaking, the action set A contains all possible labels/tags for the word vector w_i or its correspond n-gram substitute v_i, i.e. A={ l_1, ⋯, l_k}. At each time step t, the action a_t with highest predicted action-reward value is chosen as:

    a_t=_a Q(s_t,a|a ∈ A, θ_t)

Then the state will transit from its current label to the label directed by action a_t.

Rewards (r_t): The reward defined at a state s_t containing an n-gram vector v_i (with a center word/token w_i) will use the one-hot representation o_l^*_i of w_i's true label l^*_i,  the one hot vector o_l_i of the label l_i in current state s_t, and the predicted probability p_i for the word w_i using f_dnn as:


    r_t=tanh(log(||o_l^*_i-p_i||_2||o_l_i-o_l^*_i||_2+ϵ))

where tanh(·) is used to normalize the reward to be within -1 and 1, ||·||_2 is the ℒ_2 norm, and ϵ is a very small value added to avoid zero denominator.

The insight behind our reward design is using the ratio of the distance from f_dnn predicted label to w_i's true label and that from current state's label to its true label. Based on our definition, a higher reward will be assigned to a state in which its label is more closer to the true label compared with the f_dnn's predicted one. The reward function is one of the key factors for further improvement using our new augmented tagger. 

Remarks: It is worth noticing that p_i should be generated by f_dnn using the same word sequence as preparing v_i. Similarly, l^*_i is the true label of w_i in the same sentence of preparing p_i and v_i.

Training:
The training algorithm for DAT is as shown in Algorithm 1. The loss function is defined based on the difference of two estimated expected rewards at state s_t using an unsupervised approach as:

    ℒ_s_t   = (Q̂(s_t,a_t|θ_t)-Q(s_t,a_t|θ_t))^2
       =(r_t+γmax_a_t+1Q(s_t+1,a_t+1|θ_t)-Q(s_t,a_t|θ_t))^2

where Q(s_t,a_t|θ_t) is the predicted expected reward using (s_t,a_t) generated by the neural network-based estimator in DAT directly, and Q̂(s_t,a_t|θ_t) is an estimation of Q(s_t,a_t|θ_t) using the current state reward r_t and its neighbors' estimations Q(s_t+1,a_t+1|θ_t) as in (<ref>).

One training technique we borrowed from <cit.> is the experience replay used in DQN. It improves the convergence issue in neural network-estimator based Q-learning by storing the state s_t visited before, action performed a_t, state's reward r_t and the next state s_t+1 after performing the action a_t in an experience tuple (s_t,r_t, a_t, s_t+1). This tuple is then pushed into the experience replay memory queue M. The size of M is pre-defined based on experiment.

Whenever an action is performed then a new state is arrived, the past experience tuple will be pushed into the replay memory queue M if M is not full, otherwise M will pop out the first tuple and push in the latest one as First-in First-out (FIFO). At each training iteration, a random tuple is selected from M and the loss function value is calculated based on the s_t, r_t, a_t and s_t+1 given by the tuple. 

+




Remarks:
sIt is worth noticing that it is necessary to use reinforcement learning (RL) in our problem, since RL based model can learn the long-term dependency much better than the “conventional” deep learning approach. In our case, since we split a sentence into multiple word level vectors and select them randomly during training, not only we need to consider what the state’s current label is, but also how this state/word level vector is affected by its connected state in the network, such that it won’t have any difficulty to find the correct label from its current wrong label.


  §.§.§ Model Inference

As shown in Figure <ref>, the inference part of the DAT model is a bit different from training the DAT. Since during the training procedure, the entire training dataset (x_train, y_train) is used to train both DNN and DAT models. Comparatively, during inference, only partial of test data with “unsatisfied performance" will be collected and further evaluated by DAT. This is mainly because that we use DAT as an augmented tagger to compensate the minority cases when the original DNN based tagger f_dnn does not perform well. For the majority test data x_predict_dnn, on which f_dnn can perform very well, we still use f_dnn to generate their tags y_predict_dnn . In order to filter those data with “unsatisfied performance", a threshold value T_r is defined. All the tokens with their predicted tags' probabilities below T_r are filtered as the minority cases and further used as the inference input of DAT, i.e. x_dat=x_test ∖ predict_dnn. The outputs of DAT are the actions that will transfer the states from their current labels l_i to the target label l^*_i, which gives the output of minority cases, i.e. y_predict_dat.

Remarks: The choice of T_r will slightly affect the performance of DAT as different percentage of data will be filtered. A general recommended T_r is to use a similar percentage of data under minority tags in training data as shown in section <ref>. For example, we use a T_r to filter around 14%(=6,323/45,030) percent of test data in ATIS for DAT since the training tokens under minority tags in ATIS are roughly around this ratio, as shown in Table <ref>.



§ EXPERIMENT




 §.§ Data Sets

In our experiment, we will evaluate our deep reinforcement learning based augmented tagging system on two sequence labeling tasks: Slot filling task and NER task.

Slot Filling: For Slot filling task, we use the public ATIS dataset which  follows the same format as in <cit.>. The training set contains 4,978 utterances/sequences, and the test dataset contains 893 utterances. There are totally 127 slot tags.

NER: For NER task, we use the public CoNLL-2003 dataset as in <cit.>. The training set contains 14,987 sentences, and the test dataset contains 3,684 sentences. The dataset contains four different types of named entities: PERSON, LOCATION, ORGANIZATION, and MISC. By using the BIO2 tagging scheme, the total number of different labels is 9.  There are a total of 204,567 tokens in training set, and 46,666 tokens in test set.


 §.§ Training Setup


Slot Filling: For slot filling task, the pre-trained DNN model f_dnn has the same set-up as in <cit.>, by using an attention based bi-directional LSTM. The number of states in LSTM cell is 128. The randomly initialized word embedding size is also 128.The batch size is 16 and the dropout rate for non-recurrent connection is 0.5. 

NER: For NER task, the pre-trained DNN model f_dnn follows the BLSTM-CNNS-CRF structure as in <cit.>, which gives the current state-of-the-art result on CoNLL-2003 dataset. The word embedding is chosen as the GloVe 100-dimensional embedding <cit.>. The CNN's window size is chosen as 3 and the number of filters is 30. The number of states in LSTM cell is 200. The batch size is 10 and the dropout rate is 0.5.

The DAT model f_dat used for Slot fill and NER tasks are almost the same except the batch size. The network structure chosen to estimate the action-value function Q is an LSTM structure with 100 states. The averaged word vector in a reinforcement learning state is chosen as a trigram, i.e. n=3. The discount factor γ in (<ref>) is selected as 0.5, 0.7 and 0.9 for difference experiments. The minibatch size is K=16 for slot filling task and K=10 for NER in order to keep the same training batch size as f_dnn in different tasks, and the replay memory size is pre-defined as μ=5,000. The thresholds for both experiment are set as T_r=0.95.



 §.§ Performance on ATIS dataset

Our first experiment is performed on ATIS dataset and compared with other existing approaches, by evaluating their slot filling F1 scores. A detailed comparison is given in Table <ref>.



By using the same DNN based model for f_dnn as in <cit.>, our new model surpassed the previous state-of-the-art result by 0.9%,1.2% and  1.9% for γ= 0.5, 0.7 and 0.9 separately. It is also worth noticing that, a larger discount factor γ gives a better performance as shown in Table. One empirical explanation is that when a larger discount factor is used, the model puts more weights on future states during training, hence it can search the correct label for the current word within a state in a faster manner.


 §.§ Performance on CoNLL-2003 dataset

Our second experiment is conducted on the CoNLL-2003 dataset and compared with current existing neural network-based approaches for the NER tasks. The metric is also using their F1 scores, and the result is as shown in Table <ref> (The results are collected before initial submission, some better results are released during final submission <cit.>, despite our model's performance is still better).

The methods marked using * are using extra features like lexicons and etc. It can be observed that our DAT system's result outperforms the state-of-the-art results in <cit.> (without lexicon features) and <cit.> (lexicon features) by 1% and 1.4%  using γ=0.9 separately. Similar to the SLU task, a larger discount factor γ also boosts our system's performance.



 §.§ Change on Result Distribution

Another observation from our experiment's result is that the tags' distribution of wrongly labeled data changed. Table <ref> gives a summary about these changes on ATIS and CoNLL-2003 two test dataset.



It can be observed that the percentage of wrongly labeled data with minority tags decreases for both ATIS and CoNLL-2003 datasets by adding the DAT model f_dat to the DNN based model f_dnn. It indicates that the DAT model f_dat can help improve the performance of general sequence tagging model by correctly labeling data with  minority tags, which is also the weakness of a single DNN based model f_dnn.



§ CONCLUSION

In this paper, a new DRL based augmented general tagging system is designed. The system use two sequence labeling models: one is a “conventional" DNN based tagger, and the other is a novel DRL based augmented tagger, i.e. DAT. By filtering DNN's output and picking out the “unsatisfied data", DAT can further improve sequence labeling tasks' performance by correctly relabeling the data below the threshold T_r, especially for those under minority tags. The experiment results on two sequence labeling tasks, i.e. Slot fillings and NER in SLU and NLU, both outperform the current state-of-the-art models. Besides the decent experimental performance obtained, more importantly, the new augmented approach can be generalized to more general sequence labeling models without changing their original model setups. 


acl





































