Sansan Builders Box

Sansanのものづくりを支える技術やデザイン、プロダクトマネジメントの情報を発信

【ML Tech RPT. 】第8回 敵対的摂動 (Adversarial Perturbation) に対するモデルの頑健性の測り方を学ぶ (2)

f:id:ssatsuki040508:20181210005017p:plain

DSOC研究員の吉村です. 最近は健康第一ということで, 食事の面から健康に気を使い始めました. このことをチームのメンバーに話したところ, シリコンスチーマーを使うと手軽に茹でた野菜が食べれるということを教えてもらえたので, 早速購入しました.

さて, 本記事は前回に引き続き「敵対的摂動 (Adversarial Perturbation) に対するモデルの頑健性の測り方」についての話です. 今回は, 前回の記事の最後で書いた適用範囲の広い測定手法について紹介します. 本記事では前回の記事の内容について触れますので, 前回の記事をまだ読んでいらっしゃらない方はそちらから先に読まれることをお勧めします.

buildersbox.corp-sansan.com

はじめに

前回の記事では「敵対的摂動 (Adversarial Perturbation) に対するモデルの頑健性の測り方」というテーマに対して, それが「どのような研究テーマなのか」, 「なぜ研究されているのか」について詳しく説明をしました. また, おそらくこの分野の最初の手法である Cross-Lipschitz Regularizationを用いる手法[*1] についての紹介もしました. しかし, この手法は各出力に対応する多クラス分類器の内部分類器が, 入力に関して連続であり微分可能な時に限り用いることが可能であるという制約がありました. それを受けて更に適用範囲を広げた手法として提案された CLEVER (Cross Lipschitz Extreme Value for nEtwork Robustness) [*2] について今回は紹介します.

[T. W. Weng et. al., 2018] の中では, 敵対的摂動による攻撃を二種類に分類して評価手法が提案されています. そのため, まずはこの二つの攻撃がどのようなものかについて説明するところから始めます.

敵対的摂動による攻撃の分類

[T. W. Weng et. al., 2018] では, 敵対的摂動による攻撃を Untargeted Attack と Targeted Attack の二つに分けています. なお, 以降  \boldsymbol{x_o} を元のサンプル,  \boldsymbol{x_a} を敵対的サンプル,  c(\cdot) を入力を受けてクラスを返す多 ( K) クラス分類器とします.

Untargeted Attack


Untargeted Attack は, 元のサンプルに対応する出力を, 別の任意の出力に変更すること, つまり, 出力を元のサンプルに対応するクラスとは別のクラスに変えさせるのが目的です. 具体的に書くと, Untargeted Attack とは

 c(\boldsymbol{x_a}) \neq c(\boldsymbol{x_o}) となる  \boldsymbol{x_a} を見つけること

と言えます.

Targeted Attack


Targeted Attack は, 元のサンプルに対応する出力を, 別の特定の出力に変更させること, つまり, 出力を狙った特定のクラスに変えさせるというのが目的です. 具体的に書くと, Targeted Attack とは

目的となるクラス  t \neq c(\boldsymbol{x_o}) が与えられた時に,  c(\boldsymbol{x_a}) = t となる  \boldsymbol{x_a} を見つけること

と言えます.


CLEVER (Cross Lipschitz Extreme Value for nEtwork Robustness) [T. W. Weng et. al., 2018]

敵対的摂動による二種類の攻撃方法について確認できたので, CLEVER の詳細に触れていきます. CLEVER は前回の記事で紹介した二種類の測定アプローチのうち, Verification Based Approach に属する手法です. [T. W. Weng et. al., 2018] のなかで著者らは, 敵対的摂動に関する研究と敵対的摂動に対するモデルの頑健性の評価方法に関する研究は独立に行われるべきであるというような種の話をしており, それが反映されていると考えられます.

