Segmenting Natural Language Sentences via Lexical Unit Analysis
Authors: Yangming Li
lemao liu
Shuming Shi
Venue:  (2021)
Keywords: Neural Sequence Labeling
Neural Sequence Segmentation
Dynamic Programming

Abstract: In this work, we present Lexical Unit Analysis (LUA), a framework for general sequence segmentation tasks. Given a natural language sentence, LUA scores all the valid segmentation candidates and utilizes dynamic programming (DP) to extract the maximum scoring one. LUA enjoys a number of appealing properties such as inherently guaranteeing the predicted segmentation to be valid and facilitating globally optimal training and inference. Besides, the practical time complexity of LUA can be reduced to linear time, which is very efficient. We have conducted extensive experiments on 5 tasks, including syntactic chunking, named entity recognition (NER), slot filling, Chinese word segmentation, and Chinese part-of-speech (POS) tagging, across 15 datasets. Our models have achieved the state-of-the-art performances on 13 of them. The results also show that the F1 score of identifying long-length segments is notably improved.

Under review as a conference paper at ICLR 2021
SEGMENTING NATURAL LANGUAGE SENTENCES VIA LEXICAL UNIT ANALYSIS
Anonymous authors Paper under double-blind review
ABSTRACT
In this work, we present Lexical Unit Analysis (LUA), framework for general sequence segmentation tasks. Given a natural language sentence, LUA scores all the valid segmentation candidates and utilizes dynamic programming (DP) ex- tract the maximum scoring one. LUA enjoys a number of appealing properties such as inherently guaranteeing the predicted segmentation to be valid and facil- itating globally optimal training and inference. Besides, the practical time com- plexity of LUA can be reduced to linear time, which is very efficient. We have conducted extensive experiments on 5 tasks, including syntactic chunking, named entity recognition (NER), slot filling, Chinese word segmentation, and Chinese part-of-speech (POS) tagging. across 15 datasets. Our models have achieved the performances on 13 of them. The results also show that the Fl score of identifying long-length segments is notably improved.
INTRODUCTION
Sequence segmentation is essentially the process of partitioning sequence of fine- fine-grained lexical units into a sequence of coarse-grained ones. In some scenarios, each composed unit is assigned categorical label. For example, Chinese word segmentation splits a character sequence into a word sequence (Xue, 2003). Syntactic chunking segments word sequence into a sequence of labeled groups of words (i.e., constituents) (Sang Buchholz, 2000).
There are currently two mainstream approaches to sequence segmentation. The most common is to regard it as a sequence labeling problem by using IOB tagging scheme (Mesnil et al., 2014; Ma & Hovy, 2016; Liu et al., 2019b; Chen et al., 2019 Luo et al., 2020). A representative work is Bidirectional LSTM-CRE (Huang et al., 2015), which adopts LSTM (Hochreiter & Schmidhuber, 1997) to read an input sentence and CRF (Lafferty et al., 2001) to decode the label sequence. This type of method is very effective, providing tons of state-of-the-ar performances. However, it is vulnerable producing invalid labels, for instance, "O, I-tag, I-tag". This problem is very severe in low resource settings (Peng et al., 2017). In experiments (see section 4.6), we also find that it performs poorly in recognizing long-length segments.
Recently, there is a growing interest in span-based models (Zhai et al., 2017: Li et al., 2019; Yu al., 2020). They treat span rather than a token the basic unit for labeling. Li et al. (2019) cast named entity recognition (NER) to a machine reading comprehension (MRC) task, where entities extracted retrieving answer spans. Yu al. (2020) rank all the spans in terms of the scores predicted by a bi-affine model (Dozat & Manning, 2016). In NER, span-based models have signif- icantly outperformed their sequence labeling based counterparts. While these methods circumvent the use of 1OB tagging scheme, they still rely on post-processing rules to guarantee the extracted span set to be valid. Moreover, since span-based models are locally normalized at span level, they potentially suffer from the label bias problem (Lafferty et al., 2001).
This paper seeks to provide a new framework which infers the segmentation of a unit sequence by directly selecting from all valid segmentation candidates, instead of manipulating tokens or spans. To this end, we propose Lexical Unit Analysis (LUA) in this paper. LUA assigns a score to every valid segmentation candidate and leverages dynamic programming (DP) (Bellman, 1966) to search for the maximum scoring one. The score a segmentation is computed by using the scores of its all segments. Besides, adopt neural networks to score every segment of the input sentence.

---

