Paper reading (54):deepfool: a simple and accurate method to four deep neural networks

1 introduce

1.1 subject

  2016CVPR： Simple fool deep neural network (DeepFool: A simple and accurate method to fool deep neural networks)

1.2 motivation

   There is no doubt about the achievements of deep neural network in image classification . However , These architectures have been shown to be less robust to small perturbations in images , At present, there is also a lack of effective methods to accurately calculate the robustness of depth classifiers to large-scale data sets . This paper quantifies these robustness reliably .

1.3 Code

  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

   For a given classifier , Define a minimum Antagonistic disturbance $r$, It is used to change the evaluation label of the sample $\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)}$$ among $x$ It's the input image . This formula is also called $\hat{k}$ At point $x$ Robustness of , So the classifier $\hat{k}$ Of Robustness, Defined as ：
$${\rho }_{\text{adv}}(\hat{k})={\mathbb{E}}_x\frac{\Delta (x;\hat{k})}{\Vert x{\Vert }_2},\text{\hspace{1em}(2)}$$ among ${\mathbb{E}}_x$ Is the expectation of data set distribution .

3 DeepFool And two categories

   Under the second classification problem , Yes $\hat{k}(x)=\text{sign}(f(x))$, among $f:{\mathbb{R}}^n\to \mathbf{R}$ Is an image classification function . Make $\mathcal{F}\stackrel{\Delta }{=}\{x:f(x)=0\}$ Express $f$ stay 0 Situated level set. First, the linear classifier is analyzed $f(x)=w^{T}x+b$ The situation of , Then we derive a general algorithm that can be applied to any differentiable two classifiers .
   It is easy to see the linearity $f$ At point $x_0$ Robustness at ,$\Delta (x;f)$ Equivalent to $x_0$ To the separating hyperplane $\mathcal{F}=\{x:w^{T}x+b=0\}$ Distance of ( Such as chart 2), The minimum disturbance that changes the decision of the classifier corresponds to $x_0$ To $\mathcal{F}$ The orthogonal projection of . A closed form formula to describe the process is as follows ：
$$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)}$$

   hypothesis $f$ A general two class differentiable classifier , We use one Iteration strategy To assess robustness $\Delta (x_0;f)$. In each iteration ,$f$ Around the current point $x_i$ Linearization , The minimum disturbance of the linear classifier is calculated as
$$\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)}$$ Disturbance $r_i$ Pass the formula in each iteration 3 Calculation , And in the next iteration $x_{i+1}$ When the update . The algorithm will stop when the flag of the classifier changes . Algorithm 1 Sum up DeepFool Process for binary classification problems . chart 3 Is a visual result .


   actually , The above algorithm can often converge to the zero level set $\mathcal{F}$ The last point . To reach the other side of the classification boundary , The final disturbance $\hat{r}$ Will multiply by a constant $1+\eta$, among $\eta \ll 1$. Set to... In the experiment $0.02$.

4 DeepFool And multiclassification

   One to many is the most commonly used multi classification strategy , So we extend... Based on this strategy DeepFool To multiple categories . Under this setting , The classifier will have $c$ Outputs , So the classifier is defined as $f:{\mathbb{R}}^d\to {\mathbb{R}}^c$ And ：
$$\hat{k}(x)=\underset{k}{\mathrm{argmax}}{f}_k(x),\text{\hspace{1em}(5)}$$ among $f_k(x)$ yes $f(x)$ In the $c$ Class . Similar to the second classification , First, the linear case is analyzed and extended to other classifiers .

4.1 Linear multiple classifiers

   Make $f(x)=W^{T}x+b$ Represents a linear classifier , Under the one to many strategy , The minimum disturbance of fooling the classifier is rewritten as ：
$$\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)}$$ among $w_k$ yes $W$ Of the $k$ Column . Geometrically , The above problem corresponds to the calculation $x_0$ And convex polyhedron complement$P$ Distance between ：
$$P=\bigcap _{k=1}^c\{x:f_{\hat{k}(x_o)}(x)\ge f_k(x)\},\text{\hspace{1em}(7)}$$ among $x_0$ It's located in $P$ In the point . We define this distance by $\mathbf{d}\mathbf{i}\mathbf{s}\mathbf{t}(x_0,P^c)$. Polyhedron $P$ Defined $f$ Output label $\hat{k}(x_0)$ The spatial area of , Such as chart 4 Shown .

   The formula 6 The solution of can be calculated in closed form as follows . Make $\hat{l}(x_0)$ It means to leave $P$ The nearest hyperplane to the boundary of , for example chart 4 Medium $\hat{l}(x_0)=3$. Formally ,$\hat{l}(x_0)$ It can be calculated as ：
$$\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)}$$ Minimum disturbance $r_{\ast }(x_0)$ Yes, it will $x_0$ Projected to by $\hat{l}(x_0)$ Vectors on the hyperplane of the index ：
$$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)}$$ let me put it another way , We can find $x_o$ stay $P$ The nearest projection on the plane of .

4.2 Generalized classifier

   For nonlinear classifiers , The formula 7 Describes the output label of the classifier $\hat{k}(x_0)$ A collection of spatial regions $P$ No longer a polyhedron . It is similar to the iterative solution under two categories , aggregate $P$ Pass the first $i$ Round iterated polyhedron ${\tilde{P}}_i$ The approximate ：
$${\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)}$$ And then in each iteration through $\mathbf{d}\mathbf{i}\mathbf{s}\mathbf{t}(x_i,{\tilde{P}}_i)$ To approximate $\mathbf{d}\mathbf{i}\mathbf{s}\mathbf{t}(x_i,P_i)$. Algorithm 2 Shows the process . It should be noted that , The proposed algorithm runs greedily , Convergence to... Is not guaranteed The formula 1 Optimal perturbation in . The observation results in practice show that the proposed algorithm can produce very small disturbance , This is considered to be a good approximation of the minimum disturbance .

4.3 ${\ell }_p$ An extended version of the norm

  DeepFool The previous steps of are in ${\ell }_2$ Proceed under , When in ${\ell }_p,p\in [1,\infty )$ When you lower the constraint , Algorithm 2 No 10、11 The line needs to be replaced with ：
$$\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)}$$
among $\odot$ Multiply by elements 、$q=\frac{p}{p-1}\cdot$. Specially $p=\infty$ when , Yes ：
$$\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)}$$