CLEVER は [T. W. Weng et. al., 2018] で4つの長所があると書いてあります.

  1. 攻撃方法に依存せず頑健性の評価が可能.
  2. 任意の NN 系 のモデルに応用が可能.
  3. 強い理論保証あり.
  4. 大きなネットワークであっても, 計算が可能.

CLEVER の大まかな方針は元のサンプル  \boldsymbol{x}_o ごとに,  \boldsymbol{x_o}+\boldsymbol{\delta}敵対的サンプルになるようなノイズ  \boldsymbol{\delta} p ノルム  ||\boldsymbol{\delta}||_p の最小値  \Delta_{p, \text{min}} を求めることになります. (ただし, ここで言っている「敵対的サンプルになる」とは, 元のサンプルに対応する出力クラスと, 元のサンプルにノイズが乗ったサンプルに対応する出力クラスが異なる状況のことを指しています.) しかし, この  \Delta_{p, \text{min}} を厳密に求めるのは難しいため, 基本的には  \Delta_{p, \text{min}} の上界  \beta_U と下界  \beta_L を見積もることが目標になります.

ある元のサンプル  \boldsymbol{x_o} に対応する p=2 ノルムでの最小値, 上界, 下界のイメージが下記になります. ただし,  B_2 = B_2(\boldsymbol{x_o}, \Delta_{2, \text{min}}) です.

f:id:ssatsuki040508:20190725134132p:plain
ある元のサンプル  \boldsymbol{x_o} に対応する p=2 ノルムでの最小値, 上界, 下界のイメージ

 \Delta_{p, \text{min}} の下界  \beta_L を半径にとる  p ノルムに基づく超球内部の全てのノイズが乗ったサンプルは, 敵対的サンプルになり得ません. 逆に,  \Delta_{p, \text{min}} の上界  \beta_U を半径にとる  p ノルムに基づく超球内部には少なくとも一つ以上の敵対的サンプルが含まれます. このことから, 元のサンプルにノイズが乗ったある点が敵対的サンプルとなる場合には, そのノイズの  p ノルムがまさに上界  \beta_U の一つと言えるため, 上界を求めるのは比較的容易な作業になります. しかし, 問題は下界を求める部分で, こちらを理論的に求める手法を提案したのがこのCLEVERです.

CLEVER における \Delta_{p, \text{min}} の下界  \beta_L の求めるための考え方


CLEVER では, 最終的に  \Delta_{p, \text{min}} の下界  \beta_L極値理論 (Extreme Value Theory) を応用することで求めます. 次の流れでCLEVERの考え方を説明することができます.

  1.  \Delta_{p, \text{min}} の下界  \beta_L の求値問題」 から 「 f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の局所 Lipschitz 定数求値問題」への帰着.
  2.  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の局所 Lipschitz 定数求値問題」から「 \boldsymbol{x_o}の近傍の任意の二点間の  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の勾配の絶対値の極大値の求値問題」への帰着.
  3.  \boldsymbol{x_o}の近傍の任意の二点間の  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の勾配の絶対値の極大値を極値理論を応用して求値.

上記の流れを順を追って見ていきます.

1.「 \Delta_{p, \text{min}} の下界  \beta_L の求値問題」から「 f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の局所 Lipschitz 定数求値問題」への帰着.

下記の補題で説明ができます.

Corollary 3. 2. 1 of [T. W. Weng et. al., 2018]
(Formal guarantee on  \beta_L for untargeted attack)

 L_{q, \boldsymbol{x_o}}^j f_c(\boldsymbol{x}) -  f_j(\boldsymbol{x}) について B_p(\boldsymbol{x_o}, R) 空間上で点  \boldsymbol{x_o} に対応する Lipschitz 定数とし,  \boldsymbol{\delta} \in B_p(\boldsymbol{0}, R) ならば,
$$||\boldsymbol{\delta}||_p \leq \min \left\{\min_{j\neq c}\frac{f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o})}{L_{q, \boldsymbol{x_o}}^j}, R \right\}$$
の時,  c = \text{argmax}_{j=1,\cdots, K} f_j(\boldsymbol{x}+\boldsymbol{\delta}) を満たす. つまり, 元のサンプルに対する分類器の出力クラスと, ノイズ  \boldsymbol{\delta} が乗ったサンプルに対する分類器の出力クラスが変わらない.

