In this paper, we propose a class of non-parametric classifiers, that learn
arbitrary boundaries and generalize well.
Our approach is based on a novel way to regularize 1NN classifiers using a
greedy approach. We refer to this class of classifiers as Watershed
Classifiers. 1NN classifiers are known to trivially over-fit but have very
large VC dimension, hence do not generalize well. We show that watershed
classifiers can find arbitrary boundaries on any dense enough dataset, and, at
the same time, have very small VC dimension; hence a watershed classifier leads
to good generalization.
Traditional approaches to regularize 1NN classifiers are to consider $K$
nearest neighbours. Neighbourhood component analysis (NCA) proposes a way to
learn representations consistent with ($n-1$) nearest neighbour classifier,
where $n$ denotes the size of the dataset. In this article, we propose a loss
function which can learn representations consistent with watershed classifiers,
and show that it outperforms the NCA baseline.

我们提出了一种非参数分类器，可以学习任意边界并且具有良好的推广能力，通过用一种贪婪方法来正则化 1NN 分类器。我们称这类分类器为 Watershed 分类器。传统方法正则化 1NN 分类器是考虑 K 个最近邻。我们提出了一种可以学习与 watershed 分类器一致的表示的损失函数，并且证明其优于 NCA 基准线。

一种用于改进泛化能力的正则化 1NN 分类器的新方法

A Novel Approach to Regularising 1NN classifier for Improved  Generalization

Adversarially robust machine learning has received much recent attention.
However, prior attacks and defenses for non-parametric classifiers have been
developed in an ad-hoc or classifier-specific basis. In this work, we take a
holistic look at adversarial examples for non-parametric classifiers, including
nearest neighbors, decision trees, and random forests. We provide a general
defense method, adversarial pruning, that works by preprocessing the dataset to
become well-separated. To test our defense, we provide a novel attack that
applies to a wide range of non-parametric classifiers. Theoretically, we derive
an optimally robust classifier, which is analogous to the Bayes Optimal. We
show that adversarial pruning can be viewed as a finite sample approximation to
this optimal classifier. We empirically show that our defense and attack are
either better than or competitive with prior work on non-parametric
classifiers. Overall, our results provide a strong and broadly-applicable
baseline for future work on robust non-parametrics. Code available at
this https URL .

文章系统研究了非参数分类器的对抗性问题，提出了全新的数据预处理方案 adverasrial pruning，并且得到了理论最优的鲁棒分类器，实验结果显示该方法更好或竞争性更好。