# Instance-based learning using the Half-Space Proximal Graph

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 39 references that are in the map.
- First posted on arXiv 4 Feb 2021.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Matching Networks for One Shot Learning](https://mlsanity.com/paper/1606.04080/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Deep Learning for Sensor-based Activity Recognition: A Survey](https://mlsanity.com/paper/1707.03502/) (2017)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)

## Abstract (arXiv)

The primary example of instance-based learning is the k-nearest neighbor rule (kNN), praised for its simplicity and the capacity to adapt to new unseen data and toss away old data. The main disadvantages often mentioned are the classification complexity, which is O(n), and the estimation of the parameter k, the number of nearest neighbors to be used. The use of indexes at classification time lifts the former disadvantage, while there is no conclusive method for the latter. This paper presents a parameter-free instance-based learning algorithm using the em Half-Space Proximal (HSP) graph. The HSP neighbors simultaneously possess proximity and variety concerning the center node. To classify a given query, we compute its HSP neighbors and apply a simple majority rule over them. In our experiments, the resulting classifier bettered KNN for any k in a battery of datasets. This improvement sticks even when applying weighted majority rules to both kNN and HSP classifiers. Surprisingly, when using a probabilistic index to approximate the HSP graph and consequently speeding-up the classification task, our method could em improve its accuracy in stark contrast with the kNN classifier, which worsens with a probabilistic index.