# A Novel Approach to Regularising 1NN classifier for Improved Generalization

arXiv: https://arxiv.org/abs/2402.08405 · HTML: https://mlsanity.com/paper/2402.08405/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 13 Feb 2024.

## Builds on (most cited first, 10 of 10)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [No Fuss Distance Metric Learning using Proxies](https://mlsanity.com/paper/1703.07464/) (2017)
- [ProxyNCA++: Revisiting and Revitalizing Proxy Neighborhood Component Analysis](https://mlsanity.com/paper/2004.01113/) (2020)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Improving Generalization via Scalable Neighborhood Component Analysis](https://mlsanity.com/paper/1808.04699/) (2018)
- [Ultrametric Fitting by Gradient Descent](https://mlsanity.com/paper/1905.10566/) (2019)
- [Towards General and Efficient Active Learning](https://mlsanity.com/paper/2112.07963/) (2021)
- [Learned Watershed: End-to-End Learning of Seeded Segmentation](https://mlsanity.com/paper/1704.02249/) (2017)
- [Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning](https://mlsanity.com/paper/1911.02921/) (2019)
- [Triplet-Watershed for Hyperspectral Image Classification](https://mlsanity.com/paper/2103.09384/) (2021)

## Built on by (most cited first, 1 of 1)

- [Quantile Activation: Correcting a Failure Mode of ML Models](https://mlsanity.com/paper/2405.11573/) (2024)

## Abstract (arXiv)

In this paper, we propose a class of non-parametric classifiers, that learn arbitrary boundaries and generalize well. Our approach is based on a novel way to regularize 1NN classifiers using a greedy approach. We refer to this class of classifiers as Watershed Classifiers. 1NN classifiers are known to trivially over-fit but have very large VC dimension, hence do not generalize well. We show that watershed classifiers can find arbitrary boundaries on any dense enough dataset, and, at the same time, have very small VC dimension; hence a watershed classifier leads to good generalization. Traditional approaches to regularize 1NN classifiers are to consider K nearest neighbours. Neighbourhood component analysis (NCA) proposes a way to learn representations consistent with (n-1) nearest neighbour classifier, where n denotes the size of the dataset. In this article, we propose a loss function which can learn representations consistent with watershed classifiers, and show that it outperforms the NCA baseline.