今天介紹一些 ADX 的性質，要探討兩個問題：

- 為何 ADX 會存在
- 有辦法達到可以抵抗 ADX 的強健 model 嗎
- 因為現在就算透過 Adversarial training，準確率相比 standard accuracy 還是很低
- 統計上是可能達到的嗎？
- 運算資源是否會很龐大
- 如果真的可以達到，是否會需要一些 trade-off

# 為何 ADX 會存在

以下內容來自 Adversarial Examples Are Not Bugs, They Are Features 這篇論文。

# Robust & Non Robust Features

原本人們以為，會存在 ADX 是因為資料中存在兩種 features：

- Useless features
- Useful features

也就是有用的跟沒用的。人們以為 ADX 就是在 Useless features 動過手腳所得到的結果。

但是上面那篇論文經過實驗發現，實際上正確來說是三種 features：

- Useless features
- Useful features
- Robust features
- Non-Robust features

也就是有用的 features 中其實有兩種，強壯跟不強壯的。

## Robust features 跟 Non-Robust features

該篇論文把資料集，全都轉換成 ADX 之後，再拿去重新訓練一個新網路，卻發現依舊可以有一定的正確率。

原因就是圖片中存在 Robust features 跟 Non-Robust features。

- Robust features：經過 Adversarial 攻擊後，依舊跟原 label 相關
- 也就是攻擊後人感覺上沒有差異的部分
- Non-Robust features：經過 Adversarial 攻擊後，變得跟原 label 無關
- 這些 features 是細小的，人類難以察覺
- 例如帆船圖片中，存在大量小小的三角形結構，這樣的結構就是一種 Non-Robust features
- 但也導致只要其他圖片被修改成也具有小小的三角形結構，就會被判定為帆船

但是在訓練的時候我們並沒有給予「選擇特徵的限制」，因此他兩種 features 都會學到：

- Robust features：原本可以幫助他判斷圖片，但是因為經過了攻擊，會使 model 誤判
- 例如原本應該是屬於狗的 Robust features，現在被認為是帆船的
- Non-Robust features：就算狗圖片被攻擊的 label 是帆船，但是 model 還是學到了那些小小的 Non-Robust features
- 因此就算在測試的時候遇到帆船圖片，但因為 model 學會了這些 Non-Robust features，如果帆船圖片中 Robust features 的部分很少，那麼 model 就可以根據 Non-Robust features 做出正確判斷

# 實驗內容

## Set up

實驗情境是對單純的 Binary Classification：

$$
(x,y)\in \mathcal{X}\times \{\pm 1\}
$$

然後資料是以某個未知的分佈，從 $\mathcal{D}$ 取樣。

接著他定義 feature 是一個 function：

$$
f:\mathcal{X}\rightarrow \mathbb{R}
$$

也就是把原本的資料，對應到一個實數。

:::warning
意思是將資料 $x$ 透過模型所萃取出來的一個特徵(實數值)
:::

然後實驗有做一些基本的位移縮放，使得：

$$
E_{(x,y)\sim \mathcal{D}}[f(x)]=0
$$

$$
E_{(x,y)\sim \mathcal{D}}[f(x)^2]=1
$$

平均值為 0 ，變異數為 1，以方便討論。

## Useful, Robust, Non-robust Features

然後他又定義了：

- $\rho$-useful features
- $\rho$ 是一個非負的常數
$$
E_{(x,y)\sim \mathcal{D}}[y\cdot f(x)]\ge \rho
$$

>也就是說該資料的 features 跟其類別同號，跟其類別正相關，有助於判別其類別。

- $\gamma$-useful features
- $\gamma$ 是一個非負的常數
$$
E_{(x,y)\sim \mathcal{D}}[\underset{\delta \in \Delta (x)}{\text{inf}} y\cdot f(x+\delta)]\ge \gamma
$$

>也就是說該資料就算經過攻擊，得到的 features 也會跟其類別同號。

有了上面的定義，就知道所謂的 Useful, non-robust features 就是：

- 存在一些 $\rho$ 使得資料是 $\rho$-useful features
- 但是不存在任何一個 $\gamma$ 使得資料是 $\gamma$-useful features
- 也就是資料被攻擊後就喪失了跟原本 label 的一致性

