Source-linked AI summary
Optimal weighted nearest neighbour classifiers
Richard J. Samworth
TL;DR
The paper asks how to improve the asymptotic regret of nearest-neighbour classifiers beyond equal weighting. It derives regret expansions and optimal weights, then compares weighted, unweighted, and bagged classifiers, finding dimension-dependent gains and faster rates under stronger smoothness with negative weights.
Problem
Equal weighting in k-nearest-neighbour classification may be improvable by assigning decreasing weights to successively more distant neighbours.
Method
The paper derives an asymptotic regret expansion, obtains optimal nonnegative weights, analyzes bagging as weighted nearest-neighbour classification, and studies negative weights under stronger smoothness assumptions.
Results
Regret improvement over unweighted k-nearest neighbour is at least 5% for d ≤15, peaks at just over 8% when d = 4, and becomes negligible as d →∞.
Takeaways & Limitations
The optimal weighted classifier offers dimension-dependent leading-constant improvements, while bagged nearest-neighbour weights are close to optimal when d is large.
Takeaways & Limitations
The faster-rate results require stronger smoothness assumptions and negative weights, and their asymptotic leading terms may require rather large sample sizes to dominate error terms.
Abstract
from arXiv · showhide
We derive an asymptotic expansion for the excess risk (regret) of a weighted nearest-neighbour classifier. This allows us to find the asymptotically optimal vector of nonnegative weights, which has a rather simple form. We show that the ratio of the regret of this classifier to that of an unweighted k-nearest neighbour classifier depends asymptotically only on the dimension d of the feature vectors, and not on the underlying populations. The improvement is greatest when d=4, but thereafter decreases as $d\rightarrow\infty$. The popular bagged nearest neighbour classifier can also be regarded as a weighted nearest neighbour classifier, and we show that its corresponding weights are somewhat suboptimal when d is small (in particular, worse than those of the unweighted k-nearest neighbour classifier when d=1), but are close to optimal when d is large. Finally, we argue that improvements in the rate of convergence are possible under stronger smoothness assumptions, provided we allow negative weights. Our findings are supported by an empirical performance comparison on both simulated and real data sets.
1. Introduction.
The paper analyzes weighted nearest-neighbour classifiers, derives asymptotically optimal nonnegative weights, and compares them with unweighted and bagged alternatives. It also studies faster convergence under stronger smoothness assumptions and negative weights.
- The paper studies how weighted nearest-neighbour risk differs asymptotically from Bayes risk, decomposing regret into dominant bias and variance terms.
- It derives a relatively simple asymptotically optimal vector of nonnegative weights for minimizing misclassification rate.
- Only a proportion O(n^-d/(d+4)) of weights is positive; the profile is concave for d = 1, linear for d = 2, and convex for d ≥3.
- The optimal weighted classifier uses k∗ larger by a dimension-dependent factor than unweighted k-nearest neighbour, around 1.27 at d = 1 and approaching 2 in high dimensions.
- 15% improvement is not the reported result; for d ≤15, regret improvement is at least 5%, peaks at just over 8% when d = 4, and becomes negligible as d →∞.
- Bagged nearest-neighbour classifiers correspond to approximately exponentially decaying weighted classifiers, with an asymptotically optimal resample fraction compared against weighted and unweighted methods.
2. Main results.
The paper develops an asymptotic theory for weighted nearest-neighbour classifiers, decomposing regret into variance and squared-bias terms and deriving asymptotically optimal nonnegative weights. Under stated regularity conditions, the optimized classifier improves the leading regret constant over unweighted k-nearest neighbours in a dimension-dependent way that is independent of the underlying populations.
- Assumptions: The analysis assumes a two-class model in R^d with compact feature support, a nonempty decision boundary, smooth class densities near that boundary, and regularity conditions on the regression function.The assumptions also control local feature mass and require the decision boundary to be a regular (d−1)-dimensional manifold, including at the support boundary.
- Asymptotic regret: Theorem 1 asymptotically decomposes weighted nearest-neighbour regret into dominant variance and squared-bias contributions.The constants depend on the class densities and their first and second derivatives along the Bayes decision boundary.
- Optimal weighting: Theorem 2 identifies a simple asymptotically optimal vector of nonnegative weights under the same assumptions and B2 > 0.The optimality characterization applies to admissible sequences of weight vectors, with the displayed construction providing the target weights.
- Comparison with unweighted k-nearest neighbours: The optimal effective neighbour count k∗ is larger than the optimal unweighted k-nearest-neighbour choice by {2(d+4)/(d+2)}^{d/(d+4)}, up to rounding, when B2 > 0.The comparison concerns the asymptotically optimal k for the weighted procedure versus kopt for the traditional unweighted classifier.
- Comparison with unweighted k-nearest neighbours: Both optimized weighted and unweighted classifiers have regret rate O(n^−4/(d+4)), so the weighted improvement is in the leading constant and does not depend on the underlying populations.The improvement is at least 5% for d ≤ 15, while the broader minimax-rate discussion shows that several weighted procedures attain the same worst-case rate.
3. The bagged nearest neighbour classifier.
The paper represents infinite-simulation bagged nearest-neighbour classifiers as weighted nearest-neighbour rules, with weights determined by the resampling fraction. Their asymptotic relative performance depends on dimension: bagging is worse in one dimension, equal in two, and better from three dimensions onward.
- Bagging as weighting: Infinite-simulation bagging with or without replacement becomes a weighted nearest-neighbour classifier whose weights decay approximately exponentially with neighbour distance.The resample fraction is q = m/n, and the two bagging variants correspond to explicit weight vectors or their approximation.
- Bagging as weighting: The resampling fraction q plays a crucial role in the performance of the bagged nearest-neighbour classifier.The paper derives an asymptotically optimal q for the considered bagging variants.
- Asymptotic comparison: The bagged nearest-neighbour regret ratio is about 1.18 when d = 1, equals 1 when d = 2, and is less than 1 for d ≥3.The ratio compares bagged nearest-neighbour regret with k-nearest-neighbour regret.
- Asymptotic comparison: The bagged classifier has almost optimal performance among nonnegatively weighted nearest-neighbour classifiers because its weights decay approximately geometrically, like the asymptotically optimal weights.Figure 3 compares the bagged ratio with the optimally weighted ratio as functions of dimension.
- Data-driven tuning: The same limiting regret ratio applies when the corresponding neighbour count is data driven, provided it lies between n^β and n^(1−β) with probability tending to one.This condition requires some β ∈ (0,1/2).
4. Faster rates of convergence.
Under stronger smoothness assumptions, weighted nearest-neighbour classifiers with negative weights can cancel the dominant squared-bias term and attain faster regret rates. The construction imposes moment restrictions on the weights, but the authors caution that negative weights and finite-sample dominance of asymptotic terms limit practical use.
- Bias cancellation: Allowing negative weights makes it possible to impose moment conditions that eradicate the dominant squared-bias term in the regret expansion.The restriction is expressed through weighted sums of powers of neighbour indices.
- Higher smoothness: The stronger smoothness condition requires the class densities near the decision boundary to have 2r continuous derivatives.The condition is denoted (A.2)(r) and retains the nonempty decision boundary requirement.
- Weight construction: The allowable negative-weight vectors satisfy kernel-like restrictions controlling moments, squared weights, and the contribution of distant neighbours.These restrictions define the class W† used for the higher-order expansion.
- Faster rates: Under the stated conditions and B2^(r) > 0, the resulting classifiers achieve the regret rate O(n^(-4r/(4r+d))).The construction truncates the weights after k*(r) neighbours and chooses coefficients to satisfy the moment constraints.
- Weight construction: The coefficients are obtained by solving r linear equations and, for large k, using asymptotic approximations to their dominant terms.For r = 1, the paper gives an explicit example of the resulting weights.
- Practical caveats: The authors caution that negative weights may be uncomfortable for practitioners and that large samples may be needed before the leading asymptotic terms dominate the error terms.These concerns motivate not pursuing adaptation to an unknown smoothness level with Lepski’s method.
5. Empirical performance study.
The study compares unweighted, optimally weighted, and bagged nearest-neighbour classifiers across simulated and real data. Optimally weighted classifiers generally improve on k-nearest neighbours, while empirical regret ratios largely agree with theory and bagging performs comparably in higher dimensions.
- Study design: The study evaluates k-nearest neighbour, optimally weighted nearest neighbour, and bagged nearest neighbour classifiers on simulated and real data sets.Simulations vary distributional characteristics, sample sizes, dimensions, and dependence; benchmark data sets come from the UCI repository.
- Study design: The simulations include four settings covering benign, bimodal, dependent, heavy-tailed, and nuisance-variable classification problems.Sample sizes are n ∈ {50,200,1000}, with dimensions d ∈ {1,2,3,5,10}, except where noted for setting 3.
- Study design: The simulations use 1000 independent test points per data set, with each simulation repeated 1000 times to estimate classifier risks.Distances are evaluated in advance, and weighted and unweighted classifiers have computational requirements of the same order of magnitude.
- Simulation results: 54 of 57 simulated scenarios show lower risk for the optimally weighted classifier than for k-nearest neighbours.One exception is within Monte Carlo error; the other two occur at d = 10 with n = 50 and n = 200, where the asymptotics appear inaccurate.
- Simulation results: The theoretical first regret ratios are 0.943, 0.924, 0.919, 0.920, and 0.936 for d = 1,2,3,5,10, respectively, and empirical improvements generally agree with these predictions.Bagged nearest-neighbour relative performance also matches its theoretical predictions reasonably well.
- Real-data results: On the three UCI data sets, the optimally weighted classifier outperforms k-nearest neighbours in every case, while bagging performs comparably well.The data-set dimensions are d = 9, 8, and 19; the choice between ℓ1 and ℓ2 distance appears to make little difference to relative performance.
APPENDIX
The appendix outlines the proof of the asymptotic excess-risk expansion by isolating the decision boundary, approximating the dominant integral there, and controlling the remaining region. Uniform bounds, concentration inequalities, and normal approximations complete the argument under the stated regularity conditions.
- Proof strategy: The proof begins by representing the weighted neighbour statistic and analyzing its behavior uniformly over admissible weights and points near the decision boundary.The appendix introduces local scaling and bounds distributional quantities for the relevant neighbour indices.
- Proof strategy: The dominant contribution to the risk integral comes from a shrinking neighborhood of the decision boundary.The integral is decomposed along the boundary and the perpendicular direction, followed by a normal approximation to the integrand.
- Boundary analysis: The boundary integral is handled using a diffeomorphic normal-coordinate map and integration results for manifolds.The appendix controls the replacement of neighborhoods by the boundary itself using a tube-volume bound.
- Tail-region control: The contribution away from the decision boundary is bounded using the assumption that the regression function stays separated from one-half there.Hoeffding’s inequality is applied to control deviations of the weighted neighbour statistic in this region.
- Asymptotic expansion: A nonuniform Berry–Esseen bound, Taylor expansions, and a change of variables yield the asymptotic terms involving B1 and B2.The appendix states that uniformity over the admissible weight class completes the remaining proof steps and Theorem 1.