この補題から,
$$\beta_L = \min \left\{\min_{j\neq c}\frac{f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o})}{L_{q, \boldsymbol{x_o}}^j}, R \right\}$$
となることがわかり, この時, 未知の値は局所 Lipschitz 定数  L_{q, \boldsymbol{x_o}}^j だけなので, この局所 Lipschitz 定数  L_{q, \boldsymbol{x_o}}^j を求めることができれば, 下界  \beta_L を得ることができます. こうして「 \Delta_{p, \text{min}} の下界  \beta_L の求値問題」を「 f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の局所 Lipschitz 定数求値問題」へ帰着させることができました.

上記は Unterget Attack の場合についての話ですが, Target Attack についても [T. W. Weng et. al., 2018] の補題3. 2. 2 で同様の帰着ができます.

また, CLEVER の略さない言い方である Cross Lipschitz Extreme Value for nEtwork Robustness の Cross Lipschitz とは, 二つの関数の差分  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の Lipschitz 定数のことを指しています.

2. 「 f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の局所 Lipschitz 定数求値問題」から「 \boldsymbol{x_o}の近傍の任意の二点間の  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の勾配の絶対値の極大値の求値問題」への帰着.

そもそも局所 Lipschitz 定数とはどのような値かを考えます. 点  \boldsymbol{x_o} での局所 Lipschitz 定数  L_{q, \boldsymbol{x_o}}^j は, 点  \boldsymbol{x_o} の近傍の任意の二点間の関数  f_c(\boldsymbol{x}) -  f_j(\boldsymbol{x}) (=g(\boldsymbol{x})) の勾配の絶対値を上から抑えることができることが知られています. これは, 言い換えれば, そのような点  \boldsymbol{x_o} の近傍の任意の二点間の  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の勾配の絶対値の極大値と局所 Lipschitz 定数  L_{q, \boldsymbol{x_o}}^j が等しいことを意味します. したがって, 「 f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の局所 Lipschitz 定数求値問題」から「 \boldsymbol{x_o}の近傍の任意の二点間の  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の勾配の絶対値の極大値の求値問題」への帰着ができました.

3.  \boldsymbol{x_o}の近傍の任意の二点間の  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の勾配の絶対値の極大値を極値理論を応用して求値.

これまでの流れで, 点  \boldsymbol{x_o} の近傍の任意の二点間の  f_c(\boldsymbol{x_o}) - f_j(\boldsymbol{x_o}) の勾配の絶対値の極大値を求めることができれば,  \Delta_{p, \text{min}} の下界  \beta_L を求めることができることがわかりました. したがって, この極大値を求めることが最終的な目標となります. この勾配の絶対値は back propagation を用いることで容易に計算が可能ですが, その極大値を求めることは, ある超球内の最大値を求める問題となるため, 計算量は非常に多くなります. 探索対象の空間の次元がある程度低いと仮定しても, 全探索を行うには膨大な計算量となるため単純に全てを調べ尽くすという方法では対応できないことがわかります. そこで, CLEVER ではサンプリングに基づいてある分布から得られる値の最大値を見積もります. この時, 極値理論を用いる事でサンプリング結果から分布の上限が得られる場合があり, その場合において厳密に局所 Lipschitz 定数を得ることができます. ここで用いている極値理論の定理としては Fisher-Tippett-Gnedenko Theorem が用いられています.

CLEVER における \Delta_{p, \text{min}} の下界  \beta_L を求めるアルゴリズム


前節で色々複雑な話をしてきましたが, アルゴリズム自体は非常に簡単です. まず, Targeted Attack に対応するアルゴリズムが下記になります. ただし, 下記アルゴリズムの逆ワイブル分布というのは, 上述した分布の上限を正確に得ることができる場合に出現する分布のことです.

