[Review] TRADES: Theoretically Principled Trade-off between Robustness and Accuracy

Hwan Heo·2021년 11월 28일
1
post-custom-banner

이전까지 Adversarial Training 으로 학습된 Neural Network 는 vanilla training 에 비해서 accuracy 에서 성능 하락이 있는 것이 알려져 있었다, 즉 Robustness ↔ Accuracy 간의 Trade-off 가 존재한다. 이 논문은 이러한 Robustness ↔ Accuracy 간의 Trade-off 를 수학적으로 규명하고 이를 이용해 새로운 Adversarial Defense Algorithm: Trades 을 소개한다.
ICML2019

1. Introduction

1.1. Empirical Risk Minimization

논문에 본격적으로 들어가기에 앞서, Empirical Risk Minimization 에 대한 간단한 소개를 하도록 한다.

우리가 어떠한 loss function (or risk function :L: \mathcal L ) 을 통해서 supervised learning 으로 Machine Learning Model (f(x))(f(x)) 을 학습할 때, 이 학습의 loss (risk) 를 다음과 같이 정의할 수 있다.

R(f)=E[ L(f(x),y) ]=L(f(x),y)dP(x,y)R(f) = \mathbb E [ \ \mathcal L(f(x), y) \ ] = \int \mathcal L(f(x), y) \cdot dP(x,y)

여기서 yy 는 ground-truth label 이고, P(x,y)P(x, y) 는 data 와 label 간의 Joint-Probability-Distribution 이다. 하지만 이러한 risk 는 다음 두 가지의 이유로 사용할 수 없다.

  1. Computationally Intractable

  2. Intractable Joint-Probability Distribution

그렇기 때문에 우리는 실질적으로는 training dataset 에서 sampling 된 risk 인 Empirical Risk

1Ni=1NL(f(xi),yi){1 \over N} \sum _{i=1}^N \mathcal L (f(x_i ), y_i )

를 통해 model 을 학습해야하고, 이를 Empirical Risk Minimization (ERM)이라고 한다.

1.2. Adversarial Training with ERM

이제 ERM formulation 을 통해 Optimal Robust Training 을 다음과 같이 표현하자.

