Abstract
Deep neural networks often struggle to capture the local geometric structure of data manifolds, a task where classical k-Nearest Neighbors (kNN) excels. This paper proposes bridging this gap by training neural networks to reconstruct a sample's local neighborhood. Using Sequence-to-Sequence and Memory Network architectures, the models predict labels and feature vectors of neighbors. Results across nine diverse datasets show that these "neighborhood-aware" models, particularly the V2VSLS variant, consistently outperform standard benchmarks and maintain robustness in out-of-core scenarios.
Introduction
While deep neural networks (DNNs) are the current gold standard for many tasks, they often struggle with interpretability and capturing the local geometric structure of data manifolds. The "manifold hypothesis" suggests that high-dimensional data sits on lower-dimensional manifolds; classification is essentially the task of separating these tangled manifolds.
Classical k-Nearest Neighbors (kNN) is built on the intuitive idea that points from the same manifold should be close together. However, kNN is computationally expensive on large datasets and doesn't "learn" representations in the way neural networks do. This research aims to combine the representational power of deep learning with the robust local logic of kNN, while also addressing the "out-of-core" problem—performing kNN-like reasoning when the entire dataset cannot fit into memory.
Methodology
The authors propose two primary families of models designed to "work harder" by reconstructing local neighborhoods:
- Sequence-to-Sequence (Seq2Seq) kNN: These models use an encoder-decoder architecture (specifically LSTMs). Given an input $x$, the decoder generates a sequence of $K$ outputs. Variants include V2LS (Vector to Label Sequence), V2VS (Vector to Vector Sequence), and V2VSLS, a hybrid that predicts both labels and feature vectors.
- Memory Network kNN (MNkNN): Based on the MemN2N architecture, this model uses an external memory containing a subset of training samples. It employs attention mechanisms to identify and predict the labels and features of neighbors within that memory.
Training utilizes a combination of KL divergence (for label distributions) and $L^2$ norms (for feature vectors). This forces the network to capture the "essence" of the neighborhood, effectively regularizing the model to learn more robust features.
Key Insights
- The "Work Harder" Hypothesis: The authors postulate that their models perform better because they are forced to do more than standard classification. By predicting the features of out-of-sample neighbors, the model must capture a deeper understanding of the data's underlying structure.
- Sequence vs. Set: The research finds that the order of neighbors matters. Modeling the neighborhood as a sequence (from closest to furthest) outperforms treating it as an unordered set, suggesting that relative distance information is a crucial signal.
- Generative Oversampling: Because these models can predict feature vectors of "potential" neighbors, they naturally function as synthetic data generators, making them powerful tools for balancing imbalanced datasets.
Experimental Results
The proposed models were evaluated across nine diverse datasets, including structured tabular data (NI, COV, SensIT, CCD) and unstructured image/text data (MNIST, CIFAR-10, News20, IMDb, Reuters).
Comprehensive Performance
The hybrid V2VSLS model consistently outperformed standard benchmarks like Random Forest, XGBoost, and standard feed-forward networks (FFN) across nearly every dataset tested.
Out-of-Core Robustness
In "out-of-core" scenarios—where the model only sees a small batch of data at a time—the performance gap was even more significant. While standard kNN performance plummets when it cannot access the full dataset, the V2VSLS model remains remarkably robust, maintaining high F-1 scores while managing computational time effectively.
Furthermore, when used for oversampling imbalanced data, the V2VSLS approach frequently outperformed established techniques like SMOTE and ADASYN, providing a more nuanced generation of synthetic samples based on learned manifold structures.
Conclusion
By forcing neural networks to reconstruct local neighborhoods, this framework successfully merges the strengths of deep learning and kNN. While these models involve higher training complexity than simple classifiers, the gains in accuracy, out-of-core robustness, and oversampling quality represent a significant advancement in neighborhood-aware deep learning. Future work may explore more efficient architectures to mitigate training time trade-offs.
Summary updated