論文概要
タイトル
概要
小さなノイズを加えることでニューラルネットワーク(NN)の画像判別精度が落ちることが報告されており、NNが与えられた時にその頑強性を確かめる手法は重要である。ここでいう頑強性とはある入力に対してNNの出力をとした時にの近傍の像がの近傍に含まれているということである。この論文ではより一般的な以下の問題を考える。入力空間上の集合(input certainly set) と出力空間上の集合(safety specification set) が与えられた時にを満たすかどうかの判別問題を考える。論文ではとして次元区間を扱い、として二次制約で表現されるものを扱う。また、写像としては 活性化関数(全層で共通で最終層は無し)を含んだ多層全結合層ネットワークにによって表現される多変量ベクトル値関数を考える。活性化関数を二次制約で上手く近似することで、あるLMN(linear matrix inequality) の解が存在すればが満たすことを示している(逆は成立しないことに注意)
※二次制約で表される集合としてはelipsoid(楕円体)、polytopes(多面体)、 zonotopes
Contribution(実験結果)
実験環境
- 5-coreでRAMが8GBの個人PCを使用
- SDPのソルバーとしてMOSEK with CVXを使用
実験結果
層数が多くなると非線形関数の影響で既存手法(2018年)では像の近似が上手くいかないが、提案手法ではある程度tightに近似できている(Figure 5)。層でもニューロン数が多くなると近似精度が悪くなる(Figure 6)。定義域が広いと近似精度が悪くなる(Figure 7)。1層における計算速度やメモリ使用量においても既存手法を大幅に上回っている(table 1)
問題のサイズ LMN(linear matrix inequality) feasible problemの変数の数は入力次元を、活性化関数の出力次元をとするととなるので入力を画像等にしてCNNなどに適応することで大規模計算を行うことが出来ると考えられる。(実験ではやなどtoyモデルで行っている)
気になっていること
- CNNへの拡張
論文の読み方のTips
メインの定理がTheorem1でそれを多層に拡張したのがTheorem2となっている。その他のPropositionやLemmaはTheorem1を具体的な問題で用いるための補足定理となっている。その為、Theorem1を読んで概要を掴んでから興味があるLemmaやPropositionを読んでいけば良いと思います。
その他
- 凸関数や微積分の勉強としてLem2の補足やProp2の補足>(f)は読むと良いと思います。
- 論文に記載されている証明は全て簡単な行列計算です。
論文の構成
Theorem 1
単層全結合NNにおいて問題をLMN(linear matrix inequality) に変換する為の重要な定理
Theorem 2
Theorem 1を多層全結合NNに拡張した定理
Proposition 1
Theorem 1においてとして次元区間を用いるための命題
Lemma1
Theorem 1においてslope-restricted(論文内で定義)である活性化関数を用いるための補題
Lemma2
多変数ベクトル値関数がslope-restrictedである事を証明するのを手助けする定理の紹介
Proposition2
活性化関数でよく使われる関数ReLU, sigmoid, tanh, leaky ReLU, exponential linear function, softmax functionがslope-restrictedであることを紹介
Lemma 3
Theorem 1を活性化関数ReLUに適応するための補題
論文の重要な定理と解釈
0.1. Theorem 1(SDP for one layer)
Consider a one-layer neural network described by the equations
where and .
Given an input uncertainty set and , consider the following matrix inequality:
where such that
If the above inequality is feasible for some which satisfy
We have
Moreover if we define
we can conclude that
(proof)
(補足)
行列がそれぞれ(1)、(2)を満たすことを確かめるのが現実的には難しいのでProposition1やLemma1などを使っての探索範囲を前もって(1)、(2)を満たすところに絞って計算を行うことがポイント
(解釈)
上記の証明から定理を自分なりに解釈
を含むような2次制約で表される領域(によって表現されている)と非線形関数の入力と出力に関するtightな2次制約(によって表現される)を与えることができ、それらを用いて表現されるの近似がに十分含まれているならと評価できる。
この事を示してみる。定理を満たしているとが存在したとする。この時、 と定義するとの定義から(はを含むような二次制約)
また、を、をと定義するとと表現できる。次にを評価する。 と定義した時にを以下で評価する。 この時の定義よりである。
最後にを評価するを以下のように定義する。
まず、任意のに対して と定義する。
また、任意のに対して 、と定義する。
不等式の右辺はの定義より正でないことから、であることは即座に分かる。
またというのは本来は入力に対しての像がに入るかチェックするところをそれより、狭いに入るか確認するためのものである。入力がによって定まる集合の境界付近にある時にはに近づくように大きくなる(についても同様)
以上の議論からであるかを以下のようにチェックしていると考えられる。
を満たすが存在したら であるのでが確かめられる。
論文の証明の補足
0.2. Prop1の補足
Given, and , the hyper rectangle satisfies the quadratic constraint defined by
which means that ,
(Proof)
0.3. Def3の補足
Definition3 (slope-restricted nonlinearity)
A nonlinear function is slope-restricted on () if for any , one has
If it is equivalent to this inequality
(proof)
(上) →(下)
である時は であることに注意すると示せる。の場合も同様に示す。
(下)→(上)は定義通りすれば示せる。
論文の対象としているNN
- 同一の層であれば各ニューロンに対して同じ活性化関数が使われている
- The activation value might be bounded from below or above (e.g., the ReLU)
0.4. Lem1の補足
本文中の証明で という数式のはに訂正する必要あり
0.5. Lem2証明
Lemma2の証明は論文中では以下の論文を参照とあったが、探すことが出来なかったので他の資料を探して証明した.
まず定義
Def (slope-restricted nonlinearity)
A nonlinear function is slope-restricted on () if for any , one has
Def (-smooth)
We say that a continuously differentiable function is -smooth if the gradient is -Lipschitz, that is
Def (-strongly convex)
We say that is -strongly convex () if it satisfies the following sub gradient inequality:
Since , is convex
Lemma 2 (gradient of convex functions)
Consider a function that is -strongly convex and -smooth. Then the gradient function is slope-restricted in the sector .
(proof)
の時はこの定理を式変形することで示せる。の時はとなるのでが-smoothであることから示せる。
0.6. Prop2の補足
0.6.1. a
については であることとから示せる。
0.6.2. b
についてはででありは連続であることからはslope-restricted in the sectorであることが示される。詳細
0.6.3. c
についてはでありであるのででありは連続であることからslope-restricted in the sector.また、であるのでsector-bounded in the sector.
0.6.4. d
の場合にslope-restrictedは以下のように示せる。がそれぞれ以上かどうかで場合分けをする。一番厄介なの場合のみを示す。 他も同様。またであるのでsector-boundedである。
0.6.5. e
論文の主張は間違っているので訂正。 With の時はslope-restricted and sector-bounded in the sector である。論文ではのところがとなっているが誤りである。実際の時はを満たすが存在するのでとなり矛盾。slope-restricted and sector-boundedであることの証明は定義通りに確かめれば出来るので略。
0.6.6. f
がslope-restricted in the sector であることを示す。
と定義するとであるのでLemma2を用いることを考える。まず、が凸集合(つまり、-strongly convex)であることを示す。任意のと任意のに対してヘルダーの不等式を用いると、 であるので凸関数。
次にのリプシッツ定数が以下であることを示す。
ベクトル値関数のリプシッツ定数についての定理より、 が成立する。ここで、は行列およびベクトルに関するフロベニウスノルムを表し、はヤコビ行列を表す。つまり、の成分はを表す。この時、 であるので、 となる、この時に注意するとはの時に最大値をとる。そのことを背理法を用いて証明する。まずは有界閉集合であり、とノルムの連続性よりはコンパクトであるので最大値を持つ。今、の時にが最大値を取ったとする。この時、,と置き換えた方が値が大きくなるので最大値に矛盾する。なお、値が大きくなることは、以下の事実から分かる。 よって、はの時に最大値をとるのでのときはのリプシッツ定数がより小さいことが分かった。また、の場合はであるのでリプシッツ定数は1である。
Backup(執筆者のメモ)
0.6.7. indefinite matrix
- A symmetric matrix that is not positive semi-definite and not negative semi-definite is called indefinite
- Symmetric matrix is called indefinite if it has at least one positive eigenvalue and at least one negative eigenvalue.
Let be the class of univalent(単射) functions in the unit disk , normalized by the conditions and and given by We say that is starlike if and only if, for , and we denote the subclass of functions by .
We say that is convex if and only if, for , and we denote the subclass of functions by .
Then it is widely known that .
For any real number , denote by the class of alpha-convex, or so-called Ma-Minda functions defined for by the relationship [3] 参考資料
今後の展開:
区間と領域が与えられた時にを満たすニューラルネットを求める。