對抗子空間維度探討

引言

?對抗樣本是深度學習模型的主要威脅之一，對抗樣本會使得目標分類器模型分類出錯并且它存在于稠密的對抗子空間中，對抗子空間又包含于特定的樣本空間中，本文主要是對對抗子空間維數進行探討，即針對于單個模型的特定樣本對抗子空間的維度是多少，針對多個模型的特定樣本對抗子空間的維度是多少，

對抗子空間

?給定干凈樣本 x ∈ R d x\in \mathbb{R}^d x∈Rd，以及其對應的標簽 y y y，帶有引數 θ \theta θ的神經網路分類器為 f θ ( ? ) f_\theta(\cdot) fθ?(?)，損失函式為 J ( x , y ; θ ) J(x,y;\theta) J(x,y;θ)，對抗樣本為 x ′ x^{\prime} x′，則根據多元泰勒展開式可得 J ( x ′ , y ; θ ) = J ( x , y ; θ ) + ( x ′ ? x ) ? ? x J ( x , y ; θ ) + O ( ∥ x ′ ? x ∥ 2 ) J(x^{\prime},y;\theta)=J(x,y;\theta)+(x^{\prime}-x)^{\top}\nabla_x J(x,y;\theta)+O(\|x^{\prime}-x\|^2) J(x′,y;θ)=J(x,y;θ)+(x′?x)??x?J(x,y;θ)+O(∥x′?x∥2)進一步可得優化目標為 m a x i m i z e J ( x , y ; θ ) + ( x ′ ? x ) ? ? x J ( x , y ; θ ) s u b j e c t t o ∥ x ′ ? x ∥ ∞ ≤ ε \begin{array}{rl}\mathrm{maximize}& J(x,y;\theta)+(x^{\prime}-x)^{\top}\nabla_x J(x,y;\theta)\\\mathrm{subject \text{ }to}& \|x^{\prime}-x\|_{\infty} \le \varepsilon\end{array} maximizesubject to?J(x,y;θ)+(x′?x)??x?J(x,y;θ)∥x′?x∥∞?≤ε?進而可得對抗樣本的計算公式為 x ′ = x + ε ? ? x J ( x , y ; θ ) x^{\prime}=x+\varepsilon \cdot\nabla_x J(x,y;\theta) x′=x+ε??x?J(x,y;θ)其中 ε \varepsilon ε表示的是對抗擾動的大小，由上公式可知，干凈樣本 x x x沿著梯度方向 ? x J ( x , y ; θ ) \nabla_x J(x,y;\theta) ?x?J(x,y;θ)可以進入到對抗子空間中，進一步詳細的闡述如下圖所示，其中圖（a）,（b）和（c）表示的是給定一個干凈樣本沿著不同的方向生成的樣本輸入到分類器分類的結果示意圖，每個方格表示每一個樣本的分類結果，方格中白色表示分類器分類正確，彩色表示分類器分類成其它不同的類別，圖（d） ,（e）和（f）表示樣本移動的方向分解示意圖，

由上圖（d）可知，如果選擇兩個正交方向，一個是對抗擾動的梯度方向，另一個是隨機擾動方向，從圖（a）可知，沿著對抗擾動方向的干凈樣本可以進入到對抗子空間中，沿著隨機擾動的方向則沒有生成對抗樣本，由上圖（e）可知，如果這兩個正交方向與梯度方向成一個角度，則從圖（b）可知這兩個正交方向都可以進入到對抗子空間中，但是卻不是最速方向，由上圖（f）可知，如果這兩個正交方向是都是隨機擾動，從圖（c）可知，干凈樣本都很難進入到對抗子空間中去，該圖出現誤分類的情況與對抗樣本無關，跟模型自身的訓練情況有關，

單模型對抗子空間維數