arg maxx:xxϵ1{f(x)y}\argmax {}_ {x' : \|x-x' \| \le \epsilon} \mathbf 1 \{ f(x') \neq y \}

통상적인 supervised learning problem 에서 0-1 loss 는 우리가 학습을 통해 구하는 Estimator 가 maximun a posterior (joint probability) 가 되기 때문에 optimal loss 이다.

이를 통해 구할 수 있는 model 을 BayesOpt 라 하는데, 문제는 이 BayesOpt 를 구하는 방법이 np-hard problem 이라는 데 있다. (기본적으로 미분이 안되는 함수들은 최적화하기 굉장히 곤란하다)

따라서 0-1 loss 를 대체할 수 있는 surrogate loss 가 필요하고, 기존의 adversarial training 은 모두 이러한 surrogate loss 를 도입하여 adversarial training 을 진행하였다. 즉, 다음과 같은

minθmaxδ Ei[ L(fθ(xi+δ), yi ;θ) ]\min _\theta \max _{\delta \in \triangle }\ \mathbb E_i \left [ \ \mathcal L (f_\theta (x_i +\delta ) ,\ y_i \ ; \theta )\ \right ]

min-max formulation 으로 나타나는 기존의 adversarial training 은 모두 이 0-1 loss 에 대한 surrogate loss 를 도입하여 training 을 진행한 것이다.

하지만 저자들은 이러한 formulation 이 실제 optimal risk 에 대한 tightest approximation 이 아니라고 주장하며, 이를 classification-calibrated loss 의 도입으로 differentiable tightest bound 를 구하여 도입한 새로운 Adversarial Training Algorithm 인 Trades 를 제시한다.

2. Preliminaries

2.1. Notations

  1. Ball of Decision Boundary

    B(DB(f),ϵ)=f:{xX:xB(x,ϵ)s.t. f(x)f(x)}\mathbb B( \text{DB} (f) , \epsilon ) = f : \{ x \in \mathcal X : \exist {x' \in \mathbb B(x, \epsilon) \quad \text{s.t.} \ f(x) \neq f'(x) } \}

    Radius 가 ϵ\epsilon 인 norm ball 안의 xx' (perturbed) 가 original input 과 다른 model output 을 도출하는 점이 존재. 즉, data point xx 근처에 Decision Boundary 가 있는 집합을 의미한다.

  2. Conjugate function

    f(y)=supy{xTyf(x)}f^* (y) = \sup_y \{ x^Ty - f (x) \}

    이 함수는 yy 에 대한 pointwise supremum of affine function 이기 때문에 원함수의 convex 여부에 상관없이 convex function 이다. 본 논문에서는 bi-conjugate 이 원함수에 대한 convex hull 을 만든다는 성질을 이용한다.

2.2. Robust Classification Error with Natural & Boundary Error

저자들은 ERM 학습에서의 error 를 다음과 같이 총 3개로 나누어서 정의한다.

  1. Robust Error

    Rrob(f):= EX,Y1{ XB(X,ϵ)s.t. f(X)Y}\mathcal R_{\text{rob}} (f) := \ \mathbb E _{X,Y} \mathbf 1 \{ \exist \ X' \in \mathbb B(X, \epsilon ) \quad \text{s.t. } f(X') \neq Y \}

    Norm ball 내에서 neighborhood data 의 model output 이 ground-truth label 와 다른 경우의 error 이다. 학습된 model 이 얼마나 generalize 를 잘하는지를 나타내는 error 라고 보면 될 듯 하다.

  2. Natural Error

    Rnat(f):= EX,Y1{f(X)Y}\mathcal R_{\text{nat}} (f) := \ \mathbb E _{X,Y} \mathbf 1 \{ f(X) \neq Y \}

    Original data 의 model output 이 ground-truth label 과 다른 경우의 error 이다. (즉 True Negative)

  3. Boundary Error

    Rbdy(f):= EX,Y1{XB(DB(f),ϵ)s.t. f(X)=Y}\mathcal R_{\text{bdy}} (f) := \ \mathbb E _{X,Y} \mathbf 1 \{ X \in \mathbb B(\text{DB}(f), \epsilon ) \quad \text{s.t. } f(X) = Y \}

    2.1. 의 Decision boundary set 정의에서 data point xx 의 norm ball 내의 decision boundary 위의 점 xx'f(x)f(x)f(x) \neq f(x') 이다. 따라서 original model output 은 ground-truth label 과 같지만 perturbed data 에 대해 다른 output 을 내뱉는, 즉 adversarial attack 이 성공하는 경우의 error 이다.

각 3개의 error 의 정의를 통해 다음과 같은 관계를 도출할 수 있다.

Rrob=Rnat+Rbdy\mathcal R_{\text{rob}} = \mathcal R_{\text{nat}} + \mathcal R_{\text{bdy}}
  • Robust Error : '잘못 배움' + 'perturbed 이후 DB 넘어감' 정도로 해석할 수 있겠다.

논문에서는 다음과 같은 Toy Example 에서 BayesOpt classifier (optimal estimator) 와 all-1 classifier (worst-case estimator) 에 대한 각각의 error 를 나타낸다.

