Efficient Classification for Metric Data

DOI10.1109/TIT.2014.2339840MaRDI QIDQ2986185zbMATH OpenFDO

Authors Robert Krauthgamer, Lee-Ad Gottlieb, Aryeh Kontorovich

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2547

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Pattern recognition, speech recognition (68T10)

Abstract: Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as string edit and earthmover distance. A general framework developed for this purpose by von Luxburg and Bousquet [JMLR, 2004] left open the questions of computational efficiency and of providing direct bounds on generalization error. We design a new algorithm for classification in general metric spaces, whose runtime and accuracy depend on the doubling dimension of the data points, and can thus achieve superior classification performance in many common scenarios. The algorithmic core of our approach is an approximate (rather than exact) solution to the classical problems of Lipschitz extension and of Nearest Neighbor Search. The algorithm's generalization performance is guaranteed via the fat-shattering dimension of Lipschitz classifiers, and we present experimental evidence of its superiority to some common kernel methods. As a by-product, we offer a new perspective on the nearest neighbor classifier, which yields significantly sharper risk asymptotics than the classic analysis of Cover and Hart [IEEE Trans. Info. Theory, 1967].

Cited in

(15)

• Universal Bayes consistency in metric spaces
• Non-uniform packings
• Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs
• \(L_{p}\)-norm Sauer-Shelah lemma for margin multi-category classifiers
• Active nearest-neighbor learning in metric spaces
• Boosting conditional probability estimators
• Robust randomized optimization with k nearest neighbors
• On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
• Adaptive metric dimensionality reduction
• Fully dynamic clustering and diversity maximization in doubling metrics
• What Is Known About Vertex Cover Kernelization?
• An improved uniform convergence bound with fat-shattering dimension
• Stable sample compression schemes: new applications and an optimal SVM margin bound
• Exploiting geometric structure in mixture proportion estimation with generalised Blanchard-Lee-Scott estimators
• Improved generalization bounds for robust learning

This page was built for publication: Efficient Classification for Metric Data

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