Adversarial Examples for k-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
Adversarial Examples for k-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Chawin Sitawarin;Evgenios M. Kornaropoulos;D. Song;David A. Wagner
中科院分区：
文献类型：
--
作者：
Chawin Sitawarin;Evgenios M. Kornaropoulos;D. Song;David A. Wagner
对抗性示例是机器学习模型中广泛研究的现象。虽然大多数注意力都集中在神经网络上，但其他实际模型也会遇到这个问题。在这项工作中，我们提出了一个算法评估的对抗鲁棒性的$k$-最近邻分类，即，找到一个最小范数的对抗性例子。与以前的建议不同，我们采取了几何方法，通过执行从给定输入点向外扩展的搜索。在高级别上，搜索半径扩展到附近的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.