?由上一節對對抗樣本損失函式的多元泰勒展開可以近似有 J ( x ′ , y ; θ ) ≈ J ( x , y ′ ; θ ) + ( x ′ ? x ) ? ? x J ( x , y ; θ ) J(x^{\prime},y;\theta)\approx J(x,y';\theta)+(x^{\prime}-x)^{\top} \nabla_x J(x,y;\theta) J(x′,y;θ)≈J(x,y′;θ)+(x′?x)??x?J(x,y;θ)其中令 g = ? x J ( x , y ; θ ) ∈ R d g = \nabla_x J(x,y;\theta)\in \mathbb{R}^d g=?x?J(x,y;θ)∈Rd， r = ( x ′ ? x ) ∈ R d r = (x^{\prime}-x)\in \mathbb{R}^d r=(x′?x)∈Rd，目的是要探究給定一個模型，求解對抗擾動 r r r使得模型損失函式至少增長 α \alpha α得對抗子空間維度的問題，數學表述為 J ( x ′ , y ; θ ) ? J ( x , y ; θ ) = r ? g ≥ α \begin{aligned}J(x^{\prime},y;\theta)-J(x,y;\theta)&=r^{\top} g\ge \alpha\\\end{aligned} J(x′,y;θ)?J(x,y;θ)?=r?g≥α?其中 r ∈ S p a n { r 1 , r 2 ? ? , r k } r \in \mathrm{Span}\{r_1,r_2\cdots,r_k\} r∈Span{r1?,r2??,rk?}，即擾動 r r r屬于 r 1 , r 2 , ? ? , r k r_1,r_2,\cdots,r_k r1?,r2?,?,rk?這 k k k個正交向量組成的對抗子空間中， k k k就是對抗子空間的維度，此時有如下定理成立，詳細證明程序如下所示：

定理： 給定 g ∈ R d g \in \mathbb{R}^{d} g∈Rd 和 α ∈ [ 0 , 1 ] \alpha \in[0,1] α∈[0,1]，最大對抗子空間維數 k k k的正交向量 r 1 , r 2 , … , r k r_1,r_2,\ldots,r_k r1?,r2?,…,rk? 滿足 ∥ r i ∥ 2 ≤ 1 \left\|r_{i}\right\|_{2} \leq 1 ∥ri?∥2?≤1， g ? r i ≥ α ? ∥ g ∥ 2 g^{\top} r_{i} \geq \alpha \cdot\|g\|_{2} g?ri?≥α?∥g∥2?的充要條件是 k = min ? { ? 1 α 2 ? , d } k=\min \left\{\left\lfloor\frac{1}{\alpha^{2}}\right\rfloor, d\right\} k=min{?α21??,d}，

證明：
必要性證明： 已知 g ∈ R d g \in \mathbb{R}^{d} g∈Rd 和 α ∈ [ 0 , 1 ] \alpha \in[0,1] α∈[0,1]，令 r ^ i : = r i ∥ r i ∥ 2 \hat{r}_{i}:=\frac{r_{i}}{\left\|r_{i}\right\|_{2}} r^i?:=∥ri?∥2?ri??，并且 r 1 , r 2 , … , r k r_{1}, r_{2}, \ldots, r_{k} r1?,r2?,…,rk?是正交的，由此可知 k ≤ d k \leq d k≤d，
（1）如果 k = d k = d k=d，則由向量乘積公式可知： ∑ i = 1 k ∣ g ? r ^ i ∣ 2 = ∑ i = 1 d ∣ g ? r ^ i ∣ 2 = ∑ i = 1 d ∥ g ∥ 2 2 ∥ r ^ i ∥ 2 2 cos ? 2 α i \sum_{i=1}^{k}\left|g^{\top} \hat{r}_{i}\right|^{2}=\sum_{i=1}^{d}\left|g^{\top} \hat{r}_{i}\right|^{2} = \sum_{i=1}^{d} \|g\|_{2}^{2} \|\hat{r}_{i}\|_{2}^{2} \cos^{2} \alpha_{i} i=1∑k?∣∣?g?r^i?∣∣?2=i=1∑d?∣∣?g?r^i?∣∣?2=i=1∑d?∥g∥22?∥r^i?∥22?cos2αi?其中， cos ? α i \cos \alpha_{i} cosαi? 表示的是向量 g g g和 r ^ i \hat{r}_{i} r^i?的余弦值，并且又知道 ∥ r ^ i ∥ 2 2 = 1 \|\hat{r}_{i}\|_{2}^{2}=1 ∥r^i?∥22?=1，所以有 ∑ i = 1 d ∥ g ∥ 2 2 ∥ r ^ i ∥ 2 2 cos ? 2 α i = ∥ g ∥ 2 2 ∑ i = 1 d cos ? 2 α i = ∥ g ∥ 2 2 \sum_{i=1}^{d} \|g\|_{2}^{2} \|\hat{r}_{i}\|_{2}^{2} \cos^{2} \alpha_{i} = \|g\|_{2}^{2} \sum_{i=1}^{d} \cos^{2} \alpha_{i} = \|g\|_{2}^{2} i=1∑d?∥g∥22?∥r^i?∥22?cos2αi?=∥g∥22?i=1∑d?cos2αi?=∥g∥22?進而則有 ∑ i = 1 k ∣ g ? r ^ i ∣ 2 = ∥ g ∥ 2 2 \sum_{i=1}^{k}\left|g^{\top} \hat{r}_{i}\right|^{2} = \|g\|_{2}^{2} i=1∑k?∣∣?g?r^i?∣∣?2=∥g∥22?
（2）如果 k < d k < d k<d，則先對 r 1 , r 2 , … , r k r_{1}, r_{2}, \ldots, r_{k} r1?,r2?,…,rk?進行正交擴充，擴充為 r 1 , r 2 , … , r k , r k + 1 , … , r d r_{1}, r_{2}, \ldots, r_{k}, r_{k+1},\ldots, r_{d} r1?,r2?,…,rk?,rk+1?,…,rd?則可知 ∑ i = 1 k ∣ g ? r ^ i ∣ 2 < ∑ i = 1 d ∣ g ? r ^ i ∣ 2 = ∑ i = 1 d ∥ g ∥ 2 2 ∥ r ^ i ∥ 2 2 cos ? 2 α i = ∥ g ∥ 2 2 \sum_{i=1}^{k}\left|g^{\top} \hat{r}_{i}\right|^{2}< \sum_{i=1}^{d}\left|g^{\top} \hat{r}_{i}\right|^{2} = \sum_{i=1}^{d} \|g\|_{2}^{2} \|\hat{r}_{i}\|_{2}^{2} \cos^{2} \alpha_{i} = \|g\|_{2}^{2} i=1∑k?∣∣?g?r^i?∣∣?2<i=1∑d?∣∣?g?r^i?∣∣?2=i=1∑d?∥g∥22?∥r^i?∥22?cos2αi?=∥g∥22?進而可知 ∥ g ∥ 2 2 ≥ ∑ i = 1 k ∣ g ? r ^ i ∣ 2 \|g\|_{2}^{2} \geq \sum_{i=1}^{k}\left|g^{\top} \hat{r}_{i}\right|^{2} ∥g∥22?≥i=1∑k?∣∣?g?r^i?∣∣?2又因為 r ^ i : = r i ∥ r i ∥ 2 \hat{r}_{i}:=\frac{r_{i}}{\left\|r_{i}\right\|_{2}} r^i?:=∥ri?∥2?ri??，所以有 ∑ i = 1 k ∣ g ? r ^ i ∣ 2 = ∑ i = 1 k ∣ g ? r i ∥ r i ∥ 2 ∣ 2 ≥ ∑ i = 1 k ∣ g ? r i ∣ 2 ∥ r i ∥ 2 2 \sum_{i=1}^{k}\left|g^{\top} \hat{r}_{i}\right|^{2} = \sum_{i=1}^{k}\left|g^{\top} \frac{r_{i}}{\left\|r_{i}\right\|_{2}} \right|^{2} \geq \sum_{i=1}^{k} \frac{\left|g^{\top} r_{i}\right|^{2}}{\left\|r_{i}\right\|_{2}^{2}} i=1∑k?∣∣?g?r^i?∣∣?2=i=1∑k?∣∣∣∣?g?∥ri?∥2?ri??∣∣∣∣?2≥i=1∑k?∥ri?∥22?∣∣?g?ri?∣∣?2?
因為 g ? r i ≥ α ? ∥ g ∥ 2 g^{\top} r_{i} \geq \alpha \cdot\|g\|_{2} g?ri?≥α?∥g∥2?， ∥ r i ∥ 2 ≤ 1 \left\|r_{i}\right\|_{2} \leq 1 ∥ri?∥2?≤1，所以有 ∑ i = 1 k ∣ g ? r i ∣ 2 ∥ r i ∥ 2 2 ≥ k ? α 2 ? ∥ g ∥ 2 2 \sum_{i=1}^{k} \frac{\left|g^{\top} r_{i}\right|^{2}}{\left\|r_{i}\right\|_{2}^{2}} \geq k \cdot \alpha^{2} \cdot\|g\|_{2}^{2} i=1∑k?∥ri?∥22?∣∣?g?ri?∣∣?2?≥k?α2?∥g∥22?又因為 k ≤ ? 1 α 2 ? k \leq \left\lfloor\frac{1}{\alpha^{2}}\right\rfloor k≤?α21??
最終有 max ? { k } = min ? { ? 1 α 2 ? , d } \max\{k\} = \min\{ \left\lfloor\frac{1}{\alpha^{2}}\right\rfloor,d\} max{k}=min{?α21??,d}

充分性證明： 已知 k = min ? { ? 1 α 2 ? , d } k=\min \left\{\left\lfloor\frac{1}{\alpha^{2}}\right\rfloor, d\right\} k=min{?α21??,d}，令 e 1 , e 2 , … , e d e_{1}, e_{2}, \dots, e_{d} e1?,e2?,…,ed?表示的是 R d \mathbb{R}_{d} Rd?的基向量， R R R為旋轉矩陣并且有 R g = ∥ g ∥ 2 ? e 1 R g=\|g\|_{2} \cdot e_{1} Rg=∥g∥2??e1?， 令 z : = ∑ i = 1 k k ? 1 2 ? e i z:=\sum_{i=1}^{k} k^{-\frac{1}{2}} \cdot e_{i} z:=∑i=1k?k?21??ei?，并且 S S S為旋轉矩陣，所以有 S z = ∥ z ∥ 2 e 1 = e 1 S z=\|z\|_{2} e_{1}= e_{1} Sz=∥z∥2?e1?=e1?
易知，矩陣 Q : = S ? R Q:=S^{\top} R Q:=S?R為旋轉矩陣，其滿足 Q g = S ? R g = ∥ g ∥ 2 S ? e 1 = ∥ g ∥ 2 z Q g= S^{\top} R g = \|g\|_{2} S^{\top} e_1 = \|g\|_{2} z Qg=S?Rg=∥g∥2?S?e1?=∥g∥2?z
令向量 r i : = Q ? e i r_{i}:=Q^{\top} e_{i} ri?:=Q?ei?，并且 1 ≤ i ≤ k 1 \leq i \leq k 1≤i≤k ，其中 r i r_i ri?是矩陣 Q Q Q的第 i i i列， Q Q Q是正交矩陣，進而可知： g ? r i = ( Q g ) ? e i = ∥ g ∥ 2 ? z ? e i = ∥ g ∥ 2 ? k ? 1 2 ≥ ∥ g ∥ 2 ? α g^{\top} r_{i}=(Qg)^{\top}e_{i} = \|g\|_{2} \cdot z^{\top} e_{i}=\|g\|_{2} \cdot k^{-\frac{1}{2}} \geq\|g\|_{2} \cdot \alpha g?ri?=(Qg)?ei?=∥g∥2??z?ei?=∥g∥2??k?21?≥∥g∥2??α
證畢！

?通過以上的證明可以得到一個非常嚴謹漂亮的結論，即對抗子空間的維度 k k k大小與損失函式增長程度 α \alpha α的平方成反比，這也是很符合直觀理解，增長程度越大，對抗子空間就越往梯度方向坍縮，因為梯度方向是最速方向，

多模型對抗子空間維數

?在黑盒模型中，經常會利用到對抗樣本的可遷移性進行攻擊，即利用模型 f θ f_{\theta} fθ?生成的對抗樣本 x ′ x^{\prime} x′，遷移未知分類模型 g η g_\eta gη?中進行攻擊，其主要原因在于針對兩個不同的模型有重疊的對抗子空間，所以才會使得對抗樣本有攻擊的可遷移性，假定 r r r表示的是樣本 x x x針對模型 f θ f_\theta fθ?的使得其損失函式增長 α \alpha α的對抗擾動； s s s表示的是樣本 x x x針對模型 g η g_\eta gη?的使得其損失函式增長 α \alpha α的對抗擾動，其中 r ∈ S p a n { r 1 , r 2 ? ? , r k } r \in \mathrm{Span}\{r_1,r_2\cdots,r_k\} r∈Span{r1?,r2??,rk?}，即擾動 r r r屬于 r 1 , r 2 , ? ? , r k r_1,r_2,\cdots,r_k r1?,r2?,?,rk?這 k k k個正交向量組成的對抗子空間中，其中 s ∈ S p a n { s 1 , s 2 ? ? , s l } s \in \mathrm{Span}\{s_1,s_2\cdots,s_l\} s∈Span{s1?,s2??,sl?}，即擾動 s s s屬于 s 1 , s 2 , ? ? , s l s_1,s_2,\cdots,s_l s1?,s2?,?,sl?這 l l l個正交向量組成的對抗子空間中；則此時針對多個模型對抗子空間維度的大小為 q = d i m { S p a n { r 1 , r 2 , ? ? , r k } ? S p a n { s 1 , s 2 , ? ? , s l } } q=\mathrm{dim}\{\mathrm{Span}\{r_1,r_2,\cdots,r_k\}\bigcap\mathrm{Span}\{s_1,s_2,\cdots,s_l\}\} q=dim{Span{r1?,r2?,?,rk?}?Span{s1?,s2?,?,sl?}}同理根據以上推導思路可以求出3個模型以上重疊的對抗子空間的維度，