DeepFool: a simple and accurate method to fool deep neural networks

Moosavidezfooli S, Fawzi A, Frossard P, et al. DeepFool: A Simple and Accurate Method to Fool Deep Neural Networks[C]. computer vision and pattern recognition, 2016: 2574-2582.

@article{moosavidezfooli2016deepfool:,
title={DeepFool: A Simple and Accurate Method to Fool Deep Neural Networks},
author={Moosavidezfooli, Seyedmohsen and Fawzi, Alhussein and Frossard, Pascal},
pages={2574–2582},
year={2016}}

概

本文从几何角度介绍了一种简单而有效的方法.

主要内容

adversarial的目的:
$\tag{1} \Delta(x;\hat{k}):= \min_{r} \|r\|_2 \: \mathrm{subject} \: \mathrm{to} \: \hat{k}(x+r) \not = \hat{k}(x),$Δ(x;k^):=rmin​∥r∥2​subjecttok^(x+r)​=k^(x),(1)
其中$\hat{k}(x)$k^(x)为对$x$x的标签的一个估计.

二分类模型

当模型是一个二分类模型时,
$\hat{k}(x) = \mathrm{sign}(f(x)),$k^(x)=sign(f(x)),
其中$f:\mathbb{R}^n \rightarrow \mathbb{R}$f:Rn→R为分类器, 并记$\mathcal{F}:= \{x: f(x)=0\}$F:={x:f(x)=0}为分类边界.

$f$f为线性

即$f(x)=w^Tx+b$f(x)=wTx+b:

假设$x_0$x0​在$f(x)>0$f(x)>0一侧, 则
$r_*(x_0)= -\frac{f(x_0)}{\|w\|_2^2}w.$r∗​(x0​)=−∥w∥22​f(x0​)​w.

$f$f为一般二分类

此时, 我们$f$f的一阶近似为
$f(x_0+r)\approx f(x_0)+\nabla^T f(x_0) r,$f(x0​+r)≈f(x0​)+∇Tf(x0​)r,
此时分类边界为$\mathcal{F} =\{x:f(x_0)+\nabla^T f(x_0) (x-x_0)=0\}$F={x:f(x0​)+∇Tf(x0​)(x−x0​)=0},此时$w=\nabla f(x_0),b=f(x_0),$w=∇f(x0​),b=f(x0​), 故
$\tag{4} r_*(x_0) \approx -\frac{f(x_0)}{\|\nabla f(x_0)\|_2^2} \nabla f(x_0).$r∗​(x0​)≈−∥∇f(x0​)∥22​f(x0​)​∇f(x0​).(4)

所以, 每次
$r_i = -\frac{f(x_i)}{\|\nabla f(x_i)\|_2^2} \nabla f(x_i), \\ x_{i+1} = x_i+r_i,$ri​=−∥∇f(xi​)∥22​f(xi​)​∇f(xi​),xi+1​=xi​+ri​,
直到$\hat{k}(x_i) \not= \hat{k}(x_0)$k^(xi​)​=k^(x0​)是停止, 算法如下

多分类问题

$f:\mathbb{R}^n \rightarrow \mathbb{R}^c$f:Rn→Rc, 此时
$\tag{5} \hat{k}(x) = \arg \max_k f_k(x).$k^(x)=argkmax​fk​(x).(5)

$f$f仿射

即$f(x) = W^Tx + b$f(x)=WTx+b, 设$W$W的第$k$k行为$w_k$wk​,
$\tag{7} P=\cap_{k=1}^c \{x: f_{\hat{k}(x_0)}(x) \ge f_k(x)\},$P=∩k=1c​{x:fk^(x0​)​(x)≥fk​(x)},(7)
为判定为$\hat{k}(x_0)$k^(x0​)的区域, 则$x+r$x+r应落在$P^{c}$Pc, 而
$\Delta (x_0;f)= \mathbf{dist} (x_0, P^c).$Δ(x0​;f)=dist(x0​,Pc).
当$f$f为仿射的时候, 实际上就是找$x_0$x0​到各分类边界(与$x_0$x0​有关的)最短距离,
$\tag{8} \hat{l}(x_0) = \arg \min _{k \not = \hat{k}(x_0)} \frac{|f_k(x_0) - f_{\hat{k}(x_0)}(x_0)|}{\|w_k-w_{\hat{k}(x_0)}\|_2},$l^(x0​)=argk​=k^(x0​)min​∥wk​−wk^(x0​)​∥2​∣fk​(x0​)−fk^(x0​)​(x0​)∣​,(8)
则
$\tag{9} r_*(x_0)= \frac{|f_{\hat{l}(x_0)}(x_0) - f_{\hat{k}(x_0)}(x_0)|}{\|w_{\hat{l}(x_0)}-w_{\hat{k}(x_0)}\|_2^2}(w_{\hat{l}(x_0)}-w_{\hat{k}(x_0)}),$r∗​(x0​)=∥wl^(x0​)​−wk^(x0​)​∥22​∣fl^(x0​)​(x0​)−fk^(x0​)​(x0​)∣​(wl^(x0​)​−wk^(x0​)​),(9)

