论文阅读 (54)：DeepFool: A Simple and Accurate Method to Fool Deep Neural Networks

1 引入

1.1 题目

  2016CVPR：简单愚弄深度神经网络 (DeepFool: A simple and accurate method to fool deep neural networks)

1.2 动机

  深度神经网络在图像分类任务上的成就毋庸置疑。然而，这些架构已被证明对图像的小扰动缺乏健壮性，目前也缺乏有效的方法来准确计算深度分类器应对大规模数据集上扰动的鲁棒性。本文则对这些鲁棒性进行可靠量化。

1.3 代码

  Torch：http://github.com/lts4/deepfool

1.4 Bib

@inproceedings{Moosavi:2016:25742582,
author		=	{Seyed-Mohsen Moosavi-Dezfooli and Alhussein Fawzi and Pascal Frossard},
title		=	{Deep{F}ool: A simple and accurate method to fool deep neural networks},
booktitle	=	{
   {IEEE} Conference on Computer Vision and Pattern Recognition},
pages		=	{2574--2582},
year		=	{2016}
}

2 DeepFool

  对于给定的分类器，定义一个最小对抗性扰动$r$，其用于改变样本的评估标签$\hat{k}(x)$：
$$\Delta (x;\hat{k}):=\underset{r}{\min }\Vert r{\Vert }_{2}s.t.\hat{k}(x+r)\ne \hat{k}(x),\text{\hspace{1em}(1)}$$其中$x$是输入图像。该式也称为$\hat{k}$在点$x$的健壮性，因此分类器$\hat{k}$的健壮性定义为：
$${\rho }_{\text{adv}}(\hat{k})={\mathbb{E}}_x\frac{\Delta (x;\hat{k})}{\Vert x{\Vert }_2},\text{\hspace{1em}(2)}$$其中${\mathbb{E}}_x$是数据集分布的期望。

3 DeepFool与二分类

  二分类问题下，有$\hat{k}(x)=\text{sign}(f(x))$，其中$f:{\mathbb{R}}^n\to \mathbf{R}$是一个图像分类函数。令$\mathcal{F}\stackrel{\Delta }{=}\{x:f(x)=0\}$表示$f$在0处的level set。首先分析线性分类器$f(x)=w^{T}x+b$的情况，然后推导出可以应用于任何可微分二分类器的通用算法。
  可以很容易看出线性$f$在点$x_0$处的鲁棒性，$\Delta (x;f)$等价于$x_0$到分隔超平面$\mathcal{F}=\{x:w^{T}x+b=0\}$的距离 (如图2)，改变分类器决策的最小扰动对应于$x_0$到$\mathcal{F}$的正交投影。一个用于描述该过程的封闭式公式如下：
$$r_{\ast }(x_0):=\mathrm{argmin}\Vert r{\Vert }_{2}s.t.\text{sign}(f(x_0+r))\ne \text{sign}(f(x_0))=-\frac{f(x_0)}{\Vert w{\Vert }_2^2}w.\text{\hspace{1em}(3)}$$

  假设$f$一个一般性二分类可微分分类器，我们使用一个迭代策略来评估健壮性$\Delta (x_0;f)$。在每次迭代中，$f$围绕当前点$x_i$线性化，线性分类器的最小化扰动计算为
$$\underset{r_i}{\mathrm{argmin}}\Vert r_i\Vert s.t.f(x_i)+\nabla f(x_i{)}^T{r}_i=0.\text{\hspace{1em}(4)}$$扰动$r_i$在每次迭代中通过公式3计算，并在下一次迭代$x_{i+1}$时更新。算法将在分类器的标志改变时停止。算法1总结了DeepFool针对二分类问题的过程。图3是一个可视化结果。


  实际上，上述算法往往可以收敛到零水平集$\mathcal{F}$上的一点。为了达到分类边界的另一边，最终的扰动$\hat{r}$将乘以一个常量$1+\eta$，其中$\eta \ll 1$。在实验中将设置为$0.02$。

4 DeepFool与多分类

  一对多是最常用的多分类策略，因此我们基于该策略来扩展DeepFool到多分类上。在该设置下，分类器将有$c$个输出，因此分类器被定义为$f:{\mathbb{R}}^d\to {\mathbb{R}}^c$且：
$$\hat{k}(x)=\underset{k}{\mathrm{argmax}}{f}_k(x),\text{\hspace{1em}(5)}$$其中$f_k(x)$是$f(x)$在第$c$类上的输出。与二分类相似，首先分析线性情况并推广到其他分类器。

4.1 线性多分类器

  令$f(x)=W^{T}x+b$表示一个线性分类器，在一对多的策略下，愚弄分类器的最小扰动被重写为：
