# Certified Robustness / CR 介紹

如其名，有認證的 Robustness。

之前介紹的防禦都是所謂的 Empirical Defense，沒有任何的理論保證，都是說在某種情境下，然後嘗試供給自己訓練的模型，看看防禦的數值結果。

但是這個數值不是固定的，他會隨著情境的不同，或是更強的攻擊出現而變更差。

所以這個主題就是希望可以在「某些假設之下」，模型遭受各式強烈攻擊可以有的安全下限。

>在這個領域 Certification 有時又叫做 Verification

## 領域的分支

分為 Probabilistic 跟 Deterministic。

- 從先前的內容可以知道將模型搭配上「機率」，可以有不錯的保護效果
- 但是目前這個領域目前還只有 Incomplete 的方法，無法確定一個 model 到底有沒有 ADX
- 方法叫做「**RS**」
- 有 Probabilistic，就有 Deterministic 的方法
- 這個目前有 Incomplete 跟 Complete 兩種方法
- Complete 的話雖然可以確定一個 model 有沒有 ADX，但代價是需要很難的工具： 「**MIP 或 SAT**」
- 因為代價太高了，目前並不 scalable
- MIP 就是 MILP
- Incomplete 只能確保部份的 example 是不是 ADX
- 方法目前分為兩支：Linear Relaxation 跟 Lipschitz
- Linear Relaxation 顧名思義就是從 MIP relaxation 後得到的解法
- 根據 relaxation 的程度有不同的 bound
- 方法有「**LP**」
- 另一個從 LR 分下來的分支叫做 Linear Bound，方法有「**IBP 跟 CROWN**」
- Lipschitz 方法就是去看 Lipschitz constant
- Lipschitz constant 較小代表 model 概念上來說變動程度不會很大，robust 程度就比較高
- 目前這個領域有兩派，一個是去算一個 model 的 Lipschitz constant 是多少，或是 bound 在哪
- 另一個是嘗試建構出一個 model，具有特殊的結構可以使他的 Lipschitz constant 在某個 bound 內
- Lipschitz constant 的壞處是 expressive 的能力比較差

:::warning
這週的內容會提到 RS、 Deterministic 的 Complete，以及 Incomplete 中的 LR。
老師說助教下週會介紹 RS 的最新研究，以及有時間的話會提到一些 Lipschitz 的方法
:::

## CR 想知道什麼

給一個 model $f$，3集一個 example $(x,y)$，和一個範圍 $\epsilon$。
>範圍 $\epsilon$ 就是第一週提到，可以做變動的範圍大小

有兩種 Certification：

- Exact Certification：
- 如果這個在該範圍下沒有任何 perturbation 可以讓模型犯錯，那麼就要回答 YES
- 如果存在的話要回答 NO
- 這樣就可以知道這個 model 經過攻擊後的正確率是多少了
- 但從上面可以知道這是個 NP hard 難度
- Relaxed Certification：
- 如果這個在該範圍下沒有任何 perturbation 可以讓模型犯錯，那麼就要回答 YES
- 跟上面一樣
- 如果「可能」存在的話要回答 NO
- 也就是保證只剩一邊

---

# Exact Certification

可以用 MILP 去解； MILP 可以去看我的智慧型汽車導論，有稍微介紹。

## 問題 model

會使用一個比較 general 的模型表示法：

$$
\begin{align}
z_1&=x\\
z_{i+1}&=ReLU(W_i z_i+b),\ i=1,...,d-1\\
h_{\theta}(x)&=W_d z_d+b\\
\end{align}
$$

$x$ 就是 input，當中每一層的 $x$ 是 $z$，通往下一層配對的權重矩陣是 $W$。

這樣一來我們的問題就可以被描述成一個最佳化問題：

$$
\begin{align}
\underset{z_1:d}{\text{minimize }}& (e_y-e_{y_{\text{targ}}})^{T}(W_dz_d+b)\\
\text{subject to }&z_{i+1}=ReLU(W_i z_i+b)\\
&||z_1-x||_{\infty}\le \epsilon\\
\end{align}
$$

