# Robustness

跟第一週提到的一樣，在機器學習的領域中，我們希望的 Robustness 有以下三個部分：

- Adversarial
- 面對攻擊性圖片要可以扛住
- Domain shift
- 面對跟學過的有點不一樣但同種的圖片要分得出
- Unseen data
- 面對沒學過的種類要可以分辨

為了避免一下一方贏，一下一方輸，這種交替的情境發生，所以改成研究 Certified Robustness 比較有保證。

# 三種描述 Robustness 的方法

## Lipschitz Constant

$$
\text{sup}\frac{||f(x_1)-f(x_2)||_p}{||x_1-x_2||_p}
$$

概念上來說，分母就是擾動程度，分子就是 model 受到擾動後，輸出的變動程度，然後取這個的上限；也就是 model 最差的抗干擾能力。

## Data Point

概念上就是對於一個資料點，在多大的範圍內他怎樣被攻擊都不會有事。

## Dataset

請見講義的圖。

那張圖的閱讀方式是，橫軸是攻擊的半徑，綜軸是在這樣的攻擊下，至少有多少正確率

:::info
以上三個其實是有互相關連的。

- Model 得到的 Lipschitz Constant 可以算出 Data point 的容忍半徑
- 既然可以求得資料點的容忍半徑，那就可以算出一個資料集，在某個攻擊強度下至少可以有多少正確率
:::

# Sound & Complete

我們定義「Certified Robustness」為「Positive」

- 沒有 False Positive 叫做「Sound」
- 不會把錯的說成對的
- 沒有 False Negative 叫做「Complete」
- 不會把對的說成錯的

在 Verfication 中我們只要求 Sound，不一定要 Complete，對應上週提到的內容。

- 也就是他錯了我們一定可以知道他是錯的，不會說成對的
- 但他如果對了我們不一定一定要知道他是對的，可以不小心說成錯的
- 也就是比較保守

---

# LP 跟其他手段

上禮拜有提到我們將 MILP 放鬆成 LP 問題，可以加快驗證的速度，但是依舊還是太慢了。
>助教說 2080 光是跑完 CIFAR 10 就要好幾天

以下的四個方法比較快，但是原理不是去跑 LP 做驗證，而是直接 Foward 看看情況最糟會變哪樣：

- Fast-Lin
- IBP
- CROWN
- Alpha-CROWN

# Interval Bound Propagation / IBP

IBP 是最快的。相對的他是最鬆的。

參考講義的圖。

概念上從輸入開始，我們有個攻擊的預算(Budget)，每次 forward 完邊界可能會變形，而他到底變形成怎樣的複雜邊界我們可能不知道。

但是我們可以知道邊界最寬長怎樣，所以每次就將邊界放寬到某個固定形狀，例如圖片中都是某個長方形。

所以每經過一次 forward，就會放寬一次，所以最後可能會越來越寬。

## 公式

放寬的公式就是上周的上下界公式。

因為整個流程其實就是多四個矩陣乘法，所以基本上跟預測的時間是同個 Order。

但是因為太 loose 了，所以不一定有好效果，例如在 CIFAR 10 上可行，但是在 ImageNet 上就很慘。

## Certified Training

請見講義 IBP training 的圖。

左邊那個 Loss value 上面有 3 條顏色線，實際上最下面應該還會有一條黑色線：

- 黑色線代表一般訓練時的 Loss
- 是 Loss 的基準值
- 紅色線代表 AT 時的 Loss
- 根據攻擊的 AT 的過程可以知道，我們將輸入主動的做一些攻擊，讓 Loss 變高
- 綠色線是最強攻擊的 Loss
- 最強攻擊可以產生出最大的 Loss
- 這是一個理想值，實際上我們找不到，太困難了
- 藍色線是 IBP training / Certified Training 的 Loss
- 利用 IBP 方法求出一個輸入可以答到的最大的 Loss
- 但是他是最鬆的，也就是他比最強攻擊造成的 Loss 還大

一般做 AT 時，只是在壓低紅色線，但是綠色線可能壓根沒有變動。

但如果訓練時改成壓低藍色線，也就是拿 IBP 算出的最壞攻擊去算 Loss，就一定可以壓低綠色線，因為他是 Loss 的 Upper Bound。

## 最鬆的 Bound

根據 Gowal et al. 的結果，可以看到 MIP bound，也就是最強攻擊，再給定的 Budget 下錯誤率是多少。左側則是 IBP bound 的結果，可以看到跟最強攻擊的 Bound 很接近。
>那個 MIP Bound 其實就是在做上週提到的 MIP 的驗證

:::warning
但是不要被誤會了，實際上 IBP Bound 是最鬆的，這裡會跟實際的 Bound 很接近單純是資料集的特色。
助教說可能跟資料的 calss 數量、pixels 數量有關。
:::

## IBP Pro -- SABR

Mueller, Mark Niklas, et al. "Certified Training: Small Boxes are All You Need." in ICLR, 2022.

