论文标题
向虚构$ 0 $ neart邻居及其提高的融合率外推
Extrapolation Towards Imaginary $0$-Nearest Neighbour and Its Improved Convergence Rate
论文作者
论文摘要
$ k $ - 最新的邻居（$ k $ -nn）是用于监督分类的最简单，最广泛使用的方法之一，它通过取下$ k $对象的观测标签的加权比来预测查询的标签。权重和参数$ k \ in \ mathbb {n} $规范其偏差差异，而权衡会隐含影响$ k $ -nn分类器的多余风险的收敛率；现有的一些研究考虑选择最佳$ K $和权重以获得更快的收敛速度。尽管已广泛开发了具有非负重的$ K $ -NN，但也证明负权重对于消除偏差术语并达到最佳收敛率至关重要。在本文中，我们提出了一种新颖的多尺度$ k $ -nn（ms- $ k $ -nn），它将未加权的$ k $ -nn估计器从几个$ k \ ge 1 $ aluty推出到$ k = 0 $，从而给出了一个假想的0-NN估计器。我们的方法隐含地计算自适应查询及其邻居点的最佳实用值。从理论上讲，我们证明MS-$ K $ -NN达到了提高的利率，这与某些条件下的现有最佳利率相吻合。
$k$-nearest neighbour ($k$-NN) is one of the simplest and most widely-used methods for supervised classification, that predicts a query's label by taking weighted ratio of observed labels of $k$ objects nearest to the query. The weights and the parameter $k \in \mathbb{N}$ regulate its bias-variance trade-off, and the trade-off implicitly affects the convergence rate of the excess risk for the $k$-NN classifier; several existing studies considered selecting optimal $k$ and weights to obtain faster convergence rate. Whereas $k$-NN with non-negative weights has been developed widely, it was also proved that negative weights are essential for eradicating the bias terms and attaining optimal convergence rate. In this paper, we propose a novel multiscale $k$-NN (MS-$k$-NN), that extrapolates unweighted $k$-NN estimators from several $k \ge 1$ values to $k=0$, thus giving an imaginary 0-NN estimator. Our method implicitly computes optimal real-valued weights that are adaptive to the query and its neighbour points. We theoretically prove that the MS-$k$-NN attains the improved rate, which coincides with the existing optimal rate under some conditions.