- 上面是一個「target attack」，使用 $l_{\infty}$ 作為範圍。
- $(e_y-e_{y_{\text{targ}}})^{T}(W_dz_d+b)$ ，其實拆成 $e_y ^{T}(W_dz_d+b)-e_{y_{\text{targ}}}^{T}(W_dz_d+b)$ 會比較好理解
- $e_{i}$ 是單位向量，只有 $i$ 這個方向是 1，其他都是 0
- 假設上面最佳化問題真的找到了最佳解
- 如果是大於 0，那就代表不管如何攻擊，一定都會把 $x$ 分類成 $y$，因為在 $y$ 這個 class 的分量比較大
- 如果是小於 0，那就代表一定可以透過攻擊，使 model 把 $x$ 分到 $y_{targ}$ 這個類別，因為 $y_{targ}$ 的分量比較大

## 轉成 MILP

$$
\begin{align}
\text{subject to }&z_{i+1}=ReLU(W_i z_i+b)\\
&||z_1-x||_{\infty}\le \epsilon\\
\end{align}
$$

把這兩個限制轉成 MILP 的形式：

- $||z_1-x||_{\infty}\le \epsilon$
- 這個比較好處理，根據 $l_{\infty}$ 的定義，就是 $\text{max}(|z_{1,i}-x_{i}|)\le \epsilon$，再拆掉絕對值。
- 不知道為什麼老師講義是寫 $z_1-x\le \epsilon$ 跟 $z_1-x\ge -\epsilon$，理論上這兩個應該是向量才對
- $z_{i+1}=ReLU(W_i z_i+b)$
- 簡潔版：$z=ReLU(x)$，並且我們要知道 $x$ 的上下界 $x\in [l,u]$
- 而 $z=ReLU(x)$ 跟下面的限制是等價的：
- $a=\mathbf{1}[[x\ge0]]$，沒錯，是 boolean function
- $z\le x-l(1-a)$
- $z\le u\cdot a$
- $z \ge x$
- $z \ge 0$
- 只要把 $x \le 0$ 跟 $x < 0$ 的時候帶進去，就會發現跟 ReLU 是一樣的
- 然後那個 boolean function 就是導致難算的原因，或者說他就是 MILP 中 Integer 的部分，因為他限制了 $a$ 只能是 $\mathbf{1}$ 或 $\mathbf{0}$
- 要怎麼知道 ReLU 中 $x$ 的上下界？
- 有很多種方法可以得到，只不過寬鬆的程度不一樣，下面是講義的例子：
- 對於某一層 $z$，如果已知 $l\le z \le u$：
- 把該層的 $W$ 拆出 $W_+$ 跟 $W_-$，一個只有大於等於 0 的權重，一個則只有小於等於 0
- 於是就可以神奇的得到：$W_+ l - W_- u + b\le Wz+b \le W_+ u - W_- l + b$
- 因為 $W=W_+ + W_-$，所以 $l\le z \le u$ 就可以知道 $(W_+ + W_-)l + b\le Wz+b \le (W_+ + W_-)u + b$
- 好吧我不知道

## ReLU 的問題

因為那個 boolean function 會導致 Integer Programming，所以目前：

- 如果可以確保 $l$ 跟 $u$ 同號，那麼就可以移除 boolean function，就可以從 IP 退化為 LP
- 所以有人把 LOSS 中加入 $-tanh(1+l\cdot u)$ 這個項，讓模型比較容易出現 $l$ 跟 $u$ 同號的情形
- 另一個是讓 $W$ 變得更稀疏，這樣 MILP 的 Solver 就可以解更快

:::warning
但是目前來說依舊是非常慢，也不 Scalable，只能跑在小型 model，但是小型 model 往往不是那些有著最佳 robust accuracy 的 model
:::

# Convex Relaxation

既然 MILP 那麼難，那麼我們就放鬆一下：)。

## Convex set

