Prior methods to text segmentation are mostly at token level. Despite the adequacy, this na-ture limits their full potential to capture the long-term dependencies among segments. In this work, we propose a novel framework that incrementally segments natural language sentences at segment level. For every step in segmentation, it recognizes the leftmost segment of the remaining sequence. Implementations involve LSTM-minus technique to construct the phrase representations and recurrent neural networks (RNN) to model the iterations of determining the leftmost segments. We have conducted extensive experiments on syntactic chunking and Chinese part-of-speech (POS) tagging across 3 datasets, demonstrating that our methods have significantly outperformed previous all baselines and achieved new state-of-the-art results. Moreover, qualitative analysis and the study on segmenting long-length sentences verify its effectiveness in modeling long-term dependencies. Sequence segmentation, as an important task in natural language understanding (NLU), partitions a sentence into multiple segments. The first two rows of Table 1 show a case from a syntactic chunking dataset. The input sentence is a sequence of tokens and the output segments are multiple labeled phrases. These segments are nonoverlapping and fully cover the input sentence. In previous works, there are two dominant approaches to sequence segmentation. The most common is to regard it as a sequence labeling problem with resorting to IOB tagging scheme (Huang et al., 2015; Akbik et al., 2018; Liu et al., 2019). This method is simple yet very effective, providing tons of state-of-the-art performances. For example, Huang et al. (2015) present Bidirectional LSTM-CRF for named entity recognition (NER) and POS tagging, which adopts BiLSTM (Hochre-Sentence Tangible capital will be about $ 115 million . Segments (Tangible capital, NP), (will be, VP), (about $ 115 million, NP), (., O) IOB Tags B-NP I-NP B-VP I-VP B-NP I-NP I-NP I-NP O SHIFT SHIFT REDUCE-NP Transition SHIFT SHIFT REDUCE-VP Actions SHIFT SHIFT SHIFT SHIFTREDUCE-NP OUT Table 1: The first two rows show an example extracted from CoNLL-2000 dataset (Sang and Buchholz, 2000). iter and Schmidhuber, 1997) to read the input sentence and CRF (Lafferty et al., 2001) to decode the label sequence. An alternative method employs a transition-based system to incrementally segment and label an input token sequence (Zhang et al., 2016, 2018). For instance, Zhang et al. (2016) present a transition-based model for Chinese word segmentation that exploits not only character embedding but also token embedding. This type of method enjoys a number of attractive properties, including theoretically lower time complexity and capturing non-local features. The above two approaches are essentially at token level, where a single segment is represented by multiple token-level labels (e.g., transition actions). In spite of the adequacy, the labels used to model the relation among output segments are far more than the segments themselves. As demonstrated in Figure 1, modeling the transition between the two segments, will be" and about $ 115 million", consumes 6 IOB tags or 8 transition actions. This ill-posed design certainly limits the full potential of segmentation models to capture the long-term dependencies among segments. velop segment-level models, which define a joint probability distribution over the partition of an input sentence and the labeling of the segments. Such an approach circumvents using token-level labels. However, we find that, in experiments, it underperforms current token-level models. Moreover, its use of dynamic programming (DP) incurs quadratic running time, which is too slow for both training and inference (see Section 3.7). In this paper, we introduce a novel framework that incrementally segments a sentence at segment level. The segmentation process is iterative and incremental. At each iteration, the proposed framework determines the leftmost segment of the remaining unprocessed sequence. Under this scheme, we don't resort to token-level labels and enjoy linear time complexity. The implementation contains two stages. Firstly, we utilize LSTM-minus (Wang and Chang, 2016; Cross and Huang, 2016) technique to construct the representations for all the phrases. Secondly, we adopt LSTM to model the iterative segmentation process, which captures the strong correlation among segments. At every step, the input consists of the previous segment and the remaining unprocessed sequence, and the output is the leftmost segment. Figure 1 depicts how our framework segments the sentence in Table 1. The output segments are obtained in an iterative and incremental manner. At each iteration, the leftmost segment of the remaining sequence is extracted and labeled. Compared with token-level models, we take much fewer steps to complete the segmentation process. Extensive experiments have been conducted on syntactic chunking and Chinese part-of-speech (POS) tagging across 3 datasets. The proposed framework has obtained new state-of-the-art performances on all of them. Besides, qualitative study and the results on segmenting long-length sentences confirm its effectiveness in capturing long-term dependencies. we present a novel framework that incrementally segments a natural language sentence at segment level. In comparison, previous approaches are mostly at token-level;  we have notably outperformed previous baselines and established new state-of-the-art results on the 3 datasets of syntactic chunking and Chinese POS tagging. Experiments also show that our model is competitive with strong NER baselines;  compared with prior methods, our model well captures the long-term dependencies among segments. This is strongly verified by qualitative study and the experiment on segmenting long-length sentences. We denote a n -length input sentence as x = [ x 1 , x 2 ,    , x n ] , where x i is a token (such as a word or a character). The output segments are represented as y = [ y 1 , y 2 ,    , y m ] , where m is the amount of segments. Every segment y k is denoted as a triple ( i k , j k , l k ) . ( i k , j k ) is the span of the segment, corresponding to the phrase x i k ,j k = [ x i k , x i k +1 ,    , x j k ] . l k is from a prede-fined label space L and specifies the label of the segment. These segments are non-overlapping and fully cover the input sentence. The example in Table 1 is represented as x = [Tangible , capital , will , be , about , $ , 115 , million , . ] y = [(1 , 2 , NP) , (3 , 4 , VP) , (5 , 8 , NP) , (9 , 9 , O)] . Our goal here is to construct the representation for every phrase x i,j . Later, we will use the phrase representation to embed the segment y k  1 and the unprocessed sequence x i k ,n . where E t is a token embedding matrix and  is the column-wise vector concatenation. Following previous works (Ma and Hovy, 2016; Liu et al., 2019), we use CharCNN to extract the character-level representations. Secondly, we utilize bidirectional LSTMs  f e and  f e to compute the context-sensitive representation for each token x k :    h c k =  f e (  h c k  1 , e k )  h c k =  f e (  h c k +1 , e k ) h c k =  h c k   h c k . (2) Inspired by previous works (Wang and Chang, 2016; Gaddy et al., 2018) in syntactic analysis, we integrate LSTM-minus features into phrase representations. Specifically, the representation h p i,j for a phrase x i,j is computed as the concatenation of the difference of LSTM hidden states: h p i,j = h c j  ( h c j  h c i )  h c i . Inside algorithm (Lari and Young, 1990) is another method to extracting phrase representation. Its advantage is to incorporate the potential hierarchical structure of natural language without using treebank annotation. For example, Drozdov et al. (2019) utilize inside algorithm to recursively compute the content representations. Despite the attractive property, its time complexity O ( n 3 ) is too inefficient to practice use. Figure 2 demonstrates how our method iteratively and incrementally segments the sentence in Table 1. LSTM is used as the backbone to model the iterative process. At every step, the input consists of the prior segment and the unprocessed sequence, and the output is the predicted segment. Firstly, we embed the previous segment y k  1 and the unprocessed sequence x i k ,n . h s k  1 = (cid:26) h p i k  1 ,j k  1  E l ( l k  1 ) k > 1 v k = 1 , (4) where E l is a label embedding matrix and v is a trainable vector. The unprocessed sequence is embedded as h p i k ,n . During training, i k is known since the ground truth segments y is reachable. At evaluation time, we set i k = j k  1 + 1 . Then, we separately predict the span and the label of a segment. We define a set S k containing all valid span candidates for prediction: S k = { ( i k , i k ) , ( i k , i k + 1) ,    , ( i k , n ) } . (6) The probability of a span ( i, j )  S k is Q s k,i,j  exp (cid:0) ( h d k ) (cid:62) W s h p i,j (cid:1) . (7) The probability of a label l  L for a span ( i, j ) is Q l k,i,j,l  exp (cid:0) E l ( l ) (cid:62) W l ( h p i,j  h d k ) (cid:1) . (8) The matrices W s and W l are learnable. ( i k ,  j k ) = arg max ( i,j ) S k Q s k,i,j  l k = arg max l L Q l k,i,j,l  y k = ( i k ,  j k ,  l k ) . (9) The iterative process ends when the remaining sequence x j k +1 ,n is empty (i.e., j k = n ). During training, we use teacher forcing where every segment y k is predicted using its previous ground-truth segments [ y 1 , y 2 ,    , y k  1 ] . A hybrid loss is induced as J =  (cid:88) y k  y (log Q s k,i k ,j k + log Q l k,i k ,j k ,l k ) . At test time, every segment  y k is inferred in terms of the previous predicted segments [ y 1 ,  y 2 ,    ,  y k  1 ] . Algorithm 1 demonstrates how our proposed framework makes inference. Note that Algorithm 1 uses greedy search to get  y because it is both fast in speed and effective in accuracy in our experiments, although beam search may be better in accuracy. Extensive experiments have been conducted on syntactic chunking and Chinese POS tagging across 3 datasets. Firstly, our models have obtained new state-of-the-art performances on all the datasets. Then, we have investigated ablation studies to understand the importance of each component. Lastly, case study and the results on segmenting long-length sentences confirm the effectiveness of the proposed framework in capturing the long-term dependencies among segments. Syntactic chunking segments a word sequence into multiple labeled groups of words. We use CoNLL-2000 dataset (Sang and Buchholz, 2000), which defines 11 syntactic chunk types (NP, VP, PP, etc.). Standard data includes a training set and a test set. Following Xin et al. (2018), we randomly sample 1000 sentences from the training set as the development set. Chinese POS tagging converts a Chinese character sequence into a token sequence and associates every word with a POS tag. We use Penn Chinese Treebank 9.0 (CTB9) (Xue et al., 2005) and Universal Dependencies 1.4 (UD1) (Nivre et al., 2016). CTB9 contains the source text in various genres, covering its previous versions (e.g., CTB6). We use the Chinese section of UD1. We follow the same format and partition of the two datasets as Shao et al. (2017). We use the same neural network configuration for all 3 datasets. The dimensions of token embedding and label embedding are respectively set as 300 and 50 . The hidden unit sizes for the encoder and decoder are 256 and 512 , respectively. The layers of two LSTMs are both 2 . L2 regulariza-Approach CoNLL-2000 Segmental RNN (Kong et al., 2015) 95 . tion is set as 1  10  6 and dropout ratio is set as 0 . 4 for reducing overfit. The above setting is obtained by grid search. We adopt Adam (Kingma and Ba, 2014) as the optimization algorithm and adopt the suggested hyper-parameters. For CoNLL-2000 dataset, the cased, 300d Glove (Pennington et al., 2014) is used to initialize token embedding. CharCNN is not used in Chinese tasks. The batch size is set as 16. All our models in experiments are running on NVIDIA Tesla P100. At test time, following previous literature, we convert the prediction of our model into IOB format and use the standard conlleval script 1 to get the F1 score. We select the model that works the best on development set, and then evaluate it on test set. In all the experiments, the improvements of our models over the baselines are statistically significant with p < 0 . 05 under t-test. Our models are compared with two groups of baselines. One of them is trained without any external resources besides the training data: 1 https://www.clips.uantwerpen.be/conll2000/chunking/co nlleval.txt. Segmental RNN It's a segment-level model that defines a joint probability distribution over the partition of an input sequence and the labeling of the segments; Bi-LSTM + CRF It utilizes bidirectional LSTM to read the input sentence and CRF to decode the label sequence; Char-IntNet-5 It is a funnel-shaped CNN model with no down-sampling which learns a better internal structure for tokens; GCDT It deepens the state transition path at each position in a sentence and assigns each token with a global representation learned from the entire sentence. Flair Embedding It firstly pre-trains a character-level language model on a large corpus, and then uses a sequence labeling model (e.g., BiLSTM + CRF) to fine-tune on it; We adopt most of the results of baselines as reported in Huang et al. (2015); Akbik et al. (2018); Xin et al. (2018). Since the evaluation method of GCDT is not standard (see the experiment setup in Luo et al. (2020)), we correct its source code 2 to retest the performance. The result for Segmental RNN is from our re-implementation. Table 2 demonstrates that we have notably outperformed previous methods and achieved new state-of-the-art results on CoNLL-2000 dataset. When not using external resource, we obtain the F1 score of 96 . 13 , which outperforms Segmental RNN by 1 . 10% , Bi-LSTM + CRF by 1 . 77% , Char-IntNet-5 by 0 . 88% , and GCDT by 1 . 01% . Note that Segmental RNN, a segment-level model, underperforms Char-IntNet-5, a token-level model, by 0 . 22% . To make a fair comparison with the baselines using additional unlabeled corpora, we also use BERT (Devlin et al., 2019), a powerful pretrained language model, to replace our token embedding. In this way, we achieve the F1 score of 97 . 05 , which outnumbers Flair Embedding by 0 . 34% , Cross-view Training by 0 . 05% , and GCDT w/ BERT by 0 . 25% . All these results verify the effectiveness of our framework. We categorize the baselines into two types. The methods without using external resources: Segmental RNN Also described in Section 3.2; Bi-RNN + CRF It utilizes bidirectional RNN and CRF to model joint word segmentation and 2 https://github.com/Adaxry/GCDT. Table 3 shows that our models have achieved state-of-the-art results on the two datasets, PTB9 and UD1. When BERT is not used, we have obtained the F1 scores of 92 . 56 and 91 . 65 , which outperform Glyce + Lattice LSTM by 0 . 19% and 0 . 86% and Bi-RNN + CRF (ensemble) by 0 . 24% and 2 . 12% . Note that Segmental RNN, a segment-level model, underperforms Lattice LSTM, a token-level model, by 0 . 09% on UD1. When using BERT, even without incorporating Chinese glyph information, we still obtain the F1 scores of 93 . 38 and 96 . 43 , which outperform Glyce + BERT by 0 . 25% and 0 . 30% . These results further confirm the effectiveness of our proposed framework. As shown in Table 4, we conduct ablation studies to explore the impact of every component. Effect of Representation Learning. Following prior works (Ma and Hovy, 2016; Liu et al., 2019), we employ CharCNN to incorporate character information into word representations. By removing it, the F1 score on CoNLL-2000 decreases by 0 . 33% . Inside algorithm is another technique to construct phrase representations. After using it to replace LSTM-minus, the results on the three datasets are slightly improved by 0 . 23% , 0 . 16% , and 0 . 24% . Our implementation of inside algorithm is the same as described in Drozdov et al. (2019). Despite the slight improvements, its time complexity O ( n 3 ) is too slow for both training and inference. Empirically, we find that the running time of inside algorithm is about 7 times slower than that of LSTM-minus. Effect of Modeling the Dependencies Among Segments. LSTM decoder f d models the long-term dependencies among segments. The prediction of every segment y k is conditional on prior segments y k (cid:48) , 1  k (cid:48) < k . By replacing it with multilayer perceptron (MLP), the performances fall by 1 . 29% , 1 . 40% , and 1 . 78% on the three datasets. We use both phrase representation h pi k  1 ,j k  1 and label representation E l ( l k  1 ) to embed the previous segment y k  1 . After removing the phrase representations, the F1 scores decrease by 0 . 37% , 0 . 51% , and 0 . 42% on the three datasets. By removing the label representations, the results also drop by 0 . 32% , 0 . 70% , and 0 . 67% . tasks, like machine translation (Bahdanau et al., 2014; Vaswani et al., 2017; Li and Yao, 2020b) and data-to-text generation (Shen et al., 2020; Li et al., 2020c; Li and Yao, 2020a). We have attempted to use beam search (with the beam size being 5 ), instead of greedy search, for inference. By doing so, the F1 scores of our models increased by 0 . 09% on CoNLL-2000, 0 . 23% on PTB9, and 0 . 08% on UD1. While obtaining slightly better performances, the time costs for inference become intolerably high (increase about 10 times). Therefore, we adopt greedy search as the default inference algorithm. Compared with token-level methods, our framework better captures the long-term dependencies among segments. Therefore, our model should be more accurate in segmenting long-length sentences. To verify this, we test the baselines and our model on the sentences of different lengths. The study is conducted on CoNLL-2000 dataset. Bi-LSTM + CRF and GCDT are very strong baselines and have open source implementations. We use toolkit NCRFPP 3 to reproduce the performances of Bi-LSTM + CRF. We use the reproduction in Section 3.2 as the results of GCDT. Table 5 shows the experiment results. Each column name denotes the sentence length range and the case number. Our model notably outperforms prior methods in terms of long sentence length ranges. For length range 45-66, our model obtains the F1 score 3 https://github.com/jiesutd/NCRFpp. of 94 . 82 , which outperforms Bi-LSTM + CRF by 1 . 98% and GCDT by 1 . 12% . For length range 67-88, our model outperforms Bi-LSTM + CRF by 4 . 57% and GCDT by 4 . 51% . In Table 6, we present an example extracted from the test set of CoNLL-2000. Given an input sentence, we show the prediction from a strong baseline, GCDT, and our model. The output segments from our model are consistent with the ground truth segments. The segment in bold is the one incorrectly produced by GCDT. Understanding the structure of this sentence is very hard because the main constituents Other antibodies", are", and rarely present" locate far apart. By removing the two middle phrases sparked by the preparation" and of a sort", the original sentence can be simplified to Other antibodies are rarely present in large quantities in infected or ill individuals", which is very clear. Therefore, correctly predicting the segment, (rarely present, ADJP), implies that our model well captures the long-term dependencies among the segments. For GCDT, a token-level segmentation model, it mistakes rarely present" for the verb phrase of a sort". This may result from the following two causes:  The adjacent segments labeled with (NP, VP) frequently appear in training data;  the token present" acting as a verb is much more common than as a adjective. Both potentials indicate that token-level models can't capture the long-term dependencies well. Table 7 demonstrates the running time comparison among different methods. The last two columns are respectively the running times for training (one epoch) and evaluation. We set the batch size as 16 and run all the models on 1 GPU. From the table, we can draw the following two conclusions. Firstly, Segmental RNN, a segment-level model, is very slow for both training and inference due to the high time complexity. For instance, its training and testing are respectively 6 . 26 and 9 . 05 times slower than ours. Secondly, our framework is very efficient. For example, training our model for one epoch is 1 . 33 times faster than training Bi-LSTM + CRF, a token-level model. While our model is tailored for sequence segmentation tasks, we have also tested its performances on two widely used NER datasets, CoNLL-2003 (Sang and De Meulder, 2003) and OntoNotes 5.0 (Prad-han et al., 2013). Note that, in NER, the label correlations among adjacent segments are very weak. This seems bad for our model. Table 8 diagrams the comparison of our model and strong NER baselines. The results of GRN and HCR are copied from Chen et al. (2019); Luo et al. (2020). For BiLSTM-CNN-CRF, its scores on CoNLL-2003 and OntoNotes 5.0 are respectively from Chen et al. (2019) and our re-implementation. From the table, we can see that our model is competitive with prior methods. For example, our model underperforms HCR by only 0 . 27% on OntoNotes 5.0. In particular, our F1 scores are notably higher than those of BiLSTM-CNN-CRF by 0 . 23% and 0 . 79% on the two datasets. This experiment shows that our model is applicable to general sequence labeling tasks. There are two mainstream approaches to sequence segmentation. One of them treat sequence segmentation as a sequence labeling problem by using IOB tagging scheme (Huang et al., 2015; Xin et al., 2018; Clark et al., 2018; Akbik et al., 2018; Liu et al., 2019; Li et al., 2020a). Each token in a sentence is labeled as B-tag if it's the beginning of a segment, I-tag if it is inside but not the first one within the segment, or O otherwise. This method is extensively studied by prior works and provides tons of state-of-the-art results. Xin et al. (2018) introduce a funnel-shaped convolutional architecture that learns a better internal structure for the tokens. Akbik et al. (2018) propose an efficient character-level framework that uses pretrained character embedding. Clark et al. (2018) adopt semi-supervised learning to train LSTM encoder using both labeled and unlabeled corpora. Despite the effectiveness, these models are at token level, relying on multiple token-level labels to represent a single segment. This limits their full potential to capture the long-term dependencies among segments. The other uses transition-based systems as the backbone to incrementally segment and label an input sequence (Qian et al., 2015; Zhang et al., 2016, 2018). For example, Qian et al. (2015) design special transition actions to jointly segment, tag, and normalize a sentence. These models have many advantages, such as theoretically lower time complexity and capturing non-local features. However, they are still token-level models, which predict transition actions to shift a token from the buffer to the stack or assign a label to a span. Recently, there is a surge of interest in developing span-based models, such as Segmental RNN (Sarawagi and Cohen, 2004; Kong et al., 2015) and LUA (Li et al., 2020b). These methods circumvent using token-level labels and directly label the phrases in a sentence. Span-based models also enjoy great popularity in language modeling (Li et al., 2020d), NER (Yu et al., 2020; Li et al., 2021), and constituent parsing (Cross and Huang, 2016; Stern et al., 2017). However, its underperforms current token-level models (see Section 3.2 and Section 3.3) and is very slow in terms of running time (see Section 3.7). In this work, we present a novel framework to sequence segmentation that segments a sentence at segment level. The segmentation process is iterative and incremental. For every step, it determines the leftmost segment of the remaining sequence. Implementations involve LSTM-minus to extract phrase representations and RNN to model the iterations of leftmost segment determination. Extensive experiments have been conducted on syntactic chunking and Chinese POS tagging across 3 datasets. We have achieved new state-of-the-art performances on all of them. Case study and the results on segmenting long-length sentences both verify the effectiveness of our framework in modeling long-term dependencies. This work was done when the first author did internship at Ant Group. We thank anonymous reviewers for their kind and constructive suggestions.
abstain abstain objective abstain abstain objective abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain objective abstain abstain abstain abstain method method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective method abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain other other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain other result result abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain method abstain abstain result abstain abstain abstain result abstain abstain result other abstain abstain abstain abstain result abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain result other other other other other other other other other other other other other other other other other objective abstain abstain abstain abstain objective result other other