原本 IBP 就是每次 propagate 採用最寬的框框，他一定可以包住那個複雜的未知邊界，這篇 paper 改成不要框這麼大，先用 PGD 在該範圍找到一個最危險的點，然後以該點為中心框一個小框框。

也就是減少每次框的範圍，這樣在運算上比較快。

但是缺點是，因為他並沒有框住完整的變形範圍，而是可能有個重疊，所以這個方法不能拿來 Verfication，只能做 IBP training。
>因為有可能沒框到的範圍卻可以製造出 ADX，造成 FP

不過有趣的是，雖然不是用最準確的 IBP bound 做 IBP training，但是最終用 IBP evaluate 的時候效果卻挺好的。

>我稍微看了一下，作者說可以將 SABR 看作是 IBP training 跟 AT 的 Interpolation。

# Fast-Lin、CROWN、Alpha-CROWN

剛剛 IBP 的 Verfication 做法是 Boundary 的 Propagation。

現在這三個也一樣，只不過 Boundary 沒有 IBP 這麼 Loose：

- Fast-Lin：在傳遞的過程中，直接以某個固定斜率作為 ReLU 輸出範圍上下界的斜率
- 跟 IBP 的差別在於 IBP ReLU 輸出上下界是水平線
- CROWN：把 Fast-Lin 的下界改成某個 Heuristic 的下界
- 根據 Heuristic 判斷該 ReLU 是活的還是死的
- Alpha-CROWN：CROWN 的 Heuristic 下界改成有某個學習率 alpha
- 讓 lower 不是固定的，而是可以動的，用 alpha 來學斜率
- 只能用在 training

---

# Lipschitz Architecture

## Lipschitz Constant

令 $x_1, x_2$ 是在 $l_p$ norm 作為距離函數的某個 $B$ 內挑選的兩個點：

$$
L=Lip_p(f)=\text{sup}\frac{||f(x_1)-f(x_2)||_p}{||x_1-x_2||_p}
$$

此時這個 L 值就是 Lipschitz Constant，並且會說這個函數是 L-Lipschitz。

## Lipschitz Composition Property

$$
Lip(f \circ g)\le Lip(f)Lip(g )
$$

在神經網路中，其實就是很多層函數一直複合下去，尤其是 CNN 的 Kernel 操作，而如果過程中每個函數都可以保持 1-Lipschitz，那麼最終的結果也會是 1-Lipschitz。

# Orthogonal Operation

如果有一個 matrix $W$ 滿足 $WW^T=W^TW=I$，那麼 $W$ 就叫做 Orthogonal matrix。

並且我們會叫 $y=Wx$ orthogonal linear operation。

這個正交操作就有上面提到的好處：

- 是 1-Lipschitz
- 並且保 norm：$||Wx||_2=||x||_2$

那麼要怎麼找到 $W$？

以下三種方法，就是各位大佬各顯神通，找出一個神奇弄出 $W$ 的方式，並且他們還都帶有「隱含性的 Convolution」操作。

:::info
因為當初就是希望將 1-L 這個性質用在 CNN 上面，所以那些大佬就改成找一個方法可以隱性的做 Convolution，同時又是 Orthogonal Matrix。
:::

# Skew orthogonal (convolution) network / SOC

首先提到一個性質，如果一個 Mmatrix $A$ 是「skew-symmetry」，那麼 $exp(A)$ 就會是 Orthogonal Matrix。

所謂 skew-symmetry 是指：

$$
A=-A^T
$$

然後作者他們發明了一種產生 convolution kernel $L$ 的方法：

$$
L=M-\text{conv_transpose(M)}
$$

然後拿這樣構建出來的 $L$，去跟輸入矩陣 $X$ 做 convolution，然後計算結果的 Jacobian：

$$
J=\nabla_{\overset{\rightarrow}{X}}\overset{\longrightarrow}{(L \star X)}
$$

>$\star$ 是卷積操作

這樣得到的 $J$ 矩陣，就會是 Skew-Symmetry。

得到 $J$ 之後，根據上面說的，$exp(J)$ 就會是 Orthogonal matrix。而這個 $exp(J)$ 如果跟 $\overset{\rightarrow}{X}$ 相乘，再搭配泰勒展開：

$$
exp(J)\overset{\rightarrow}{X}=\overset{\rightarrow}{X}+\frac{J\overset{\rightarrow}{X}}{1!}+\frac{J^2\overset{\rightarrow}{X}}{2!}+...
$$

此時搭配下面的這個性質：

$$
J\overset{\rightarrow}{X}=\overset{\longrightarrow}{(L \star X)}
$$

>這好像是卷積跟 jacobian 的性質，但是我不知道怎麼來的

上面的泰勒展開就可以變成：

$$
exp(J)\overset{\rightarrow}{X}=\overset{\rightarrow}{X}+\frac{\overset{\longrightarrow}{(L \star X)}}{1!}+\frac{\overset{\longrightarrow}{(L \star^2 X)}}{2!}+...
$$

也就是變成將不同次的卷積操作結果，加總起來。這就是上面提到的隱性卷積。