一個範圍是 Convex set ，代表在這個範圍中任取兩點，兩點的中間點也會在這個範圍內。
>[參見WIKI](https://zh.wikipedia.org/zh-tw/%E5%87%B8%E9%9B%86)

一旦範圍是 Convex set，就有一些好性質可以用；但是 $z=ReLU(x)$ 限制的 $z$ 的範圍，不是 Convex set，而是一個「有折角的直線」。

所以我們就把範圍放鬆，把那個「有折角的直線」，多補一條線接在兩端，構成一個三角形，這個範圍內都可以選。
>請參考講義的圖

如果範圍變成那個多邊形，這樣一來限制的範圍就會從原本 ReLU 的範圍，變成：

- $z_{i+1}\ge 0$
- 這個是水平等於 0 那條
- $z_{i+1}\ge W_{i}z_i+b$
- 這個是原本的斜直線那條
- $z_{i+1}\le \frac{u_i}{u_i-l_i}(z_i-l_i)$
- 這個是補上去的那條，但我不是很知道他怎麼推導的

這樣一來，問題**就從 MILP 變成 LP** 了，這就是 Convex Set 得到的好性質。

## Lower Bound of MILP

上面的做法就是放寬限制，讓解的範圍變多了，但這會讓得到的解變成 MILP 的 Lower Bound：

$$
\text{Objective(LP)}\le \text{Objective(MILP)}
$$

- 如果 LP 解出來大於 0，那麼很安全，MILP 的解一定也大於 0，沒有問題發生
- 如果 LP 解出來小於 0，MILP 的解就有可能大於 0 或小於 0，這就有問題了
- 我們就不知道 MILP 的解到底是哪種情形

---

# Random Smoothness / RS

這個方法的構想很簡單\[Cohen et al. ICML’19\]：

- 原本一個 model 在判斷一個 $x$ 是哪一類的時候，就是單純「對那個 $x$」做計算
- RS 方法則是改成以 $x$ 為中心的常態分佈 $\mathcal{N}(x,\sigma^2I)$ 那群點做判斷
- 例如假設在這樣的分佈下，有 80% 的機率是熊貓，15% 機率是長臂猿, 5% 是貓
- 那麼模型就會回傳熊貓

這個方法有效的原因也很直覺，因為攻擊時就是只移動一點點，如果改成用上面的方式，「在一般情況下」攻擊要移動的距離就要很大才會有效

## 保證半徑

作者有算出一個點的保證半徑，也就是在該半徑內，top class 都可以被正確的回傳：

$$
R=\frac{\sigma}{2}({\phi}^{-1}(p_A)-{\phi}^{-1}(p_B))
$$

- $\sigma$ 就是採樣時高斯分佈的標準差，越大的話 $R$ 會越大
- 但是有可能會降低正確率，因為範圍越大，則機率最高的 class 可能不是正確的 class
- $p_A$ 是 top class 的占比，$p_A$ 是 second class 的占比
- ${\phi}^{-1}$ 是標準高斯分佈 CDF 的反函數 [**請見WIKI**](https://zh.wikipedia.org/zh-tw/%E6%AD%A3%E6%80%81%E5%88%86%E5%B8%83#%E7%B4%AF%E7%A9%8D%E5%88%86%E5%B8%83%E5%87%BD%E6%95%B8)
- $x\sim \mathcal{N}(0,1)$，則 ${\phi}^{-1}(p)=v\text{ s.t. }\mathbb{P}_x(x\le v)=p$
- 因為 ${\phi}^{-1}$ 是單調的，機率越高 ${\phi}^{-1}$ 值越大
- 所以直白上來說 ${\phi}^{-1}(p_A)-{\phi}^{-1}(p_B)$ 這個是在算兩者的占比的差距

## 蒙地卡羅

但是對於一個 model 來說，在某個範圍內機率分佈是不知道的，所以就是蒙地卡羅派上用場的時候了。

藉由採樣足夠多的點，求得 $p_A$ 的下限跟 $p_B$ 的上限。

所以上面的公式可以修改成：

$$
R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}({p_B}^{↑}))
$$

## Formal Definition

接著把上面的描述轉成數學的形式。

模型就是：

$$
f：\mathbb{R}^d\rightarrow y
$$

$y$ 是 class 的集合。

我們想將 $f$ 轉換成一個 smoothed classifier $g$：

$$
g(x):=\underset{c\in y}{\text{argmax }}\mathbb{P}_{\epsilon}(f(x+\epsilon)=c)
$$
>$\epsilon \sim \mathcal{N}(x,\sigma^2\mathbf{1})$

就是上面說的，以 $x$ 為中心的常態分佈，看看哪個類別的機率最大。

然後只要滿足下面的不等式：

