摘要
本文研究K-近邻分类器的鲁棒性验证问题.形式化鲁棒性验证的目标是计算分类器在给定样本点上的最小对抗扰动的精确值或者最小对抗扰动的非平凡下界.我们将计算K-近邻分类器的最小对抗扰动形式化为一组二次规划问题.二次规划问题的数目随近邻参数K的增大呈指数级增长,精确求解该组二次规划问题往往不可行.约束放松法通过放松优化的约束项,可以在多项式时间内求解最小对抗扰动的下界.然而,本文通过理论分析和实验发现,当近邻参数K取值较大时,约束放松法求得的下界往往过于宽松,甚至会出现K越大下界越小的反直觉结果.为解决这一问题,本文提出使用随机平滑法对K-近邻分类器进行鲁棒性验证.随机平滑法利用了K-近邻分类器对高斯(Gauss)白噪声鲁棒的特点,获得了较为理想的鲁棒性验证效果.基准数据集上的实验结果表明,相比于最新的鲁棒神经网络,"随机平滑的"K-近邻分类器展现出了更好的验证鲁棒性.
We study the robustness verification problem for K-NN classifiers.The objective of formal robustness verification is to find the exact minimal adversarial perturbation or a guaranteed lower bound of the perturbation.We find that the robustness verification of K-NN classifiers could be formalized as a series of quadratic programming problems.Solving these quadratic programming problems is not possible in general because the number of problems grows exponentially with respect to K.The constraint relaxation method is proposed to compute the lower bound of the minimal adversarial perturbation in polynomial time.However,we find that the resulting lower bound tends to be extremely loose when K is large;hence,K-NN with a large K being less robust is counterintuitive.To tackle this issue,we propose to employ the randomized smoothing method to verify the robustness of K-NN classifiers.By exploiting the resistance of K-NN to random Gaussian noise,the randomized smoothing method achieves high performance in verification.Our experiments on benchmark datasets show that the smoothed K-NN classifier is more verifiably robust than state-of-the-art robust neural networks.
作者
王璐
姜远
Lu WANG;Yuan JIANG(National Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China;Collaborative Innovation Center of Novel Software Technology and Industrialization,Nanjing University,Nanjing 210023,China)
出处
《中国科学：信息科学》
CSCD
北大核心
2021年第1期27-39,共13页
Scientia Sinica(Informationis)
基金
国家自然科学基金(批准号:61673201,61921006)
南京大学优秀博士研究生创新能力提升计划A资助项目。
关键词
监督学习
对抗机器学习
对抗鲁棒性
鲁棒性验证
K-近邻分类器
supervised learning
adversarial machine learning
adversarial robustness
robustness verification
K-NN classifier