## Classification and Training

實驗的分類問題就是常見的樣子：

$$
C(x)=\text{sgn}\left(b+\sum_{f\in F}w_{f}\cdot f(x)\right)
$$

也就是把各種從 $F$ 裡面的 features $f$，對應上一個權重 $w_{f}$，然後看看分數如何。

而有了上面的分類定義後，標準的 training 就是在最小化：

$$
E_{(x,y)\sim \mathcal{D}}\left[\mathcal{L}_{\theta}(x,y)\right]=-E_{(x,y)\sim \mathcal{D}}\left[y\cdot \left(b+\sum_{f\in F}w_{f}\cdot f(x)\right)\right]
$$

也就是希望訓練出完美的權重，可以判別出 $\rho$-useful features。

而 Robust training 則是改成最小化：

$$
E_{(x,y)\sim \mathcal{D}}\left[\underset{\delta \in \Delta (x)}{max}\mathcal{L}_{\theta}(x+\delta,y)\right]
$$

也就是希望訓練出完美的權重，可以判別出 $\gamma$-useful features。

:::info
上面可以知道，經過 Robust training 的 model 就可以只專精於辨認出 $\gamma$-useful features
:::

## Construct A Robust Dataset

有了上面的訓練定義，我們希望透過一個 robust model $C$ 找出「Robust Dataset」，滿足：