η(x):=Pr(Y=1X=x)={0,x[2kϵ,(2k+1)ϵ],1,x[(2k+1)ϵ,(2k+2)ϵ]\begin{aligned} \eta(x) :&= \text{Pr} (Y=1 |X=x) \\ &= \begin{cases} 0, \quad x \in [2k\epsilon, (2k+1)\epsilon], \\ 1, \quad x \in [(2k+1)\epsilon, (2k+2)\epsilon] \end{cases} \end{aligned}

즉, 위 예제에서조차 optimal estimator 라고 하더라도 robust error 를 0으로 만드는 것은 impossible 한 것을 알 수 있다.

3. Method

저자들은 위에서 제시한 robust error 와 natural error 등의 정의를 이용해 기존의 min-max formulation 으로 정의된 Adversarial Training 은 optimal objective 가 아님을 주장한다. 또한 Classification-Calibrated 를 통해 새롭게 정의되는 Adversarial Training 방법론을 제시한다.

3.1. Classification-Calibrated Loss

3.1.1. Optimal Risk & Good Classifier

Binary classification model ff 의 training risk 와 이의 하한을 다음과 같이 정의할 수 있다. (y{1,1})( y \in \{-1, 1 \} )

R(f)=P(sign(f)y)R=inffR(f)\begin{aligned} &R (f) = P (\text{sign} (f) \neq y ) \\ &R^* = \inf _f R(f) \end{aligned}

여기서 정의된 R(f)R^*(f) 는 어떠한 training loss 로 구할 수 있는 최적의 estimator ff 에 대한 risk 임을 의미한다. 이를 통해 어떤 classifier model ffExcess Risk 를 정의할 수 있다 .

  • Excess Risk:
    R(f)RR(f) - R^*
    이 값은 어떤 loss 에 대하여 현재 model ffBayesOPT 와 얼마나 차이나는지를 의미한다.

또한 저자들이 인용한 'Convexity, Classification and Risk Boudns' 에서,
Good classifier 를 알맞은 예측을 50% 이상의 confidence 로 예측하는 classifier 라고 정의한다. 즉,

f:=f f(x)(η(x)12)0f := \exist _f \ f(x) ( \eta(x) - {1 \over 2} ) \ge 0

를 만족하는 classifier 가 good classifier 이다. (η:( \eta : confidence score of f)f )

3.1.2. Surrogate Risk with Confidence Score

0-1 loss 에 대한 surrogate loss function ϕ\phi 를 통해 binary classification (predicted 와 GT label 의 곱이 1) 에 대한 surrogate loss 의 training risk 를 다음과 같은 Conditional ϕ\phi risk 로 나타낼 수 있다.

  • Conditional ϕ\phi risk :
    E[ϕ(Yf(X))  X=x]=P(y=1  x)ϕ(1f(x))+P(y=1  x)ϕ(1f(x))=η(x)ϕ(f(x))+(1η(x))ϕ(f(x))\begin{aligned} &\mathbb E [ \phi (Yf(X)) \ | \ X = x ] \\ &= P(y=1 \ | \ x)\cdot \phi(1 \cdot f(x) ) + P(y= -1 \ | \ x)\cdot \phi(-1 \cdot f(x) ) \\ &= \eta (x) \cdot \phi (f(x)) + (1 - \eta (x) ) \cdot \phi(-f(x)) \end{aligned}

이를 이용하여 다음과 같은 함수를 정의할 수 있다.

  • General Conditional ϕ\phi risk :
    Cη(α)=ηϕ(α)+(1η)ϕ(α)\begin{aligned} &C _{\eta } (\alpha ) = \eta \cdot \phi (\alpha ) + (1- \eta) \cdot \phi(- \alpha) \\ \end{aligned}
    이는 binary classification 에서의 confidence score η\eta 에 따른 risk function 이다.

여기서 CηC_\etaη\eta 에 대한 affine function 이고, 이 함수에 대한 infimum 을 다음과 같이 정의할 수 있다. (이는 affine function 의 infimum 이기 때문에 convex 이다.)

  • Risk Infimum :
    Hϕ(η)=infηCη(α)H_{\phi} (\eta) = \inf _\eta C _{\eta } (\alpha)
    이는 어떤 surrogate loss ϕ\phi 에 대하여 prediction α\alpha 가 정해졌을 경우, confidence 에 변함에 따라 risk 가 가질 수 있는 최저값을 의미한다. 이를 통해 우리는 optimal ϕ\phi risk 를 risk infimum 을 이용하여 정의할 수 있다.
    Rϕ:=inffRϕ(f)=Ex[Hϕ(η(x))]R^*_\phi := \inf _f R_\phi (f) = \mathbb E_x \left[ H_\phi (\eta(x)) \right]

여기서 CηC_\eta 는 affine function 이기 때문에, affine function 의 infimum 인 HϕH_\phi 는 convex 이다. 따라서 이 conditional risk 가 121 \over 2 에서 최댓값을 가짐을 다음과 같이 보일 수 있다.

H(12)=H(12η+12(1η))12H(η)+12H(1η)=H(η)H( {1 \over 2} ) = H({1 \over 2 } \eta + {1 \over 2} (1-\eta) ) \\ \ge {1\over 2}H(\eta ) + {1 \over 2} H(1-\eta ) = H(\eta)

직관적으로는, 어떤 binary classifier 의 prediction 에 대한 확률이 50% (: coin toss classifier)일 때 risk 값이 최대임을 의미한다.

3.1.3. Classification-Calibrated

이제 Bad classifier (i.e. not Good Classifier) 를 다음과 같이 정의하자.

f:=f f(x)(η(x)12)0f := \exist _f \ f(x) ( \eta(x) - {1 \over 2} ) \le 0

이를 통해 Bad Classifier 의 lower bound of conditional risk HH^- 를 다음과 같이 정의할 수 있다. (i.e., correct confidence score 가 50% 이하인 classifier : bad classifier 의 infimum)

Hϕ(η)=infα:α(2η1)0Cη(α)H^-_\phi (\eta ) = \inf {}_{\alpha : \alpha (2 \eta -1) \le 0 } C_\eta (\alpha)

Classification-Calibrated 는 다음과 같이 정의된다.

  • Classification-Calibrated :
    Hϕ(η)>Hϕ(η)H^- _\phi (\eta) > H_\phi(\eta )
    즉, 어떠한 surrogate loss ϕ\phi 에 대한 risk 로 학습되는 classifier 에 대해,
    Bad Classifier 의 lower risk bound > Good Classifier 의 lower risk bound
    를 만족할 때 이를 Classification-Calibrated 라고 한다.

정의에 따라, classification-calibrated 를 만족시키는 surrogate loss risk 는 training 이 Bad Classifier -> Good Classifier 로 이루어질 것이기 때문에, Classification-Calibrated 는 good classifier 를 학습시킬 수 있는 좋은 surrogate loss 가 되어주는 기준이 된다.

3.1.4. Surrogate Loss Boundary Estimation

이제 surrogate loss ϕ\phi 에 대한 다음과 같은 transformation 을 정의하자.

ψ^(θ)=Hϕ(1+θ2)Hϕ(1+θ2)\hat \psi (\theta) = H_\phi^- \left({1 + \theta \over 2} \right) - H_\phi \left({1 + \theta \over 2}\right)
ψ=ψ^\psi = \hat \psi ^{**}

ψ^\hat \psi 의 각 Risk infimum 의 input 은 θ[0, 1]1+θ2[12, 1]\theta \in [0,\ 1] \rightarrow {{1+\theta} \over 2} \in [{1 \over 2}, \ 1] 의 input 을 받기 때문에, 이 transformation 은 어떠한 surrogate loss ϕ\phi 에 대해 confidence 가 50% 이상인 prediction 에 대한 false prediction risk 와 positive prediction risk 의 차이를 의미한다.
이 transformation ψ\psi 는 다음과 같은 몇 가지 중요한 성질을 갖는다.

  • Hϕ(12)=Hϕ(12)H_\phi^- ({1 \over 2}) = H_\phi({1 \over 2}) 이기 때문에 ψ(0)=0\psi(0)=0 이다.

  • ψ\psi transformation 은 bi-conjugate 임으로, 원함수의 tightest closed convex hull 이 되는데, 이에 따라 epi ψ=coˉ epi ψ\textbf{epi}\ \psi^{**} = \bar{\text{co}} \ \textbf{epi} \ \psi 를 만족한다 (co : convex hull). 이는 convex 함수를 pointwise affine function 으로 나타낼 수 있기 때문이다. 따라서 ψ(θ)\psi(\theta) 는 convex function 이다.

  • Convexity 로부터, λ[0, 1]\lambda \in [0, \ 1]λ\lambda 에 대하여 ψ(λx)λψ(x)\psi(\lambda x) \le \lambda \psi(x) 를 만족하고, 이로부터 0yx0 \le y \le xλ=x/y\lambda = {x / y} 에 대해

    ψ(y)yψ(x)x{\psi(y) \over y} \le {\psi(x) \over x}

    이 성립한다. i.e.  ψ(θ)/θ{\ \psi(\theta) / \theta} : non-decreasing 이므로 다음과 같이 ψ\psinon-decreasing 임을 알 수 있다.

    ddθψ(θ)θ=ψ(θ)θψ(θ)θ20{d \over d\theta}{{\psi(\theta)} \over \theta} = {{\psi'(\theta)\cdot\theta - \psi(\theta)} \over \theta^2 } \ge 0
    ψ(θ)ψ(θ)θ0\therefore \psi'(\theta) \ge {\psi(\theta) \over \theta} \ge 0

다음은 binary classification problem 에서 classification-calibrated loss 의 몇 가지 예시이다.

3.2. Relating 0-1 loss to Surrogate Loss

위에서 정의된 transformation boundary 을 통해서 우리는 optimal robust training risk 의 bound 를 설정할 수 있다.

Transformation ψ\psi 을 통해, 어떠한 surrogate loss ϕ\phi 로 정의되는 empirical ϕ\phi excess risk 와 optimal excess risk 사이에 다음과 같은 inequality 가 성립한다.

ψ(R(f)R(f))Rϕ(f)Rϕψ(θ)R(f)R(f)ψ(θ)+ζ\psi (R(f) - R^* (f) ) \le R_\phi(f) - R^* _\phi \\ \psi (\theta ) \le R(f) - R^* (f) \le \psi (\theta) + \zeta

이때 Rrob=Rnat+Rbdy\mathcal R_{\text{rob}} = \mathcal R_{\text{nat}} + \mathcal R_{\text{bdy}} 로부터,

RrobRnat=RnatRnat+Rbdy\mathcal R_{\text{rob}} - \mathcal R^*_{\text{nat}}= \mathcal R_{\text{nat}} - \mathcal R^*_{\text{nat}} + \mathcal R_{\text{bdy}}

를 만족한다. 위에서 제시된 inequality 를 이용하여 다음과 같은 식을 도출할 수 있는데,

Rrob(f)Rnat=Rnat(f)Rnat+Rbdy(f)ψ1(Rϕ(f)Rϕ)+Rbdy(f)R_{\text{rob}} (f) - R_{\text{nat}} ^* = R_{\text{nat}}(f) - R_{\text{nat}}^* + R_{\text{bdy}} (f) \le \psi^{-1} (R_{\phi} (f) - R^* _\phi) + R_{\text{bdy}} (f)

이로부터 다음과 같은 upper bound, lower bound 를 유도할 수 있다.

  1. Upper Bound

    Rrob(f)Rnat ψ1(Rϕ(f)Rϕ) + Pr[XB(DB(f),ϵ),f(X)Y>0] ψ1(Rϕ(f)Rϕ) + EmaxXB(X,ϵ)ϕ(f(X)f(X))\begin{aligned} R_{\text{rob}} (f) - R_{\text{nat}} ^* \le \ &\psi^{-1} (R_{\phi} (f) - R^* _\phi )\ + \ \text{Pr}[X\in \mathbb B(\text{DB}(f), \epsilon) , f(X)Y > 0] \\ \le \ &\psi^{-1} (R_{\phi} (f) - R^* _\phi )\ + \ \mathbb E \max _{X' \in \mathbb B(X, \epsilon)} \phi(f(X')f(X) ) \end{aligned}
  2. Lower Bound

ψ(θEmaxXB(X,ϵ)ϕ(f(X)f(X)))Rϕ(f)Rϕψ(θEmaxXB(X,ϵ)ϕ(f(X)f(X)))+ζ\psi \bigg(\theta - \mathbb E \max _{X' \in \mathbb B(X, \epsilon)} \phi(f(X')f(X) ) \bigg) \\ \le R_{\phi} (f) - R^* _\phi \le \\ \psi \bigg(\theta - \mathbb E \max _{X' \in \mathbb B(X, \epsilon)} \phi(f(X')f(X) ) \bigg) + \zeta