$f$f为一般多分类

$\tag{10} \tilde{P}_i=\cap_{k=1}^c \{x: f_{\hat{k}(x_0)}(x_i) + \nabla^T f_{\hat{k}(x_0)}(x_i) (x-x_i)\ge f_k(x_i) + \nabla^Tf_k(x_i)(x-x_i)\},$P~i​=∩k=1c​{x:fk^(x0​)​(xi​)+∇Tfk^(x0​)​(xi​)(x−xi​)≥fk​(xi​)+∇Tfk​(xi​)(x−xi​)},(10)
则
$r_i(x_i)=\frac{|f_{\hat{l}(x_i)}(x_i) - f_{\hat{k}(x_0)}(x_i)|}{\|\nabla f_{\hat{l}(x_i)}(x_i) - \nabla f_{\hat{k}(x_0)}(x_i)\|_2^2}(\nabla f_{\hat{l}(x_i)}(x_i) - \nabla f_{\hat{k}(x_0)}(x_i)).$ri​(xi​)=∥∇fl^(xi​)​(xi​)−∇fk^(x0​)​(xi​)∥22​∣fl^(xi​)​(xi​)−fk^(x0​)​(xi​)∣​(∇fl^(xi​)​(xi​)−∇fk^(x0​)​(xi​)).

$l_p$lp​

$p \in (1, \infty)$p∈(1,∞)的时候
考虑如下的问题
$\begin{array}{ll} \min & \|r\|_p^p \\ \mathrm{s.t.} & w^T(x+r)+b=0, \end{array}$mins.t.​∥r∥pp​wT(x+r)+b=0,​
利用拉格朗日乘子
$\min_r \: \|r\|_p^p + c(w^T(x+r)+b),$rmin​∥r∥pp​+c(wT(x+r)+b),
由KKT条件可知(这里的$r_k$rk​表示第$k$k个元素)
$p\: |r_k|^{p-1} = c_kw_k,$p∣rk​∣p−1=ck​wk​,
注: 这里有一个符号的问题, 但是可以把符号放入$c_k$ck​中进而不考虑,
故
$r_*= c \odot w^{q-1},$r∗​=c⊙wq−1,
其中$q=\frac{p}{p-1}$q=p−1p​为共轭指数, 并$c=[c_1,\ldots]^T$c=[c1​,…]T,且$|c_i|=|c_j|,$∣ci​∣=∣cj​∣, 记$w^{q-1}=[|w_1|^{q-1},\ldots]^T$wq−1=[∣w1​∣q−1,…]T,又
$w^T(x+c\odot w^{q-1})+b=0,$wT(x+c⊙wq−1)+b=0,
故
$|c|=\frac{|w^Tx+b|}{\|w\|_q^q} ,$∣c∣=∥w∥qq​∣wTx+b∣​,
故
$r_*=-\frac{w^Tx+b}{\|w\|_q^q} w^{q-1} \odot \mathrm{sign}(w).$r∗​=−∥w∥qq​wTx+b​wq−1⊙sign(w).

$p=1$p=1, 设$w$w的绝对值最大的元素为$w_{m}$wm​, 则
$r_*=-\frac{w^Tx+b}{w_m} \mathrm{1}_m,$r∗​=−wm​wTx+b​1m​,
$\mathrm{1}_m$1m​为第$m$m个元素为1, 其余元素均为0的向量.
$p=\infty$p=∞,
$r_*=-\frac{|w^Tx+b|}{\|w\|_1} \mathrm{sign} (w).$r∗​=−∥w∥1​∣wTx+b∣​sign(w).

故:

$p \in [1, \infty)$p∈[1,∞):

$p=\infty$p=∞:

注: 因为, 仅仅到达边界并不足够, 往往希望更进一步, 所以在最后(?)$x=x+ (1+\eta) r$x=x+(1+η)r, 文中取$\eta=0.02$η=0.02.