论文标题
$ k $ neart的邻居分类器的对抗性示例基于高阶voronoi图
Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
论文作者
论文摘要
对抗性示例是机器学习模型中广泛研究的现象。尽管大多数注意力集中在神经网络上，但其他实用模型也遭受了这个问题的困扰。在这项工作中，我们提出了一种算法，用于评估$ k $ neart最邻居分类的对抗性鲁棒性，即找到一个最小值 - 符号对抗性示例。与以前的建议不同，我们通过执行从给定输入点向外扩展的搜索来采用几何方法。在高水平上，搜索半径扩展到附近的Voronoi细胞，直到我们找到一个与输入点不同的单元格。为了将算法扩展到大型$ K $，我们引入了近似步骤，与基线相比，在各种数据集中找到具有较小规范的扰动。此外，我们分析了数据集的结构属性，在该数据集中我们的方法表现优于竞争。
Adversarial examples are a widely studied phenomenon in machine learning models. While most of the attention has been focused on neural networks, other practical models also suffer from this issue. In this work, we propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification, i.e., finding a minimum-norm adversarial example. Diverging from previous proposals, we take a geometric approach by performing a search that expands outwards from a given input point. On a high level, the search radius expands to the nearby Voronoi cells until we find a cell that classifies differently from the input point. To scale the algorithm to a large $k$, we introduce approximation steps that find perturbations with smaller norm, compared to the baselines, in a variety of datasets. Furthermore, we analyze the structural properties of a dataset where our approach outperforms the competition.