특이할만한 점은 bound 를 설정함에 있어서 ground-truth label 이 필요하지 않다는 것이다. 또한 통상적인 min-max formulation 에서 볼 수 있는 adversarial attack 과도 조금 다른데, Robust classifier 의 tightest boundary 가 GT label 이 아닌, vanilla model 의 decision boundary 에만 관련이 있음을 알 수 있다.

3.3. Adversarial Training with Classification-Calibrated Bound

이제 기존의 Adversarial Training 과의 비교를 통해서 Trade-off Training 알고리즘을 설명한다.

  1. Prior-Work :

    minfE{maxXB(X,ϵ)ϕ(f(X)Y)}\min _f \mathbb E \bigg \{ \max _{X' \in \mathbb B(X, \epsilon)} \phi(f(X')Y) \bigg \}

    기존 Adversarial training 에서는 inner-maximization problem 을 ground-truth label 과 adversarial example 간의 loss 를 이용해서 구했다.

  2. TRADES

    minfE{ϕ(f(X)Y) + 1λmaxXB(X,ϵ)ϕ(f(X)f(X)}\min _f \mathbb E \bigg \{ \phi(f(X)Y ) \ + \ {1 \over \lambda}\max _{X' \in \mathbb B(X, \epsilon)} \phi(f(X')f(X) \bigg \}

    TRADES 는 natural error 와 decision boundary error 를 분리하여 <span style='color:red'decision boundary 에서의 maximization 을 통해 adversarial example 을 구하게 된다.

    • 저자들은 제시하는 adversarial training 방법이 inner maximization 에서 label 이 필요하지 않으므로 semi-supervised setting에서 adversarial training 방법론으로써 쓰일 수 있다고 한다.

    • 여기서 λ\lambda parameter 는 커질수록 BayesOpt, 작아질수록 all-one classifier 처럼 행동하게 될 것이다.

    • 해당 값이 커짐에 따라 natural risk 만을 신경쓰는 BayesOpt 처럼 학습될 것이고, 작을수록 boundary risk 만을 신경쓰는 all-one-classifier 처럼 학습될 것이다. 즉 regulaizer 로써의 Trade-off coefficient 역할을 하게 된다.

2에서 제시된 optimization objective 를 이용한 학습 알고리즘은 다음과 같다.

주의할만한 점은 (7)에서 natural image 에 gaussian noise 를 더해주는 것이다. 이는 이미 학습이 끝난 classifier 는 seen data 에 대한 gradient 가 0에 가깝게 흐르기 때문이다. (local minima : f=0\nabla f = 0 )

4. Experiments

  • 성능은 당시 기준 SOTA 이다.
  • 또한 parameter λ\lambda 에 따른 robust, natural error 변화도 report 되었다. 값이 커짐에 따라 natural error 가 작고, 작을수록 robust error 가 작음을 알 수 있다.

논문 자체보다는 인용한 논문인 'Convexity, Classification and Risk Boudns' 를 이해하는데 더 어려웠고, 실제로 convex optimization 에 익숙하지 않은 사람이 읽는다면 꽤 장벽이 있는 논문이라고 생각된다.

지금까지 Robust Traning 에서 accuracy 와 robustness 간의 trade-off 가 있다는 것이 알려진 것은 사실이지만, 이를 직접 수학적으로 규명하고 그러한 trade-off 가 필연적인 것임을 규명했다는 데 의의가 있다.

여담으로 FGSM 등과 비교하여 inner maximization 을 decision boundary error 로 접근했을 때 attack 의 성능 차이가 어떻게 되는지를 비교했으면 더 좋지 않았을까 하는 생각이 든다.

profile
기타치는AI Researcher
post-custom-banner

0개의 댓글