Improving classifier decision boundaries using nearest neighbors

Johannes SchneiderSubmission to ICLR 2024 · Rejected

TL;DR

Deep neural networks often place their decision boundaries in sparse regions of the feature space, making them susceptible to local overfitting. The authors introduce LaSeNN (Latent-Self-kNN), a lightweight, training-free inference tweak that takes a weighted average of a query sample's network prediction and the predictions of its nearest neighbors in latent space. This simple post-hoc adjustment consistently yields minor improvements across clean accuracy, label-noise tolerance, adversarial robustness, and interpretability without requiring architectural changes or retraining.

What Problem Does This Paper Address?

In deep classification models, classes naturally form dense clusters separated by low-density margins. Decision boundaries slice through these sparse regions, meaning their exact shapes are dictated by only a handful of training samples. As a result, the boundary is prone to overfitting and erratic local behavior.

Existing solutions targeting boundary-related issues—such as adversarial vulnerability, label noise, or lack of interpretability—typically require significant trade-offs (e.g., adversarial training often hurts clean accuracy) or require costly retraining pipelines and specialized loss functions. The authors ask: Can we smooth and correct classifier decision boundaries after training, purely at inference time, across multiple desiderata simultaneously?

Methods

The proposed algorithm, LaSeNN (LAtent-SElf-kNN), modifies model inference as follows:

  1. Latent Space Embedding: Instead of computing distances on raw input pixels, intermediate layer activations $C_{:i}(X)$ (typically from the penultimate or near-final layers) serve as representations for all training samples and the query sample $X_q$.
  2. Nearest Neighbor Retrieval: Retrieve the $k$-nearest neighbors ($\text{NN}_k$) of the query sample in latent space using cosine similarity (favored for sparse, high-dimensional spaces like CIFAR) or Euclidean distance ($L_2$, favored for dense datasets like ImageNet).
  3. Prediction Blending: Compute a weighted average between the network's direct prediction for the query $C(X_q)$ and the average network predictions of its $k$ latent neighbors: $$X^i_w = w_q \cdot C(X_q) + (1 - w_q) \cdot \frac{1}{k}\sum_{X \in \text{NN}_k} C(X)$$ where $w_q$ heavily weights the query itself (empirically optimal around $0.75 \le w_q \le 0.94$).

How LaSeNN differs from classical $k$-NN: * Operates in deep latent feature space rather than input space. * Combines the query’s own prediction with its neighbors rather than ignoring the query's model output. * Averages continuous network output vectors rather than performing a discrete majority vote over training labels.

Datasets

The authors evaluate their approach on standard computer vision benchmarks:

  • CIFAR-10 and CIFAR-100 (using self-trained VGG-13 and ResNet-10 models).
  • ImageNet-1k (using pre-trained torchvision models: ResNet-34, ConvNeXt-Tiny, and MobileNetV3-Large).

No new benchmarks are introduced.

Key Insights and Ideas

  • Overfitting occurs at the periphery: Analysis confirms that class pureness and sample distance to neighbors are negatively correlated ($r = -0.29$ to $-0.49$). Correctly classified samples reside in dense clusters, whereas misclassified samples and adversarial examples populate sparse boundary regions.
  • Surgical intervention: Over 99% of sample predictions remain untouched by LaSeNN because high-confidence, dense-cluster points dominate their neighbors. The adjustments occur almost exclusively in sparse regions where the classifier's boundary is ambiguous.
  • Free lunch, small portions: Rather than trading clean accuracy for robustness, smoothing the boundary with latent neighbors gives a simultaneous lift to clean accuracy, adversarial resistance, and label-noise tolerance.
  • $k=1$ is often best: In high-dimensional latent space, points quickly become dissimilar. Empirical sensitivity checks show that keeping $k$ very small ($k=1$ or $k=3$) yields the cleanest gains.

Key Results

  • Clean Accuracy Gains: LaSeNN boosts clean test accuracy across self-trained models by up to $+1.7\%$ on CIFAR-100 (VGG-13) and $+1.9\%$ (ResNet-10). On ImageNet, pre-trained models see slight but consistent gains (e.g., $+0.09\%$ on ConvNeXt-Tiny, $+0.05\%$ on ResNet-34).
  • Adversarial Robustness: Under targeted PGD and Basic Iterative Attacks (BIA), LaSeNN provides distinct gains without adversarial training. For CIFAR-100 on VGG-13, BIA accuracy improves from $9.1\%$ to $13.2\%$ ($+4.0\%$), and PGD improves from $11.3\%$ to $15.0\%$ ($+3.7\%$).
  • Label Noise Resistance: When training labels are randomly permuted (up to $32\%$), the relative performance advantage of LaSeNN grows. At $32\%$ noise on CIFAR-10 with VGG-13, LaSeNN achieves $60.4\%$ accuracy compared to the baseline's $57.7\%$ ($+2.6\%$).

Limitations and Future Work

  • Inference Overhead: Running nearest-neighbor searches over an entire training set during inference is computationally demanding and requires storing cached training embeddings.
  • Modest Effect Sizes: The authors candidly acknowledge that the method provides "a little bit of most things" rather than dramatic improvements or complete defenses against adversarial attacks.
  • Scope of Architectures: Experiments are restricted to convolutional neural networks (CNNs) in vision; evaluation on vision transformers (ViTs), NLP, or tabular modalities is left unexplored.
  • Future Work: Scaling neighborhood search via approximate nearest neighbor (ANN) indexing and investigating whether similar boundary-smoothing effects can be distilled directly into network weights during training.

Summary updated

Abstract

In this paper, we show that neural networks are not learning optimal decision boundaries. Decision boundaries go through areas of low training data density. They are impacted by few training samples which can easily lead to overfitting. We show that performing a weighted average of the prediction of a sample and its nearest neighbors' (computed in latent space) leads to a variety of minor favorable outcomes. 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 provides only 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},
}

Loading related content...

Figure