Algorithm 1: CLEVER-t of [T. W. Weng et. al., 2018]
入力:  K クラス分類器  f(x) , クラスが c と予測されるデータ点  \boldsymbol{x_o}, 目標クラス  j , バッチサイズ  N_b, バッチ一回あたりのサンプリング数  N_s, ノイズのノルム  p, 最大ノイズ  R
出力: クラス  j に対応するCLEVER スコア  \mu \in \mathbb{R}_+

  1.  S \in \{\emptyset\}, g(\boldsymbol{x}) \leftarrow f_c(\boldsymbol{x}) - f_j(\boldsymbol{x}), q \leftarrow \frac{p}{p-1}
  2. for  i \leftarrow 1 to  N_b do
  3.  \ \ \ \ for  k \leftarrow 1 to  N_s do
  4.  \ \ \ \ \ \ \ \  \boldsymbol{x}^{(i,k)} \in B_p(\boldsymbol{x_o}, R) をランダムサンプリング
  5.  \ \ \ \ \ \ \ \ back propagation で  b_{ik} \leftarrow ||\nabla g(\boldsymbol{x}^{(i,k)})||_q
  6.  \ \ \ \ end
  7.  \ \ \ \ S \leftarrow S \cup \{\max_k\{b_{ik}\}\}
  8. end
  9.  \hat{a}_W \leftarrow  S 上で逆ワイブル分布の location parameter を最尤法で推定.
  10.  \mu \leftarrow \min (\frac{g(\boldsymbol{x_o})}{\hat{a}})


また, Untargeted Attack に対応するアルゴリズムは, 上記の Targeted Attack に対応するアルゴリズムを用いて下記のようにかけます.

Algorithm 2: CLEVER-u of [T. W. Weng et. al., 2018]
入力:  K クラス分類器  f(x) , クラスが c と予測されるデータ点  \boldsymbol{x_o}, バッチサイズ  N_b, バッチ一回あたりのサンプリング数  N_s, ノイズのノルム  p, 最大ノイズ  R
出力: Untarget Attack に対応するCLEVER スコア  \nu \in \mathbb{R}_+

  1.  S \in \{\emptyset\}, g(\boldsymbol{x}) \leftarrow f_c(\boldsymbol{x}) - f_j(\boldsymbol{x}), q \leftarrow \frac{p}{p-1}
  2. for  j \leftarrow 1 to  K, j \neq c do
  3.  \ \ \ \ \mu_j \leftarrow \text{CLEVER}(f, \boldsymbol{x}, c, j, N_b, N_s, p, R)
  4. end
  5.  \nu \leftarrow \min_j \{ \mu_j\}

おわりに

今回は CLEVER について説明をしました. この手法は, 一般的な NN や CNN に対して適応可能な点で, それ以前の手法よりも大きく研究を進めた手法です. [T. W. Weng et. al., 2018] のなかでは, 実際にMLP (Multi Layer Perceptron), CNN (Convolutional Neural Network) などについて頑健性の評価を行う実験を行なっています. (より具体的なモデルとして, ResNet, Inception, MobileNet なども評価されています.) しかし, この手法にも欠点があり, それは RNN 系のモデルに対する頑健性の評価をできない点です. そこで, 次回は RNN 系のモデルに対しても頑健性の測定が可能となった最新の手法について紹介します.

今回も読んでくださりありがとうございました. 是非次回もお楽しみに!

*1:M. Hein, and M. Andriushchenko, "Formal guarantees on therobustness of a classifier against adversarial manipulation," in NIPS, 2017.

*2:T. W. Weng, H. Zhang, P. Y. Chen, J. Yi, D. Su, Y. Gao, C. J. Hsieh, and L. Daniel, "EVALUATING THE ROBUSTNESS OF NEURAL NET- WORKS: AN EXTREME VALUE THEORY APPROACH," in ICLR, 2018.

© Sansan, Inc.