$$
\mathbb{P}_{\epsilon}(f(x+\epsilon)=c_A)\ge{p_A}^{↓}\ge{p_B}^{↑}\ge\underset{c\ne c_A}{\max}\mathbb{P}_{\epsilon}(f(x+\epsilon)=c)
$$
>右邊那項就是機率第二高的 class，上下箭頭代表上下限。

則：

$$
\begin{align}
g(x+\delta)=c_A\ \text{for all } ||\delta||_{2}< R\\
R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}({p_B}^{↑}))
\end{align}
$$

:::info
要注意，並沒有說 $c_A$ 就是正確的 class，而是單純是機率最高的 class
:::

:::warning
雖然 $\phi^{-1}$ 的值可以是負的，但是因為有確保 ${p_A}^{↓}\ge{p_B}^{↑}$，加上單調性質，所以可以知道會得到非負的值
:::

## Gaussian data augmentation

對於固定的 $\sigma$，想要增加半徑的話就是要有較高的 $p_A$ 上限跟較低的 $p_B$ 下限，所以作者有說模型要先訓練成在 gaussian noise 下也有很好的表現會比較好。

## Certification Procedure

接下來介紹要怎麼用這個 $R$ 來求得 Certified Accuracy。

情境如下：

- 首先會給定一個目標半徑 $T$，就是攻擊的半徑
- 採樣時的 $\sigma$ 是給定的
- 然後檢查在測試集中哪些點，用上面的方法算出的 R 滿足兩件事情：
- $R\ge T$
- $R$ 半徑內機率最大的點跟 label 是符合的

這樣就可以算出哪些點是分對跟分錯了；下面是演算法：

- 先做較小數量的抽量 $n_0$，從這次抽的資料當中，紀錄數量最多的 class 作為 $\hat{c_A}$
- 接著再抽一次較大數量 $n$，然後紀錄 $\hat{c_A}$ 的數量 $n_{C_A}$
- 根據 $n_{C_A}$，抽取數量 $n$，以及一個信賴常數 $\alpha$，計算出 ${p_A}^{↓}$
- 我們至少有 $1-\alpha$ 的信心可以確保 ${p_A}^{↓}$ 是正確的下限
- 如果 ${p_A}^{↓}>\frac{1}{2}$，回傳預測的 $\hat{c_A}$ 作為預測的 class，以及由 ${p_A}^{↓}$ 算出的 $R$
- $R$ 可以由一條公式算出：
- $R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}({p_B}^{↑}))\ge R=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})-{\phi}^{-1}(1-{p_A}^{↓}))$
- $=\frac{\sigma}{2}({\phi}^{-1}({p_A}^{↓})+{\phi}^{-1}({p_A}^{↓}))$ (對稱性質)
- $=\sigma{\phi}^{-1}({p_A}^{↓})$
- 不然就回傳 $ABSTAIN$，說窩不知道

也就是說，只要結果回傳的不是窩不知道，那麼我們就至少有 $1-\alpha$ 的信心可以確保模型在半徑 R 內，$g(x+\delta)=\hat{c_A}$。

:::warning
但是要注意：

- $\hat{c_A}$ 不一定是正確的 class，因為隨著 $\sigma$ 變大，雖然半徑變大了，但是占比最多的 class 很有可能就不會是真正的 label；從講義後面的圖表也可以看到正確率會隨 $\sigma$ 變大而下降。

而會算在 incorrect 的除了上述的分錯之外，回答窩不知道也算在錯，情況有可能是：

- $n_0$ 太小，取樣不足
- 第一大跟第二大占比太接近

這兩個原因導致算出的 ${p_A}^{↓}\le\frac{1}{2}$，而得到窩不知道的回答。
:::

## Increasing Certified Radius

想要提升 $R$ 以增加 Robust 程度，如果在固定 $\sigma$ 的情況下，會跟第二次的 $n$ 以及信心值 $\alpha$ 有關。

作者有推導出 ${p_A}^{↓}$ 有個很緊的 lower bound 是 $\alpha^{\frac{1}{n}}$，也就是說 $\alpha$ 越小，想要提升 ${p_A}^{↓}$(或者說提升$R=\sigma{\phi}^{-1}({p_A}^{↓})$)，就需要越大的 $n$，而且 $R$ 的成長幅度很緩慢。

