No bad local minima: Data independent training error guarantees for multilayer neural networks

今まで「3行で」コーナーやってたけど、「概要でよくね？」という気がしてきたし、なんとなく馬鹿らしくなってきたのでやめる。

"No local bad minima"というタイトル見た瞬間面白そうだと思ったので読もうと思った。

概要

ニューラルネットの学習誤差をネットワークの構造によって解析的に評価しようという内容。
凸最適化ならば勾配法で最適化できることが保証されるが、非凸最適化の場合は極小値にトラップしてしまい、最適な学習ができない可能性がある。
しかし、非凸な誤差関数でも学習誤差を抑えることができることを示している。
前提として誤差関数を勾配法で最小化する学習を想定しているので、誤差関数の微分可能な極小値(DLM; Differentiable Local Minimum)における解析を行う。
隠れ層1層の場合は意外とシンプルな解析で評価できるので、そのアナロジーで隠れ層の層数が一般の場合に拡張し、極小値における安定性を議論している。

隠れ層数が1の場合

f:id:levelfour:20160604160445p:plain

まず、教師データを $(x,y)$ 、第 $l$ 層の活性化要素を $a_l$ 、出力を $v_l$ 、全体の推定誤差を $e$ 、ニューラルネットの総層数を $L$ として以下のように定式化する。

$v_l=\mathrm{diag}({a_l})W_lv_{l-1}$
$e=v_L-y$

活性化関数は非線形の関数(シグモイド関数等)が用いられることもあるが、ここでは線形の関数およびその組合せで書ける関数(ReLU, max-pooling等)に限定する。このように制限すると、活性化の定式化を上記のように行列演算を用いて行うことができ、解析の都合上楽になる。
最近の結果では、特にCNN等複雑な構造になればなるほど、下手に非線形関数を活性化関数に用いるよりも、ReLUを用いた方が高精度な識別器が得られることが多い。

例えばReLUの場合、

$a_iu_i=u_i$ ( $u_i>0$ の場合)
$a_iu_i=0$ (otherwise)

を実現するには

$a_i=1$ ( $u_i>0$ の場合)
$a_i=0$ (otherwise)

で十分。

次に、誤差関数(MSEを用いる)の定式化は

$\displaystyle \mathrm{MSE}=\frac{1}{2}\mathbb{E}[e^2]=\frac{1}{2N}\sum_{i=1}^N(e^{(n)})^2=\frac{1}{2N}\|\boldsymbol{e}\|^2$

となる。ただし、 $N$ は訓練データ数である。

隠れ層数1としてMSEの式をもう少し整理すると

$\displaystyle \mathrm{MSE}=\frac{1}{2}\mathbb{E}\left[(y-W_2\mathrm{diag}(a_1)W_1x)^2\right]=\frac{1}{2}\mathbb{E}\left[(y-a_1^\mathrm{T}\mathrm{diag}(w_2)W_1x)^2\right]$

となる。活性化行列が対角成分しか持たないので、 $W_2$ もその対角成分 $w_2$ しか寄与しない。
ニューラルネットのパラメータ行列をまとめて $\tilde{W_1}=\mathrm{diag}(w_2)W_1$ と書くと、

$\displaystyle \mathrm{MSE}=\frac{1}{2}\mathbb{E}\left[(y-a_1^\mathrm{T}\tilde{W_1}x)^2\right]$

となる。シンプルな形になった。

さて、極小点ではパラメータ行列 $\tilde{W_1}$ に関する微分係数が0、すなわち

$\nabla\mathrm{MSE}=\mathbb{E}[ea_1x^\mathrm{T}]=0$

である。もう少し具体的に書き下すと、

$e^{(1)}a_1(x^{(1)})^\mathrm{T}+\cdots+e^{(N)}a_1(x^{(N)})^\mathrm{T}=0$

である。紛らわしいのだが、 $e$ や $x$ に関する上付き添字は個々の訓練データのインデックスである。

これをクロネッカー積*1を用いて次のような行列 $G_1$ を定義する。
（余談だが、クロネッカー積という単語を見たときはじめはクロネッカーのデルタと関係があるのかと思ったが、想像以上に関係無かった。テンソル積の行列だった。詳細はWikipediaを参照されたい）

$\displaystyle G_1=[a_1\otimes x^{(1)},\cdots,a_1\otimes x^{(N)}]$

すると、極値条件はシンプルに記述できる。

$G_1\boldsymbol{e}=0$

ややこしく見えるが、先程の極値条件を成分ごとに分解し、「各成分=0」という条件式を並べたのが最後の $G_1\boldsymbol{e}=0$ になる。

さて、この条件は $\boldsymbol{e}\in\ker G_1$ と言い換えられる。核空間 $\ker{G_1}$ の次元は $N-\mathrm{rank}({G_1})$ だが、もし仮に行列 $G_1$ がフルランクだったとすると核空間の次元は0になるので、 $\boldsymbol{e}=0$ 、すなわちMSEが0になる。

ところで、先程のクロネッカー積による表示は、一般にはKhatari-Rao積といい、Khatari-Rao積に関するいくかの事実を適用すると、 $N\le d_1d_0$ のときにMSEが0になることがいえる。

この結果自体は、パラメータ数が訓練標本数よりも多いことが条件として課されているので、MSEが0になるのはある意味で当然であるように感じられるが、グローバルな最小解だけでなくローカルな極小解にトラップしてもMSEが0に収束することが保証されているという意味で価値があるのだろう。

隠れ層数が $L$ 一般の場合

~~式を追うのに疲れたので割愛するが~~ 基本的には1層の場合と同様の解析手法を適用することができる。
ただし隠れ層間の依存関係があるので、最後の2層以外はパラメータを固定し、最後の2層に同じ議論を適用するといった工夫が必要だ。

f:id:levelfour:20160604171225p:plain

感想

内容としては理論系の論文の中でも新規アルゴリズム提案といったものでもなく、一般にはインパクトを出すのは難しそうに感じるが、数値実験によっても目に見えやすい結果で、こういうパターンもあるのかと感じた。
結果自体はover-parametrizedしたら誤差が0になるというのは自明に感じられてしまうのでアレなのだが、解析手法自体はなかなか興味深かった。
類似の解析手法を積み重ねれば、さらにstrictな結果を述べることができるのだろうか？