Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces

arXiv2010.00636MaRDI QIDQ6350342FDOQ6350342

Authors: László Györfi, Roi Weiss 

Publication date: 1 October 2020

Abstract: We study universal consistency and convergence rates of simple nearest-neighbor prototype rules for the problem of multiclass classification in metric paces. We first show that a novel data-dependent partitioning rule, named Proto-NN, is universally consistent in any metric space that admits a universally consistent rule. Proto-NN is a significant simplification of OptiNet, a recently proposed compression-based algorithm that, to date, was the only algorithm known to be universally consistent in such a general setting. Practically, Proto-NN is simpler to implement and enjoys reduced computational complexity. We then proceed to study convergence rates of the excess error probability. We first obtain rates for the standard $k$-NN rule under a margin condition and a new generalized-Lipschitz condition. The latter is an extension of a recently proposed modified-Lipschitz condition from $mathbb{R}^d$ to metric spaces. Similarly to the modified-Lipschitz condition, the new condition avoids any boundness assumptions on the data distribution. While obtaining rates for Proto-NN is left open, we show that a second prototype rule that hybridizes between $k$-NN and Proto-NN achieves the same rates as $k$-NN while enjoying similar computational advantages as Proto-NN. However, as $k$-NN, this hybrid rule is not consistent in general.

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

This page was built for publication: Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350342)