Optimal 1-NN Prototypes for Pathological Geometries
- URL: http://arxiv.org/abs/2011.00228v1
- Date: Sat, 31 Oct 2020 10:15:08 GMT
- Title: Optimal 1-NN Prototypes for Pathological Geometries
- Authors: Ilia Sucholutsky, Matthias Schonlau
- Abstract summary: Using prototype methods to reduce the size of training datasets can drastically reduce the computational cost of classification.
We show that it is difficult to find the optimal prototypes for a given dataset, and algorithms are used instead.
We propose an algorithm for finding nearly-optimal classifier prototypes in this setting, and use it to empirically validate the theoretical results.
- Score: 13.70633147306388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.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.
Related papers
- Accelerating prototype selection with spatial abstraction [0.0]
We propose an approach for speeding up existing prototype selection techniques.
It builds an abstract representation of the dataset, using the notion of spatial partition.
After, some conventional prototype selection algorithms can be applied to the candidates selected by our approach.
arXiv Detail & Related papers (2024-03-16T21:34:24Z) - Rethinking Semantic Segmentation: A Prototype View [126.59244185849838]
We present a nonparametric semantic segmentation model based on non-learnable prototypes.
Our framework yields compelling results over several datasets.
We expect this work will provoke a rethink of the current de facto semantic segmentation model design.
arXiv Detail & Related papers (2022-03-28T21:15:32Z) - A Closer Look at Prototype Classifier for Few-shot Image Classification [28.821731837776593]
We show that a prototype classifier works equally well without fine-tuning and meta-learning.
We derive a novel generalization bound for the prototypical network and show that focusing on the variance of the norm of a feature vector can improve performance.
arXiv Detail & Related papers (2021-10-11T08:28:43Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank.
Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
arXiv Detail & Related papers (2021-05-23T19:21:55Z) - One Line To Rule Them All: Generating LO-Shot Soft-Label Prototypes [0.0]
Prototype generation methods aim to create a small set of synthetic observations that accurately represent a training dataset.
assigning soft labels to prototypes can allow increasingly small sets of prototypes to accurately represent the original training dataset.
We propose a novel, modular method for generating soft-label lines that still maintains representational accuracy even when there are fewer prototypes than the number of classes in the data.
arXiv Detail & Related papers (2021-02-15T20:21:29Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - An AI-Assisted Design Method for Topology Optimization Without
Pre-Optimized Training Data [68.8204255655161]
An AI-assisted design method based on topology optimization is presented, which is able to obtain optimized designs in a direct way.
Designs are provided by an artificial neural network, the predictor, on the basis of boundary conditions and degree of filling as input data.
arXiv Detail & Related papers (2020-12-11T14:33:27Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret.
We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
arXiv Detail & Related papers (2020-11-19T10:00:54Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
Federated Learning (FL) has become a popular paradigm for learning from distributed data.
To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
arXiv Detail & Related papers (2020-05-22T23:07:42Z) - Discrete-Valued Latent Preference Matrix Estimation with Graph Side
Information [12.836994708337144]
We develop an algorithm that matches the optimal sample complexity.
Our algorithm is robust to model errors and outperforms the existing algorithms in terms of prediction performance.
arXiv Detail & Related papers (2020-03-16T06:29:24Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.