Published on Sat Oct 31 2020

Optimal 1-NN Prototypes for Pathological Geometries

Ilia Sucholutsky, Matthias Schonlau

The number and distribution of prototypes required for the classifier to match its original performance is intimately related to the geometry of the training data. We propose an algorithm for finding nearly-optimal prototypes in this setting, and use it to empirically validate the theoretical results.

0
0
0
Abstract

Using prototype methods to reduce the size of training datasets can drastically reduce the computational cost of classification with instance-based learning algorithms like the k-Nearest Neighbour classifier. The number and distribution of prototypes required for the classifier to match its original performance is intimately related to the geometry of the training data. As a result, it is often difficult to find the optimal prototypes for a given dataset, and heuristic algorithms are used instead. However, we consider a particularly challenging setting where commonly used heuristic algorithms fail to find suitable prototypes and show that the optimal prototypes can instead be found analytically. We also propose an algorithm for finding nearly-optimal prototypes in this setting, and use it to empirically validate the theoretical results.

Thu Feb 07 2019
Machine Learning
Bounds for the VC Dimension of 1NN Prototype Sets
The Vapnik-Chervonenkis (VC) dimension is an important combinatorial property of classifiers. To our knowledge, no theoretical results yet exist for the VC dimension of edited nearest-neighbour(1NN) classifiers with reference set of fixed size.
0
0
0
Thu Oct 01 2020
Machine Learning
Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces
Proto-NN is universally consistent in any metric space that admits a universally consistent rule. It is a significant simplification of OptiNet, a recently proposed compression-based algorithm.
0
0
0
Sun Sep 27 2015
Machine Learning
Discriminative Learning of the Prototype Set for Nearest Neighbor Classification
The nearest neighbor rule is a classic yet essential classification model. Many existing methods assume and rely on the input vector space. In the proposed model, the selection of the nearest prototypes is influenced by the respective prototypes.
0
0
0
Tue Jan 29 2019
Machine Learning
Hyperspherical Prototype Networks
This paper introduces hyperspherical prototype networks, which unify classification and regression with prototypes. We position prototypes through data-independent optimization, with an extension to incorporate priors from class semantics.
0
0
0
Sun Dec 17 2017
Machine Learning
Super-sparse Learning in Similarity Spaces
Machine-learning algorithms can become very computationally demanding. Current reduction approaches select a small subset of representative prototypes in the space induced by the similarity measure. We overcome this by jointly learning the classification function along with an optimal set of virtual prototypes.
0
0
0
Thu Oct 15 2020
Machine Learning
A Theory of Hyperbolic Prototype Learning
Hyperbolic Prototype Learning is a type of supervised learning. Learning is achieved by minimizing the 'penalized Busemann loss', a new loss function based on the Buseman function of hyperbolic space.
0
0
0