$$
E_{(x,y)\sim \mathcal{\hat{D}_{R}}}[y\cdot f(x)]=
\left\{\begin{matrix}
E_{(x,y)\sim \mathcal{D}}[y\cdot f(x)] & \text{if } f\in F_C\\
0 & \text{otherwise}
\end{matrix}\right.
$$

由於 $C$ 是一個強壯的 model，$F_C$ 就是那些 robust features，上面目的就是希望讓 $\hat{D}_{R}$ 的 features，可以只剩下 robust features，其他 features 則是期望是 0 (跟 x 不相關)。

那麼實際上要怎麼獲得 Robust Dataset？論文給出了下面的演算法：

1. 先透過 AdversarialTraining 得到一個 $C_R$
2. 從 $C_R$ 中，把 input layer 到最終的 representation layer 拿出來得到 $g_R$
- 但是不是到最終輸出層，因為最終輸出的結果會是 class 之類的
- 我們要的是他再前一層那個終極萃取出的特徵
4. $D_R\leftarrow \{\}$
5. 對所有原本資料集 $D$ 當中的每個資料 $(x,y)$
- 根據同樣的分佈，隨機從 $D$ 當中採樣一個點 $x'$ 出來
- 使用 $l_2-PGD$ 或其他 GD based 方法，去一步步更新 $x'$
- 使得 $||g_R(z)-g_R(x)||_2$ 達到最小
- 把 $(x',y)$ 塞進 $D_R$
6. 回傳 $D_R$

:::danger
可能要找時候研究細節
:::

## 成果

強壯資料集因為只剩下 robust features，所以想要用任意的圖片做攻擊，會因為缺少了 non-robust features 而攻擊不易成功。

他們還依此方法弄出了三種資料集：原始、Robust、Non-Robust 三種資料集。

- 對照組是使用原始資料集，使用標準訓練，檢測標準以及攻擊兩種情況的準確率
- 標準下的準確率很高，但是攻擊後的準確率十分低
- 第一組是使用原資料集，但是使用 Adv 訓練
- 雖然犧牲了一點標準情況的準確率，但是攻擊情況的準確率大幅提高
- 第二組是標準訓練，但是使用 Robust 資料集
- 雖然標準情況的準確率又更低了一些
- 但是因為是透過 Robust 資料集訓練，所以具有一定的攻擊情況準確率
- 最後一組是標準訓練，但是使用 Non-Robust 資料集
- 標準情況的準確率一樣比 Adv 訓練低一些
- 但是對於攻擊情況的準確率，低於對照組

## 對 Transferability 的影響

Robust 跟 Non-Robust features 也可以用來解釋 Transferability。

他們實驗有發現，越強的 model，會使用越多的 Non-Robust features 幫助判斷以達到封頂的準確率。

但這也就代表，他們都容易因為 Non-Robust 的背叛而受到影響，也就是為什麼 Adv 具有傳遞性。

>實驗發現標準情況下的準確率跟轉移成功率有正相關

## Theoretical Framework

>請參考講義

他們用高斯分佈，取樣出兩團資料，這兩團資料起初在 feature 1 很容易分別，在 feature 2 則不容易區分，也就是線呈現一個斜率較低的狀態。

接著經過稍微強的 Adv training，可以發現模型因此注意到這兩筆資料在 feature 1 很容易分別，所以使兩坨資料的分佈變得更圓，也就是已經逐漸只以 feature 1 作為分類標準。

最後則是改用更強的 Adv training，可以發現兩組資料的分界線已經變成只依靠 feature 1 了。

:::info
老師說資料會以中心變「圓」，是因為採用 $l_2$
:::

:::warning
實驗的結果是，原始 data geometry 的 misaligment，是其 Vulnerability 的原因
:::

## model 跟人類不一樣

回顧上次提到的， model 在做分類的時候，他們看的跟人類所注意的不一樣，他們還會多注意到那些人類觀察不到的 Non-Robust features。

# Discussion on Distill

老師說那篇論文出來之後引起很大回想，所以 Distill 這個論文網站，當初有邀請眾多學者跟作者做一答一覆的對談。

其中有趣的對談包括：

## Learning From Only High Frequency Data

這篇論文的作者(Yin et al. NeurIPS’19)是將圖片分成高低頻，然後他們發現只拿高跟低頻去訓練，依舊可以達到不錯的正確率。

而這些低、高頻圖片，跟上面提到的 Robust、Non-Robust 圖片概念很類似。

- 低頻對應到 Robust
- 高頻對應到 Non-Robust

他們還發現，做 Adv training 跟把圖片加上 Gaussian Noise，都可以達到類似的效果：「增加圖片對高頻區域的 robust 性」
>不過 Gaussian Noise 會犧牲一些低頻的 robust 性，Adv training 則是都顧到了

## Non-transferrable Adversarial Examples

這篇的作者(Nakkiran, Distill’19)是想表示問題不一定是出在 data 上，有可能是結構的問題，所以他們真的訓練出了一種不具轉移性質的資料：

$$
-\left(\nabla_x L(f,x_t,y_targ) + \underset{i}{\mathbb{E}}[\nabla_x L(f_i,x_t,y)] \right)
$$

上面是他們在產生 ADX 時選擇的方向；$f$ 是 target model，${f_i}$ 則是其他模型的 ensemble 模型。

也就是讓 $f$ 朝特定 target label 前進，其他模型則是朝原本的 label 前進。

但是他們驚訝的發現，這樣所得到的 ADX，並不具有 useful features，也就是他們產生的 ADX 是只修改 non-useful features 而得到的。

也就是說這些 ADX 就是真的是 BUG。

## ADX arise from overfitting

有時候 ADX 會出現，其實可能是由 overfitting 導致的。

邊界長的太偏頗，很容易就可以給你翻轉結果。

---

# ADX 統計上來講是不可避免的

## 定義

首先作者 \[Fawzi et al. NeurIPS’18\] 定義了一個 Robustness 距離：

$$
r*(x)=\underset{r\in \mathbb{R}^d}{\text{argmin}}||r||_2\text{ subject to }\hat{h}(x+r)\ne \hat{h}(x)
$$

其中 $\hat{h}$ 是分類的邊界，$x$ 是某筆資料；上面的式子是在說，以 $x$ 為出發點，找到離邊界最近的距離。

有了這個最近的距離後，就可以定義一個 global measure：

$$
\rho_{\text{adv}}(\hat{k})=\mathbb{E}_{\mu}(||r^*(x)||_2)
$$

也就是每個點到邊界的的最短距離的期望值。

## Example Problem

>請參考講義的圖

作者用了橫直條紋的圖片，然後可以找到一個最佳的 Linear 分類器長得像：

$$
f_{\text{lin}}(x)=\frac{1}{\sqrt{d}}\mathbf{1}^Tx-1
$$

也就是把每個 pixel 加起來後除以 pixel 數量的根號，再減掉一個 threshold，這裡是 1。

然後就可以知道：

- 這個分類器的「Risk」是 0：$R(f_{\text{lin}})=0$
- 「Risk」聽老師講下來應該就是錯誤率
- 但是這個分類器得 Robust 程度，或者說剛剛的 $\rho$ 值卻會被 bound 住
- $\rho_{\text{adv}}(f_{\text{lin}})=\sqrt{d}\cdot a$
- $a$ 是我們自己定義，弄在圖片的偏差值，可以看講義的圖

會發現只要 $a$ 夠小，Robust 程度就會很低。

然後作者就改成使用一個 Quadratic 的分類器：

$$
f_{\text{quad}}(x)=x_1x_2+x_3x_4-x_1x_3-x_2x_4
$$

$x_i$ 代表圖片的第幾個 pixle，這裡作者為了方便討論，所以情境只有 4 個 pixel。

然後一樣可以發現：

- 這個分類器的「Risk」是 0：$R(f_{\text{quad}})=0$
- 但是這個分類器得 Robust 程度，卻是一個常數
- $\rho_{\text{adv}}(f_{\text{quad}})=\frac{1}{\sqrt{2}}$

:::warning
這件事可以結合上週提到的，如果 model capacity 不夠，那麼他可能先天上就不太能夠抵抗 ADX。
:::

## Fundamental Limit of Robustness

該作者又很狂的推導出所有線性分類器的 $rho$ 值，可以被某個上限 bound 住：

$$
\rho_{\text{adv}}(f)\le \frac{1}{2}||\mathbb{E}_{\mu_1}(x)-\mathbb{E}_{\mu_{-1}}(x)||_2+2MR(f)
$$

- $\mathbb{E}_{\mu_1}(x)-\mathbb{E}_{\mu_{-1}}(x)$ 這個部分是指兩種類別(1 跟 -1)的資料，期望上的差距是多少。
- 這部分叫做 distinguishability measure，是跟分類器無關，只跟資料有關部分
- $M$ 老師說是 model 的 Norm 的最大值，這可能要去看論文怎麼說

總之上面的公式可以知道兩件事情：

- $rho$ 值先天上就跟資料的兩種類別，期望上的差距有關
- 如果兩種資料先天上距離就很近，那麼 Robust 程度低是難免的
- $R$ 值越低，或者說模型正確度越高，伴隨著 $\rho$ 值上限越低
- 也就是說無法做到高準確率，同時又很強壯

然後就可以畫出 $\rho$ 對 $R(f)$ 的圖形，線的上半部是理論上模型做不到的

作者也有推廣到非線性的模型上面，一樣可以看到類似的圖形，只不過變成不是斜直線。

## From Adversarial to Random Noise

上面都在探討 Robustness 跟 ADX 之間的關係，作者就想看跟平常提到的 random Noise 能不能有相關連結。

上面提到的距離函數就會變成：

$$
\min_{t}|t|\text{ subject to }f(x+tv)\ne f(x)
$$

其中 $v$ 是從 $\mathbb{S}^{D-1}$ 用 uniform 採樣出的隨機一個方向。

也就是改成看隨機的某個方向上的最短距離。

然後作者一樣很狂的推導出來，在高機率之下，會滿足：

$$
||r^*||_2=\Theta\left(\frac{1}{\sqrt{D}}||r^*_{\text{rand}}||_2\right)
$$

>高機率是因為方向是隨機選取的

上面這個結論可以發現，相比 Random Noise，想要達到 Adversarial noise 的 Robustness，是更困難的，因為兩者的距離差了 $\frac{1}{\sqrt{D}}$。

如果把 $||r^*_{\text{rand}}||_2$ 的部分當作常數，會發現 $||r^*||_2=O\left(\frac{1}{\sqrt{D}}\right)$，維度越高，越困難。

## Limits on Adversarial Robustness of Any Classifier

作者在另一篇論文做了一件更猛的事情，他希望證明改成對「任何的分類器」，所以：

- 他改成對資料下手(做假設)，假設真實資料是透過一個 smooth generator 產生的
- 資料分佈 $\mu=g(\mathcal{N}(0,I_p))$
- $g$ 是那個 smooth generator, $z,z'$ 是透過 $\mathcal{N}(0,I_p)$ 採樣得到的點，$g$ 會根據採樣倒的點吐出一張圖片
- smooth 意思是指 $\forall z,z', ||g(z)-g(z')||\le L||z-z'||_2$
- $L$ 是 Lipschitz constant，一個常數，請見 [WIKI](https://zh.wikipedia.org/zh-tw/%E5%88%A9%E6%99%AE%E5%B8%8C%E8%8C%A8%E9%80%A3%E7%BA%8C)

直白上來說，就是假設產生出的圖片是比較平滑的，不會變動很大。

然後作者就證明出，如果可以找到一個 generator $g$ 在 Wasserstein sense 下，保證 $\delta$ 的近似於原本的分佈 $mu$：

$$
W(g(\mathcal{N}(0,I_p)),u)\le \delta
$$

就可以證明距離函數 $r^*$ 的期望值為：

$$
\mathbb{E}_{x\sim \mu}(r^*(x))\le L\left(\frac{log(4\pi log(K))}{\sqrt{2log(K)}}\right)+\delta
$$

$K$ 是 class 的數量，$L$ 一樣是 Lipschitz constant

- 如果這個 generator 非常的 smooth
- 也就是 $L$ 越小，那麼 Robust 就上限就很低
- 如果 class 數量越多，Robust 上限也會很低

:::warning
**ISSUE**
但是前提是假設資料是從 smooth generator 產生的；可是現實中資料不一定都是這樣子產生的
:::

---

# Robust model is computationally intractable

想要強壯，可能需要付出極高額的代價。

## Statistical Query (SQ) Learning

在介紹之前，老師先提到一個 「frame work」，SQ Learning，是 Kearns 在 1988 年提出的論文 \[Kearns 1998\]。

- 所謂 SQ Learning，意思是你不能夠拿到真正的 raw data，你只能根據某個分佈去 Query Data
- Query 由自己定義，例如以 Binary 分類，你要定義一個 $h$ 函數：
- $h:\mathbb{R}^d\rightarrow[-1,1]$
- 當你 Query 的時候，他就會回傳 $\mathbb{E}_{x\sim D_0}[h(x)]\pm \tau$ 跟 $\mathbb{E}_{x\sim D_1}[h(x)]\pm \tau$
- $D_0$ 跟 $D_1$ 代表會回傳 -1 跟 1 的資料分佈\
- $\tau$ 是某個 noise

大多的演算法都可以歸類到這個 framework：

- 例如常見的 SVM, SGD
- KNN 是個少見的例外

## SQ 用途

當初作者是想透過 SQ 這個 framework 來證明：

- Robustness to random classification noise
- Differential privacy

但是後來也發現 SQ 拿來證明一些事情在有 nosie 時的 hardness 時很方便：

- Learning parity with noise
- Learning intersection of halfspaces
- halfspaces 就是 Linear 分類器
- Robust estimation of high-dimensional Gaussians

## 結論

作者最終得到一個結論：

:::info
- 如果學習一個 task，需要 super-poly(d) 次的 queries，伴隨著 $\frac{\epsilon}{poly(d)}$ 的 noise
- 那麼不太可能有一個演算法，可以在 poly(d) 的時間內達到 $\epsilon$ 的正確率。

會說不太可能是因為有一個很奇怪的反例；但是因為太奇怪了，所以作者認為大多應該都是不太可能的
:::

## Hardness of Adversarial Robustness

有了上面的結論就可以證明 Adversarial Robustness 在 SQ framework 下，是很難的事情：

- 作者造了兩個資料分佈，在 $\mathbb{R}^d$ 的空間
- 這兩個分佈長的很奇葩，是 「discretized」 Gaussian
- 請見講義的圖
- 存在一個 robust 的分類器，需要 poly(d) 個資料來學習
- 但是這樣的話會需要 $2^{d^{\Omega(1)}}$ 次的 queries

根據上面的結論，可以知道很難在 poly(d) 的時間內達成。

反觀，如果是一個 non-Robust 的分類器，就可以只需要 poly(d) 的時間就學習完成。

:::warning
**ISSUE**
因為作者是由一個「造」出來的分佈來證明，但是實際上的資料分佈很有可能不是都是那樣
:::