Under review as a conference paper at ICLR 2021
[Worldjo (Cuplo (standingsjo
[World Cupjusee [standings]o
(World Cuplans: (standings]o
Discard
Rules
Direct Out
B-MISC I-MISC
World Cup
MISC PER
(World Cuplunsc /standings|o
J-MISC
I-MISC
Cup Standings
MISC D... PER
[Worldjo (Cup standings|toc
B-PER IPPER
B-PER I-PER
B-PER [-PER
Cup
MISC O.SCO...
PER
[World Capjeex (stundings]o
Cup
Standings
Stundings
[Word]jo (Cup)anse (standingsjo
Sequence Labeling based Models
Span- based Models
Lexical Unit Analysis (LUA)
World
Cup
Standings
World
Cup
Standings
World
Cup
Standings
Figure 1: A toy example to show LUA and how it differs from prior methods. The items in blue and red respectively denote valid and invalid predictions.
The purpose of using DP is solve the intractability of extracting the maximum scoring segmen- tation candidate by brute-force search. The time complexity of LUA is quadratic time, yet it can be optimized to linear time in practice by performing parallel matrix computations. For training criterion, we incur a hinge loss between the ground truth and the predictions. We also extend LUA unlabeled segmentation and capturing label correlations.
Figure illustrates the comparison between previous methods and the proposed LUA. Prior mod- els at token level and span level vulnerable to generating invalid predictions, and hence rely heuristic rules to fix them. For example, in the middle part of Figure I, the spans of two inferred named entities, [Word Cup]MIsc and [Cup] conflicts, which is mitigated by comparing the predicted scores. LUA scores all possible segmentation candidates and uses DP to extract the max- imum scoring one. In this way, our models guarantee the predictions be valid. Moreover, the globality of DP addresses the label bias problem.
Extensive experiments are conducted on syntactic chunking, NER, slot filling, Chinese word seg- mentation, and Chinese part-of-speede (POS) tagging across 15 tasks. We have obtained new state- of-the-are results on 13 of them and performed competitively on the others. In particular, we observe that LUA is expert at identifying long-length segments.
2 METHODOLOGY
We denote an input sequence (i.e., fine-grained lexical units) as = 22, ,,,,, the sequence length. An output sequence (i.c., coarse-grained lexical units) represented as the segmentation = [y1, y/2.... ... 3mml with each segment yı being triple (ig. tx). m denotes its length. (ik specifies a span that corresponds to the phrase X.,.j. = [xi,, +i ,zj.). tx is label from the label space L. We define valid segmentation candidate its segments non-overlapping and fully cover the input sequence.
Un]. where is
A case extracted from CoNLL-2003 dataset (Sang & De Meulder, 2003):
[SOSS], Sangthai, Glory, 22/11/90 3000, Singapore] y [1, 1, O), (2, 3, MISC), (4, 4, O), (5, 5, 0). (6, 6, LOC)
Start-of-sentence symbol [SOS] is added in the pre-processing stage.
2.1 MODEL: SCORING SEGMENTATION CANDIDATES
We denote Y' as the universal that contains all valid segmentation candidates. Given one of its members y E 3/ we compute the score f(y) as
f(y) = Σ
f + thas))
(1)
(KJ,))Ey
2

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Inference via Dynamic Programming (DP)
Input: Composition score $ and label score $',, r for every possible segment (i, t).
Output: The maximum segmentation scoring candidate y and its score f Set two n x n shaped matrices, cf and bt, for computing maximum scoring labels. Set two n-length vectors, and b for computing maximum scoring segmentation.
for 1 - S S n do
Compute the maximum label score for each span (i,j): st. maxtec $1
Record the backtracking index: bi = arg max c $.,.1"
Initialize the value of the base case X1,1 91 si + sf,1.
for i E 2, ... .n]] do
Compute the value of the prefix 1 = gi = max اانs- (gi-j + (08-s+1s of sf-++1,)))
Record the backtracking index: bg arg max (9i-) (06 + s(-++1,))).
Get the maximum scoring candidate y by back tracing the tables bs and bc. 11 Get the maximum segmentation score: f(ş) = 9n-
where of is the composition score to estimate the feasibility of merging several fine-grained units [x,, F441.-.. ,3] into a coarse-grained unit and sf.j. is the label score to measure how likely the label of this segment is Both scores are obtained by a scoring model.
Scoring Model. scoring model scores all possible segments (i, for an input sentence x. Firstly, we get the representation for each fine- fine-grained unit. Following prior works (Li et al., 2019; Luo et al., 2020; Yu et al.. 2020), we adopt BERT (Devlin et al., 2018), powerful pre-trained language model, as the sentence encoder. Specifically, we have
[h hy b BERT(x),
Then, compute the representation for grasied unit Xi.j SiSs $ <nn
hr h hy @ (h," hy") @ (hā" @ hi"),
where vector concatenation and is element-wise product. Eventually, we employ two non-linear feedforward networks to score a segment (i,j,t):
$ (vo)² tanh Wh ", = (v!) tanh tanh(W'hP W'
(4)
where ve, We, v f. and W are all learnable parameters. Besides, the scoring model used here can flexibly replaced by any regression method.
2.2 INFERENCE VIA DYNAMIC PROGRAMMING
The prediction the maximum scoring segmentation candidate can be formulated as
y = arg max f(y).
(5)
yEy
Because the size of search space [)] increases exponentially with respect to the sequence length n, brute-force search to solve Equation 5 is computationally infeasible. LUA uses DP to address this issue, which is facilitated by the decomposable nature of Equation 1.
DP is a well-known optimization method which solves complicated problem by breaking it down into simpler sub-prot aab-problems in a recursive manner. The relation between the value of the larger prob- lem and the values of its sub-problems is called the Bellman equation.
Sub-problem. In the context of LUA, the sub- problem of segmenting input unit sequence is segmenting its prefixes x1,;, < i < n. We define 9; as the maximum segmentation score of the prefix X1.i- Under this scheme, we have maxyey f(y) In-
3

---

Under review as a conference paper at ICLR 2021
The Bellman Equation. ing its prefixes 21,1-5, S 3 S is built by the last segments (a (1-33 + 1, t)::
The relatinship between segmenting sequence X1, and segment-
(gi-) + (8f + max s(-j+1,;e)) Ji = max ss
(6)
TEC
In practice, to reduce the time complexity of above equation, the last term is computed beforehand as o = maxteL j, i Sisj n. Hence, Equation is reformulated as
max (9:-j + (55-j+1, + s st-++1,)) 15/5i-
91
The base case is the first token X1.1
[SOS]]. We get its score 91 as si + $
Algorithm shows how DP applied in inference. Firstly, we store the solutions to the sub-problems (1-st to 2-nd lines). Secondly, we get the maximum label scores for all the spans (3-rd 5-th lines). Then, we initialize the trivial case 91 and recursively calculate the values for prefixes X1,1 i > (6-th to 9-th lines). Finally, we get the predicted seg- mentation y and its score f()) (10-th to 11-th lines).
matrices and vectors to
The time complexity of Algorithm 1 is (n?²). By performing the max operation of Equation in parallel on GPU, can be optimized to only O(n), which highly efficient. Besides, DP, as the backbone of the proposed model, is non non-parametric. The trainable parameters only exist in the scoring model part. These show LUA very light-weight algorithm.
2.3 TRAINING CRITERION
We adopt max-margin penalty the loss function for training. Given the predicted segmentation and the ground truth segmentation y", we have
J max (0, - ffy"(((())))))))>()) f()).
(8)
EXTENSIONS OF LUA
We propose two extensions of LUA for generalizing it to different scenarios.
Unlabeled Segmentation. In some tasks (e.g.. Chinese word segmentation), the segments are unlabeled. Under this scheme, the Equation and Equation are reformulated
f(y) = Σ bijo
max (gi-s + s(,4).)). 1575i-1
gt
(iJ)ey
Capturing Label Correlations. In some tasks (e.g., syntactic chunking), the labels of segments strongly correlated. To incorporate this information, we redefine f(y)
f(y)
Σ (Sirss + sl
Σ
Te-gt de
(10)
Isksm
Score s4 S12-441.f 4 +42."" models the label dependencies among successive segments, yk-g+1,k: In practice, we find 9 = balances the efficiency and the effectiveness well, and thus parameterize a learnable matrix Wi E IR [R] to implement it.
The corresponding Bellman equation to above scoring function is
I1,t =
max (max(gi-5,) + sy.) + (5 + s1-5415,)) 15/5-1 PEC
(11)
where Ir,t is the maximum score of labeling the last segment of the prefix X1,8 with t. For initial- ization, the value of 9¹,o 0 and the others -o0. By performing the inner loops of two max operations in parallel, the practical time complexity for computing Ji,,, 1 < S n, t E L is also (n)) Ultimately, the segmentation score fÿ) is obtained by maX In.1-
This extension further improves the results on syntactic chunking and Chinese POS tagging, as both tasks have rich sequential features among the labels of segments.
4

---

Under review as a conference paper at ICLR 2021
Model
AS
MSR
CITYU
PKU
CTB6
Rich Pretraining (Yang et al., 2017)
95.7
97.5
96.9
96.3
96.2
Bi-LSTM (Ma et al.. 2018)
96.2
98.1
97.2
96,1
96.7
Multi-Criteria Learning + BERT (Huang et al., 2019)
96.6
97.9
97.6
96.6
97.6
BERT (Meng al., 20T9)
96.5
98.1
97.6
96.5
Glyce + BERT (Meng et al., 2019)
96.7
98.3
97.9
96.7
Unlabeled LUA
96.94
98.27
98.21
96.88
98.13
Table 1: Experiment results on Chinese word segmentation.
Model
CTB5
CTB6
CTB9
UD1
Bi-RNN CRF (Single) (Shao ct al., 2017)
94.07
90.81
91.89
89.41
Bi-RNN CRF (Ensemble) (Shao et al., 2017)
94.38
92.34
89.75
Lattice-LSTM (Meng al., 2019)
95.14"
91.43
92.13
90.09
Glyce + Lattice-LSTM (Meng al., 2019)
95.61
91.92
92.38
90.87
BERT (Meng ct al., 2019)
96.06
94.77
92.29
94.79
Glyce BERT (Meng ct al., 2019)
96.61
95.41
93.15
96. 14
LUA
96.79
95.39
93.22
96.01
This Work
LUA Label Correlations
97.96
96.63
93.95
97.08
Table 2: Experiment results the four datasets of Chinese POS tagging.
4 EXPERIMENTS
We have conducted extensive studies on 5 tasks, including Chinese word segmentation, Chinese POS tagging, syntactic chunking. NER, and slot filling, across 15 datasets. Firstly, Our models have achieved new state-of-the-arr performances on 13 of them. Secondly, the results demonstrate that the FI score of identifying long-length segments has been notably improved. Lastly, show that LUA is very efficient algorithm concerning the running time.
4.1 SETTINGS
We use the same configurations for all 15 datasets. L2 regularization and dropout ratio are respec- tively set as 1 x 10-6 and 0.2 for reducing overfit. We use Adam (Kingma & Ba, 2014) to optimize our model. Following prior works, BERT BASE is adopted the sentence encoder. We use uncased BERTBAST for slot filling, Chinese BERTBASE for Chinese tasks (e.g., Chinese POS tagging), and cased BERTRASE for others (e.g.. syntactic chunking). In addition, the improvements of our model over baselines are statistically significant with p < 0.05 under t-test.
4.2 CIINESE WORD SEGMENTATION
Chinese word segmentation splits a Chinese character sequence into a sequence of Chinese words. We use SIGHAN 2005 bake-off (Emerson, 2005) and Chinese Treebank 6.0 (CTB6) (Xue et al., 2005). SIGHAN 2005 back-off consists lowing Ma al. (2018), we randomly select 10% training data development set. We convert all digits, punctuation, and Latin letters to half-width for handling full/half-widte mismatch between training and test set. We also convert AS and CITYU to simplified Chinese. For CTB6, we follow the same format and partition as in Yang et al. (2017); Ma et al. (2018).
datasets, namely AS, MSR, CITYU, and PKU. Fol-
Table depicts the experiment results. All the results of baselines are from Yang et al. (2017); Ma et al. (2018); Huang et al. (2019); Meng et al. (2019). We have achieved new state-of-the-ar performance on all datasets except MSR. Our model improves the Fl score by 0.25% on AS, 0.32% on CITYU, 0. 1.99 on PKU, and 0.54% on CTB6. Note that our model doesn't use any external resources, such as glyph information (Meng et al., 2019) or POS tags (Yang et al., 2017). Despite this, our model is still competitive with Glyce + BERT on MSR.
4.3 CHINESE POS TAGGING
Chinese POS tagging jointly segments a Chinese character sequence and assigns a POS tag to each segmented unit. We use Chinese Treebank 5.0 (CTB5), CTB6, Chinese Treebank 9.0 (CTB9) (Xue
5

---

Under review as a conference paper at ICLR 2021
Chunking
NER
Model
CoNIII22000
CoNLI,-20003
OntoNotes 5.0
Bi-LSTM + CRF (Huang et al., 2015)
94,46
90.10
Flair Embeddings (Akbik al., 2018)
96.72
93.09
89.3
GCDT w/ BERT (Liu al., 2019b)
96.81
93.23
BERT-MRC (Li ot al., 2019)
93.04
91.11
HCR w/ BERT (Luo et al., 2020)
93.37
90.30
BERT-Biaffing Model (Yu et al., 2020)
93.5
91.3
LUA
96.95 97.23
93.46
92.09
This Work
LUA w/ Label Correlations
Table Experiment results on syntactie chunking and NER.
et al., 2005), and the Chinese section of Universal Dependencies 1.4 (UD1) (Nivre et al., 2016)- CTBS is comprised of newswire data. CTB9 consists of source texts in various genres, which cover CTB5, we convert the texts in UDI from traditional Chinese into simplified Chinese. We follow the same train/dev/test split for above datasets as in Shao et al. (2017).
Table 2 shows the experiment results. The performances of all baselines are reported from Meng al. (2019). Our model LUA w/ Label Correlations has yielded new stateoof-the-a results on all the datasets: it improves the F1 scores by 1.35% on CTB5, 1.22% on CTB6, 0.8% on CTB9, and 0.94% on UD1. Moreover, the basic LUA without capturing the label correlations also outperforms the strongest baseline. Glyce BERT, by 0.18% CTB5 and 0.07% on CTB9, All these facts further verify the effectiveness of LUA and its extension.
4.4 SYNTACTIC CHUNKING AND NER
Syntactic chunking aims to find phrases related to syntatic category for a sentence. We use CoNLL- 2000 dataset (Sang& & Buchholz, 2000), which defines 11 syntactic chunk types (NP, VP, PP, etc.) and follow the standard splittings of training and test datasets as previous work. NER locates the named entities mentioned in unstructured text and meanwhile classifies them into predefined categories. We use CoNLL-2003 dataset (Sang & De Meulder, 2003) and OntoNotes 5.0 dataset (Pradhan et al., 2013). CoNLL-2003 dataset consists of 22137 sentences totally and is split into 14987, 3466, and 3684 sentences for the training set, development set, and test set, respectively. is tagged with four linguistic entity types (PER, IOO,, ORG, MISC). OntoNotes 5.0 dataset contains 76714 sentences from a wide variety of sources (e.g., magazine and newswire). It includes 18 types of named entity, which consists of 1l types (Person, Organization, etc.) and 7 values (Date, Percent, etc.). We follow the same format and partition as in Li et al. (2019); Luo et al. (2020); Yu et al. (2020). In order to fairly compare with previous reported results, we convert the predicted segments into IOB format and utilize conlleval script! to compute the Fl score at test time.
Table shows the results. Most of baselines are directly taken from Akbik et al. (2018); et al. (2019); Luo et al. (2020); Yu et al. (2020). Besides, following Luo et al. (2020), we rerun the source code2 of GCDT and report its result on CONILL-2000 with standard evaluation method. Generally, proposed models LUA w/o Label Correlations yield competitive performance over state-of-the- art models on both Chunking and NER tasks. Specifically, regarding to the NER task, on CoNLL- 2003 dataset model LUA outperforms several strong baselines including Flair Embedding, and it is comparable to the state-of of-the--arheee art model (i.e., BERT Biaffine Model). In particular, on OntoNotes dataset, LUA outperforms by 0.79% points and establishes a new state-of-the-are result. Regarding to the Chunking task, LUA advances the best model (GCDT) and the improvements are further enlarged 0.42% points by LUA w/ Label Correlations.
4.5 SLOT FILLING
Slot filling, important task in spoken language understanding (SLU), extracts semantic con- stituents from an utterance. We use ATIS dataset (Hemphill et al., 1990), SNIPS dataset (Coucke al., 2018), and MTOD dataset (Schuster al., 2018). ATIS dataset consists of audio recordings of

---

Under review as a conference paper at ICLR 2021
Model
ATIS
SNIPS
MTOD
SLU (Goo et al., 2018)
95.20
88.30
95.12
Bi-LSTM EMLo (Siddhant et al., 2019)
95.42
93.90
Joint BERT (Chen et al., 2019b)
96.10
97.00
96.48
CM-Net (Liuu al., 2019c)
96.20
97.15
LUA
96.15
97.10
97.53
This Work
LUA w/ Intent Detection
96.27
97.20
97.55
Table 4: Experiment results on the three datasets of slot filling.
Model
(8695)
4- (2380)
8 - 11 (151)
12 24 (31)
Overall
HCR w/ BERT
91.15
85.22
50.43
20.67
90.27
BERT-Biaffine Model
91.67
87.23
70.24
40.55
91.26
LUA
92.31
88.52
77.34
57.27
92.09
Table 5: The F1 scores for NER models on different segment lengths. A - B(N) denotes that there N entities whose span lengths are between A and B.
people making flight reservations. The training set contains 4478 utterances and the test set contains 893 utterances. SNIPS dataset is collected by Snips personal voice assistant. The training set con- tains 13084 utterances and the test set contains 700 utterances. MTOD dataset has three domains, including Alarm, Reminder, and Weather. We use the English part of MTOD dataset, where training set, dev set, and test set respectively contain 30521, 4181, and 8621 utterances. We follow the same partition of above datasets as in Goo al. (2018); Schuster al. (2018).
Table 4 summarizes the experiment results for slot filling. On ATIS and SNIPS, we take the results of all baselines as reported in Liu al. (2019c) for comparison. On MTOD, we rerun the open source toolkits, Slot-gated SLU and Joint BERT*. As all previous approaches jointly model slot filling and intent detection (a classification task SI.U), we follow them to augment LUA with intent detection for fair comparison. As shown in Table 4, the augmented LUA has surpassed all baselines and obtained state-of-the-an results on the three datasets: increases the Fl scores by around 0.05% on ATIS and SNIPS, and delivers a substantial gain of 1. 1.11% on MTOD. It's worth mentioning that LUA even outperforms the strong baseline Joint BERT with a margin 0.18% and 0.21% on ATIS and SNIPS without modeling intent detection.
4.6 LONG-LENGTH SEGMENT IDENTIFICATION
Since LUA doesn't 't resort to IOB tagging scheme, it should be more accurate in recognizing long- length segments than prior methods. To verify this intuition, we evaluate different models on the segments of different lengths. This study is investigated models are adopted as the baselines: one is the best sequence labeling model (i.e., HCR) and the other is the best span-based model (i.e., BERT-Biaffine Model). Both baselines are reproduced by rerunning their open source codes, biaffine-ner and HiRe-NER'.
OntoNotes 5.0 dataset. Two strong
The results are shown in Table 5. On the hand, both LUA and Biaffine Model obtain much higher scores of extracting long-length entities than HCR. For example, LUA outperforms HCR w/ BERT by almost twofold on range 12 24. On the other hand, LUA achieves even better results than BERT-Biaffine Model. For instance, the Fl score improvements of LUA over it are 10.11% on range 8 11 and 41. 13% on range 12 24.
4.7 RUNNING TIME ANALYSIS
Table 6 shows the running time comparison among different models. The middle two columns the time complexity of decoding a label sequence. The last column is the time cost of one epoch in training. We set the batch size as 16 and run all the models on 1 GPU. The results indicate that
htttss///ttlbbboommmooooo/////nt hbanp://gtthuh.co///cyyaaaa/iie

---

Under review as a conference paper at ICLR 2021
Model BERT BERT + CRF LUA LUA w/ Label Correlations
Theoretical Complexity
Practical Complexity Running Time
(n)
0(1)
5m1ls
O O [
O
7m33s
(nn²)
(
6m25s
(n (n2)
O(n)
7m09s
Table 6: Running time comparison on the syntactic chunking dataset.
the success of our models in performances does lead to serious side-effects on efficiency. For example, with the same practical time complexity, BERT + CRF is slower than the proposed LUA by 15.01% and LUA w/ Label Correlations by 5.30%.
RELATED WORK
Sequence segmentation aims to partition fine- dnn-graiied unit sequence into multiple labeled coarse- grained units. Traditionally, there are two types of methods. The most common is to cast it into a sequence labeling task (Mesnil et al., 2014; Ma Hovy, 2016; Chen et al., 2019a) by using IOB tagging scheme. This method is simple and effective, providing a number of state-of-the-art results. Akbik et al. (2018) present Flair Embeddings that pretrain character embedding in a large corpus and directly use it, instead of word representation, encode sentence. Liu et al. (2019b) introduce GCDT that deepens the state transition path at each position in a sentence, and further assigns each word with global representation. Luo et al. (2020) use hierarchical contextualized representations to incorporate both sentence-level and document-level information. Nevertheless, these models are vulnerable to producing invalid labels and perform poorly in identifying long- length segments. This problem is very severe in low-resource setting. Ye & Ling (2018); Liu al. (2019a) adopt Semi-Markov CRF (Sarawagi & Cohen, 2005) that improves CRF at phrase level. However, the computation of CRF loss is costly in practice and the potential to model the label dependencies among segments is limited. An alternative approach that is less studied uses a transition- based system to incrementally segment and label an input sequence (Zhang et al., 2016; Lample al., 2016). For instance, Qian al. (2015) present a cransition-base model for joint word segmentation, POS tagging, and text normalization. Wang et al. (2017) employ transition- based model to disfluency detection task, which helps capture non-local chunk-level features. These models have many advantages like theoretically lower time complexity and labeling the extracted mentions at span level. However, to our best knowledge, no recent transition-baat models surpass their sequence labeling based counterparts.
More recently, there a surge of interests in span-based models. They treat a segment, instead of fine-grained token, as the basic unit for labeling. For example, Li al. (2019) regard NER as a MRC task, where entities are recognized as retrieving answer spans. Since these methods are locally normalized at span level rather than sequence level, they potentially suffer from the label bias problem. Additionally, they rely on rules to ensure the extracted span set to be valid. Span- based methods also emerge in other fields of NLP. In dependency parsing, Wang Chang (2016) propose LSTM-based sentence segment embedding method named LSTM-Minus. Stern et al. (2017) integrate LSSTM-minus feature into constituent parsing models. In coreference resolution, Lee et al. (2018) consider all spans in a document as the potential mentions and learn distributions over all the possible antecedents for each other.
CONCLUSION
This work proposes novel LUA for general sequence segmentation tasks. LUA directly scores all the valid segmentation candidates and uses dynamic programming extract the maximum scoring one. Compared with previous models, LUA naturally guarantees the predicted segmentation to be valid and circumvents the label bias problem. Extensive studies conducted on 5 tasks across 15 datasets. We have achieved the state-of-the- performances on 13 of them. Importantly, the score of identifying long-length segments is significantly improved.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alan Akbik, Duncan Blythe, and Roland Vollgraf. Contextual string embeddings for sequence labeling. In Proceedings of the 27th International Conference on Computational Linguistics, pp- 1638-1649, 2018.
Richard Bellman. Dynamic programming. Science, 153(3731):34-37, 1966.
Hui Chen, Zijia Lin, Guiguang Ding, Jianguang Lou, Yusen Zhang, and Borje Karlsson. Grm:
Gated relation network to enhance convolutional neural network for named entity recognition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 6236-6243, 2019a.
Qian Chen, Zhu Zhuo, and Wen Wang. Bert for joint intent classification and slot filling. arXiv preprint Xix: 10909, 2019b.
Alice Coucke, Alaa Saade, Adrien Ball, Théodore Bluche, Alexandre Caulier, David Leroy. Clément Doumouro, Thibault Gisselbrecht, Francesco Caltagirone, Thibaut Lavril, al. Snips voice plat- form: an embedded spoken language understanding system for private-by-desige voice interfaces. arXiv preprint arXiv: 180. 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 18X0v:/810.0444 2018.
Timothy Dozat and Christopher D Manning. Deep biaffine attention for neural dependency parsing.
arXiv preprint arXiv:1611.0173 2016.
Thomas Emerson. The second international chinese word segmentation bakeoff. In Proceedings of the fourth SIGHAN workshop on Chinese language Processing, 2005.
Chih- Wen Goo, Guang Gao, Yun-Kai Hsu, Chih-Li Huo, T'sun--Chiel Chen, Keng-Wei Hsu, and Yun-Nung Chen. Slot-gated modeling for joint slot filling and intent prediction. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp. 753-757, 2018.
Charles T Hemphill, John J Godfrey, and George Doddington. The atis spoken language systems pilot corpus. In Speech and Natural Language: Proceedings of Workshop Held at Hidden Valley, Pennsylvania, June 24-27, 1990, 1990.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
Weipeng Huang. Xingyi Cheng, Kunlong Chen, Taifeng Wang, and Wei Chu. Toward fast and accurate neural chinese word segmentation with multi-criteria learning. arXiv preprint arXiv:1903.041990 2019.
Zhiheng Huang, Wei Xu, and Kai Yu. Bidirectional Istm-crf models for sequence tagging. arXiv preprint wxXv::150.0019/1 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXivv1412.6996 2014.
John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Proba- bilistic models for segmenting and labeling sequence data. 2001.
Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. Neural architectures for named entity recognition. arXiv preprint arXiv: urXiv:1603.0/:: 1603.01360, 2016.
Kenton Lee, Luheng He, and Luke Zettlemoyer. Higher-order coreference resolution with coarse- to-fine inference. arXiv preprint arXiv: arXiv:1804.05392 2018
Xiaoya Li, Jingrong Feng, Yuxian Meng, Qinghong Han, Fei Wu, and Jiwei Li. A unified mre framework for named entity recognition. arXiv preprint arXiv: 1910. 1 2019.

---

Under review as a conference paper at ICLR 2021
Tianyu Liu, Jin-Ge Yao, and Chin- Yew Lin. Towards improving neural named entity recognition with gazetteers. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 5301-5307, 2019a.
Yiji Liu, Fandong Meng, Jinchao Zhang, Jinan Xu, Yufeng Chen, and Jie Zhou. Gedt: A global context enhanced deep transition architecture for sequence labeling. arXiv preprint (wXivv/906.024333 2019b.
Yijin Liu, Fandong Meng, Jinchao Zhang, Jie Zhou, Yufeng Chen, and Jinan Xu. Cm-net: A novel collaborative memory network for spoken language understanding. arXiv preprint arXiv: 190.009999 2019c.
Ying Luo, Fengshun Xiao, and Hai Zhao. Hierarchical contextualized representation for named entity recognition. In AAAI, pp. 8441-8448, 2020.
Ma, Kuzman Ganchev, and David Weiss. State-of-the-art chinese word segmentation with bi- Istms. arXiv preprint arXiv: /808 000800651, 2018.
Xuezhe Ma and Eduard Hovy. End-to-end sequence labeling via bi-directional lstm-cnns-erf. arXiv preprint wrXiv:1633.0133 2016.
Yuxian Meng, Wei Wu, Fei Wang, Xiaoya Li, Ping Nie, Fan Yin, Muyu Li, Qinghong Han, Xiaofei Sun, and Jiwei Li. Glyce: Glyph-vectors for chinese character representations. In Advances in Neural Information Processing Systems, pp. 2746-2757, 2019.
Grégoire Mesnil, Yann Dauphin, Kaisheng Yao, Yoshua Bengio, Li Deng, Dilek Hakkani-Tus, Xi- aodong He, Larry Heck, Gokhan Tur, Dong Yu, et al. Using recurrent neural networks for slot filling spoken language understanding. /EEE/ACM Transactions on Audio, Speech, and Lan- guage Processing, 23(3):530-33 -395, 2014.
Joakim Nivre, Marie-Catherine De Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, et al. Universal de- pendencies v1: A multilingual treebank collection. In Proceedings of the Tenth International Conference Language Resources and Evaluation (LREC'16), pp. 1659-1666, 2016.
Nanyun Peng al. Jointly Learning Representations for Low-Resource Information Extraction. PhD thesis, Ph. D. thesis, Johns Hopkins University, 2017.
Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Hwee Tou Ng, Anders Björkelund, Olga Uryupina, Yuchen Zhang, and Zhi Zhong. Towards robust linguistic analysis using ontonotes. In Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pp- 143-152, 2013.
Tao Qian, Yue Zhang, Meishan Zhang, Yafeng Ren, and Donghong Ji. transition-based model for joint segmentation, pos-tagging and normalization. In Proceedings of the 2015 Conference Empirical Methods Natural Language Processing, pp. 1837-1846. 2015.
Erik F Sang and Sabine Buchholz. Introduction to the conll-2000 shared task: Chunking. arXiv
preprint cs/0009008, 2000.
Erik Sang and Fien De Meulder. Introduction to the conll-2003 shared task: Language- independent named entity recognition. arXiv preprint cs/0306050, 2003.
Sunita Sarawagi and William W Cohen. ceni-markov conditional random fields for information extraction. In Advances in neural information processing systems, pp. 1185-1192, 2005.
Sebastian Schuster, Sonal Gupta, Rushin Shah, and Mike Lewis. Cross- lingull transfer learning for multilingual task oriented dialog. arXiv preprint arXiv:1810.1333 2018.
Yan Shao, Christian Hardmeier, Jörg Tiedemann, and Joakim Nivre. Character-based joint segmen- tation and pos tagging for chinese using bidirectional rnn-crf. arXiv preprint urXiv:1704.0133 2017.
10

---

Under review as a conference paper at ICLR 2021
Aditya Siddhant, Anuj Goyal, and Angeliki Metallinou. Unsupervised transfer learning for spoken language understanding in intelligent agents. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4959 4966, 2019.
Mitchell Stem, Jacob Andreas, and Dan Klein. minimal span-based neural constituency parser. arXiv preprint arXiv: 770503399. 2017.
Shaolei Wang, Wanxiang Che, Yue Zhang, Meishan Zhang, and Ting Liu. Transition-base dis- fluency detection using Istms. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 2785-2794, 2017.
Wenhui Wang and Baobao Chang. Graph-based dependency parsing with bidirectional Istm. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 2306 2315, 2016.
Naiwen Xue, Fei Xia, Fu-Dong Chiou, and Marta Palmer. The penn chinese treebank: Phrase structure annotation of a large corpus. Natural language engineering, 11(2):207, 2005.
Nianwen Xue. Chinese word segmentation as character tagging. In International Journal of Com- putational Linguisties Chinese Language Processing, Volume 8, Number February 2003: Special Issue on Word Formation and Chinese Language Processing, pp. 29-48, 2003.
Jie Yang, Yue Zhang, and Fei Dong. Neural word segmentation with rich pretraining. arXiv preprint 1704.086008960 2017.
Zhi-Xiu Ye and Zhen-Hua Ling. Hybrid semi-markov crf for neural sequence labeling. arXiv preprint arXiv: 03838, 2018.
Juntao Yu, Bernd Bohnet, and Massimo Poesio. Named entity recognition as dependency parsing. arXiv preprint arXiv:2005.07/50 2020.
Feifei Zhai, Saloni Potdar, Bing Xiang, and Bowen Zhou. Neural models for sequence chunking. In Thistt-First AAAI Conference on Artificial Intelligence, 2017.
Meishan Zhang, Yue Zhang, and Guohong Fu. Transition based neural word segmentation. In Proceedings the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 421-431, 2016.
11


Reviews:
[{"review_id": "tgf4_wXqwUX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new algorithm for sentence segmentation which can be applied to various sequential tagging problems.\nThe motivation and the description of the algorithm are clearly given, and the proposed method achieved state-of-the-art results for most of the problems and datasets.\n\nThe proposed method tries to find all possible segments in the given input sequence, to estimate the scores of the segments using pre-trained BERT representations, and to find the best sequence of segments using the dynamic programming algorithms.  The proposed method is general enough to apply to various sequential tagging problems and natural language sentence analysis.\n\nWhile the proposed method looks new to apply to the sequential tagging problems in natural language processing, the dynamic programming approach to sequential analysis is a well-known method in the speech recognition community where a sequence of phonemes are segmented into a word sequence.  Also, a similar method has been applied to the segmentation of character sequences into word sequences for the languages that have no delimiters between words, such as Chinese and Japanese.   In these views, the novelty of the paper is not high.   On the contrary, the application of the BERT-based representation to the sequence segmentation tasks such as sentence segmentation and sequential labelling may be new, and the finding that this method can attain a state-of-the-art performance in those problems could be worth reporting.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "njhGY3IgR0o", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is well-written, easy to follow and clear. However, the novelty and main contribution of the paper is not clear. The authors used a scoring model to score the composition of each segment, as well as the probability of having a specific label for the segment. The BERT language model is used in the paper to encode the input sequence. The training part is a more like a supervised training and a dynamic programming (DP) approach is used for inference. It is not clear how DP contributes to the success of the model, as the scores for segments are derived during the training (which seems most of the success is coming from the labeled data (i.e. supervised training) and BERT encoding). One other thing about formatting and citing references, some of the references are published in conference proceedings, not sure why authors cited their arxiv version.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VaKf2MrmuOF", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a method called LUA, Lexical Unit Analysis for general segmentation tasks. LUA scores all the valid segmentation of a sequence and uses Dynamic Programming to find the segmentation with the highest score. In addition, LUA can incorporate labeling of the segment as an additional component for span labeling tasks. \n\nPros:\n1. LUA overcomes the shortages of sequence labeling as a token-based tagging method and span-based models as well, by treating them separately.\n2. The decomposition of scoring label and scoring span allows the pre-computation of the maximum label score for each span, reducing the complexity.\n3. This method achieve the state of the art performance on 13 out of 15 data sets empirically.\n\nCons:\n1. The novelty is incremental, as the idea of calculating span-based score and label-based score with DP has been used widely in constituent parsing, which applies interval DP in a similar way. Also check semi-CRF model (Sunita Sarawagi and William W. Cohen, 2004).\n2. The way of using neural model to calculate the span-based scoring seems to be very arbitrary (Eq3), without any explanation why it is designed in this way.\n3. Label correlations are used to mimic correlation scoring, however the transition between spans are not explicitly modeled.\n\nQuestions:\n1. LUA is only used in inference stage. Do you think by using LUA in training as well, though slower, the performance can be further improved?\n2. Do you have any intuition of why designing the scoring function (Eq3) in that way?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is concerned with sequence segmentation. The authors introduce a framework which they call 'lexical unit analysis' - a neural network is used to score spans and then dynamic programming is used to find the best scoring overall segmentation. The authors present extensive experiments on various Chinese NLP tasks, obtaining better results than the systems they compare to.

Reviewers raised concerns, including about novelty. In my view, beyond beating the state of the baselines on the chosen tasks, it is hard to extract an actionable insight or novel conceptual understanding. Therefore, the paper is not recommended for acceptance in its current form.
Decision: Reject