Abstract
Traditional k-Nearest Neighbors (kNN) algorithms are valued for their simplicity and reliance on local data geometry, yet they lack the representational learning capabilities of deep neural networks and face scalability challenges. This paper introduces a novel framework that bridges this gap by training Sequence-to-Sequence (Seq2Seq) and Memory Networks to mimic the kNN search process. By predicting the labels and feature vectors of a sample’s neighbors, these models learn robust internal representations that outperform standard classifiers and provide a sophisticated mechanism for synthetic data generation in imbalanced datasets.
Introduction
Despite the dominance of deep learning in modern AI, the k-Nearest Neighbors (kNN) algorithm remains a fundamental tool due to its "distance property": the intuitive principle that points belonging to the same class should reside near one another in feature space. However, kNN is computationally expensive at scale and lacks a mechanism to learn features, relying entirely on the provided input representation.
Conversely, standard neural networks are powerful feature learners but often operate as "black boxes" that do not explicitly respect the local geometry of the data. This research seeks to integrate these two paradigms. By forcing neural networks to predict the neighborhood structure of a given data point, the authors teach the network to internalize the underlying manifold of the data, combining the interpretability of local distance with the predictive power of deep learning.
Methodology
The authors propose two primary architectural families designed to produce sequences of neighbor-related outputs:
1. Vector to Sequence (Seq2Seq) Models
These models take an input vector $x$ and generate a sequence of outputs corresponding to its $K$ nearest neighbors:
- V2LS (Vector to Label Sequence): Predicts the sequence of labels for the $K$ nearest neighbors.
- V2VS (Vector to Vector Sequence): Predicts the actual feature vectors of those $K$ neighbors.
- V2VSLS: A hybrid model that predicts both labels and feature vectors simultaneously.
2. Memory Network Models (MNkNN)
These models utilize an external memory containing a subset of training samples. Through an attention mechanism across $K$ layers, the model predicts the label of the $t^{th}$ nearest neighbor at each layer $t$.
The Loss Function and "Secret Sauce"
To train these models, the authors employ a custom multi-task loss function combining KL divergence (to match label distributions) and $L^2$ norm (to match feature vectors). By requiring the model to predict $2K$ pieces of information—both what the neighbors are and where they are—the network is compelled to learn a significantly more robust internal representation than a standard classifier. Furthermore, the authors found that the order of prediction matters; predicting neighbors from closest to furthest allows the decoder to preserve the natural decay of similarity.
Out-of-Core Framework
To handle datasets too large for system memory, the authors developed an "Out-of-Core" framework. This uses an iterative sampling algorithm to approximate kNN behavior, allowing the deep models to learn from massive datasets without requiring the entire distance matrix to be stored in RAM.
Experimental Setup
The models were evaluated across nine diverse datasets spanning three domains:
- Structured Data: Network Intrusion (NI), Forest Covertype (COV), SensIT, and Credit Card Default (CCD).
- Image Data: MNIST and CIFAR-10 (utilizing pre-trained CNNs/ResNets for feature extraction).
- Text Data: News20, IMDb, and Reuters (utilizing tf-idf/SVD or LSTM-based extraction).
Key Insights and Results
Superiority on Structured Data
In comprehensive tests, the V2VSLS model consistently outperformed established gradient-boosted decision tree (GBDT) models, including XGBoost, LightGBM, and Random Forest, across all four structured datasets. This suggests that the neighborhood-mimicking objective provides a superior inductive bias for tabular data.
Neural Oversampling for Imbalanced Data
A significant byproduct of the V2VS model is its ability to act as a synthetic data generator. Because it learns to generate feature vectors that represent valid neighbors, it can be used to balance datasets. Unlike traditional methods like SMOTE, which use simple linear interpolation, this "Neural Oversampling" generates samples based on a deep understanding of the data distribution. Experiments showed that V2VSLS-based oversampling led to higher F-1 scores for minority classes compared to SMOTE and ADASYN.
Robustness and Scalability
In "Out-of-Core" scenarios where memory was restricted, the proposed models significantly outperformed standard kNN benchmarks. The neural models proved more robust to the noise introduced by batch sampling, maintaining high accuracy even when they could only "see" a fraction of the total dataset during training.
Limitations and Future Work
While the results are promising, the authors identify several areas for improvement:
- Preprocessing Overhead: The current framework requires calculating the kNN for every training point upfront, which is a significant computational cost for massive datasets.
- Two-Stage Pipeline: For image and text data, the model relies on a separate feature extraction step. Future work could involve end-to-end architectures where the feature extractor and the kNN-mimic are trained jointly.
- Hyperparameter Sensitivity: The model introduces new hyperparameters (such as the weights balancing the different loss components) that require careful calibration to achieve peak performance.
Conclusion
By reframing k-Nearest Neighbors as a sequence prediction task, this paper demonstrates that deep neural networks can be taught to respect and replicate local data geometry. The resulting models not only improve classification accuracy on structured data but also offer a powerful new tool for handling imbalanced datasets through learned synthetic sample generation.
Summary updated