$k$-Nearest Neighbor Augmented Neural Networks for Text Classification
Zhiguo Wang Wael Hamza Linfeng Song






k-Nearest Neighbor Augmented Neural Networks for Text Classification
    
Zhiguo Wang1, Wael Hamza1, Linfeng Song2

1 IBM T.J. Watson Research Center, Yorktown Heights, NY 10598 

2 Department of Computer Science, University of Rochester, Rochester, NY 14627






    
===================================================================================================================================================================================================



In recent years, many deep-learning based models are proposed for text classification.
This kind of models well fits the training set from the statistical point of view. 
However, it lacks the capacity of utilizing instance-level information from individual instances in the training set. 
In this work, we propose to enhance neural network models by allowing them to leverage information from k-nearest neighbor (kNN) of the input text. 
Our model employs a neural network that encodes texts into text embeddings.
Moreover, we also utilize k-nearest neighbor of the input text as an external memory, and utilize it to capture instance-level information from the training set. 
The final prediction is made based on features from both the neural network encoder and the kNN memory. 
Experimental results on several standard benchmark datasets show that our model outperforms the baseline model on all the datasets, and it even beats a very deep neural network model (with 29 layers) in several datasets. 
Our model also shows superior performance when training instances are scarce, and when the training set is severely unbalanced.
Our model also leverages techniques such as  
semi-supervised training and transfer learning quite well.





§ INTRODUCTION


Text classification is a fundamental task in both natural language processing and machine learning research. 
Its goal is to assign specific labels to texts written in natural languages. Based on the definition of the specific labels, text classification has many practical applications, 
e.g., sentiment analysis <cit.> and news categorization <cit.>.

In recent years, with the renaissance of neural networks, many deep-learning based methods were proposed for text classification tasks <cit.>.
Basically, most of these methods construct some kinds of neural networks to encode a text into a distributed text embedding, and then predict the category of the text solely based on it. 
In the training stage, network parameters are optimized on the training set. 
In the testing stage, the entire training set can be discarded, and only the trained model is used for prediction. 
This method has acquired the state-of-the-art performance in many tasks. 
However, because it abstracts the training set from a statistical point of view, it cannot utilize instance-level information from individual instances in the training set very well. 
For example, in the news categorization task, the following news is annotated as the “Business” category.

Eastman Kodak Company and IBM will work together to develop and manufacture image sensors used in such consumer products as digital still cameras and camera phones .

A neural network model with the state-of-the-art performance will incorrectly predict it into the “Sci/Tech” category, 
because, in the training set,  up to 1,166 instances about “IBM” are annotated as the “Sci/Tech” category, 
whereas only 278 instances about “IBM” are annotated as the “Business” category. 
From the statistical point of view, we cannot blame our model, because the single word “IBM” is a very strong signal for the “'Sci/Tech' category. 
However, when we look at the 278 instances with the “Business” category, we found a much relevant instance:

IBM and Eastman Kodak Company have agreed to jointly develop and manufacture image sensors for mass - market consumer products , such as digital still cameras .

Therefore, if we can make use of category information of the relevant training instance, we will have a big chance to correct the error.

On the other hand, instance-based (or non-parametric) learning <cit.> provides us a good method to capture instance-level information. 
k-nearest neighbor (kNN) classification is the most representative method, where a predication is made for a new test instance only based on its kNN. 
<cit.> showed that a better performance can be achieved if combining the model-based learning and the instance-based learning.

Therefore, in this work, we propose to enhance neural network models with information from kNN. 
Our model still employs a neural network encoder to abstract global information from the entire training set, and to encode texts into text embeddings. 
Moreover, we also take the kNN of the input text as an external memory, and utilize it to capture instance-level information from the training set. 
Then, the final prediction is made based on features from both the neural network encoder and the kNN memory. 
Concretely, for each input text, we first find its kNN in the training set. 
Second, a neural network encoder is utilized to encode both the input text and its kNN into text embeddings. 
Third, based on the text embeddings of the input text and the kNN, we calculate attention weights for each neighbor. 
Based on these attention weights, the model calculates an attentive kNN label distribution and an attentive kNN text embedding. 
The final prediction is made based on three sources of features: the text embedding of the input text, the attentive kNN label distribution, and the attentive kNN text embedding. 
Experimental results on several standard benchmark datasets show that our model outperforms the baseline model on all the datasets, and it even beats a very deep neural network model (with 29 layers) in several datasets. 
Our model also shows superior performance when training instances are scarce, and when the training set is severely unbalanced.
Our model also leverages techniques such as  
semi-supervised training and transfer learning quite well.

