Filtered Semi-Markov CRF
Authors: Urchade Zaratiana
Nadi Tomeh
Niama Elkhbir
Pierre Holat
Thierry Charnois
Venue: Submitted to ICLR 2023 (2023)
Keywords: Structured prediction
Text segmentation
Named Entity Recognition

Abstract: Semi-Markov CRF \citep{semicrf} has been proposed as an alternative to the traditional Linear Chain CRF\citep{crf} for text segmentation tasks such as Named Entity Recognition. In contrast to CRF, which treats text segmentation as token-level prediction, Semi-CRF considers spans as the task's basic unit, which makes it more expressive. However, Semi-CRF has two major drawbacks: (1) it has quadratic complexity over sequence length as it operates on every span of the input sequence, and (2) empirically, it performs worse than classical CRF for sequence labeling tasks such as NER. In our work, we propose Filtered Semi-Markov CRF, a Semi-CRF variant that addresses the aforementioned issues. Our model extends Semi-CRF by incorporating a filtering step for eliminating irrelevant segments, which helps in reducing the complexity and allows to dramatically reduce the search space. On a variety of NER benchmarks, we find that our approach outperforms both CRF and Semi-CRF models while being significantly faster. We will make our code available to the public. 

alter- Under review as a conference paper at ICLR 2023
FILTERED SEMI-MARKOV CRF
Anonymous authors
Paper under double-blind review
ABSTRACT
Semi-Markov CRF (Sarawagi and Cohen 2005) has been proposed native to the traditional Linear Chain CRF(Lafferty et al., 2001) for text seg- mentation tasks such as Named Entity Recognition. In contrast to CRF, which treats text segmentation as token-level prediction, Semi-CRF considers spans as the task's basic unit, which makes it more expressive. However, Semi-CRF has two major drawbacks: (1) it has quadratic complexity over sequence length as it operates on every span of the input sequence, and (2) empirically, it performs worse than classical CRF for sequence labeling tasks such as NER. In our work, we propose Filtered Semi-Markov CRF, a Semi-CRF variant that addresses the aforementioned issues. Our model extends Semi-CRF by incorporating a filter- ing step for eliminating irrelevant segments, which helps reduce the complexity and dramatically reduce the search space. On variety of NER benchmarks, we find that our approach outperforms both CRF and Semi-Cr CRF models while being significantly faster. We will make our code available to the public.
INTRODUCTION
Sequence segmentation is the process of dividing a sequence into several distinct, non-overlapping segments to cover the entire sequence (Sarawagi and Cohen, 2005; Terzi 2006). It has a wide range of use cases, including Named Entity Recognition (Tjong Kim Sang and De Meulder 2003) and Chinese Word Segmentation (Li and Yuan 1998). Sequence segmentation has traditionally been seen as a sequence labeling problem using pre-exee pre-exiiting templates such as BIO and BILOU schemes (Ratinov and Roth 2009). Conditional Random Field (CRF) (Lafferty et al. 200T) has been widely used in sequence labeling problems to model the dependence between adjacent token tags. Although the Linear-chain CRF has performed well in various segmentation tasks, operating at the segment level rather than the token level would be a more natural way to perform sequence segmentation. To this end, the Semi-Markov CRF (Sarawagi and Cohen 2005) has been proposed variant of CRF, allowing for the incorporation of higher-level segment features, such as segment width. However, Semi-CRF, unlike CRF, is considerably slower for both learning and inference due to its quadratic complexity with respect to the sequence length. Moreover, Semi-CRF generally performs worse than CRF (sometimes the Semi-CRF performs better but the gain is only marginal) (Liang) 2005
Daumé and Marcu 2005; Andrew (006). Indeed, the Semi-CRF performs joint segmentation and labeling which results in much larger search space making learning more challenging.
To address this problem, we propose a filtered version of the Semi-CRF. Like Semi-CRF (Srawagi and Cohen 2005), our model operates on segments, but we add filtering model discard large number of candidate segments. Our aim is to reduce the computational complexity by pruning the segmentation search space. During inference and after the filtering step, finding the best segmen- tation and labeling boils down to finding the maximum scoring path in weighted directed acyclic graph. During training we use similar dynamic programming algorithm allowing us to sum over all paths in the graph.
We evaluate our approach on benchmark datasets for Named Entity Recognition and find that performs better than CRF and Semi-CRF models with noticeably faster inference. The rest of this paper is organized as follows. In the next section, we provide some background and context for un- derstanding the foundational CRF and Semi-CRF models. Next, present our filtered Semi-CRF model in detail, followed by the experimental setup, the results and further experimental analysis, and overview of related works. The final section concludes this paper.

---

