Obey Your MATHEMATICS.

機械学習関連の純粋数学や実験など

損失関数はそれほど複雑な関数ではないのかも?と言う話

前回の記事

mathetake.hatenablog.com


にある論文(2-2-9)[1605.07110] Deep Learning without Poor Local Minimaについてのお話です*1


Abstractを読んだ瞬間に、こんな重要な論文をどうして今まで知らなかったのかと言うぐらい興奮しました。

少し長いですが引用しますと

In this paper, we prove a conjecture published in 1989 and also partially address an open problem announced at the Conference on Learning Theory (COLT) 2015. With no unrealistic assumption, we first prove the following statements for the squared loss function of deep linear neural networks with any depth and any widths: 1) the function is non-convex and non-concave, 2) every local minimum is a global minimum, 3) every critical point that is not a global minimum is a saddle point, and 4) there exist "bad" saddle points (where the Hessian has no negative eigenvalue) for the deeper networks (with more than three layers), whereas there is no bad saddle point for the shallow networks (with three layers). Moreover, for deep nonlinear neural networks, we prove the same four statements via a reduction to a deep linear model under the independence assumption adopted from recent work.*2

と言った具合です。

要するに誤解を恐れず言えばある種の仮定の下、モデルの構成(ハイパーパラメータ)に依らず

−線形ニューラルネットワーク極値を全て分類しました。極小値は全部大域最小値です。

非線形(ActivationがReLU関数の場合)のニューラルネットワーク極値を全て分類しました。極小値は全部大域最小値です。


と言うものです。仮定はともあれ、この主張ヤバすぎませんか?かなり強い主張です。


証明に使われている仮定が、実際の現場で使われるセッティングに対してPlausibleであるならば、現時点でこれ以上に分かりやすく「Deep Learningの学習が何故上手くいくのか」を簡単に説明するものはないように思われます。

と言う事で、簡単にこの論文のMain TheoremのStatementとSettingそしてそのPlausibilityについて考えてみたいと思います。

§1. Notationの準備

定理について述べる前にNotationを準備します。*3


{ H }隠れ層の数
{ (d_x,d_1,...,d_H,d_y) }(入力層,第一隠れ層,第二隠れ層,...,第{ H }隠れ層,出力層)の次元
{ p:= \min (d_1,\dots,d_H) }
{ m }トレーニングセットの総数
{ (X,Y) \in \mathbb{R}^{d_x \times m} \times  \mathbb{R}^{d_y \times m}}トレーニングセット
{ W_{1} \in \mathbb{R}^{d_1 \times d_x} }, { W_{2}\in \mathbb{R}^{d_2 \times d_1} },....,{ W_{H} \in \mathbb{R}^{d_H \times d_{H-1}} }, { W_{H+1}\in  \mathbb{R}^{d_y \times d_H} }:各Weight Matrix

と言う記号を準備します。

線形ネットワークのアウトプット

{ Y_{linear}(W,X) :=W_{H+1}\circ W_H\circ \cdots W_1(X)  \in \mathbb{R}^{d_y \times m}}

として表記します。そして損失関数*4

{ \mathcal{L}_{linear}(W) := \|Y_{linear}(W,X) - Y \|^2_{Frobenius} }

と定めます。ここで{ \| \cdot \|_{Frobenius} }は行列のFrobeniusノルムです。*5

§2. 線形ネットワークの場合

準備ができたので、線形ネットワークに関してのStatement を述べたいと思います。

Theorem 2.3 in [1])
{ XX^T,XY^T }full rankの行列であると仮定(※)する。この時線形ネットワークの損失関数{ \mathcal{L}_{linear}(W )}について次の主張が成立する。
(1) { \mathcal{L}_{linear}(W )}はnon-convexかつnon-concaveである。
(2) { \mathcal{L}_{linear}(W )}の全ての極小値は大域最小値。
(3){ \mathcal{L}_{linear}(W )}の全ての極小でない極値は鞍点である。
(4)もし{ p=rank(W_H\cdots W_2)}ならば{ \mathcal{L}_{linear}(W )}極値におけるHessianは必ず負の固有値を持つ。□

と言うものです。歴史的な背景として1989年にBaldi & Hornik [2]が、”{H=1 }かつ次元に対するある条件”といったかなり限定的な場合に証明を与えていて、その論文の中で””同様の主張が任意の深さについて成り立つ””と言う予想を述べていたらしいです。*6

仮定(※)の妥当性については[2]にある次のコメントのように実用的にもPlausibleです;

To assume that they are all strictly positive is equivalent to assuming that both  { \Sigma_{XX}} and  {\Sigma_{YX} } are of full rank. Full rank matrices are dense and in a realistic environment with noise and finite precision, we can always slightly perturb the conditions so as to make I invertible and eigenvalues.*7

要するにこの仮定を満たす行列は、行列の成すベクトル空間の中で稠密*8なので、ちょっとの摂動でこの仮定は満たされるので問題ないと言うことです。

これはもう文句なし、と言う感じで言葉が出ないくらい凄い結果だと思います。約25年の未解決問題を解決したわけですから。

凄い!*9

§3. 非線形ネットワークの場合

非線形の場合についても、同様の仮定の下で同様の主張が成り立ってくれたら嬉しいのですが…そう簡単にもいかないみたいです。

[1]はスピングラスモデルのアナロジーで損失関数を解析した論文[3]のアイディアを拡張し、Roughly Speakingで以下のような主張を証明しました。

まず線形の場合と同様に

{ Y_{nonlinear}(W,X) :=W_{H+1}\circ \sigma \circ W_H\circ \cdots \circ \sigma \circ W_1(X)  \in \mathbb{R}^{d_y \times m}}
{ \mathcal{L}_{nonlinear}(W) := \|Y_{nonlinear}(W,X) - Y \|^2_{Frobenius} }

非線形ネットワークのアウトプットと損失関数とします。

ここで重要な仮定(※※)として、

ReLU関数{ \sigma }によるActivationはベルヌーイ分布に従って起こるものとし、その分布は【素子の位置】【Weight】【入力】に対して独立である

と仮定します。

Corollary3.2 in [1]
仮定(※)&(※※)が成立している時、{ \mathcal{L}_{nonlinear}(W) }{ \sigma }に関する期待値を取った関数に対してTheorem2.3と同様の性質が成り立つ。□


と言うものです。証明は結局期待値取ると線形な損失関数の定数倍になるので、Theorem2.3より従います。

やはり線形の場合のようにすんなりと証明は出来ないみたいです、が、これはこれで…!


非線形の場合の損失関数の挙動はもっと良く調べられるべき課題ですが、全容解明の日も近いかも…?

*1:著者はMITにいる日本人PhD学生!凄い!

*2:[1605.07110] Deep Learning without Poor Local Minima

*3:[1]§2.1 参照。ほんの少しだけ記号変えてます。

*4:通常算術平均を取って誤差二乗平均にしますが、定数倍で極値の挙動は不変なので問題ありません。

*5:elementごとに内積入れたやつです。

*6:[1] §2.2参照

*7:[2] p 56.上の方

*8: 位相空間の中にある集合の閉包がその空間全体に一致する時、その集合は稠密であると言います。{\mathbb{R} }の中の有理数全体{ \mathbb{Q} }なんかが代表例です。

*9:証明は、ひたすら計算と言う感じでした。読むには相当根気が入りそうです…。