In following parts, we start with the description of our model, then evaluate the model on some standard benchmark datasets and different experimental settings. We then talk about related work, and finally conclude this work.






§ MODEL



In this section, we propose a model to capture both global and instance-level information from the training set for text classification tasks. 
To capture global information, we train a neural network encoder to encode texts into an embedding space based on all training instances and their category information. 
To capture instance-level information, for each input text, we search its kNN from the training set, and then take the kNN as an external memory to augment the neural network.

Figure <ref> shows the architecture of our model. 
The blue flow 1 is the typical method for text classification,  where an input text is encoded into a text embedding by a neural network “Text Encoder”, and then a prediction is made based on the text embedding. 
The remaining flows are our kNN memory, which employs the attention mechanism to extract some instance-level features for prediction. Formally, given an input text x, its kNN {x_1,...,x_k,...,x_K} and their correct labels y and {y_1,...,y_k,...,y_K}, our task can be formulated as estimating a conditional probability (y|x,x_1,...,x_K,y_1,...,y_K) based on the training set, and predicting the labels for testing instances by 

    y^* = _y ∈𝒜(y)(y|x,x_1,...,x_K,y_1,...,y_K),

where 𝒜(y) is a set of all possible labels.



 §.§ Text Encoder


Text Encoder is a critical component in both typical models and our model. Its task is to encode an input text into a text embedding. Typically, an encoder encodes a text in two steps: (1) word representation step represents all words in the text as word embeddings or character embeddings <cit.>; and (2) sentence representation step composes the word embedding sequence into a fixed-length text embedding with the Convolutional Neural Networks (CNN) <cit.> or the Long Short-Term Memory Network (LSTM) <cit.> models. For example, <cit.>, <cit.>, and <cit.> employed the CNN model to encode texts, <cit.> utilized the LSTM model to represent texts, and <cit.> combined both the CNN and the LSTM.

In this work, we utilize a LSTM network to encode texts. For word representation step, 
inspired by <cit.> and <cit.>, 
we construct a d-dimensional vector for each word with two components: a word embedding and a character-composed embedding. The word embedding is a fixed vector for each individual word, which is pre-trained with GloVe <cit.> or word2vec <cit.>. The character-composed embedding is calculated by feeding each character (also represented as a vector) within a word into a LSTM. For sentence representation step, we apply a bi-directional LSTM (BiLSTM) to compose the word representation sequence, and then concatenate the two vectors from the last time-step of the BiLSTM (both the forward and the backward directions) as the final text embedding.



 §.§ kNN Memory


