Speculate-Correct Error Bounds for k-Nearest Neighbor Classifiers
We introduce the speculate-correct method to derive error bounds for local classifiers. Using it, we show that k nearest neighbor classifiers, in spite of their famously fractured decision boundaries, have exponential error bounds with O(sqrt((k + ln n) / n)) error bound range for n in-sample examples.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
K-Nearest Neighbor Classification Using Anatomized Data
This paper analyzes k nearest neighbor classification with training data anonymized using anatomy. Anatomy preserves all data values, but introduces uncertainty in the mapping between identifying and sensitive values. We…
AnatomyClassificationGeneral ClassificationNearest Neighbor and Kernel Survival Analysis: Nonasymptotic Error Bounds and Strong Consistency Rates
We establish the first nonasymptotic error bounds for Kaplan-Meier-based nearest neighbor and kernel survival probability estimators where feature vectors reside in metric spaces. Our bounds imply rates of strong consist…
Survival AnalysisOn the Resistance of Nearest Neighbor to Random Noisy Labels
Nearest neighbor has always been one of the most appealing non-parametric approaches in machine learning, pattern recognition, computer vision, etc. Previous empirical studies partly shows that nearest neighbor is resist…
Multiclass Classification via Class-Weighted Nearest Neighbors
We study statistical properties of the k-nearest neighbors algorithm for multiclass classification, with a focus on settings where the number of classes may be large and/or classes may be highly imbalanced. In particular…
ClassificationGeneral ClassificationLearning Label Embeddings for Nearest-Neighbor Multi-class Classification with an Application to Speech Recognition
We consider the problem of using nearest neighbor methods to provide a conditional probability estimate, P(y|a), when the number of labels y is large and the labels share some underlying structure. We propose a method fo…
General ClassificationMulti-class Classificationspeech-recognitionSpeech Recognition