Universal adversarial perturbations を読んでみた

Universal adversarial perturbations　の論文について読んだので，少しまとめてみます．　ついでにこの分野（perturbation）の論文を読むのはこれが初めて．

アーカイブのリンク→ https://arxiv.org/pdf/1610.08401.pdf

# perturbation(パタベイション，パータベイション)　とは？
perturbationsは日本語に直訳すると，「摂動」になります．何かのノイズになりうる，微小な擾乱の事でしょうか． 日本語の記事を書かれている方は「Adversarial perturbations」のことを「敵対的摂動」とか言う風に訳してることが多いみたいです．　

# 画像認識分野におけるperturbationとは？

この論文の画像ではないですが，有名なパンダの画像を載せます．何を示しているのかというと，右も左も人間の目には，パンダの画像にしか見えませんが，　実は右側のパンダの画像（左の画像＋ノイズ）は人工知能というかニューラルネットには全く別物に見えてしまう　ということを意味しています．
![スクリーンショット 2018-05-02 14.38.09.png](https://qiita-image-store.s3.amazonaws.com/0/205922/93ad2031-bdd0-d104-4848-6e3bfea49dbd.png)
　　　　　　　　　[https://arxiv.org/pdf/1412.6572.pdf](https://arxiv.org/pdf/1412.6572.pdf)から引用

右側の画像のキャプションに書いてある「gibbon」とはテナガザルのことです．我々人間にはパンダにしか見えませんが，ニューラルネットにはテナガザルだと判断されてしまうのですから，面白いものです．

これを応用すれば人工知能をハッキングして，人間を敵とみなすようにして反逆させることもできるわけですね！　

しかし逆を言えば，上記の例のようにニューラルネットの判断を狂わせることができるのですから，「危険因子の人工知能」の対「人工知能」　を作ることもできるわけです．そんなSFチックな世界感が頭をよぎったのでこの論文を読んでみることにしました．


話はそれましたが，「perturbation」は元の画像に加えられるノイズのことです．**上の画像の中央のやつ**ですね．
この画像ではわかりづらいですが，元画像によってはperturbationが加えられたのがなんとなくわかるものもあります．ノイズが加えられ若干カラフルになっているような，なっていないような感じです．下の画像をみてもらうとわかるかと思います．

![スクリーンショット 2018-05-02 14.50.27.png](https://qiita-image-store.s3.amazonaws.com/0/205922/ac77b825-4512-ce86-b325-3ae55f0ca179.png)![スクリーンショット 2018-05-02 14.50.32.png](https://qiita-image-store.s3.amazonaws.com/0/205922/9adee4b0-6aec-661b-5682-0e16de545286.png)
[https://www.cv-foundation.org/openaccess/content_cvpr_2016/papers/Moosavi-Dezfooli_DeepFool_A_Simple_CVPR_2016_paper.pdf](https://www.cv-foundation.org/openaccess/content_cvpr_2016/papers/Moosavi-Dezfooli_DeepFool_A_Simple_CVPR_2016_paper.pdf)から引用


右側の鯨の画像の**海の部分**とかみてみると，荒いノイズが入っているのがわかると思います．ただこれは，「ノイズが入っている」という先入観がある状態で見ているので気づけるのであって，おそらく言われなかったら「多少画像が荒い，鯨の画像」と我々は判断してしまうと思います．

# Universal adversarial perturbations 

ここからが本論文の本題になります．先行研究がすでに10本くらい？あって，全部遡るのは大変なので，前提の知識は結構省きます．

## Universalとは？

この論文で幾度となく出てくる「Universal」は  
・　あらゆる画像に適用可能な，悪い意味で汎用性のあるノイズ
・　どんなニューラルネットのアーキテクチャに対しても適用可能なノイズ

上記の２点の意味で使用しています．そしてこれを「doubly universal」と本論文で記述していました．


単純に考えて怖いです，　一個ノイズを作って，それを世界中にばらまけば，狂った人工知能がいつでも作れる可能性があるわけです．

## Universal perturbations
まとめると　二つの制約条件下で解く最適化問題です．

1. $||v_p|| \leq \xi $
2. $ {\bf P}_{x\sim\mu}( \hat k(x+v)\neq \hat k(x)) \geq 1-\delta $

条件1は摂動が大きくならないように，なるべく小さくなるように範囲を指定する条件．条件2はノイズが一定以上の誤認識を引き起こすための条件です．ノイズがあっても「誤認識」されなければperturbationの意味がありませんからね．

要するに，$\xi$と$\delta$　を最小化するアルゴリズムを解くことになります．　こうすると難しくないように聞こえますし，実際にアルゴリズムをみると確かに複雑なことはしていないことがわかります．

![スクリーンショット 2018-05-02 15.38.07.png](https://qiita-image-store.s3.amazonaws.com/0/205922/60cf7af5-dd3a-4b19-ccce-6799b09f2364.png)

以下ではこのアルゴリズムの詳細について述べていきます．

## Universal Perturbations Algorithm

ここで文字の定義について確認しておきましょう．

・ $v$: perturbationベクトル（摂動ベクトル），我々が最終的に得たいものです．
・ $\xi$: perturbationベクトルの大きさ，これはハイパーパラメータです．これをめちゃくちゃ小さくすれば，摂動もその分小さくなります．と思ったのですが，結局誤認識されるまでアルゴリズムを繰り返すので最終的な摂動の大きさは変わらないのでは？と思います．　もしかしたら，これは各ステップで加える摂動の大きさを意味しているのかもしれません．だとすると，これが大きすぎても小さすぎてもダメなことになります．
・ $\mu$: データ（画像のピクセル）をサンプリングする確率分布
・ $\hat{k}(x)$： データxにおける分類ラベル 

## アルゴリズム

1. データポイントX(ピクセルの輝度値が入っている配列)，分類ラベル$\hat{k}$,摂動がある状態での精度$\delta$（ハイパーパラメータ）,perturbation$\xi$のノルム$l_p$ を入力とします．
2. Universal Perturbation vector $v$ を出力します．（最適化するもの）
3. $v = 0$ として初期化します
4. 各データポイント（各ピクセル）において，$\hat{k}(x_i+v)=\hat{k}(x_i)$の時，領域$R_1$の境界までの最小のperturbationを求める． 要するに識別境界までの最短のベクトルです．
5. $\Delta{v_i}$が求まった後に， ${\bf P}_{x,\xi}(v+\Delta{vi})$ → $v$ として更新します．ここでやっていることは識別境界までのベクトルを可能な限り保ちつつ，Lp-normを制限以下にしています．
6. 4，５の作業を全てのピクセルに対して行います．
7. 各ピクセルに対して，指定の誤認識率になるまで繰り返す．（while文）

ここまでさらっとアルゴリズムについて述べましたが，これだと全然理解できないので，もう少し深めてみようと思います．

## 指定の誤認識率とは？　

上のフローの7で述べられている「指定の誤認識率」は，論文では以下のように定式化されています．

$$
\mathrm{Err}(X_v) :=\frac{1}{m}\sum_{i=1}^m 1_{\hat{k}(x_i+v_i)\neq\hat{k}(x_i)} \geq 1 - \delta 
$$

大まかにいうと，これは画像のピクセルあたりの誤認識率を意味しています（mはピクセル数）．各ピクセルに対して，誤認識されるかどうかを判定し，誤認識される時に，1を足していきそれを全ピクセルに対して繰り返し，最終的に平均をとり，それを一枚の画像の誤認識率としているようです．

δは誤認識率なので，これが小さいほど，$\hat{k}(x_i+v_i)\neq\hat{k}(x_i)$の回数を多くすることがきます．要するに，$v_i$を加えた後の領域において，$v_i$を加える前とラベルが異なるものとして扱う回数も多くするということです．

そして当然毎回異なるラベルとして認識されるわけでなく，$x$に$v_i$が加えられても同じラベルと認識される場合があり，その時だけフローの4と5を計算することになります．

## 識別境界への最短のベクトルとは？

アルゴリズムの中に，$r$が出て来きていますが，これは本論文では一切論じられておらず先行研究の論文で触れらています．　→ [https://www.cv-foundation.org/openaccess/content_cvpr_2016/papers/Moosavi-Dezfooli_DeepFool_A_Simple_CVPR_2016_paper.pdf](https://www.cv-foundation.org/openaccess/content_cvpr_2016/papers/Moosavi-Dezfooli_DeepFool_A_Simple_CVPR_2016_paper.pdf)

「識別境界への最短ベクトル」について理解するには，おそらく上記の論文に出てくる$r$とアルゴリズムを知っておく必要があるので，以下ではその内容を踏まえながら，識別境界への最短ベクトルについて記述していきます．

![スクリーンショット 2018-05-04 16.18.39.png](https://qiita-image-store.s3.amazonaws.com/0/205922/6185466f-5615-f561-10f1-1a43fbc122d4.png)
　　　　　　　　[https://arxiv.org/pdf/1511.04599.pdf](https://arxiv.org/pdf/1511.04599.pdf)から引用

境界はラベルが変化するところかつ，2次元だとアフィン変換で表現できるので

$$
\begin{equation}
f(x) = 0  \leftrightarrow f(x) = W^Tx + b
\tag{1}
\end{equation}
$$

という式になります．　この論文の式4にある条件

$$
f(x_i) + \nabla f(x_i)^Tr_i = 0
$$
を使用して，rについて解くと，

$$
\begin{eqnarray}
r_i = - \frac{f(\bf x_i)}{||\nabla f(\bf x_i)||^2_2} \nabla f(\bf{x}_i)
\tag{2}
\end{eqnarray}
$$

識別境界の式(1)より，
$$
\nabla f(x_i) = \bf W
\tag{3}
$$

式(3)を(2)に代入すれば，

$$
r_i = - \frac{f(\bf x_0)}{||\bf W||^2_2}) \bf W
$$

となり，[論文中](https://arxiv.org/pdf/1511.04599.pdf)の式(3)(上の式(3)ではないです．)が導出できます．

ついでにベクトルの下付きの文字が意味しているのはノルムの次元です．今は$L_2$ノルムなのでユークリッド距離におけるベクトルの2乗，すなわちベクトルの成分の和を意味しています．

この$r$についてこれ以上深掘りするのは他の人に任せます(笑)．とりあえず論文中（参考文献ではなく本項で述べている[Universal adversarial perturbationsの方](https://arxiv.org/pdf/1610.08401.pdf)）の$r$が何を意味しているのかなんとなくわかったところで先に進もうと思いますが，疲れたので一回終わり．











## 本記事の参考文献
https://arxiv.org/pdf/1610.08401.pdf
https://arxiv.org/pdf/1511.04599.pdf
https://speakerdeck.com/diracdiego/universal-adversarial-perturbations
https://arxiv.org/pdf/1412.6572.pdf
https://www.cv-foundation.org/openaccess/content_cvpr_2016/papers/Moosavi-Dezfooli_DeepFool_A_Simple_CVPR_2016_paper.pdf