## Inference

上述是拿來用於驗證的，現在要介紹的是平常用於預測時的算法，或者說 $g$ 本身是如何計算的。

- 一樣進行大數量的取樣，然後紀錄第一第二多的兩種類別 $\hat{c_A}$ 跟 $\hat{c_B}$，以及對應的數量 $n_A$ 跟 $n_B$
- 去做 BinomialPValue 的虛無檢驗
- 要檢驗的是 $\text{BinomialPValue}(n_A, n_A+n_B, 0.5)$
- $\text{BinomialPValue}(i, n, q)$ 的意思是，計算成功機率為 $q$ 的二項式分佈
- 然後給定一個拒絕假設的機率 $\alpha$，選定分佈的某範圍機率加總為 $\alpha$，有分為單尾跟雙尾
- 最後看 $i$ 有沒有在拒絕範圍內，意思就是說 $i$ 有沒有落在那個機率很小的範圍內
- 有的話就代表成功的機率不是 $q$，此時要拒絕虛無假設
- 所以上面想要知道的是 $n_A$ 在 $n_A+n_B$ 中是不是 0.5%
- 如果 p 值比 $\alpha$ 大，代表我們接受虛無假說，相信真的是 0.5%，回傳 ABSTAIN 窩不知道
- 相信是 0.5% 代表這兩種 class 數量很接近，model 會無法分出是哪個 class
- 否則就是拒絕，相信不是 0.5%，回傳 $\hat{c_A}$

作者有接著證明拒絕之後回傳的 $\hat{c_A}$，但是犯錯 $\hat{c_A}\ne c_A$ 的機率至多就是 $\alpha$：

$$
\begin{align}
&\mathbb{P}(\hat{c_A}\ne c_A, \text{ no abstain })\\
= & \mathbb{P}(\hat{c_A}\ne c_A)\cdot\mathbb{P}(\text{ no abstain }| \hat{c_A}\ne c_A)\\
\le & \mathbb{P}(\text{ no abstain }| \hat{c_A}\ne c_A)=\alpha\\
\end{align}
$$

---

# Future Research Direction

RS 目前只適用 $l_2$ 的距離，如果是其他距離函數就會需要換掉 noise，或是用其他研究方式。

- 例如 $l_1$ 就要改用 [Laplace noise](https://zh.wikipedia.org/wiki/%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E5%88%86%E5%B8%83) 而不是 Gaussian noise

並且作者有說，如果想要提高 Certified Accuracy，可以根據特定的模型做實驗的修正，例如善用模型的某些特性，可以得到更精確的 Certified Accuracy。

- 因為這篇 paper 是黑盒，也就是完全對模型沒有任何假設
- 老師說其實這也是優點，不一定真的要改成用灰盒

# Is Certified Robustness All We Need

\[Wang & Bovik et al. IEEE signal processing magazine’09\] 這篇有提到，其實人類的視覺跟 $l_p$ distance 有很大的差距。

例如範例的圖中，雖然那幾張圖的 $l_2$ 距離都一樣，但是就人眼來看，已經從寫實變成畢卡索了。

# Small Changes Can Be Semantically Meaningful

雖然提到了那麼久的攻擊跟防禦，都是在「微小的改動」上做研究；但其實有時候「微小的改動」卻是有意義的而不是無意或是帶有惡意的。

如果一個模型非常抗擾動，那他有可能就因此對這些「微小的改動」很遲鈍。

- 例如數字辨識，0 跟 8 、5 跟 3 等等，加上顏色配置，可能只差一點點的 pixel

# “Breaking” Certified Defenses

\[Ghiasi et al. ICLR 2020\]

老師說這其實只是下個很聳動的標題，因為 RS 的理論保證就在那了。

這篇 paper 是透過調整明暗度，來達到人眼看不出來，但是 $l_2$ 的距離卻很大，使得準確率很低。

- 但是調整明暗度這個做法並不是基於 $l_2$ 距離，也就是說這篇 paper 是使用不同的 threat model 了
- 這篇 paper 是想說 RS 只專注於 $l_2$ 意義不大

:::info
老師有提到另一篇也是再說 break Certified Defenses，他是對 Numerical 計算的部分動手腳找到破綻，但是就算是 Edge case
:::