所以作者設計的網路就是做很多層的 $exp(J)\overset{\rightarrow}{X}$，這樣就等同做了很多次的隱性卷積，達到更強的特徵萃取能力，同時 Orthogonal matrix 又保證了 1-L，因此就確保了整體網路的 L 常數上限。

# LOT

這個是搭配傅立葉轉換來達到卷積的效果。

傅立葉轉換我們知道具有下面的性質：

$$
\mathcal{F}\{f\star g\}=\mathcal{F}\{f\}\mathcal{F}\{g\}
$$

左邊是時域做卷積，其效果等同在頻域做點積。

而有些傅立葉轉換具有 Orthogonal 的性質，也就是轉換前後都保持 Orthogonal，例如這篇 paper 用的 FFT。

這篇作者的方法是網路分成很多層，跟剛剛很類似，然後每一層都是做 convolution，但是這時他們就轉換一條道路，不做卷積，改成先 FFT，然後在 FFT 裡面跟一個 Orthogonal matrix 做點積，然後在 IFFT 轉回來，繼續往下傳。

這樣的效果是，FFT 跟 IFFT 都是 Orthogonal，中間的點積操作也是 Orthogonal，所以整條路上都保持 Orthogonal 的性質，同時其效果等同下面路線的卷積，所以又成功的達成有卷積又有 1-L。

:::warning
Orthogonal matrix $W$ 助教沒有講出是怎麼來的，但是有列出來長相為：

$$
W=(VV^T)^{\frac{1}{2}}V
$$

$V$ 沒有說是什麼。

:::

# Cayley

助教沒有介紹這種。

他用的 Orthogonal matrix 是：

$$
(I-V+V^T)(I+V-V^T)^{-1}
$$

# Activation Functions

上面有講到，那些大佬們的架構都是分成很多層，每層之間都保有 Orthogonal 的性質，那層跟層之間的交流怎麼辦？

如果是單純線性運算就沒事，但能不能加個 ReLU 之類的激活函數？答案是可以的，一樣只要確保激活後一樣是 Orthogonal 就行，ReLU 就屬於可以的例子。

所以上面第一篇 SOC 的作者，就用了一個比較特別的激活函數，叫做 MinMax 函數；簡單來說就是把輸入矩陣 $X$ 拆成兩半 $A$ 跟 $B$，然後分別求出 $\max(A,B)$ 跟 $\min(A,B)$，一個是將兩個矩陣中大的元素留下來，一個則是小的留下來，然後再把兩個組起來組回原本的 dimension。

這樣的激活函數好處是不像 ReLU 在小於 0 的部分就不見了。

---

# RS 補充介紹

基底函數 Base classifier 是我們的 seed，我們要用他種出 smoothed classifier。

起初的方法是，對每個 input 去看以他為中心的 Gassian 分佈，看看這範圍內會輸出什麼值，而這個動作其實就等同對一個 input 做一個 gaussian 的卷積操作，得到所有受到 gaussian noise 的 input，在信號處理中叫做 Weierstrass transformation。

但後來我們知道這我們做不到，因為數量太多了，所以只好用蒙地卡羅來估計。

## 公式推導

助教放了詳細的推導過程。

總之就是要讓「$C_A$ 可以被回傳的機率」的下限，要大於「$C_B$ 可以被回傳的機率」的上限。

但是實際上 $p_A$ 是透過估計出來的，所以需要經過 Binomial confidence 的檢定來看看這個估計的機率能不能用；同時這個檢定因為在接近 0.5 的時候效果較好，接近 0 或 1 的時候會壞掉，可是 $p_A$ 大多都是在 1 附近，因此實際上作者有先做區間的偏移，來得到 ${p_A}^{↓}$

## Improve

因為 RS 是少數 Scalable 的方法，所以有許多研究都在如何加強 RS，大致方向有三個。

- 更好的 Base Classifier
- 例如，如果使用 Gaussian noise 的話，就會希望 base classifier 要可以較好的抵抗 gaussian noise，不然可能他在使用 gaussian 蒙地卡羅採樣時就先爛掉了。
- 不同的 Distribution
- 例如上次有提到的 Laplace Distribution，這樣就會讓距離 metric 從 $l_2$ 變成 $l_1$
- 嘗試建構更好的 smoothed classifier
- 例如使用不同的 smoothed classifier，讓回傳的 $R$ 可以更大

助教還有提到一種同時增強 Base Classifier 跟 $R$ 的方式，他說有個大佬建構出可微的 $R$，然後將 $R$ 加入 Base Classifier 訓練時的 loss 項，讓模型可以學出更大的 $R$。

## R 很保守

上面有提到 $p_A$ 是有做偏移後得到的下限，所以實際上在 certificated Acc 跟 radius 的圖表中，常常可以見到 radius 突然降為 0，因為 $p_A$ 下限最多就在那(助教說大概就是 0.997)，一個資料集在固定的 $\sigma$ 下算出來的 R 最多就是那樣。

所以助教上次開會報告他們的論文，就是他們開發一個算法，改成對每個 input 都找一個最佳的 $\sigma$，這樣一來在整體資料集上，就不會 R 到了某個值就產生斷層了。