k NN - CM : A Non-parametric Inference-Phase Adaptation of Parametric Text Classifiers (2023)

Abstract: Semi-parametric models exhibit the properties of both parametric and non-parametric modeling and have been shown to be effective in the next-word prediction language modeling task. However, there is a lack of studies on the text-discriminating properties of such models. We propose an inference-phase approach— k -Nearest Neighbor Classification Model ( k NN-CM)—that enhances the capacity of a pre-trained parametric text classifier by incorporating a simple neighborhood search through the representation space of (memorized) training samples. The final class prediction of k NN-CM is based on the convex combination of probabilities obtained from k NN search and prediction of the classifier. Our experiments show consistent performance improvements on eight SuperGLUE tasks, three adversarial natural language inference (ANLI) datasets, 11 question-answering (QA) datasets, and two sentiment classification datasets.

## introduction the recent advancements in natural language processing (nlp) have largely been attributed to the learning of contextual representations of text from large language models acting as a backbone. most of these language models, such as versions of bert @xcite , gpt @xcite , t5 @xcite , are parametric, i.e., they encode information required to solve a task purely in its parameters. a parametric model, irrespective of the size of the dataset, assumes that the output variables are dependent on the input variables through a predefined class of functions. the exact function is ascertained by learning its fixed set of parameters. for instance, a linear regression model fits a set of parameters in a function that defines a supposedly linear relationship between (independent) input variables and (dependent) output variables. as a complex composition of many linear regressions, many neural architectures, such as transformerbased models @xcite , can thus be classified as purely parametric. however, there has been little research on the utility of non-parametric models for nlp. in contrast to parametric models which need a predefined function, such as a linear model, non-parametric models seek training data to help define the function form itself. thus, they provide flexibility to fit a wide range of possible shapes of ground truth function. a widely known non-parametric model is the k-nearest neighbor (knn) where inference on test samples are drawn from the information provided by the neighborhood formed by train set samples @xcite . a knn model provides memorization capabilities and captures rare patterns from the training set that otherwise are ignored by a parametric model (as studied by @xcite ). language models (lms) with non-parametric properties have shown impressive gains in next-word prediction tasks @xcite @xcite . additionally, these models do not need explicit parameter learning via optimization, thus cutting the model training time completely-the lack of such characteristics in a purely parametric model motivates the proposed approach. this work explores the importance of querying neighbors to solve classification tasks in the text domain. we hypothesize that underlying language model representations have a high-dimensional spatial proximity relation between input instances which can be leveraged to enhance prediction performance-beyond the capacity of the classifier. hence, we propose a semi-parametric model knn-cm (k nearest neighbor classification model) which constitutes a parametric classifier and a nonparametric memory (i.e. datastore) for neighborhood retrieval. in reinforcement learning (rl), classifiers are often employed as tools to aid policy learning or state representation. they can help estimate the quality of different actions or policies, and classify text into different categories, thus possessing high utility for the recent paradigm shifts in generative models @xcite . contributions. we propose an inference phase semi-parametric modeling approach knn-cm that enhances the capacity of a given parametric classifier model by incorporating an external memory datastore. in the inference phase, knn-cm performs a k-neighborhood search through the datastore and merges the neighborhood predictions with the prediction obtained from the parametric classifier. since the expansion of the cm to knn-cm happens in the inference phase, it allows one to enhance the capacity of most of the existing pretrained neural classifiers. by performing an extensive set of experiments, we demonstrate the importance of neighborhood search through the memorized samples on eight superglue tasks, three nli datasets, 11 qa tasks, and two aspect-based sentiment classification tasks. we also show how the semi-parametric method can still outperform cm in out-of-domain scenarios. furthermore, we test knn-cm by tasking it under various cases of domain adaptation. since knn-cm introduces prediction latency compared with cm, we demonstrate how one can employ an entropy-based divergence measure to filter out the samples that use knn retrieval facility. additionally, we illustrate the importance of memorization in the low-resource scenario. in the end, we point out potential extensions of the proposed approach in conversation modeling and continual learning. ## related work computer vision. for the image captioning task, @xcite ; @xcite proposed nearest neighbor baselines where they assign an unseen sample the (consensus of) captions of the training set images closest to it. @xcite studied the utility of (transformed) neighborhood while performing few-shot object classification tasks. knn has also been used to analyze learned image representations @xcite as well as to classify images @xcite . for instance, @xcite performed image classification without class supervision but considering every instance as a class. recommendation systems. for session-based recommendation (based on current user interaction with the system), @xcite ; @xcite showed that a neighborhood-based model output performs a gru-based neural model on the studied tasks. knn has been widely popular in collaborative filtering (memory-based) where the recommendation is done by the user or item neighborhood search @xcite . language models. the advantage of querying nearest neighbors from a set of pre-trained lm's representations of the training set (datastore) was first observed by @xcite by proposing knn-lm. this is followed by several works such as improving retrieval speed @xcite , knn-lm adaptation @xcite , adaptive interpolation @xcite , and masked language modeling @xcite . to the best of our knowledge, this work is the first attempt to extensively study the importance of neighborhood search for text classification to enhance the capacity of parametric classifiers in the inference phase. figure 1 gives an illustrative to motivate the idea. ## methodology for a given domain, we obtain training data s:={(x 1 , y 1 ) . . . (x n , y n )} where x i denotes input text in instance space x and y i is the label of its class defined in label space y. a learning system, a classifier, comes up with a prediction rule (hypothesis) h that maps the input from x to a probability distribution over class labels in y. classifier (cm). without the loss of generality, we consider a cm constitutes a backbone large language model and a trainable classification head. during the pre-training phase, the language model is assumed to have learned semantic highdimensional text representations that can be tuned to solve a given downstream task. the input to cm is a sequence of tokens @xmath0, . . . , w n } and output is a probability distribution over the class labels. cm is tasked to approximate the ground truth input-output mapping by learning parameters of a predefined function, i.e., the neural connections within cm. we denote the task-specific trained parametric predictor by h cm . there are several aspects of this formulation: changing a model's bias-variance characteristics directly affects the model's capacity to fit a wider class of functions foot_1 . time and space complexity. similarity search can be computationally expensive and introduce high memory requirements for each task, thus we use faiss @xcite )-an efficient similarity search algorithm and clustering (indexing) algorithm of high dimensional data. the clustering of similar vectors in high dimensions obviates the need to search through the whole training set (datastore). for small-scale datasets, we use in-dexflatl2 which queries through all the vectors in the datastore. the complexity is thus o(n) where n is the number of elements in the datastore. for large-scale datastores, we use indexflativf to first cluster the vectors in datastore and then perform an nn search in each cluster. the time complexity of this method is o(n c m) where n c and m denote the number of clusters and the average number of elements in clusters, respectively. the space complexity of indexflatl2 is o(nd s ) and indexflativf is o(nd s + md s ), where d s denotes the dimensionality of the vector in the datastore. contrary to non-parametric, the time and space complexity of a parametric model, such as cm, is predefined and does not vary with the number of train samples. ## results and discussion however, the improvement in wic is comparably less (≈0.3%). after investigation, we found that cm and knn share the same set of samples where they make erroneous predictions. the conclusions are made on relatively low improvements on boolq when compared with multirc and record. amongst all, we observe a huge improvement for over 14% in copa. we notice that knn alone can surpass the baseline copa accuracy by over three points. while a combination of both gives a boost of over eight points in both performance matrices. in qa tasks ( the instance accuracy of knn is 80.45% while the cm performance is 80.98% with errors made on a similar set of samples. out-of-domain performance. we retrieve su-perglue diagnostic datasets ax b and ax g (test only) and perform anli out-of-domain evaluations foot_4 . for ax b and an observed poorer performance (by ≈1%) of knn-cm on ax g . to investigate it further, we found knn to improve the precision and recall score of the poor performing class by slightly trading-off with the precision and recall of higher performing class, the overall impact improves f1 significantly, however, accuracy degrades. ## conclusion in this work, we presented knn-cm, a semiparametric paradigm that augments the inference phase with neighborhood search through the training set. we studied the impact of adding nonparametric characteristics to a parametric classifier on 24 language understanding tasks. we further demonstrated the generalizability of knn-cm by studying their out-of-domain and domain adaptation performance. we also showed its efficacy in low-resource scenarios where cm performance reduces dramatically and neighborhood search emerges as a savior. toward the end, we leave a few important remarks on utterance classification and neighborhood weighting that carry the potential to motivate future research directions, which we elaborate on in the limitations section.