論文概要

  • タイトル

    Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming

  • 概要

    小さなノイズを加えることでニューラルネットワーク(NN)の画像判別精度が落ちることが報告されており、NNが与えられた時にその頑強性を確かめる手法は重要である。ここでいう頑強性とはある入力に対してNNの出力をとした時にの近傍の像がの近傍に含まれているということである。この論文ではより一般的な以下の問題を考える。入力空間上の集合(input certainly set) と出力空間上の集合(safety specification set) が与えられた時にを満たすかどうかの判別問題を考える。論文ではとして次元区間を扱い、として二次制約で表現されるものを扱う。また、写像としては 活性化関数(全層で共通で最終層は無し)を含んだ多層全結合層ネットワークにによって表現される多変量ベクトル値関数を考える。活性化関数を二次制約で上手く近似することで、あるLMN(linear matrix inequality) の解が存在すればが満たすことを示している(逆は成立しないことに注意)

    ※二次制約で表される集合としてはelipsoid(楕円体)、polytopes(多面体)、 zonotopes

    ellipsoidsの標準形についてのメモ)

  • 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)

論文中のTheorem1 Appendix A.4

(補足)

行列がそれぞれ(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] 参考資料

今後の展開:

区間と領域が与えられた時にを満たすニューラルネットを求める。

Last modified by akirat1993 2019-12-13 21:00:53
Created by akirat1993 2019-11-27 20:07:47

results matching ""

    No results matching ""