$$\underset{r}{\mathrm{argmin}}\Vert r{\Vert }_{2}s.t.\exists k:w_k^T(x_0+r)+b_k\ge w_{\hat{k}(x_0)}^T(x_0+r)+b_{\hat{k}(x_0)},\text{\hspace{1em}(6)}$$其中$w_k$是$W$的第$k$列。几何上，上述问题对应于计算$x_0$与凸多面体complement$P$之间的距离：
$$P=\bigcap _{k=1}^c\{x:f_{\hat{k}(x_o)}(x)\ge f_k(x)\},\text{\hspace{1em}(7)}$$其中$x_0$是位于$P$内的点。我们定义这个距离为$\mathbf{d}\mathbf{i}\mathbf{s}\mathbf{t}(x_0,P^c)$。多面体$P$定义了$f$输出标签$\hat{k}(x_0)$的空间区域，如图4所示。

  公式6的解决方案可以用封闭形式计算如下。令$\hat{l}(x_0)$表示离$P$的边界最近的一个超平面，例如图4中的$\hat{l}(x_0)=3$。形式上，$\hat{l}(x_0)$可以计算为：
$$\hat{l}\left(x_0\right)=\underset{k\ne \hat{k}\left(x_0\right)}{\mathrm{argmin}}\frac{\left|f_k\left(x_0\right)-f_{\hat{k}\left(x_0\right)}\left(x_0\right)\right|}{{\Vert w_k-w_{\hat{k}\left(x_0\right)}\Vert }_2}.\text{\hspace{1em}(8)}$$最小扰动$r_{\ast }(x_0)$是将$x_0$投影到由$\hat{l}(x_0)$索引的超平面上的向量：
$$r_{\ast }\left(x_0\right)=\frac{\left|f_{\hat{l}\left(x_0\right)}\left(x_0\right)-f_{\hat{k}\left(x_0\right)}\left(x_0\right)\right|}{{\Vert w_{\hat{l}\left(x_0\right)}-w_{\hat{k}\left(x_0\right)}\Vert }_2^2}\left(w_{\hat{l}\left(x_0\right)}-w_{\hat{k}\left(x_0\right)}\right).\text{\hspace{1em}(9)}$$换句话说，我们可以找到$x_o$在$P$的平面上的最近投影。

4.2 广义分类器

  对于非线性分类器，公式7中描述分类器输出标签$\hat{k}(x_0)$空间区域的集合$P$不再是多面体。与二分类下的迭代求解类似，集合$P$通过第$i$轮迭代的多面体${\tilde{P}}_i$近似：
$${\tilde{P}}_i=\bigcap _{k=1}^c\left\{x:f_k(x_i)-f_{\hat{k}(x_0)}(x_i)+\nabla f_k(x_i{)}^{T}x-\nabla f_{\hat{k}(x_0)}(x_i{)}^{T}x\le 0\right\}.\text{\hspace{1em}(10)}$$然后在每一次迭代中通过$\mathbf{d}\mathbf{i}\mathbf{s}\mathbf{t}(x_i,{\tilde{P}}_i)$来近似$\mathbf{d}\mathbf{i}\mathbf{s}\mathbf{t}(x_i,P_i)$。算法2展示了该过程。应该注意的是，所提出的算法以贪婪的方式运行，不能保证收敛到公式1中的最优扰动。而实践中观察中的结果显示所提算法可以产生非常小的扰动，这被认为是最小扰动的良好近似。

4.3 ${\ell }_p$范数的扩展版本

  DeepFool的前述步骤均在${\ell }_2$下进行，当在${\ell }_p,p\in [1,\infty )$下约束时，算法2中的第10、11行需要被替换为：
$$\hat{l}\leftarrow \underset{k\ne \hat{k}\left(x_0\right)}{\mathrm{argmin}}\frac{\left|f_k^{\prime }\right|}{{\Vert w_k^{\prime }\Vert }_q},\text{\hspace{1em}(11)}$$$$r_i\leftarrow \frac{\left|f_{\hat{ı}}^{\prime }\right|}{{\Vert w_{\hat{ı}}^{\prime }\Vert }_q^q}{\left|w_{\hat{ı}}^{\prime }\right|}^{q-1}\odot \mathrm{sign}\left(w_{\hat{l}}^{\prime }\right),\text{\hspace{1em}(12)}$$
其中$\odot$是按元素相乘、$q=\frac{p}{p-1}\cdot$。特别地当$p=\infty$时，有：
$$\hat{l}\leftarrow \underset{k\ne \hat{k}\left({\mathbf{x}}_0\right)}{\mathrm{argmin}}\frac{\left|f_k^{\prime }\right|}{{\Vert {\mathbf{w}}_k^{\prime }\Vert }_1},\text{\hspace{1em}(13)}$$$${\mathbf{r}}_i\leftarrow \frac{\left|f_{\hat{l}}^{\prime }\right|}{{\Vert {\mathbf{w}}_{\hat{l}}^{\prime }\Vert }_1}\mathrm{sign}\left({\mathbf{w}}_{\hat{l}}^{\prime }\right).\text{\hspace{1em}(14)}$$