Improving classifier decision boundaries using nearest neighbors

Johannes Schneider

Abstract

Neural networks are not learning optimal decision boundaries. We show that decision boundaries are situated in areas of low training data density. They are impacted by few training samples which can easily lead to overfitting. We provide a simple algorithm performing a weighted average of the prediction of a sample and its nearest neighbors' (computed in latent space) leading to a minor favorable outcomes for a variety of important measures for neural networks. In our evaluation, we employ various self-trained and pre-trained convolutional neural networks to show that our approach improves (i) resistance to label noise, (ii) robustness against adversarial attacks, (iii) classification accuracy, and to some degree even (iv) interpretability. While improvements are not necessarily large in all four areas, our approach is conceptually simple, i.e., improvements come without any modification to network architecture, training procedure or dataset. Furthermore, they are in stark contrast to prior works that often require trade-offs among the four objectives or provide valuable, but non-actionable insights.

Introduction

Deep Neural Networks (DNNs) are widely recognized for their high accuracy in classification tasks. However, they suffer from a "boundary problem": the decision boundaries they learn often fall in regions where training data is sparse. This sparsity allows the model to overfit to a small number of points, resulting in "jagged" boundaries that are vulnerable to adversarial attacks and sensitive to label noise.

Existing methods to improve robustness often involve significant trade-offs, such as a decrease in standard classification accuracy. This work introduces a post-processing approach that addresses these issues without requiring retraining or architectural modifications.

Table 1: Comparison of the proposed method against prior works across multiple performance metrics.

As illustrated in Table 1, the proposed method (LaSeNN) distinguishes itself by providing improvements across accuracy, interpretability, and robustness simultaneously, whereas prior works typically necessitate trade-offs.

Methodology: Latent Self-kNN (LaSeNN)

The core of the proposed approach is LaSeNN (LAtent SElf-kNN). Instead of relying exclusively on the final output layer of a neural network, LaSeNN utilizes the model's internal "latent" representations to refine predictions.

The algorithm operates as follows:

  1. Latent Representation Extraction: For a new query image, the model extracts its embedding (activations) from a late-stage layer.
  2. Neighbor Identification: It identifies the $k$ nearest neighbors (typically $k=3$) from the training set based on similarity in this latent space.
  3. Weighted Aggregation: A weighted average is calculated between the model's original prediction for the query image and the average predictions of the identified neighbors.
  4. Final Decision: The class with the highest weighted score is selected as the final output.
The LaSeNN pipeline: A query sample's latent representation is compared against training data to find neighbors, which then inform a weighted final prediction.

By finding neighbors in the latent space rather than the raw input space, the method leverages the model's learned features, which have already filtered out irrelevant noise and clustered similar semantic concepts.

Experimental Results

The researchers evaluated LaSeNN across standard computer vision benchmarks, including CIFAR-10, CIFAR-100, and ImageNet, using architectures such as VGG-13, ResNet, MobileNetV3, and ConvNext.

Accuracy and Robustness

The method consistently improved classification accuracy by 0.1% to 3% across various models. More importantly, it significantly enhanced adversarial robustness against PGD and Basic Iterative Attacks. In scenarios involving label noise, where training data was corrupted with incorrect labels (up to 32%), LaSeNN provided a more stable performance buffer than standard classifiers.

Interpretability

LaSeNN offers a unique interpretability benefit. Because predictions are partially derived from specific training samples, developers can inspect the $k$ neighbors to understand the rationale behind a decision—for instance, identifying which specific training images most influenced a particular classification.

Conclusion and Future Work

LaSeNN is a conceptually simple, "plug-and-play" method that improves neural network performance and robustness without the need for retraining. While it introduces some computational overhead during inference due to the nearest neighbor search, this can be optimized using efficient similarity search libraries like FAISS. Future research may focus on automating the selection of optimal layers and weights for different data types and further reducing the computational cost of the neighbor search.

Summary updated

Abstract

Neural networks are not learning optimal decision boundaries. We show that decision boundaries are situated in areas of low training data density. They are impacted by few training samples which can easily lead to overfitting. We provide a simple algorithm performing a weighted average of the prediction of a sample and its nearest neighbors' (computed in latent space) leading to a minor favorable outcomes for a variety of important measures for neural networks. In our evaluation, we employ various self-trained and pre-trained convolutional neural networks to show that our approach improves (i) resistance to label noise, (ii) robustness against adversarial attacks, (iii) classification accuracy, and to some degree even (iv) interpretability. While improvements are not necessarily large in all four areas, our approach is conceptually simple, i.e., improvements come without any modification to network architecture, training procedure or dataset. Furthermore, they are in stark contrast to prior works that often require trade-offs among the four objectives or provide valuable, but non-actionable insights.
BibTeX
@misc{schneider2023improving,
  author = {Johannes Schneider},
  title = {{Improving classifier decision boundaries using nearest neighbors}},
  year = {2023},
  eprint = {2310.03927},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.03927},
  howpublished = {arXiv},
}
Figure