敌対的学习に対するラデマッハ复雑度
?
1 like?1,865 views
Yin, Ramchandran, and Bartlett, Rademacher Complexity for Adversarially Robust Generalization, ICML 2019
![（復習）経験ラデマッハ複雑度
n 任意の関数クラス? ? ? ?に対して，サイズ?のサンプル? = ?;, ?V, … , ?: を所与とすると，経
験ラデマッハ複雑度は以下のように定義される：
? ? ? ?
1
?
sup
]∈?
^
=>;
:
?=?(?=)
ここで，?;, … , ?:はi.i.d.なラデマッハ確率変数であり，? ?= = 1 = ? ?= = ?1 =
;
V
である．
n 直観的な解釈：
? 2値判別で判別器sign ? ?= を用いて?=のラベル?= ∈ +1, ?1 を予測することを考える.
? ?= ? ?= > 0なら予測は正しい．
? ?= ? ?= が大きな値をとるとき，? ∈ ?によってデータ(?=, ?=)が十分によく学習されていると考
えることができる．
n ラデマッハ複雑度は仮設集合?の複雑さを測ることに使える．
3](https://image.slidesharecdn.com/rademacherforarg-190928144700/85/-3-320.jpg)
![ニューラル?ネットワーク
n ReLU活性化関数のもとでのFeed forward型ニューラルネットワークを考える．
n 仮説クラス?のそれぞれの関数?が行列の列? = ?;, ?V, … , ?v でパラメタライズされて
いるとする．すなわち， ? ≡ ?x．
? ?] ∈ ?$y×$yz{．
? ? ? : ReLU関数．すなわち，? ∈ ?に対して，? ? = max ?, 0 .
n 以上のノーテーションのもとで関数は以下のように表される．
? Kクラス多値分類の場合は?x ? : ?$ → ??.
? 二値分類の場合は特別に?x ? : ?$ → ?.
損失関数は，? ?x ? , ? = ? ??x ? .
ただし，?は??リプシッツ連続な関数?: ? → 0, ? .
8](https://image.slidesharecdn.com/rademacherforarg-190928144700/85/-8-320.jpg)
![攻撃のない?値NNのラデマッハ複雑度
n 二値分類を考える．
? ? = ?=, ?= =>;
:
∈ ?× ?1, +1 :をi.i.d.な訓練データとする．
? ? ? ?;, ?V, ? , ?: ∈ ?$×:
? ???? = max ?, ?;, ?V, … , ?v
Theorem 5. 以下のニューラルネットワークを用いた仮説クラスを考える．
? = ?x ? : ? = ?;, ?V, … , ?v , ?] ‰ ≤ ?], ?]
?
V,;
≤ ?], ? ∈ ? ? ? ?
このとき，
10](https://image.slidesharecdn.com/rademacherforarg-190928144700/85/-10-320.jpg)
敌対的学习に対するラデマッハ复雑度
- 1. Rademacher Complexity for Adversarially Robust Generalization Yin, Ramchandran, and Bartlett Masahiro Kato Sept. 27th, 2019 @Bread Seminar ※論文の線形モデルに関する部分は省略します． ※若干慌てて作ったので間違っているかもしれません 1
- 2. 問題設定 n 特徴空間：? ? ?$. n ラベル空間：?. n ?×?上の未知の分布：?. n 仮説クラス：? ? ? ?． ? ?は?から?の関数を表し，?は?と異なっていてもよい． n 損失関数：?: ?×? → 0, ? . n 母集団リスク：? ? ? ? 5,6 ∈? ? ? ? , ? . n 経験リスク：?: ? ? ; : ∑=>; : ? ? ?= , ?= . n 攻撃は??ノルムに限定．?の?近傍を?5 ? ? で表す． ? ?CDE ? ? arg max 5K∈?L M N ? ? ?O , ? . 2
- 3. （復習）経験ラデマッハ複雑度 n 任意の関数クラス? ? ? ?に対して，サイズ?のサンプル? = ?;, ?V, … , ?: を所与とすると，経 験ラデマッハ複雑度は以下のように定義される： ? ? ? ? 1 ? sup ]∈? ^ =>; : ?=?(?=) ここで，?;, … , ?:はi.i.d.なラデマッハ確率変数であり，? ?= = 1 = ? ?= = ?1 = ; V である． n 直観的な解釈： ? 2値判別で判別器sign ? ?= を用いて?=のラベル?= ∈ +1, ?1 を予測することを考える. ? ?= ? ?= > 0なら予測は正しい． ? ?= ? ?= が大きな値をとるとき，? ∈ ?によってデータ(?=, ?=)が十分によく学習されていると考 えることができる． n ラデマッハ複雑度は仮設集合?の複雑さを測ることに使える． 3
- 4. （復習）経験リスクの収束率 n 一様大数の法則について説明する． Theorem 1. 損失? ? ? , ? の範囲を 0, ? とする．任意の? ∈ 0,1 に対して少なくとも確率 1 ? ?で，全ての関数? ∈ ?に対して，以下が成り立つ． ? ? ≤ ?: ? + 2?? ? ?? + 3? log 2 ? 2? . 4
- 5. 敵対的学習の設定への拡張 n この論文では??ノルムの敵対的攻撃に限定する． n 学習モデルは?個の確率分布?からi.i.d.に引かれたサンプルへのアクセスを有している． n 学習が終わった後に学習によって得られた関数?が敵対者に明かされる． n 敵対者は損失を最大化できるように??ノルムで抑えられる球の範囲内でサンプル?に摂 動を加えることができる． n 学習の目標は以下の敵対的母集団リスクを最小化することである． q? ? ? ? 5,6 ～? max 5K∈?L M N ? ?(?O , ?) . 5
- 6. 敵対的学習 n 敵対的母集団リスクを最小化する自然な方法として以下の経験敵対的母集団リスクを最 小化する方法が考えられる． q?: ? ? 1 ? ^ =>; : max 5s K ?Ls M N ? ? ?= O , ?= . このリスクの最小化は敵対的学習と呼ばれている． n 敵対的損失：q? ? ? , ? ? max ?L M N ? ? ? , ? n 敵対的損失の関数クラスq?? ? 0, ? ?×?：q?? ? q? ? ? , ? ∶ ? ∈ ? . n q? ?(? , ?)の範囲は 0, ? のままなので，次の結果を得ることができる． 6
- 7. 敵対的学習の汎化誤差上界 n 敵対的母集団損失q? ?(? , ?)の範囲は 0, ? のままなので，母集団リスクのラデマッハ複雑 度の議論を適用して以下の系を用いることができる． Corollary 1. 任意の? ∈ 0,1 に対して，少なくとも確率1 ? ?で全ての関数? ∈ ?に対して， 以下が成り立つ． q? ? ≤ q?: ? + 2?? ? q?? + 3? log 2 ? 2? . したがって，ラデマッハ複雑度は敵対的学習においても汎化誤差の上界の導出に役立つ． 7
- 8. ニューラル?ネットワーク n ReLU活性化関数のもとでのFeed forward型ニューラルネットワークを考える． n 仮説クラス?のそれぞれの関数?が行列の列? = ?;, ?V, … , ?v でパラメタライズされて いるとする．すなわち， ? ≡ ?x． ? ?] ∈ ?$y×$yz{． ? ? ? : ReLU関数．すなわち，? ∈ ?に対して，? ? = max ?, 0 . n 以上のノーテーションのもとで関数は以下のように表される． ? Kクラス多値分類の場合は?x ? : ?$ → ??. ? 二値分類の場合は特別に?x ? : ?$ → ?. 損失関数は，? ?x ? , ? = ? ??x ? . ただし，?は??リプシッツ連続な関数?: ? → 0, ? . 8
- 10. 攻撃のない?値NNのラデマッハ複雑度 n 二値分類を考える． ? ? = ?=, ?= =>; : ∈ ?× ?1, +1 :をi.i.d.な訓練データとする． ? ? ? ?;, ?V, ? , ?: ∈ ?$×: ? ???? = max ?, ?;, ?V, … , ?v Theorem 5. 以下のニューラルネットワークを用いた仮説クラスを考える． ? = ?x ? : ? = ?;, ?V, … , ?v , ?] ‰ ≤ ?], ?] ? V,; ≤ ?], ? ∈ ? ? ? ? このとき， 10
- 11. 攻撃のある?値NNのラデマッハ複雑度 n 二値分類に対して， q? ?x ? , ? = max 5K∈?L M(N) ? ?x ?O , ? = ? min 5K∈?L M(N) ??x(?O) , かつ，?(?)はリプシッツ連続であるので，以下の関数クラスを考える． n この時，以下のラデマッハ複雑度の下界が得られる． Theorem 6. 定数? > 0に対して， ? ? q? ≥ ?? 1 ? ? ? + ? ? ? . n 攻撃のない時にlog ?で抑えられたものの下界が ?になる． 11
- 12. NNの汎化誤差上界を得る難しさ n ニューラルネットワークに対しては，例えその隠れ層が一層しかなくても，特定のデー タ点(?, ?)の，敵対的損失q? ?x(? , ?) = max 5K∈?L M N ? ?x(?O , ?)を計算することは困難． n 近年の研究では，多項式時間で計算できるq? ?x(? , ?)の上界の発見が行われている． その結果に基づいて，q? ?x(? , ?)を代理敵対的損失‘? ?x ? , ? で置き換える． ? ‘? ?x ? , ? ≥ q? ?x(? , ?) ??, ?, ?. n 代理敵対的損失の上界が意味のあるものであるためには，代理敵対的損失自体が敵対的 損失に十分近いものでなければならない． ? 代理的損失の例：SDP緩和とLP緩和 n 代理損失を用いた時の汎化誤差上界を抑えなくてはならない． 12
- 13. 変動のバウンド n Kクラス分類ReLU活性化関数一層隠れ層NNのSDP緩和代理損失の性質を考える． ? ?x ? = ?V ?(?; ?). ? ?Vの?番目の列を?V,?とする． n Raghunathan et al. (2018)より以下の結果が得られる． Theorem 7. For any (?, ?), ?;, ?V, and ?O ≠ ?, where ? ?, ? ? 13
- 14. Certified Defense n ネットワークとテストデータを所与として，エラーがある一定の値を超える攻撃が存在 しないことを保証するための半正定値緩和に基づく手法． n 敵対的学習は損失の最悪時の下界を最小化するものと考えることができる． n 実際には最悪時（敵対的サンプル）を正しく計算できる訳ではないので，評価がゆるく なったりする． n ニューラルネットワークを用いた時の損失の最悪時の上界の計算を行うことで，下界が 不正確になることや，敵対的サンプルの正確な計算などに伴う問題を回避できる． n この上界により特定の攻撃を防ぐことを保証できるようになる． n 上界の計算にはNP困難な計算を伴う線形近似が必要になるが，この計算を半正定値 （SDP）緩和で近似する． 14
- 16. マージン損失の上界 n 敵対的学習における汎化のマージン損失のバウンドを導出する． Theorem 8. ニューラルネットワークに基づく以下の仮説のクラスを考える． 任意の? > 0に対して，少なくとも確率1 ? ?で，全ての?x ? ∈ ?に以下の関係が成り立つ． 16
- 17. 結論 n 敵対的環境下の損失の敵対的学習の汎化誤差をラデマッハ複雑度で抑えることができた． n ニューラルネットークのラデマッハ複雑度は，通常時には入力の次元の対数で抑えられ るが，敵対的学習のもとでは少なくとも次元の2乗根に比例する． n ニューラルネットワークでは，正確な敵対的サンプルを計算できないので，何らかの近 似が必要になる． n SDP緩和のもとでの代理損失の上界を出すことができた． 17
- 18. Reference n Yin, Ramchandran, and Bartlett, Rademacher Complexity for Adversarially Robust Generalization, ICML 2019. n Bartlett and Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, Journal of Machine Learning Research 2002. n Raghunathan, Steinhardt, and Liang, Certified Defenses against Adversarial Examples, ICLR 2018. n 金森敬文「統計的学習理論」2015年 18