Interpretable rationales for model predictions play a critical role in practical applications. In this study, we develop models possessing interpretable inference process for structured prediction. Specifically, we present a method of instance-based learning that learns similarities between spans. At inference time, each span is assigned a class label based on its similar spans in the training set, where it is easy to understand how much each training instance contributes to the predictions. Through empirical analysis on named entity recognition, we demonstrate that our method enables to build models that have high interpretability without sacrificing performance. Neural networks have contributed to performance improvements in structured prediction. Instead, the rationales underlying the model predictions are dif-ficult for humans to understand (Lei et al., 2016). In practical applications, interpretable rationales play a critical role for driving human's decisions and promoting human-machine cooperation (Ribeiro et al., 2016). With this motivation, we aim to build models that have high interpretability without sacrificing performance. As an approach to this challenge, we focus on instance-based learning . Instance-based learning (Aha et al., 1991) is a machine learning method that learns similarities between instances. At inference time, the class labels of the most similar training instances are assigned to the new instances. This transparent inference process provides an answer to the following question: Which points in the training set most closely resemble a test point or influenced the prediction? This is categorized into example-based explanations (Plumb et al., 2018; Baehrens et al., 2010). Recently, despite its preferable property, it has received little attention and been underexplored. This study presents and investigates an instance-based learning method for span representations . A span is a unit that consists of one or more linguistically linked words. Why do we focus on spans instead of tokens? One reason is relevant to performance. Recent neural networks can induce good span feature representations and achieve high performance in structured prediction tasks, such as named entity recognition (NER) (Sohrab and Miwa, 2018; Xia et al., 2019), constituency parsing (Stern et al., 2017; Kitaev et al., 2019), semantic role labeling (SRL) (He et al., 2018; Ouchi et al., 2018) and coreference resolution (Lee et al., 2017). Another reason is relevant to interpretability. The tasks above require recognition of linguistic structure that consists of spans. Thus, directly classifying each span based on its representation is more interpretable than token-wise classification such as BIO tagging, which reconstructs each span label from the predicted token-wise BIO tags. Our method builds a feature space where spans with the same class label are close to each other. At inference time, each span is assigned a class label based on its neighbor spans in the feature space. We can easily understand why the model assigned the label to the span by looking at its neighbors. Through quantitative and qualitative analysis on NER, we demonstrate that our instance-based method enables to build models that have high interpretability and performance. To sum up, our main contributions are as follows. This is the first work to investigate instance-based learning of span representations. 1  Through empirical analysis on NER, we demonstrate our instance-based method enables to build models that have high interpretability without sacrificing performance. 1 Our code is publicly available at https://github. com/hiroki13/instance-based-ner.git . Neural models generally have a common technical challenge: the black-box property. The rationales underlying the model predictions are opaque for humans to understand. Many recent studies have tried to look into classifier-based neural models (Ribeiro et al., 2016; Lundberg and Lee, 2017; Koh and Liang, 2017). In this paper, instead of looking into the black-box, we build interpretable models based on instance-based learning. Before the current neural era, instance-based learning, sometimes called memory-based learning (Daelemans and Van den Bosch, 2005), was widely used for various NLP tasks, such as part-of-speech tagging (Daelemans et al., 1996), dependency parsing (Nivre et al., 2004) and machine translation (Na-gao, 1984). For NER, some instance-based models have been proposed (Tjong Kim Sang, 2002; De Meulder and Daelemans, 2003; Hendrickx and van den Bosch, 2003). Recently, despite its high interpretability, this direction has not been explored. One exception is Wiseman and Stratos (2019), which used instance-based learning of token representations. Due to BIO tagging, it faces one technical challenge: inconsistent label prediction. For example, an entity candidate World Health Orga-nization can be assigned inconsistent labels such as  B-LOC I-ORG I-ORG , whereas the ground-truth labels are  B-ORG I-ORG I-ORG . To remedy this issue, they presented a heuristic technique for encouraging contiguous token alignment. In contrast to such token-wise prediction, we adopt span-wise prediction, which can naturally avoid this issue because each span is assigned one label. NER is generally solved as (i) sequence labeling or (ii) span classification. 2 In the first approach, token features are induced by using neural networks and fed into a classifier, such as conditional random fields (Lample et al., 2016; Ma and Hovy, 2016; Chiu and Nichols, 2016). One drawback of this approach is the difficulty dealing with nested entities. 3 By contrast, the span classification approach, adopted in this study, can straightforwardly solve nested NER (Finkel and Manning, 2009; Sohrab and Miwa, 2018; Xia et al., 2019). 4 2 Very recently, a hybrid model of these two approaches has been proposed by Liu et al. (2019). NER can be solved as multi-class classification, where each of possible spans in a sentence is assigned a class label. As we mentioned in Section 2, this approach can naturally avoid inconsistent label prediction and straightforwardly deal with nested entities. Because of these advantages over token-wise classification, span classification has been gaining a considerable attention (Sohrab and Miwa, 2018; Xia et al., 2019). Formally, given an input sentence of T words X = ( w 1 , w 2 , . . . , w T ) , we first enumerate possible spans S ( X ) , and then assign a class label y  Y to each span s  S ( X ) . We will write each span as s = ( a, b ) , where a and b are word indices in the sentence: 1  a  b  T . Consider the following sentence. Here, the possible spans in this sentence are S ( X ) = { (1 , 1) , (1 , 2) , (1 , 3) , . . . , (4 , 5) , (5 , 5) } . Franz Kafka, denoted as s = (1 , 2) , is assigned the person type entity label ( y = PER ). Note that the other non-entity spans are assigned the null label ( y = NULL ). For example, a novelist, denoted as s = (4 , 5) , is assigned NULL . In this way, the NULL label is assigned to non-entity spans, which is the same as the O tag in the BIO tag set. The probability that each span s is assigned a class label y is modeled by using softmax function: P ( y | s ) = exp ( score ( s, y )) (cid:88) y (cid:48) Y exp ( score ( s, y (cid:48) )) . Typically, as the scoring function, the inner product between each label weight vector w y and span feature vector h s is used: score ( s, y ) = w y  h s . The score for the NULL label is set to a constant, score ( s, y = NULL ) = 0 , similar to logistic regression (He et al., 2018). For training, the loss function we minimize is the negative log-likelihood: L =  (cid:88) ( X,Y ) D (cid:88) ( s,y ) S ( X,Y ) log P ( y | s ) , where S ( X, Y ) is a set of pairs of a span s and its ground-truth label y . We call this kind of models that use label weight vectors for classification classifier-based span model . In Figure 1, an entity candidate Franz Kafka and the spans in the training set are mapped onto the feature vector space, and the label distribution is computed from the similarities between them. In this inference process, it is easy to understand how much each training instance contributes to the predictions. This property allows us to explain the predictions by spe-cific training instances, which is categorized into example-based explanations (Plumb et al., 2018). Formally, within the neighbourhood component analysis framework (Goldberger et al., 2005), we define the neighbor span probability that each span s i  S ( X ) will select another span s j as its neighbor from candidate spans in the training set: P ( s j | s i , D (cid:48) ) = exp ( score ( s i , s j )) (cid:88) s k S ( D (cid:48) ) exp ( score ( s i , s k )) . Here, we exclude the input sentence X and its ground-truth labels Y from the training set D : D (cid:48) = D \ { ( X, Y ) } , and regard all other spans as candidates: S ( D (cid:48) ) = { s  S ( X (cid:48) ) | ( X (cid:48) , Y (cid:48) )  D (cid:48) } . The scoring function returns a similarity between the spans s i and s j . Then we compute the probability that a span s i will be assigned a label y i : P ( y i | s i ) = (cid:88) s j S ( D (cid:48) ,y i ) P ( s j | s i , D (cid:48) ) . Here, S ( D (cid:48) , y i ) = { s j  D (cid:48) | y i = y j } , so the equation indicates that we sum up the probabilities of the neighbor spans that have the same label as the span s i . The loss function we minimize is the negative log-likelihood: L =  (cid:88) ( X,Y ) D (cid:88) ( s i ,y i ) S ( X,Y ) log P ( y i | s i ) , where S ( X, Y ) is a set of pairs of a span s i and its ground-truth label y i . At inference time, we predict  y i to be the class label with maximal marginal probability:  y i = arg max y Y P ( y | s i ) , where the probability P ( y | s i ) is computed for each of the label set y  Y . Efficient neighbor probability computation The neighbor span probability P ( s j | s i , D (cid:48) ) in Equation 1 depends on the entire training set D (cid:48) , which leads to heavy computational cost. As a remedy, we use random sampling to retrieve K sentences D (cid:48)(cid:48) = { ( X (cid:48) k , Y (cid:48) k ) } Kk =0 from the training set D (cid:48) . At training time, we randomly sample K sentences for each mini-batch at each epoch. This simple technique realizes time and memory efficient training. In our experiments, it takes less than one day to train a model on a single GPU 5 . Data We evaluate the span models through two types of NER: (i) flat NER on the CoNLL-2003 dataset (Tjong Kim Sang and De Meulder, 2003) and (ii) nested NER on the GENIA dataset 6 (Kim et al., 2003). We follow the standard training-development-test splits. Baseline We use a classifier-based span model (Section 3.1) as a baseline. Only the difference between the instance-based and classifier-based span models is whether to use softmax classifier or not. Encoder and span representation We adopt the encoder architecture proposed by Ma and Hovy (2016), which encodes each token of the input sentence w t  X with word embedding and character-level CNN. The encoded token representations w 1: T = ( w 1 , w 2 , . . . , w T ) are fed to bidirectional LSTM for computing contextual ones  h 1: T and  h 1: T . From them, we create h lstm s for each span s = ( a, b ) based on LSTM-minus (Wang and Chang, 2016). For flat NER, we use the representation h lstm s = [  h b   h a  1 ,  h a   h b +1 ] . For nested NER, we use h lstm s = [  h b   h a  1 ,  h a   h b +1 ,  h a +  h b ,  h a +  h b ] . 7 We then multiply h lstm s with a weight matrix W and obtain the span representation: h s = W h lstm s . For the scoring function in Equation 1 in the instance-based span model, we use the inner product between a pair of span representations: score ( s i , s j ) = h s i  h s j . Model configuration We train instance-based models by using K = 50 training sentences randomly retrieved for each mini-batch. At test time, we use K = 50 nearest training sentences for each sentence based on the cosine similarities between their sentence vectors 8 . For the word embeddings, we use the GloVe 100-dimensional embeddings (Pennington et al., 2014) and the BERT embeddings (Devlin et al., 2019). 9 6 We use the same one pre-processed by Zheng et al. (2019) at https://github.com/thecharm/ boundary-aware-nested-ner 7 We use the different span representation from the one used for flat NER because concatenating the addition features,  h a +  h b and  h a +  h b , to the subtraction features improves performance in our preliminary experiments. 8 For each sentence X = ( w 1 , w 2 , . . . , w T ) , its sentence vector is defined as the vector averaged over the word embeddings (GloVe) within the sentence: 1 T (cid:80) t w emb t . Overall F 1 scores We investigate whether or not our instance-based span model can achieve competitive performance with the classifier-based span model. Table 1 shows F 1 scores on each test set. 10 Consistently, the instance-based span model yielded comparable results to the classifier-based span model. This indicates that our instance-based learning method enables to build NER models without sacrificing performance. Effects of training data size Figure 2 shows F 1 scores on the CoNLL-2003 development set by the models trained on full-size, 1 / 2 , 1 / 4 and 1 / 8 of the training set. We found that (i) performance of both models gradually degrades when the size of the training set is smaller and (ii) both models yield very competitive performance curves. 10 The models using GloVe yielded slightly better results than those using BERT. One possible explanation is that subword segmentation is not so good for NER. In particular, tokens in upper case are segmented into too small elements, e.g., LEICESTERSHIRE  L, ##EI, ##CE, ##ST, ##ER, ##S, ##H, ##IR, ##E. Examples of retrieved spans The span feature space learned by our method can be applied to various downstream tasks. In particular, it can be used as a span retrieval system. Table 2 shows five nearest neighbor spans of an entity candidate Tom Moody. In the classifier-based span model, person-related but non-entity spans were retrieved. By contrast, in the instance-based span model, person ( PER ) entities were consistently retrieved. 11 This tendency was observed in many other cases, and we confirmed that our method can build preferable feature spaces for applications. Errors analysis The instance-based span model tends to wrongly label spans that includes location or organization names. For example, in Table 3, the wrong label LOC (Location) is assigned to Air France whose gold label is ORG (Organization). 11 The query span Tom moody was a cricketer at that time, and some neighbors, Ian Botham and Darren Gough, were also cricketers. Note that by looking at the neighbors, we can understand that country or district entities confused the model. This implies that prediction errors are easier to analyze because the neighbors are the rationales of the predictions. Generalizability Are our findings in NER generalizable to other tasks? To investigate it, we perform an additional experiment on the CoNLL-2000 dataset (Tjong Kim Sang and Buchholz, 2000) for syntactic chunking. 12 While this task is similar to NER in terms of short-span classification, the class labels are based on syntax, not (entity) semantics. In Table 4, the instance-based span model achieved competitive F 1 scores with the classifier-based one, which is consistent with the NER results. This suggests that our findings in NER are likely to generalizable to other short-span classification tasks. Future work One interesting line of future work is an extension of our method to span-to-span relation classification, such as SRL and coreference resolution. Another potential direction is to apply and evaluate learned span features to downstream tasks requiring entity knowledge, such as entity linking and question answering. We presented and investigated an instance-based learning method that learns similarity between spans. Through NER experiments, we demonstrated that the models build by our method have (i) competitive performance with a classifier-based span model and (ii) interpretable inference process where it is easy to understand how much each training instance contributes to the predictions. This work was partially supported by JSPS KAKENHI Grant Number JP19H04162 and JP19K20351. We would like to thank the members of Tohoku NLP Laboratory and the anonymous reviewers for their insightful comments. 12 The models are trained in the same way as in nested NER.
abstain objective method abstain objective abstain abstain abstain objective method abstain abstain abstain abstain abstain objective abstain method abstain other abstain abstain abstain method abstain abstain objective objective objective objective other abstain other other other method other other other other other other other objective other other other other other abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain method other abstain method abstain abstain method abstain method method abstain method method abstain abstain method method abstain method abstain method method method method method method method method other abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective objective abstain abstain other other other