arXiv preprint ·
Extreme classification: beating chance with one training example from each class
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study a minimal classification problem: Given independent labeled observations $X\sim P$ and $Z\sim Q$ from two unknown distributions $P,Q$, and given an independent target $Y$ drawn with equal probability from $P$ or $Q$, can one classify $Y$ strictly better than chance whenever $P\neq Q$? The one-nearest-neighbor rule succeeds for every pair of multivariate Gaussian distributions with distinct means and a common positive-definite covariance matrix but can perform strictly worse than chance even for smooth densities on the real line. We construct a fixed randomized kernel rule whose expected accuracy is exactly $1/2+\operatorname{MMD}_k^2(P,Q)/4$, and obtain characteristic kernels on countably generated measurable spaces from countable families of measurable binary questions. We also prove that a deterministic order rule on $\mathbb R$ beats chance for every pair of distinct Borel probability measures. A measurable encoding then gives a deterministic distribution-free rule which beats chance on every countably generated measurable space, in particular every separable metric space. Finally, we show that no rule works for every distinct pair of distributions and every unknown unbalanced class prior; under adaptive target-class selection, every rule other than a fair coin is strictly worse than chance for some finitely supported pair.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
Next-token functional estimation
Repulsive normalizing flow mixtures for adaptive importance sampling: reliability analysis of complex systems
Compressed Active Subspaces for Scalable Bayesian Inference
Diagonalized Attention for Individualized Regression: Latent-Row Localization and Prediction
Portfolio-Based Constrained Multi-Objective Bayesian Optimization for Materials Design
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.