Skip to main content

Certified Robustness

Certified robustness は、特定の perturbation set の中では model の予測が変わらないことを数学的に保証する分野です。Empirical robustness が「この attack では破れなかった」という経験的評価であるのに対し、certified robustness は「この radius までは破れない」と証明します。

Randomized smoothing

自作概念図。Randomized smoothing は、入力周辺に Gaussian noise を加えて base classifier の多数決を取り、class probability の差から L2L_2 certified radius を計算します。

Certificate の定義​

入力 xx に対して、半径 RR の範囲では予測が変わらないことを保証できるとします。

∀δ  s.t.  ∥δ∥p<R,g(x+δ)=g(x)\forall \delta \; \text{s.t.}\; \|\delta\|_p < R, \quad g(x+\delta)=g(x)

この RR を certified radius と呼びます。Dataset 上では、ある半径 ϵ\epsilon で certificate を持つ sample の割合を certified accuracy として報告します。

CertifiedAcc(ϵ)=1n∑i1[g(xi)=yi  ∧  Ri≥ϵ]\mathrm{CertifiedAcc}(\epsilon)=\frac{1}{n}\sum_i \mathbf{1}[g(x_i)=y_i \;\land\; R_i \ge \epsilon]

Randomized smoothing​

Randomized smoothing は、任意の base classifier ff から smoothed classifier gg を作ります。

g(x)=arg⁡max⁡c  Pη∼N(0,σ2I)(f(x+η)=c)g(x)=\arg\max_c \; \mathbb{P}_{\eta\sim\mathcal{N}(0,\sigma^2 I)}(f(x+\eta)=c)

最も確率が高い class を AA、二番目に高い class を BB とし、確率を pAp_A、pBp_B とします。このとき、L2L_2 certified radius は次のように与えられます。

R=σ2(Φ−1(pA)−Φ−1(pB))R = \frac{\sigma}{2}\left(\Phi^{-1}(p_A)-\Phi^{-1}(p_B)\right)

ここで Φ−1\Phi^{-1} は standard Gaussian CDF の inverse です。pAp_A と pBp_B の差が大きいほど、より大きい radius を certify できます。

Monte Carlo 推定​

実際には pAp_A と pBp_B は closed-form でわからないため、多数の noise sample で推定します。Certification では統計的 confidence bound を使い、過大評価しないように lower bound / upper bound を計算します。

Bound propagation​

Interval Bound Propagation (IBP) は、入力の perturbation interval を layer ごとに伝播し、出力 logit の上限 / 下限を計算します。

入力が x∈[x‾,x‾]x \in [\underline{x},\overline{x}] にあるとき、linear layer z=Wx+bz=Wx+b の bound は、WW の正負に分けて計算できます。

z‾=W+x‾+W−x‾+b\underline{z}=W^+\underline{x}+W^-\overline{x}+b z‾=W+x‾+W−x‾+b\overline{z}=W^+\overline{x}+W^-\underline{x}+b

ここで、W+=max⁡(W,0)W^+=\max(W,0)、W−=min⁡(W,0)W^-=\min(W,0) です。最後に、正解 class の logit lower bound が他 class の upper bound より大きければ certify できます。

z‾y>max⁡j≠yz‾j\underline{z}_y > \max_{j\ne y}\overline{z}_j

Convex relaxation​

ReLU network の exact verification は一般に難しいため、ReLU を convex relaxation で緩めて bound を計算する方法があります。CROWN、Fast-Lin、DeepPoly などはこの family に入ります。

Lipschitz bound​

Model の Lipschitz constant KK がわかれば、logit margin m(x)m(x) から certificate を得られます。

∥f(x)−f(x+δ)∥≤K∥δ∥\|f(x)-f(x+\delta)\| \le K\|\delta\|

正解 class と他 class の margin が十分大きければ、予測が変わらない半径を下界できます。ただし、tight な Lipschitz bound を得るのは難しいです。

Certified robustness の限界​

観点内容
Scalability大規模 model では verification cost が高い
Norm specificityL2L_2 certificate は patch や spatial attack を保証しない
Accuracy trade-offcertificate を強めると clean accuracy が下がる場合がある
TightnessBound が緩いと、本当は robust でも certify できない
DomainText や LLM の離散入力では連続 norm certificate が扱いにくい

数式で見る certified radius​

Certified robustness は、「半径 RR 以内の perturbation に対して prediction が変わらない」ことを保証します。

f(x+δ)=f(x)∀δ:∥δ∥2<Rf(x+\delta)=f(x)\quad\forall\delta:\|\delta\|_2<R

Randomized smoothing では、base classifier ff に Gaussian noise を加えた smoothed classifier を定義します。

g(x)=arg⁡max⁡cP(f(x+η)=c),η∼N(0,σ2I)g(x)=\arg\max_c P(f(x+\eta)=c),\qquad \eta\sim\mathcal{N}(0,\sigma^2I)

Top class の確率を pAp_A、runner-up class の確率を pBp_B とすると、certified radius は次のように書けます。

R=σ2(Φ−1(pA)−Φ−1(pB))R=\frac{\sigma}{2}\left(\Phi^{-1}(p_A)-\Phi^{-1}(p_B)\right)

この式の気持ちは、「noise を加えても class A が十分に安定して勝つなら、入力の周りの一定半径では class が変わらないと保証できる」というものです。Certified robustness は attack に依存しない保証を与えますが、保証半径や clean accuracy には限界があります。

関連ページ​

主なソース​