Minimizing Annotation Effort via Max-Volume Spectral Sampling (2021)

Abstract: We address the annotation data bottleneck for sequence classification. Specifically we ask the question: if one has a budget of N annotations, which samples should we select for annotation? The solution we propose looks for diversity in the selected sample, by maximizing the amount of information that is useful for the learning algorithm, or equivalently by minimizing the redundancy of samples in the selection. This is formulated in the context of spectral learning of recurrent functions for sequence classification. Our method represents unlabeled data in the form of a Hankel matrix, and uses the notion of spectral max-volume to find a compact sub-block from which annotation samples are drawn. Experiments on sequence classification confirm that our spectral sampling strategy is in fact efficient and yields good models.

## introduction in the later years the field of nlp has witnessed great progress on supervised machine learning methods for sequence classification. however, most of these methods require large amounts of annotated training data. because of this, whenever a new nlp application needs to be developed, data annotation becomes the main bottleneck in terms of cost and time. for example, a defense research analyst might wish to quickly train a text classifier to detect emergent socio-political events in a given conflict area. since there might be only a few experts on the subject their time will be costly. therefore, the expert should be able to train models fast with minimal annotation effort. to address the annotated data bottleneck, researchers have proposed active learning approaches that develop sampling strategies designed to minimize the number of annotations required to train a model @xcite @xcite . most active learning proposals are based on two figure 1 : representing unlabeled data in the form of a hankel matrix can be very effective to uncover latent structure of the data. we present a sampling technique to leverage this structure. main strategies. the first strategy uses model uncertainty and selects samples for which the prediction of the current model is the least confident. this strategy might not work very well during the first iterations of active learning, when the predictions of the model are unstable. furthermore, the model uncertainty criteria cannot be applied in the first iteration, when no model has been trained and one needs to resort to other cold start sampling strategies @xcite . to overcome the limitations of the uncertainty approach other researchers have proposed sampling strategies that attempt to maximize the diversity of the selected samples @xcite . besides the selection strategy, another dimension of an active learning method is the type of annotation feedback that it exploits. for example, in text classification the annotations can consist of labels for complete texts, phrases, sentences, features, rules or labeling functions @xcite @xcite @xcite . in this paper we focus on the problem of training sequence classification models under an annotation budget constraint and with no prior trained model for the task. this is sometimes referred as the cold start problem. we consider a setting in which the annotation feedback is at the level of phrases. our goal is to develop an efficient algorithm that can answer the question: if one has a budget of n annotations, which phrases should we select to annotate? notice that active sampling under an annotation budget is different from the classical active learning scenario. in the classical setting, the learning algorithm has access to a large unlabeled data pool, and in a series of iterations it alternates between sampling data to annotate and training a new model. in contrast, when training under budget constraints, the focus is on the initial setting, when there is no model that can guide the selection and when all that is available to the selection algorithm is the unlabeled data pool. the second difference is that our goal is to find the optimal set of size n , i.e. the selection criteria should be able to score a set or batch of phrases. in that sense our work is more related to cover-set approaches @xcite . our proposed solution for the problem of learning under a budget constraint follows a diversity sampling strategy. that is, given a fixed budget our batch selection method attempts to maximize the amount of useful information contained in the batch. or equivalently, it tries to minimize annotation redundancy in the selected batch. more precisely, our approach is inspired in methods that minimize annotation redundancy by uncovering latent structure in the input domain @xcite . intuitively, imagine a classification problem with k classes. if we had access to a clustering of the data into k groups that perfectly align with the target classes only k labeled points would be needed. that is, we would label a representative sample for each cluster. of course, the perfect clustering might not exist but the point is that by discovering relevant latent structure one can minimize annotation redundancy and ask only for the annotations that are really necessary. we take this basic idea and translate it to the sequence classification setting. essentially, our method induces an implicit soft clustering of phrases (i.e., subsequences) so that we only need annotations for one phrase in each cluster. following the classical distributional principle, we con-sider two phrases to be similar if they can appear in similar contexts. our technical contribution exploits ideas from the theory of spectral and hankel-based learning methods for estimating recurrent sequence prediction functions with linear state-dynamics @xcite @xcite . we reduce the problem of training sequence classification models under annotation budget constraints to the problem of selecting a high-volume matrix sub-block (i.e. a sub-block of high rank) from a hankel matrix (computed from the unlabeled pool) that captures key statistics of the sequence domain distribution. see figure 1 for a sketch. to our knowledge, sampling strategies reduced to spectral matrix operations is a novel technical approach. recent methods for cold-start sampling with an annotation budget have considered clustering embeddings of sentences derived from bert @xcite , either as a single shot sampling (like our method), or by iterative fine-tuning of the embeddings used for sampling. we highlight two main contributions: the paper is organized as follows: section 2 starts with a description of linear recurrent sequence functions, and then provides the spectral learning background necessary to understand our sampling strategy, and in particular the concept of hankel matrices. section 3 presents the proposed phrase selection method based on selecting a max-volume sub-block from a hankel matrix representing the unlabeled pool. section 4 presents our experiments on text classification. finally, section 5 concludes the paper. ## linear rnns and hankel matrices in this paper we work with simple recurrent neural networks that use linear functions (matrix products) to compute hidden-state vectors along the sequence. in this setting, we describe connections to spectral learning, and specifically to the hankel matrix of a recurrent sequence model. this is a central tool to derive the sampling strategy. a recurrent neural network (rnn) takes as input a sequence x and outputs a vector of k real numbers, f : σ → r k , where @xmath0. we denote as σ the set of all finite sequences, and we use it as a domain of our functions. an rnn with hidden dimension d and output dimension k is defined as a tuple: the functions γ h and γ y are activation functions, and in this paper we focus on simply using the identities. the most common use of general rnns in nlp is language modeling. in this case the model is set to predict the conditional probability of the next symbol (with @xmath1, and by means of the chain rule, the model defines a distribution over the language and is trained to generate sequences left-to-right. another popular use is sequence classification, where the model computes a classification score for each of the k labels of a task, given input sequences x 1:n . another application of rnns, which is less common in the literature, is to frame language modeling as a density estimation task, where the model estimates the probability of a full sentence directly. in this case, the rnn predicts a single score (i.e. @xmath2:n , and we can regard this as a regression learning problem, i.e. learn a real-valued function that approximates the target probabilities given the hidden state vector of the input sequence. finally, instead of modeling the probability of full sequences, rnns can directly approximate the moments of the distribution. that is, learn a function from σ * → r that estimates the expected number of times of observing a subsequence x 1:n in a random sequence sampled from the target distribution. modeling moments, such as ngram statistics, has the advantage that the target statistics are less sparse than full sequences even for long ngrams. ## phrase sampling via max-volume optimization in this section we describe a deterministic phrase sampling method for sequence classification. we assume an unlabeled pool of sequences, and the goal is to select an annotation batch. once selected, the batch will be first annotated, and then a model will be learned from it. the sampling strategy we describe selects phrases for annotation, i.e. subsequences of sentences (i.e. ngrams) found in the unlabeled pool. notice that when learning a sequence model with the spectral method, we only use the information contained in the selected hankel sub-block. in the previous section we discussed the importance of selecting a small sub-block of the hankel matrix for computational efficiency. in such setting, it is assumed that there is enough training data to compute all the entries of the hankel. a sub-block of h is selected to ease the computation of the svd, which is required to infer the model parameters. the problem that we address in this paper is different: the focus is annotation efficiency, not computational efficiency. in our case, we assume that we need to estimate the hankel matrices h l of each label l. initially, we do not have samples to compute any of its entries, so we ask the question: is there a way to select the samples to annotate so that it provides the most information about the target class distributions? or equivalently, is there a way to request annotations so that it gives us the most information about h l ? our solution uses an approximation of h l given by the hankel matrix h u associated with a language model of the unlabeled distribution. we use h u to pick the most informative entries of h l , i.e. those for which we will request annotations. intuitively, each prefix in the matrix is described as a distribution over suffixes, and the analogue for suffixes. the proposed approach will select prefix and suffix rows that are the most uncorrelated, so that annotating their compositions will provide the most information about h l . in essence, this selects a set of representative prefix and suffix prototypes in the latent space of prefix and suffix embeddings derived from h u . the difference between the computational and sampling problems has an analogue in recommendation systems based on collaborative filtering. in this case, one creates a matrix where rows are users and columns are movies, and the corresponding entry has the rating given by a user to a movie. some entries are observed and some are missing, the matrix is assumed to be low-rank, and the goal is to complete the matrix and predict the ratings that users will give to unseen movies. in this context, the computational challenge is to perform svd of a potentially very large matrix, which is required for low-rank matrix completion. in contrast, the sampling problem, assumes that we can query users for ratings on specific movies. the optimal sampling question is: what is the most informative subset of user-movie ratings to request so that from the chosen subset we can predict unseen user-movie ratings? ## experiments we evaluate the spectral sampling method on two sentence classification tasks. we compare our sam- ## conclusions sequence distributions that can be modeled with latent state models have low-rank signatures. that is, the whole distribution can be learned from statistics over a small number of key phrases. the main contribution of our work is to show how we can leverage that property to design efficient sampling strategies for sequence classification under annotation budget constraints. the idea is quite simple: while for a given category we cannot know a priori (that is without labeled sequences) its low-rank signature (and key phrases), we can try to estimate the signature from unlabeled domain data. using that approximation we can design an efficient way of selecting phrases to label. our experiments show that with this strategy we can obtain reasonable sequence classification models under small budget constraints. to the best of our knowledge our proposal is the first sampling strategy to implicitly exploit low-rank embeddings of domain phrases. once a low-rank hankel signature has been found we could imagine several different annotation strategies for estimating the relevant statistics. this work is just a first step where we consider one of the simplest of such strategies. however, future work should explore the space of annotation strategies taking into account what feedback would result in the best estimation, and what is easiest for the human annotator. we see this work as opening the door for future research on interactive machine learning for sequence modeling where the annotation feedback strategy is designed to exploit the structural properties of the domain. our sampling strategy contrasts with recent work in active learning, which exploits bert-based embeddings. we empirically observed that the performance of our combo is better for very low annotation budget, but eventually the neural approaches improve and gradually achieve state-of-the-art results. thus, one natural question for future research is if our sampling strategy can be coupled with more expressive neural classifiers. a second re-lated question is how to use the spectral models trained with max-volume sampling to warm-start neural approaches.