Under review as a conference paper at ICLR 2023
2 BACKGROUND
In this section, we first present the Linear-Chail CRF (Lafferty et al. 2001) and then the semi- Markov CRF (Sarawagi and Cohen 2005), namely their structured representation and their learning and inference algorithms.
2.1 LINEAR CHAIN CRF
The Linear-Chain CRF (Lafferty al. 2001) is a sequence labeling model that assigns label to each token in the imput sequence. It assumes dependencies between adjacent output labels (typically Markov dependency of order 1). Hence, given an input sequence a sequence of labels y of the same size L is produced with yi E Y. The conditional probability of y given æ is computed using the following estimator:
exp [EI= ((i(())) + + TortTTTor Ti- exp V (ylar)
ply (+)
((x)
2 2(x)
where (b (x) e R is the score of the sequence label position and R | is a learnable
label transition matrix defined for each pair of labels. Furthermore, Z(x) = E>( exp V/ (yyla
is the partition function that serves normalizer of the probability distribution, where V(x)) is the set of all possible label sequences admissable for æ.
During training, the goal is to update all model parameters by minimizing the negative log proba-
bilities of the gold labels: - log p(y yy ((x) = - -V [x) + log (xx). The partition function ((x) computed in polynomial time using the Forward algorithm (See Eq. [3] in Appendix A.2 for de- tails). For inference, the goal is to produce the optimal segmentation y argmax,, v (y a+). which
computed using the Viterbi algorithm (Eqq. [4 Appendix (A.2). The CRF has linear complexity in terms of the sequence length L, and quadratic complexity in terms of the number of labels Y for both learning and inference, i.e., (²).
2.2 SEMI-MARKOV CRF
Unlike the Linear-chain CRE, the Semi-CRF (Sarawagi and Cohen 2005)
operates at the segment
level to account for segment features that cannot be easily modeled using sequence labeling. The Semi-CRF produces segmentation (of size M) of input sequence (of size L, with L 2 M). The conditional probability of the labeled segmentation y given an input x computed as follows:
p(yla:) = exp EM
A== (ssx(x) + T(k-1,14))
exp (zylar)
((x)
Z ((x)
(ss2 x)) E R is the score of the k-th segment of y and Ti4a-1,44 4el is the label transition score
with T 41]
Furthermore, following Sarawagi and Cohen (2005). a labeled segmentation
{si, ................................ sM ((x)) has the following properties:
A segment sæ (in.Jks, 4) E y consists of start position ig. an end position ja, and label 4 E Y.
The segments have positive lengths and completely cover the sequence 1. ... without
overlapping, i.e., ja and ig always satisfy i 1, jM = L, 1 S is S js L, and i++1 = jk +
For instance, for Named Entity Recognition, a segmentation of the sentence "Michael Jordan eats an apple would be Y=[(1, PER), (3, о), (4, 4, O), (5, 5, O), (6. 6, O)]. In (Sarawagi and Cohen 2005), it is always assumed that non-entity segments (also O or null segments) have unit length.
The model parameters are learned to maximize the conditional probability of gold segmentation p(y(z) over the training data, similar to CRF. The partition function 2(x) = Ey')((a)) exp (by(z) can be computed in polynomial time using modification of the Forward algorithm (Eq. [5 in Appendix(A.3] and inference done by segmental Viterbi (Eq. 16 Appendix (A.3) to produce the best segmentation y = argmax, (b())z) ()). Finally, the Semi-CRi has quadratic complexity in terms of both sequence length and the number of labels for both learning and inference, i.e., (1T.2)119).
2

---

Under review as a conference paper at ICLR 2023
2.3 GRAPH-BASED FORMULATION OF SEMI-CRF
Given a sequence a of lenght |x| = L, labeled segment 81 - Ji (2 ) is defined by its start and end positions S in jk L and its label E Y. Let G(V, E) be directed graph, whose set of nodes V is made of all segments æ; with [z|] Le
L I v
UU0 (3....) i=jj=il=
and the directed edge sp" 5k E E if and only if jæ ig. We further define the weight of an edge S - as follows:
w(Kk + 84 (x) = ((xx()) + [[]
(4)
where (ss (z) is the score of the segment 8y and T ( [x] is the label transition score.
Any directed path {81, 82, 82,-..,8M1 .8M in the graph verifying i = and jM corresponds a segmentation of x.
Proposition 1.
Proof. Any directed path {s1, section 2.2 namely i 1. jM L. in S jN L, and ji i (by definition).
SM verify the properties of the segmentation described in
In addition, the score of the path {s1, 82, SM) computed as the sum of the edge scores is equiv- alent to the Semi-CRF score (2.2 of the segmentation y {81, 82
score 82: ..... SM)
w(sk- + sk sx(20) Σ ( (+) +144
(5)
2 {si...., (M)))
The search for the best segmentation consists in finding the maximal weighted path of the graph that begins at i1
and end at jaM L. Finding the best path this graph has a complexity L using a generic search algorithm such as Bellman-Ford (see section 3.3 for details). Nevertheless, taking into account the lattice structure the problem allows reducing the complexity to T.2, as done in the Viterbi algorithm (Viterbi 1967).
3 FILTERED SEMI-MARKOV CRF
We describe in this section our proposed alternative to Semi-CRF, which we term Filtered Semi- CRF. The motivations for this new model is to address two weaknesses of the Semi-CRF. First, the Semi-CRF is not well-suited for long texts due to its quadratic complexity and the search space is prohibitively large. Second, in tasks such as NER where some segments should be labeled null. 1, multiple paths in the Semi-CRF graph can produce the same set of entities. This is because long null segments can be broken into smaller contiguous null segments without modifying the result. In fact, [Sarawagi and Cohen (2055) constrains nu 11 segments to have unit length and assigns them a score. The crux of our approach to use an independent model to filter the Semi-CRF graph described in $ [2.3 prior to further computations. The resulting graph is order of magnitude smaller than the original one and does not contain null 1 segments thus addressing both issues.
3.1 FILTERING
In our model, filtering applied the full set of segments (we denote as Vywi). The filtering eliminates the segments that are predicted to be null segments by means of a local classifier dlocal:
= 81 E Vfuit arg max (So = (ix, ju. 44) # null
(6)
4
Since the filtered nodes V may not contain all segments, defining the edges E as we did in 2.3 would not be applicable here. Thus, propose to define the edges using the method of Li al.
3

---

Under review as a conference paper at ICLR 2023
[2] Filtering stop
(X) segments- Pu
Es. Langeaa,, Stuss suit]
(3) Graph construction
(4) Scoring, loss computation and decoding
Adgrneba pate:
21 0.6
Start, fL 26, R. and Jocere 6-6
11.2)
[1. -21
0.7
Statt 21 end
11.3)
[3. 1.4
Parttin hastee w012.3 cea(L-)) 14)
0,113
[4, 5) 0.7
11.11
0.7
Toiazg seentrrt highti
Decceiing Reeu mww.mmm
Figure I: Filtered Semi-Markov CRF. 1) Enumerate all the segments of the input sequence. 2) null segments are dropped (Bq. 6 using local segment classifier Plocal- 3) Construct the path graph from the filtered segments; we omit the transition scores for better readability. 4) During training. we compute the loss function (Eq. [nnd TO) by constraining the gold path y be a path of the graph, and during inference, return the maximum weighted path (Alg. 2 Please note that the size of the graph can vary a lot depending on the input sequence and training stage (Fig. 2 and 3)
1991 V(Sw, sk) VV, SK' - S jK < and there is 8g. E V such that jus ig. and Rk < -jk- This formulation means that Sy/ - St. is an edge if sy begins after Skr, and that no other segment lies completely inside (fw, This formulation generalizes the Semi-CRF graphs with missing segments. However, when segments are missing, the starting and ending of segmentation are necessarily i and jM L. To fix this problem, we simply add two terminal nodes start and end:
*start + 36 Ef + sk & E for all K + starr 9% +nd E 9h sk $ for K' # end
A segmentation in the graph is path from start end, i.e. {so, ......,.MM. SM+1) } with so start and 8M+1 = end An illustration of the graph construction is shown in the figure 1
For named entity recognition, if take again the example of Section 2.2 the correct segmentation of "Michael Jordan eats an apple." using the Filtered Gemi-CRF would be y=(start, 21, 2, PER), end], the remaining segments being considered null label: in fact, the Filtered Semi-CRF only accounts for entity segments and assumes that the remaining parts of the sequence have the null label.
3.2 SCORING, LEARNING AND INFERENCE
Segmentation probability To compute segmentation score in the filtered graph, we sum the weights of the path edges representing the segmentation as for the Semi-CRF described Section
2,3
score(y = -.00
8M+1H() = Σ w(sk-1 + sx(
ELEN
where w((8k Sk sk(ar) Ogtobal (ox (x) + Th--1, 4c] if & (1,M 1} and wr 81) Ogtabal (81 (z) and w(sM - 8M+1) = O. where 80 = start and 8M#1 = end. Note that the start and end nodes added only to make the problem a single-source, single-destination shortest path problem. Moreover, Ogtobal is neural network, similarly to éiocat it takes as input the labeled segments $ą (iRTJA, 4) V and returns their scores. Finally, the segmentation
probability of the Filtered Semi-CRF is:
p(y = {so, * exp score(y)a)
(8)
2(x)
((x) = Ey'E((a) exp score (x) is the partition function, which makes the probabilities of all segmentation sum to one.
It is worth noting that the segmentation problem can be formulated as finding the highest scoring Maximal Independent Set (MIS) in interval graph (Gupta al. 1982).
4

---

Under review as a conference paper at ICLR 2023
The set (x)) contains all paths in the graph from start to end. For reasonably small graphs, ((()) can be enumerated, but this is intractable for larger graphs. The partition function can be effi- ciently computed without enumeration; with dynamic programming using variant of the Bellman- Ford algorithm, which can be seen as a message- algorithm (Wainwright and Jordan 2008):
Algorithm 1 Computing ((x)
I: Topologically the nodes of V
2: o[start] = and [* = 0 otherwise for E V for all start in do
4: for all k' such that k' + l E Eo
5:
asAb [[k + a<k' exp[w(sk - 8t)(
6: end for
end for
8: Z ((x) [eeed]
In practice, this implementation 2 (xx) ) unstable, so we did all the computations the log space prevent overflow/underflow. The complexity of the algorithm O(V) + |E]). We provide more details about the size of V and E as a function of L in Section 3.3
Learning During training, we jointly minimize the filtering loss and the segmentation loss. The filtering loss Liocal of the local classifier Plocot is the sum the negative log-probability of all gold labeled segments of the training the loss for the label / = null as a mean of regularization. The weighting ratio 3 E [0, 1] is tuned
T. Since the filtering task is highly imbalanced, we down-weight
on the development set:
Liocal
Σ logp(i.j,1(x) 8- x
Σ log po,
(.JJET Ignull
(LJJ)T
[=zull
where p(i, j. ([x)) is the probability that the segment (i.j) has the label / using the local classifier Plocal- The loss of the segmentation model & @atobal is computed as:
Legobal - -scoreyyla
log 2(x)
(10)
Furthermore, during the training, we constrain the candidate segments V (Eq. 66 to contain the gold entity segments y, and we also ensure that the gold segmentation is path of the filtered graph. i.e., all other candidate spans should be overlapping at least with one segment of the gold. This choice may be sub-optimal since can cause exposure bias, i.e., a training-inferenee discrepancy. However, found that it works well in practice, and suppressing leads to unstable learning and negative value the global loss since score (x) can be larger than log Z(x). The total loss the model the sum of the local and global losses, Liotal giobbul + Llocal-
Inference During inference, the objective is to return the path (from sta rt to end) of graph that has the best score. We solve this problem using max-sum dynamic programming algorithm that has the same structure as Algorithm
Algorithm 2 Decoding
1: Topologically sort the nodes of V ][start] =
3: for all / start in V do
8[k]
8[k'] + w(sk - *x1(x)
(K' K)-
end for
The highest scoring path, ie argmax, score is the path traced by 6[end] which can be obtained by backtracking. This algorithm has a complexity of [(V|+|E) the same as computing the partition function 2(xr).
5

---

Under review as a conference paper at ICLR 2023
Conll-2003
OntoNotes
Arabic ACE
10
30
20
10
60
1000
20
40
80
100
103
Figure 2: Empirical complexity analysis. This plot illustrates the relationship between the size of the filtered graph (VI + E and the input sequence length L, on three NER datasets. This experment is done with trained models.
3.3 COMPLEXITY ANALYSIS
In this section, we analyze the complexity of the algorithms (1 and 2 O(V) the input sequence length L. Note that the size of V does not depend on the number of labels |Y] since there is at most one label per segment due to the filtering step in equation
+ (EI)
as a function of
Proposition 2. There are L(L+1) nodes in a complete segment path graph constructed using a sequence of length I.
2
Proposition 3. There are L(L-I)(L+1) edges in a complete segment path graph constructed from sequence of length L.
We use propositions and to derive the complexity of the Filtered Semi-CRF model, developed below. Their proofs can be found in Appendix A.1
Worst complexity In the worst case, the filtering model &local does not filter any segments, ie., all segments are kept. From propositions 2 and 3, we can deduce that in the worst case, O(T)) which means that the complexity of our worst case al-
O(VV)) O and O( gorithm is cubic as a function of the sequence length T. since O(VV + [F = O(L.). However, note that in the worst case, the resulting graph is the Semi-CRF and the complexity can be reduced to L using the algorithms Forward (during training) and Viterbi (during inference).
Best case complexity The best case scenario means that the filtering is perfect, so the number of nodes in the graph [V] equal to the true number of non-rull segments in the input sequence, which we denote by J. Moreover, since I does not contain overlapping segments, [J] < L with [J] = L if all segments in J have unit length and cover the entire sequence i.c J = (,, 4) 1... L,4 * null). Furthermore, |E| = |J| - -1 < L 1 because perfect filtering implies that the path number is unique. Finally, we can conclude that the complexity is linear i.e, O(VV + |E]) O(L).
Empirical analysis We further investigate the empirical complexity of our approach by looking for relationship between |V|+ E and the sequence length L in practice. We performed the exper- iments on three text segmentation datasets, Conll-2003, OntoNotes 5.0 and Arabic ACE dedicated to the task of Named Entity Recognition. The results are shown in Figure 2 The plots show that the graph size |V++ + |E] is generally smaller than the sequence length for trained model, mean- ing that empirically, the complexity is close to the best case complexity which is OL).. However, during training, especially in the first stage, the size of the graph can be large because the filtering model may be poor, illustrated in the figure g Empirically, the early steps of the training can be time consuming due to larger graph size. However, after a few gradient steps, the size of the graph decreases significantly since most of the segments of an input sequence are labeled as nul.

---

Under review as a conference paper at ICLR 2023
OntoNotes
Arabic
321
105
144 [+(5]
331-
131
221
10
307
100
Triining stop
Training step
Training step
Figure 3: Evolution of the graph size during training. The two axis are in log-scale and the data are smoothed using Swvizkky-Golan filter (Savitzky and Golay 1964). There are three main stages. At the beginning of the training, the size of the graph is large because the filtering model is trained. At the second stage, the size of the graph is small because the filtering model is confident about null segments (most segments are null). At the last stage, the size of the graph is stabilizing.
EXPERIMENTAL SETUPS
4.1 REPRESENTATION AND SCORES
For all our models, we used pre-trained transformer models (Devlin et al. 2019) to compute word representations. Specifically, the input sequence {->}==] is fed into a pre-trained transformer pro- ducing set of contextualized embeddings (h) R with D the emhedding size of the model. In addition, since pre-trained transformers typically separate words into sub-tokens, we use the first sub-token embedding as the representation of the whole word, which a common practice for token-level prediction tasks.
In our sequence labeling baseline, we compute the label score at position as linear projection of the token representation at the same position: ab(us (x) = no h; E IR, where Wy R Dx1 is label-specific learnalee weight vector.
Token scores
Segment scores
For our segment-level models (Semi-CRF and FSemiCRF), we compute the rep- resentation S:j the segment (i,j) using a sum pooling of the representations of the tokens com- prising the segment, Stj = SUM [h;, h.t1,...,,;))
Indeed, according to Adi et al. (217)), sum pooling can effectively model the length of the sequence. Moreover, for the segment-base based models (i.e, Semi-CRF and Filtered Semi-CRF), we restrict the segment to a maximum width to reduce complexity without harming the recall score on the training set (however some segments may be missed for the test set). By bounding the maximum width of the segments, we reduce the number of segments from L to LK, where is the maximum width. Thus, under this setup, the the complexity of the Semi-Markoy CRF become O(LK Finally, the segment scores (i.e all @ (sx)) are computed using a linear projection of the segment representations, analogous token scores.
4.2 SETUP
Datasets and evaluation We evaluate our models on three diverse datasets of Named Entity Recognition. conll-2003 (Tjong Kim Sang and De Meulder, (2033) is a dataset from the news do- main designed for extracting entities such as Person, Location, and Organisation. OntoNotes 5.0 (Weischedel et al. 2013) large corpus comprising various kinds of text, including newswire, broadcast news, and telephone conversation, with total of 18 different entity types, such as Person, Organization, Location, Product, or Date, Arabic ACE is the Arabic portion of the multilingual in- formation extraction corpus, ACE 2005 (Walker et al. 2006). It includes texts from wide range of genres, such as newswire, broadcast news, and weblogs, with a total 7 entity types. We follow the standard common approach for evaluating NER models, based exact matching between predicted and gold entities, discarding non-entity segments. We report the micro-averaged precision (P), recall (R), and the F1-score (F) on the test set for models selected the dev set.

---

Under review as a conference paper at ICLR 2023
Conll-2003
OntoNotes 5,0
Arabic ACE
Models
R
F
P
R
F
Yu et
2020
93.7
93.3
93.5
91.1
91.5
91.3
Yan et al.
2021 )
92.61
93.87
93.24
89.99
90.77
90.38
Zhu and Li
2022
93.61
93.68
93.65
91.75
91.74
91.74
Shen et al.
2022
93.29
92.46
92.87
91.43
90.73
90.96
Our experiments
CRF
93.29
92.21
92.75
89.00
90.16
89.57
82.79
84.44
83.61
Semi-CRF
92.37
90.49
91.42
88.91
89.78
89.34
82.97
84.24
83.60
+ Unit size nullf
92.08
91.41
91.74
89.17
89.76
89.47
83.35
83.62
83.48
FSemiCRF
94.72
93.09
93.89
90.69
91.31
91.00
83.43
85.51
84.46
-w/ Lglobal
10
94.24
92.70
93.46
90.85
89.57
90.21
83.73
83.56
83.64
Table 1: Main results. All English models employ bert bert-large cased for representing the tokens on English datasets, except (Yan et al. (021)) that uses bart-large. See ablation study (sec.
5.2 for details about these models.
Hyperparameters To produce contextual token representations, we used bert- bert-lazge-cased (Devlin et al.] 2019) for both conll-2003 and OntoNotes 5.0 datasets, and (Antoun et al.] (2000) for Arabic ACE. For simplicity, we do not use auxiliary embeddings (eg. character embeddings). All models are trained with Adam optimizer (Kingma and Ba (017). ). We employed a learning rate of 2e-5 for the pre-trained parameters and a learning rate of 5e-4 for the other parameters. We used a batch size of 8 and trained for maximal epoch of 15. We keep the best model on the validation set for testing. We trained all the models on server equipped with V100 GPUs. We implemented our model with PyTorch (Paszke) et al. 2019). The pre-trained transformer models were loaded from HuggingFace's Transformers library (Wolf et al. 2019). We used AllenNI.P (Gardner et al., 2018) for data preprocessing and the seqeval library (Nakayama) 2018) for evaluating the sequence labeling models. Our Semi-CRF implementation based on pytorch-struct (Rush 2020).
Baselines We compare Filtered Semi- against the CRF (Lffferty al. 2001 and the Semi-CRF (Sarawagi and Cohen 2005). We also report some results from the literature: Bi- affineNER Yuu al. 2020), Bart-NER (Yan al. (02T), Boundary Smoothing (Zhu and Li 2022) and PIQN (Shen et al. (022). For English datasets, all the models are using bert 1ar-arre---- case for token representation except BartNER which used part-large (Lewis al.) 2020). Moreover, for a fair comparison, we only report results for models using sentence-level context (in contrast to paragraph-level context).
RESULTS
5.1
MAIN RESULTS
CRF v.s. Semi-CRF v.s. FSemiCRF We here compare our proposed model to the CRF and Semi- CRF baseline models reported in Table Semi-CRF is the worst-performing model, with the lowest scores on conll-2003 and OntoNotes 5.0 datasets and the same performance as CRF on the Arabic ACE dataset. Moreover, on all datasets, our proposed FSemiCRF outperforms CRF and Semi-CRF in terms of precision and recall, demonstrating its utility in a variety of scenarios. Furthermore, we find that there is no significant difference between FSemiCRF with and without transition scores (in fact, most of the time the result is the same), which can be explained by the fact that adjacent segments in the filtered graph may be far from each other.
Comparison to SOTA Compared the oftee-of-the-ar models, our FSemiCRF has the highest score on the 2003 dataset, outperforming the second-hine highest score by 0.24 terms F1- score. On OntoNotes, while not the best, our model is still competitive.
8

---

Under review as a conference paper at ICLR 2023
Training
Inference
Datasets
[
CRF
SemiCRF
FSemiCRF
CRF
SemiCRF
FSemiCRE
conll-2003
4
9.51
8.73
7.50
20.41
17.35
31.54
OntoNotes 5.0
18
7.68
3.38
5.49
13.63
4.26
23.22
Arabic ACE
7
4.60
4.14
6.12
7.87
6.30
12.60
Table 2: Model Throughput (higher is better). We measure the throughput of the model in batch per second, using batch size of 8 V100 GPU. All models use the same vector dimensions for token representation for fair comparison.
5.2 ABLATION STUDY
Semi-CRF Unit size null We study an alternative variant of Semi-CRF that allows nul labels only for segments of unit length. To do this, we simply modify the original Semi-CRF by climinating/masking segmentation paths that contain null segments whose size is greater than onc. The motivation for this study is to reduce the search space and force out segmentation ambiguity. We can see that it improves the results on conll-2003 and OntoNotes 5.0. However, the results are still poor compared to the other approaches.
ESemiCRF w/o global loss As shown in Table L we investigate the influence of global loss FSemiCRF by removing it, resulting in a local span-based NER model. Its decoding is performed using greedy algorithm where the highest-scoring entity is iteratively added the result as long as it does not overlap with the previously selected entities, As shown in the Table [ even without the global loss, the model competitive, but the global model consistently improves the scores.
5.3 EFFICIENCY ANALYSIS
In this section, we analyse the computational efficiency of the models both for training and infer- ence. We performed two experiments: 1) the training and inference throughput in Table measured in batch per second; 2) the inference wall clock time for comparing the Semi-CRF and FSemi- CRF to show the time needed for computing the span scores and the decoding, in millisecond per sample. For both experiments, we use a batch size of and an Nvidia V100 GPU with 16 GB of memory. For a fair comparison, for all the datasets and models, we employed a similar model size for the token representation, namely -awett-baeecaseeeee for Conll-20n 2003 and OntoNotes 5.0 and for Arabic ACE.
Throughput For training, the results show that the CRF model is the fastest for most of the datasets. Then, the FSemiCRF is the second fastest; it has a better training throughput than the Semi-CRF on all datasets except for Conll-2003. We empirically found that the speed of the Semi- CRF depends strongly on the number of labels; therefore, it is fast on Conll-2003 since this dataset has only few label types. During inference, our FSemiCRF significantly faster than other meth- ods: it is 5 times faster than Semi-CRF on OntoNotes 5.0 and 2 times faster on Arabic ACE. We explain this behavior by two main points: 1) During inference, segment filtering is highly paral- lelizable, while during training it is not. 2) The complexity of FSemiCRF strongly depends on the performance of the filtering model; the early stage of training. the filtering model may be poor, which leads to larger graph (as shown in the figure while the size of the graph is generally small during inference. See section 3.3 for more detail.
Wall clock time We performed a wall clock time analysis of the Semi-CRF and Filtered Semi-CRF on the table As shown in the table, computing the segment scores (using bert-based models) is the same for both approaches. However, for the decoding, Semi-CRF applies the segmental Viterbi algorithm to the segments, while FSemiCRF only uses the filtered segments. This study shows that the decoding time of the FSemiCRF is almost negligible compared to computing the segment scores. In contrast, the decoding for Semi-CRF is significantly slower. Noticeably, the decoding sometimes slower than computing the segment score for the Semi-CRF, which is the case on OntoNotes 5.0 and Arabic ACE datasets.

---

Under review as a conference paper at ICLR 2023
Conll-2003
OntoNotes 5.0
Arabic ACE
Semi-CRF
FSemiCRF
Semi-CRF
FSemiCRF
Semi-CRF
FSemiCRF
Scoring
3.85 ms
4.88 ms
8.33 ms
Decoding
3.71 ms
0.21 ms
27.5 ms
0.22 ms
10.13 ms
0.33 ms
Total
7.56 ms
4.06 ms
32.38 ms
5.10 ms
18.47 ms
8.66 ms
Table 3: Wall clock time (lower is better). This table reports the average wall-clock time comparison of Semi-CRF and Filtered Semi-CRF in milliseconds (per sample). We separate the time needed for computing the segment representations (with BERT) and the decoding algorithm. Please note that the scoring time is the same for Semi-CRF and FSemiCRF. We use the same setup as in table 2
RELATED WORK
Many frameworks have been proposed for text segmentation. The most popular is the Linear-Chan CRF (Lafferty al., 2001), which treats text segmentation tasks as token-level prediction. It is trained by maximizing the sequence-level objective of the gold standard labeling and using the Viterbi algorithm (Viterbi 1967: Forney 20T0) for decoding, adding some constraints to the tran- sition matrix to enforce the well well-formedness of the output. First variants employed handcrafted features (Lafferty et al., [200]] Gross et al. 2006 Roth and tau Yih 2005) and has been further ex- tended to automatic feature learning using neural networks (Do and Artières 2010 van der Maaten al.] 2011T Kim et al.) 2015] Huang et al.) 20155] Lample et al. (016). Usually, CRF is used with 1st order Markov transition on the labels, but other methods such as Ye et al. (2009) Cudng et al. (0144) have proposed to employ higher order dependency to further enhance the performance, how- ever due to the high complexity and the marginal gains, it has not gained in popularity. Semi-CRF (Sarawagi and Cohen, 2005) has been proposed as an alternative to CRF for sequence segmenta- tion tasks. Instead of operating
the token level, the Semi-CRF considers segments the basic unit for the prediction. It has been applied to several sequence segmentation tasks, such as Chinese word segmentation (Kong et al. 2016) and Named Entity Recognition (Sarawagi and Cohen 2005 Andrew 2006; Zhuo et al.) 2016 Liu et al. [0166] Ye and Ling] 2018). Its main advantage over traditional CRFs that it can incorporate segment-level features such as segment length, which can help obtain a model with higher predictive ability. However, it presents two major shortcomings: has quadratic complexity as function of the sequence length, which makes it difficult to apply for long sequences, and it generally obtains inferior or marginal gains over the CRFs (Liang) (2055] Daumé and Marcu 2005) Andrew] 2006). In this work, we proposed a more efficient alternative by adding filtering step that drops null segments. Our approach provides significantly better performance and more efficient inference than both CRF and Semi-CRF.
7 CONCLUSION
In this paper, proposed Filtered Semi-CRF, novel technique for text segmentation tasks. We applied our method to the Named Entity Recognition (NER) task and obtained significant gain over traditional CRF and Semi-CRF models on various benchmark datasets. In addition to being more efficient, our algorithm is faster and more scalable than the baseline models. In future work, we plan extend algorithm nested segment structures.
REFERENCES
Yossi Adi, Einat Kermany, Yonatan Belinkov, Ofer Lavi, and Yoav Goldberg, Fine-grained analysis of sentence embeddings using auxiliary prediction tasks. In International Conference on Learning Representations, 2017. URL
Galen Andrew. A bybrid Markov/semi-Mart conditional random field for sequence segmentation. In Proceedings the 2006 Conference on Empirical Methods in Natural Language Processing, pages 465-472, 472, Sydney, Australia, July 2006. Association for Computational Linguistics. URL
https: //ss://ac antho ' www.oorg.ooooooooooooooo.......o ND -
10

---

Under review as a conference paper at ICLR 2023
Wissam Antoun, Fady Baly, and Hazem M. Hajj. Arabert: Transformer-bint model for arabic language understanding. ArXiv, abs/aa03.00111000 2020.
Nguyen Viet Cuong, Nan Ye, Wee Sun Lee, and Hai Leong Chieu. Conditional random field with high-order dependencies for sequence labeling and segmentation. Journal of Machine Learning Research, 15(28):981-009, 2014. URL http:// jmlr. httpg//aaprssv////// cuo.g/g/a.. html
Hal Daumé and Daniel Marcu. Learning as search optimization: approximate large margin methods for structured prediction. Proceedings of the 22nd international conference Machine learning, 2005.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Lan- guage Technologies, Volume (Long and Short Papers), pages 4171-4186 Minneapolis, Min- nesota, June 2019. Association for Computational Linguistics. doi: 10. 1111866//1/11111422 URL
Pre- Pre-training of deep
hatiis://aoLanthooooyy..uo
Trinh Minh Tri Do and Thierry Artières, Neural conditional random fields. In AISTATS, 2010.
Jr. G. Forney. Viterbi algorithm. In Encyclopedia of Machine Learning, 2010.
Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke Zettlemoyer. AllenNLP: A deep semantic natural language processing platform. In Proceedings of Workshop for NLP Open Source Software (NLP-OSS), pages 1 1-6, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 1/118865/1/111-25001 URL htt.httss///aclatttii
org/w18 2301
Samuel Gross, Olga Russakovsky, Chuong B., and Serafim Batzoglou. Training condi- tional random fields for maximum labelwise accuracy. In B. Schölkopf. J. Platt, and T. Hoffman, editors. Advances in Neural Information Processing Systems, volume 19. MIT Press, 2006. URL
nwwrips.............e........... cc/pppper/200//iie.... pdf
U. I. Gupta, D. T. Lee, and Joseph Y.-T. Leung. Efficient algorithms for interval graphs and circular- are graphs. Networks, 12:459 467, 1982.
Zhiheng Huang, Wei Xu, and Kai Yu. Bidirectional Istm-crf models for sequence tagging, 2015.
Young-Bum Kim, Karl Stratos, and Ruhi Sarikaya. Pre-training of hidden-unit CRFs. In Pro- ceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 192-1999999 198, Beijing. China, July 2015. Association for Computational Linguistics. doi: 10.3115/v1/P15
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Lingpeng Kong. Chris Dyer, and Noah A. Smith. Segmental recurrent neural networks. CoRR, 2016.
John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings the the Eighteenth International Conference on Machine Learning, ICML '01, page 282-289 San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ISBN 1558607781.
Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. Neural architectures for named entity recognition. In North American Chapter of the Association foor Computational Linguistics, 2016.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy. Veselin Stoyanov, and Luke Zettlemoyer. Bart: Denoising requence-to-sequeee pre- training for natural language generation, translation, and comprehension. In ACI., 2020.

---

Under review as a conference paper at ICLR 2023
Haizhou Li and Baosheng Yuan. Chinese word segmentation. In Proceedings of 12th Pacific Asia Conference on Language, Information and Computation, pages 212-217, Singapore, February 1998. Chinese and Oriental Languages Information Processing Society. doi: http://hd..andle.. 201/2065/12081. URL https: / http///aaaatttooto ant htwphhoooyyoo..//--g11/1 1020
Percy Liang. Semi- Semi-supervised learning for natural language. 2005.
Y.D. Liang, S.K. Dhall, and S. Lakshmivarahan. On the problem of finding all maximum weight independent sets in interval and circular-arr graphs. In (Proceedings) 1991 Symposium on Applied Computing, pages 465-470, 1991. doi: 10. 1190//0AC.19911144.
Yijia Liu, Wanxiang Che, Jiang Guo, Bing Qin, and Ting Liu. Exploring segment representations for neural segmentation models. In IJCAI, 2016.
Hiroki Nakayama. segeval: A python framework for sequence labeling evaluation, 2018. Software available from
URL https:://ithbb.coo com
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vitito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. 2019.
Lev Ratinov and Dan Roth. Design challenges and misconceptions in named entity recognition. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL-2009), pages 147-155, Boulder, Colorado. June 2009. Association for Computational Linguistics. URL URL https:://// httpss//lcaaanhooo....oo. wwwp/ooggg//o////. /209-099-000 1119
Dan Roth and Wen tau Yih. Integer linear programming inference for conditional random fields. Proceedings of the 22nd international conference Machine learning, 2005.
Alexander M. Rush. Torch-struct: Deep structured prediction library, 2020.
Sunita Sarawagi and William Cohen. Semi-markov conditional random fields for information extraction. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Process- ing Systems, volume 17. MIT Press, 2005, URL http::tttt/tttcttcttt
neurips. cc/ pdf
A. Savitzky and M. J. E. Golay. Smoothing and differentiation of data by simplified least squares procedures. Analytical Chemistry, 36: 1627-1666,,, January 1964.
Yongliang Shen, Xiaobin Wang, Zeqi Tan, Guangwei Xu, Pengjun Xie, Fei Huang, Weiming Lu, and Yue Ting Zhuang. Parallel instance query network for named entity recognition. In ACL, 2022.
Evimaria Terzi Problems and algorithms for sequence segmentations. University of Helsinki, Finland, 2006. URL htttpp://eeed..heeeeeeee hww.ink.eel.iik.... ht/bbitttttteem/aaaaeee//// 21344/prablems
Erik F. Tjong Kim Sang and Fien De Meulder. Introduction to the CoNLL-2003 shared task: Ganguage-independee named entity recognition. In Proceedings the Seventh Conference on Natural Language Learning at HITT-AACI, 2003, pages 142-147, 2003. URL https:
Laurens van der Maaten, Max Welling, and Lawrence K. Saul. Hidden-unit conditional random fields. In AISTATS, 2011.
A. Viterbi. Error bounds for convolutional codes and asymptotically optimum decoding algo- rithm. IEEE Transactions on Information Theory, 13(2):260-22) 269, 1967. doi: 19.1 1054010.
12

---

Under review as a conference paper at ICLR 2023
Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and T in Machine Learning. ((1-2): 2008. ISSN 1935-8237. doi: 10.1561/22000000001. URL URLpttp:: /tx. doi. wtt.:o......//... 11w.:...5611111 1511020000020000000011111
Christopher Walker, Stephanie Strassel, Julie Medero, and Kazuaki Maeda. Ace 2005 multilingual training corpus, Feb 2006. URL https:t/cttaaaloooo Idc. upenn Sttt/LDC220600
Ralph Weischedel, Martha Palmer, Mitchell Marcus, Eduard Hovy, Sameer Pradhan, Lance Ramshaw, Nianwen Xue, Ann Taylor, Jeff Kaufman, Michelle Franchini, Mohammed El- Bachouti, Robert Belvin, and Ann Houston. OntoNotes Release 5.0, 2013. URL https:
7/hal. www.hhandle....m wwt./ettttt2.. www.aanee.nee/112...2...... 1/AB2/ /MKJJ2R
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface's trans- formers: State-of-th the-art natural language processing. ArXiv, abs/1910.03771, 2019.
Hang Yan, Tao Gui, Junqi Dai, Qipeng Guo, Zheng Zhang, and Xipeng Qiu. A unified gen- erative framework for various NER subtasks. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 5808-5822, Online, August 2021. Association for Computational Linguistics. doi: 10.18653/v1/2033 1/220////oo2....ooog.g.o.. acl-
URL
otg. a00llaallloon 451
Nan Yc, Wee Lee, Hai Chicu, and Dan Wu. Conditional random fields with high-order features for sequence labeling. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Cu- lotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Asso- ciates, Inc., 2009. URL https: / http:///pceeeeins.eeeeep hwwpeeeedddiis..e.eeeeeeeeeeeeee nwwrinuriis.... cc/ppaper/200///iiiee
pdf
Zhixiu Ye and Zhen-Hua Ling. Hybrid semi-Markov CRF for neural sequence labeling. In Pro- ceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Pupers), pages 235-240, Melbourne, Australia, July 2018. Association for Compu- tational Linguistics. doi: 10. 12..8863/11/P182000
URL. https:: hataa/aaaaaoollooooooooooooooooa ooy.oogyr......o..o.............
Juntao Yu, Bernd Bohnet, and Massimo Poesio. Named entity recognition dependency parsing. In Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, pages 6470-6476, Online, July 2020. Association for Computational Linguistics. doi: 18.55vv//v1/ 2020.acl-main.57. URL htt.ttts//acaaaanooooooo// org/2020.002.... acl -ww.aaal...mm.... main.57)
Enwei Zhu and Jinpeng Li. Boundary smoothing for named entity recognition. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volune 1: Long Papers), pages 7096-7108, Dublin, Ireland, May 2022. Association for Computational Linguis-
tics. doi: 10.18653/w122222.acl-
URL https: http:////caaatthhhccocoo httppss///claatttooooyyyyoeoee org/2022.
ac ong.ong.....................oo.. 490
Jingwei Zhuo, Yong Cao, Jun Zhu, Zhang, and Zaiqing Nie. Segment-level sequence modeling using gated recursive Semi-Markov conditional random fields. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1413- 1423, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/ v1/P16- 1116-1134 134, URL /tt.ttts:://ccaaaaoooooooo
1134
13

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 PROOFS
Proposition There are L(L+1)
nodes a complete segment path graph constructed using
2
sequence of length L.
Proof. Nodes are the enumeration of all segments (regardless of labels). Thus,
L -U V
|V|
E(++1-1) 1)
i=1j=i
j=i
L Σ
L(I 11)
( Σ
(11)
2
1=1
1=1
[V L(L+1)
Proposition 3. There are LIL-1)(++) edges in complete segment path graph constructed from a sequence of length L.
Proof. We know that in the complete segment graph
1. By definition, (is,jx) (ivije) E iff jR
in
2. There are ju segments ending at ja ie 1 = JA
(i,
3. There are L ju segments starting at in ie U (ix,, i) L - in + 1 L jr.
From and 3, we can deduce that there jx j&) segments starting in and ending ja. Finally, the total number of edges of the graph is the sum over all ja from 0 to L:
E
Σ j==1
ja jk) T.
Σ jk
Σ
J
j==1
1)
L(T. + (2T +1)
L
2L +
L(L
1)(
(12)
2
6
6
L(I + 1)(I-
E
6
A.2 CRF
Partition function The partition function 2 Z(x) of the CRF (Lafferty et al. 2001 is computed using the forward algorithm, with a(1, y) = (((l)) and for i - L:
ali Σ a(i 1, 1/) exp(xb(y) + Ty.
B'EY
(13)
3(x) = Σ a(L,y)
BEY
Decoding The decoding of CRF is done with the Viterbi algorithm, with 8(1. (b(()2))) x))
8(i, 3)
max 8(i L.y') + (5/(+) + Ty
(14)
y' y'EY
The best labeling is given by the path traced by max 8(L, v). Both the computation of the partition function and the decoding of the CRF have complexity of (
14

---

Under review as a conference paper at ICLR 2023
A.3 SEMI-CRF
Partition function The partition function of the Semi-CRF (Sarawagi and Cohen 2005) ((x)
computed using the following dynamic program (a modification of the forward algorithm) with a00,:) = 1 and c(m;;) = 0f m < 0 and otherwise:
a(m, v) Σ Σ a(m d, exp n -d-d+ 1,j m, l = y)( T(y.. y'e'
(15)
Z(z)
Σ a(L.y)
yEY
Decoding The decoding the Semi-CRF is done with the segmental/Semi-Martt Viterbi algo- rithm with 5(0,:) 0 and 8(m,:) if m and otherwise:
8(m, max ō(i d,y') <( m d + 1,j m, ( y)(=) T//.20 v)
(16)
B'EY
The highest scoring segmentation is the path traced by maX 8(L, Both the computation of the partition function and the decoding of the Semi-CRI have complexity of ((L?)
15


Reviews:
[{"review_id": "dl5LjZshuxk", "reviewer": "Reviewer_YFd7", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "A method is proposed for filtering spans to be labeled in a semi-Markov CRF, which empirically reduces training/inference complexity and increases evaluation metrics relative to basic CRF or basic semi-CRF.", "summary_of_the_review": "The proposed method does well in ablation experiments (reducing to CRF, or expanding to full semi-CRF) but some obvious baselines were neglected (greedy decoding over Transformer, bounding maximum span of semiCRF).", "strength_and_weaknesses": "The paper is clearly written. The method is, to my knowledge, original.\n\nIt does not compare to state-of-the-art methods, which generally use something like transformer decoders with greedy decoding. (https://paperswithcode.com/sota/named-entity-recognition-ner-on-conll-2003, https://paperswithcode.com/sota/named-entity-recognition-ner-on-ontonotes-v5, https://paperswithcode.com/sota/named-entity-recognition-on-ace-2005) The results are a bit worse than SOTA.\n\nThe motivation is to address the shortcoming of semiCRF that it considers all spans. It turns out that the proposed method is not only faster but gets better evaluation scores than pure semi-CRF. (The authors might want to speculate on why that is-- it isn't clear to me a priori that the proposed method should be more accurate.) However the proposed method has some shortcomings: it introduces a hyperparameter beta, it has the possibility of discarding good spans in the filtering phase, and the worst-case complexity is higher. For many tasks it is possible to give a reasonable upper bound on the span length that needs to be considered, so complexity of semiCRF training/inference is reduced to linear from quadratic in sentence length. What about a baseline that uses a maximum segment length and allows null labels only for spans of length 1? I think that should address the weaknesses of semiCRF in a cleaner way and I would not be surprised to see it working quite well in terms of evaluation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "A8t_RaDWkUy", "reviewer": "Reviewer_JeoQ", "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": "This paper focuses on reducing the inference complexity of semi-Markov CRF and thus achieving better performance on NER by introducing a filtering step before forward algorithm and Viterbi decoding. More specifically, segments that are predicted to be null and whose label does not achieve the highest predicted score according to an additional local classifier will be filtered. Experiments are conducted on the task of NER and evaluated on three datasets: CONLL-2003, OntoNotes 5.0 and Arabic ACE.", "summary_of_the_review": "In general, this paper focuses on an important problem w.r.t. SemiCRF which prevents its widespread application as CRF and proposes an applicable method for resolving it. However, this method lacks thorough analysis (especially experiments), which weakens the claims made in the paper.", "strength_and_weaknesses": "Strength:\n1. Experiment results on performance and throughput verify the claim that Filtered Semi-Markov CRF are better than CRF and Semi-Markov CRF on NER tasks.\n\nWeakness:\n1. Some parts of the paper is a little hard to follow, especially Section 3. For example, what is the model architecture of local classifier compared to the global ones?  Do they share parameters? Besides, without reading the rest part in Section 3, it is hard to recognize that Eq. (6) chooses segments whose labels are not predicted to null but also achieves the highest scores. There also exist some typos. For example, in the 4th row from the bottom of Page 3, $j_k<i_{k^*}$, which should be $i_{k^*} < j_k$.\n\n2. Lack of detailed analysis about why filtering leads to better performance. FSemiCRF does Viterbi decoding on a subset of segments compared to the original SemiCRF, whose optimum should be worse than that of SemiCRF in theory. I'm curious whether the introducing of local filtering models and corresponding segment filtering in training or segment filtering during inference is the primary cause of performance improvement. an ablation study and analysis will be helpful. For example, how FSemiCRF performs if it is trained as described in Section 3 but still follows original SemiCRF (i.e., run Viterbi decoding on all the segments) during inference?\n\n3. Model throughput needs further explanation. During inference, both SemiCRF and FSemiCRF have two steps: (1) to calculate segment scores for all segments; (2) Viterbi decoding, in which SemiCRF does Viterbi decoding directly while FSemiCRF runs segment filtering and does Viterbi decoding on the rest segments. It will be better to show which step is the bottleneck (e.g., to show empirical wall-clock time of these two steps) and how FSemiCRF improves SemiCRF in the second step (e.g., to show wall-clock time of segment filtering and Viterbi decoding on the rest segments).\n\n4. What about training complexity (e.g., wall-clock time) of FSemiCRF compared to SemiCRF.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2Imhof2H3M", "reviewer": "Reviewer_z7Y1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposes a semi-Markov conditional random field model that integrates a filtering step to eliminate irrelevant segments when performing named entity recognition in text. According to the authors this helps reducing the complexity compared to a semi-Markov CRF and dramatically reduces the search space. \n", "summary_of_the_review": "The paper is below the threshold for acceptance at ICLR because of:\n- Important details and evaluations are missing.\n\nSeveral of my questions were answered during the rebuttal, for which I thank the authors. ", "strength_and_weaknesses": "Strengths\n\nAttempt to learn segmentation jointly with classification (here named entity recognition or NER) that does not rely on an expansion of the label space (as is commonly done in NER by specializing the labels into begin label, intermediate and outside label).\n\nWeaknesses\n\n-\tThe model relies on an extra classifier that filters segments. The model is jointly trained by considering the filter classification loss, the segmentation loss and the NER classification loss. It is not clear from the paper how during training the computational complexity is reduced as initially all potential segments need to be considered in the inference step during training. That means that the complexity is equal to the complexity of the semi-Markov model.  The authors acknowledge that “during training, especially in the first stage, the graph size can be large since the filtering is poor.” It is not clear how exactly the filtering is performed during training. \n-\tBecause the segment filtering is the contribution of the paper, its approach (which should be explained in detail) should be separately evaluated, that is, its behavior and reduction in complexity during training and ablating the assumptions made here. \n-\tResults could have been evaluated on many more NER datasets. \n-\tThe claim that the proposed filtering model drastically reduces the search space compared to a CRF and SemiCRF model is not seen in the model’s throughput numbers, especially not during training. Moreover, the effect of dynamic programming on the model’s throughput during inference on the test data could be investigated. Is dynamic programming also used in the decoding of the CRF and SemiCRF models?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject