【论文快读】DeepFool: a simple and accurate method to fool deep neural networks(2016)

作者：Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Pascal Frossard École Polytechnique Fédérale de Lausanne
链接：https://arxiv.org/abs/1511.04599
摘要：

本文内容：
对于robustness的量化与计算；
DeepFool算法。

形式化

图像x∈$\mathbf{\text{x}}\in$图像空间Rn${\mathbb{R}}^n$。
分类器k^(x)$\hat{k}(\mathbf{\text{x}})$在点x$x$处的鲁棒性Δ(x;k^)$\mathrm{\Delta }(\mathbf{\text{x}};\hat{k})$：(几何意义是x$\mathbf{\text{x}}$到分类边界的距离)

其中r$\mathbf{\text{r}}$是能够fool分类器的最小扰动。
分类器k^(x)$\hat{k}(\mathbf{\text{x}})$的鲁棒性：
（点面距离越远，计算输入的样本度量越小，模型越健壮）

二分类问题

记k^(x)=sign(wTx+b):=sign(f(x))$\hat{k}(\mathbf{\text{x}})=sign({\mathbf{\text{w}}}^T\mathbf{\text{x}}+b):=sign(f(\mathbf{\text{x}}))$
分类边界F={x:f(x)=0}$\mathcal{F}=\{\mathbf{\text{x}}:f(\mathbf{\text{x}})=0\}$
扰动向量r⋆(x0):=argminr||r||2s.t. sign(f(x0+r))≠sign(f(x0))${\mathbf{\text{r}}}_{\star }({\mathbf{\text{x}}}_0):=\arg \underset{\mathbf{\text{r}}}{min}||\mathbf{\text{r}}|{|}_{2}s.t.sign(f({\mathbf{\text{x}}}_0+\mathbf{\text{r}}))\ne sign(f({\mathbf{\text{x}}}_0))$
=−f(x0)||w||22w$=-{\displaystyle \frac{f({\mathbf{\text{x}}}_0)}{||\mathbf{\text{w}}|{|}_2^2}}\mathbf{\text{w}}$
迭代算法如下：

多分类问题

label数：c$c$
记分类函数f(x)=WTx+b$f(\mathbf{\text{x}})={\mathbf{\text{W}}}^T\mathbf{\text{x}}+\mathbf{\text{b}}$
分类器k^(x)=argmaxkfk(x)$\hat{k}(\mathbf{\text{x}})=\arg \underset{k}{max}{f}_k(\mathbf{\text{x}})$，fk(x)是向量f(x)$f_k(\mathbf{\text{x}})是向量f(\mathbf{\text{x}})$的第k$k$个维度。
扰动向量：argminr||r||2$\arg \underset{\mathbf{\text{r}}}{min}||\mathbf{\text{r}}|{|}_2$
s.t.∃k:wTk(x0+r)+bk≥wTk^(x0)(x0+r)+bk^(x0)$s.t.\mathrm{\exists }k:{\mathbf{\text{w}}}_k^T({\mathbf{\text{x}}}_0+\mathbf{\text{r}})+{\mathbf{\text{b}}}_k\ge {\mathbf{\text{w}}}_{\hat{k}({\mathbf{\text{x}}}_0)}^T({\mathbf{\text{x}}}_0+\mathbf{\text{r}})+{\mathbf{\text{b}}}_{\hat{k}({\mathbf{\text{x}}}_0)}$
其中wk${\mathbf{\text{w}}}_k$是W$\mathbf{\text{W}}$的第k$k$列。、
几何意义为寻找x0${\mathbf{\text{x}}}_0$与所在的凸区域P=⋂k=1c{x:fk^(x0)(x)≥fk(x)}$P=\bigcap _{k=1}^c\{\mathbf{\text{x}}:f_{\hat{k}({\mathbf{\text{x}}}_0)}(\mathbf{\text{x}})\ge f_k(\mathbf{\text{x}})\}$边界的最小距离，即：

所以最小扰动r⋆(x0)=|fl^(x0)(x0)−fk^(x0)(x0)|||wl^(x0)−wk^(x0)||22(wl^(x0)−wk^(x0))${\mathbf{\text{r}}}_{\star }({\mathbf{\text{x}}}_0)={\displaystyle \frac{|f_{\hat{l}({\mathbf{\text{x}}}_0)}({\mathbf{\text{x}}}_0)-f_{\hat{k}({\mathbf{\text{x}}}_0)}({\mathbf{\text{x}}}_0)|}{||{\mathbf{\text{w}}}_{\hat{l}({\mathbf{\text{x}}}_0)}-{\mathbf{\text{w}}}_{\hat{k}({\mathbf{\text{x}}}_0)}|{|}_2^2}}({\mathbf{\text{w}}}_{\hat{l}({\mathbf{\text{x}}}_0)}-{\mathbf{\text{w}}}_{\hat{k}({\mathbf{\text{x}}}_0)})$
当边界非线性时，把上述w$\mathbf{\text{w}}$替换成∇f((x))$\mathrm{\nabla }f(\mathbf{\text{(}}x))$即可（如下算法2）

值得注意的是本算法的输出不是optimal的，但实验中已经能够大概率实现小幅度扰动了。