kNN memory is the core component of our model. 
Its goal is to capture instance-level information for each input text from its kNN. This component includes the following six procedures.



  
Searching for the kNN 
This procedure, corresponding to the black flow 2 in Figure <ref>, is to find the kNN of the input text from the training set.
In order to efficiently search over the large training set, we employ a traditional information retrieve method to find the kNN. 
We first build an inverted index for all texts in the training set with the open source toolkit Lucene (https://lucene.apache.org/). 
Then, we take the input text as the query, and utilize the simple and effective BM25 ranking function <cit.> to retrieve the kNN from the inverted index.




  
Encoding for the kNN
This procedure encodes all the kNN into text embeddings, which corresponds to the yellow flow 3 in Figure <ref>. We re-utilize the Text Encoder described above, and apply it to each of the K neighbors individually.



  
Calculating the neighbor attention
This procedure corresponds to the gray flow 4 in Figure <ref>, and its goal is to calculate similarities (neighbor attention) between the input text and each of the K neighbors in the embedding space.
Formally, let's denote the text embeddings for the input text x and the k-th neighbor x_k as h and h_k, which are l-dimensional vectors calculated by the Text Encoder.
Theoretically, any similarity metrics will fit here.
Inspired from <cit.>,
here, we adopt the effective multi-perspective cosine matching function  f_s to compute similarities between two vectors h and h_k: 


    s_k = f_s(h,h_k;W)

where W∈^I × l is a trainable parameter with the shape I × l, I is a hyper-parameter to control the number of perspectives, and the returned value s_k is a I-dimensional vector s_k=[s_k^1,...,s_k^i,...,s_k^I]. Each element s_k^i ∈s is a similarity between h and h_k from the i-th perspective, and it is calculated by the cosine similarity between two weighted vectors

    s_k^i=cosine(W_i ∘h, W_i ∘h_k)

where ∘ is the element-wise multiplication, and W_i is the i-th row of W, which controls the i-th perspective and assigns different weights to different dimensions of the l-dimensional text embedding space.

We set I=1 for the illustration in Figure <ref>, therefore the neighbor attention is just a vector and each neighbor has only one similarity to the input text. However, for the experiments in following sections, we will utilize multiple perspectives (I>1), and each neighbor could have multiple similarities to the input text.



  
Calculating the attentive kNN label distribution Based on the neighbor attentions, we calculate the attentive kNN label distribution by weighted summing up the label distributions of all kNN (the green flow 5 in Figure <ref>).
Formally, let's denote the label distribution of the k-th neighbor x_k as y_k, which is an one-hot c-dimensional vector for the correct label y_i, and c is the number of all possible labels in the classification task. Given the label distributions and the neighbor attentions of all kNN, we calculate the i-th perspective of the attentive kNN label distribution by

    ŷ_i=∑_k=1^K s_k^i * y_k

where * is an operation to multiply the left scalar with each element of the right vector.
Then, the final attentive kNN label distribution ŷ is the concatenation of {ŷ_1,...,ŷ_i,...,ŷ_I} from all I perspectives.



  
Calculating the attentive kNN text embedding
Similarly, the attentive kNN text embedding is the weighted sum of text embeddings of all kNN (the orange flow 6 in Figure <ref>).
Given the text embeddings and neighbor attentions of all kNN, we calculate the i-th perspective of the attentive kNN text embedding by

    ĥ_i=∑_k=1^K s_k^i * h_k

Then, the final attentive kNN text embedding ĥ is the concatenation of {ĥ_1,...,ĥ_i,...,ĥ_I} from all I perspectives.



  
Concatenating all features to make the prediction
As the final procedure, we concatenate three sources of features (or vectors): the input text embedding h, the attentive kNN label distribution ŷ, and the attentive kNN text embedding ĥ. Then, a fully-connected layer with the softmax function is applied to make the final prediction.




§ EXPERIMENTS





  
Datasets



We evaluate our model on eight publicly available datasets from <cit.>. Here are the brief descriptions for all datasets.


  * AG's News: This is a news categorization dataset. All news articles are obtained from the AG's corpus of news article on the web. Each news belongs to one out of the four labels {World, Sports, Business, Sci/Tech}.

  * Sogou News: This is a Chinese news categorization dataset. All news articles are collected from SogouCA and SogouCS news corpora <cit.>. Each news article belongs to one out of the five categories {sports, finance, entertainment, automobile, technology}. All Chinese characters have been transformed into pinyin (a phonetic romanization of Chinese).

  * DBPedia: This dataset is designed for classifying Wikipedia articles into 14 ontology classes from DBpedia. Each instance contains the title and the abstract of a Wikipedia article.

  * Yelp Review Polarity/Full: This is a sentiment analysis dataset. All reviews are obtained from the Yelp Dataset Challenge in 2015. Two classification tasks are constructed from this dataset. The first one predicts the number of stars the user has given, and the second one predicts a polarity label by considering stars 1 and 2 as negative, and 3 and 4 as positive.

  * Yahoo! Answers dataset: This is a topic classification dataset. The dataset is obtained from Yahoo! Answer Comprehensive Question and Answer version 1.0 dataset. Each instance includes the question title, the question content and the best answer. And each instance belongs to one out of 10 topics.

  * Amazon Reviews Polarity/Full: This is another sentiment analysis dataset. All reviews are obtained from the Stanford Network Analysis Project (SNAP). Similar to the Yelp Review dataset, a Full version and a Polarity version of the dataset are constructed.

The original datasets didn't provide the devsets. To avoid tuning model parameters on the test sets, for each dataset, we build a devset by randomly holding out 500 instances for each class from the original training set, and take the remaining instances as our new training set. Table <ref> shows the statistics of all the datasets.





  
Experiment Settings
We initialize word embeddings with the 300-dimensional GloVe word vectors pre-trained from the 840B Common Crawl corpus <cit.>. 
For the out-of-vocabulary (OOV) words, we initialize their word embeddings randomly.  
For the character-composed embeddings, we represent each character with a 20-dimensional randomly-initialized vector, and feed characters of each word into a LSTM layer to produce a 50-dimensional vector. 
We set the hidden size to 100 for our BiLSTM Text Encoder.
We train the entire model from end-to-end, and minimize the cross entropy of the training set. We use the ADAM optimizer <cit.> to update parameters, and set the learning rate as 0.0001. 
During training, we do not update the pre-trained word embeddings. For all experiments, we iterate over the training set for 15 times, and evaluate the model on the devset at the end of each iteration. Then, we pick the model which works the best on the devset as the final model, and all the results on the test sets are performed from the final models.












 §.§ Properties of our Model

There are several hyper-parameters in our model.
The choices of them may affect the final performance. In this subsection, we conduct some experiments to demonstrate the properties of our model, and select a group of proper hyper-parameters for subsequent experiments.
All experiments in this subsection are conducted on the AG's News dataset, and evaluated on the devset.

First, we study the effectiveness of the three sources of features: the input text embedding (text-embedding), the attentive kNN label distribution (attentive-kNN-label), and the attentive kNN text embedding (attentive-kNN-text). 
We create seven models according to different feature configurations. 
For all models, we set K=20 for the number of kNN, and I=20 for the number of perspectives in our multi-perspective cosine matching function (Equation (<ref>)).  
Table <ref> shows the corresponding results on the devset, where M1 is our BiLSTM model without using the kNN memory, M2/M3/M4 are the models only utilizing the kNN memory, and M5/M6/M7 are the models leveraging both the text encoder and the kNN memory.
From this experiment, we get several interesting observations: 
(1) when comparing M2 with M1, we find that only utilizing the label information from the kNN can achieve a competitive performance to the typical BiLSTM model;
(2) the performance from M3 is on par with M1, which indicates that features solely extracted from the kNN (but without label information) can represent the input text very well;
(3) the performance of M4 shows that considering both the label and the text information from the kNN achieves a better performance than the typical BiLSTM model, which shows the effectiveness of our kNN memory;
(4) from the results of M5/M6/M7, we can see that combining the kNN memory with our BiLSTM text encoder achieves even better accuracies.
The best accuracy is obtained by M7. 
Therefore, we will use this configuration for the subsequent experiments.

Second, to test the influence of the kNN, we vary K from 1 to 20. 
Figure <ref> shows the accuracy curve, where K=0 corresponds to the performance from our BiLSTM without using the kNN memory. 
We can see that even with only one neighbor (K=1), our model gets a significant improvement over the BiLSTM model.
When increasing the number of neighbors, the performance improves at the beginning, and then drops when K exceeds 8. 
One possible reason is that the neighbors become noisy when increasing K. In the subsequent experiments, we fix K=5.

Third, we investigate the influence of the hyper-parameter I in our multi-perspective cosine matching function (Equation (<ref>)) by varying I from 1 to 20. 
We build a baseline by replacing Equation (<ref>) with the vanilla cosine similarity function. Both of the baseline and our model with I=1 calculate a single attention for each neighbor, but the difference is that our model assigns some trainable parameters to each dimension of the embedding space.

Figure <ref> shows the accuracy curve, where I=0 corresponds to the performance of our baseline.
We find that even if utilizing only one perspective (I=1), our model achieves a significant improvement than the baseline. 
When increasing the number of perspectives, the accuracy improves at the beginning, and then decreases after I is over 5. 
Therefore, we fix I=5 in the subsequent experiments.



 §.§ Comparison with the State-of-the-art Models



We construct two models to evaluate on all of the test sets. 
The first model is the baseline: our BiLSTM model without using the kNN memory (M1 in Table <ref>). 
The second model is the BiLSTM model with the kNN memory (M7 in Table <ref>). 
Table <ref> gives the experimental results. 
We find that by utilizing the kNN memory, our BiLSTM with kNN model outperforms the baseline on all datasets. 
Among all the state-of-the-art models, the VDCNN model <cit.> is a very deep network with up to 29 convolutional layers.
Our model even beats the VDCNN model on the AG's News, DBpeida and Yahoo! Answers datasets, which shows the effectiveness of our method. Moreover, our kNN memory can be easily adapted into these more complex neural network models.



 §.§ Evaluation in Other Training Setups

To study the behaviors of our model, we further evaluate it in some other common training setups. 
All the experiments in this subsection are conducted on the AG's News dataset, and the accuracies are performed on the devset.





  
Low-Resource Training Setup
In the introduction section, we claimed that the kNN memory captures instance-level information from the training set. 
To verify this claim, we evaluate our model on a low-resource training setup. 
We construct a low-resource training set by randomly selecting 10% of all instances for each category from the original training set.
Then, we train our “BiLSTM” and “BiLSTM with kNN” models, with the same configurations as before, on this low-resource training set. 
In Table <ref>, the third column, with the title “Low_Resource Setup”,  shows the accuracies of our two models. Comparing with the models trained with the full training set (“Full Setup”), our “BiLSTM with kNN” model only drops 4.4 percent, which is lower than the 6.7 percent drop from our “BiLSTM” model. 
This result shows our kNN memory can capture instance-level information to remedy shortage of the low-resource training set.



  
Unbalanced Training Setup 
In this sub-section, we evaluate our model on an unbalanced training set, a scenario not uncommon in text classification. 
To severely skew the label distribution, we construct an unbalanced training set by randomly selecting 2,000 instances for the World category, 4,000 instances for the Sports category, 8,000 instances for the Business category and 16,000 instances for the Sci/Tech. 
We train both our BiLSTM and proposed models (with the same configuration as before) on this unbalanced training set. 
The last column of Table <ref> shows the accuracies. 
The BiLSTM model shows a severe (43.3%) degradation of accuracy in the unbalanced setting.
On the other hand, our BiLSTM with kNN model only drops 4.0% when trained on the unbalanced training set. 
We believe this is because our model can capture instance-level information from the unbalanced training set.





  
Semi-supervised Training and Transfer Learning 
So far, we have verified that the effectiveness of the kNN retrieved from the same training set.
What if we search the kNN from a dataset of a completely different task? 
If we consider the text (without the label) information of the kNN from a different task, then this becomes the semi-supervised training setup. 
If we utilize the label information of the kNN from a different task, where the definition of labels are quite different from the task at hand, then this becomes the transfer learning setup. 
To reveal the behavior of our model in these two setups, we take the training set of the DBPedia dataset as the corpus to find the kNN for each text in the AG's News dataset. 
We construct four models: “BiLSTM” using the “M1” configuration in Table <ref>,
“Semi-supervised Training” using the “M6” configuration, “Transfer Learning (M5)” using the “M5” configuration, 
and “Transfer Learning (M7)” using the “M7” configuration.
Here, we should notice that the “attentive-kNN-text” and the “attentive-kNN-label” features are extracted from the kNN from the DBPedia corpus, which is a different classification task.
Table <ref> gives the results.
We can see that our model achieves improvements from the baseline (BiLSTM) in both the Semi-supervised Training and the Transfer Learning setups.



 §.§ Qualitative Analysis

We perform qualitative analysis by looking at some instances incorrectly predicted by the baseline (BiLSTM) but get corrected by adding the kNN memory (BiLSTM with kNN).

First, for the error illustrated in the introduction section, our model corrected it as expected.

Another example is “President George W. Bush 's campaign website was inaccessible from outside the United States .” with the correct label Sci/Tech. 
In the training set, the appearances of the phrase “George W. Bush” in each category are 1,659 (World), 410 (Business), 67 (Sports) and 299 (Sci/Tech), and the frequencies of the word “President” in each category are 4,486 (World), 1,021 (Business), 233 (Sports) and 554 (Sci/Tech). 
Based on these strong signals, the BiLSTM baseline assigned it with an incorrect label World. 
On the other hand, our BiLSTM with kNN corrected it, because there is a very similar neighbor in the training set “President George W. Bush 's official re-election website was down and inaccessible for hours , in what campaign officials said could be the work of hackers .” with the label Sci/Tech.



§ RELATED WORK


In recent years, there have been several studies trying to augment neural network models with external memories. Generally, these models utilize the attention mechanism to access useful information outside the model itself (so-called the external memory). 
For the machine translation task, <cit.> introduced the attention mechanism to access source side encoding information while generating the target sequence. 
For the question answering task, <cit.> proposed the memory network to access all supporting sentences before generating the correct answer word. 
<cit.> designed a more complicated “computer-like” external memory to simulate the Turning Machine. 
Our model also belongs to this group, but with the distinction that we construct the external memory with the K nearest neighbors of the input text, and utilize a multi-perspective attention model.

<cit.> proposed a matching network for one shot learning task. 
Their model also classifies the input instance by utilizing a labeled support set as our model does. 
However, our model differentiates from their model in two ways. 
First,  they assume the labeled support set is given beforehand, whereas our model searches the kNN independently based on the input instance. 
Second, their model only utilizes the label information of the support set for prediction, whereas our model makes use of information from both the input text and the kNN.

Our model follows an old idea of combining the model-based (or parametric) learning and the instance-based (or non-parametric) learning <cit.>. We infuse the old idea with the advanced neural networks and the attention mechanism.



§ CONCLUSION

 In this work, we enhanced neural networks with a kNN memory for text classification. Our model employs a neural network encoder to abstract information from the entire training set, and utilizes the kNN memory to capture instance-level information. 
The final prediction is made based on features from both the input text and the kNN.
Experimental results on several standard benchmark datasets show that our model outperforms the baseline model on all the datasets, and it even beats a very deep neural network model (with 29 layers) in several datasets. 
Our model also shows superior performance when training instances are scarce, and when the training data is severely unbalanced. Our model also leverages techniques such as 
semi-supervised training and transfer learning quite well.



aaai

