論文紹介: Elimination of All Bad Local Minima in Deep Learning

tl; dr

• Kawaguchi and Kaelbling. 2019. Elimination of All Bad Local Minima in Deep Learning. arXiv. を紹介。
• ある前提条件を満たすニューラルネットワークに、ある特殊なニューロン (exponential neuron) を1つ加えると、そのニューラルネットワークの全ての局所解は大域最適な解になることをLiangらが証明した。
• Liangらの手法は厳しい前提があり、既存のニューラルネットワークでは前述した性質が維持されるかが未知であった。本研究はExponential neuronの恩恵が一般的なニューラルネットワークでも得られることを証明した。
• 一方で、この手法がうまく行かないケースがあることも示した。

Disclaimer

本論文紹介は、提案手法の証明部分を詳細に説明するものではありません（というか、証明部分は私もさらっとしか ほとんど読んでいません）。あくまでも、応用的な観点から、本論文の主張にどういう意義があるかを説明するものになります。

本論文では2つの亜種（3.1、3.2）を提案していますが、特に重要だと思われる3.1に絞って説明しています。

また、基本的に説明はゆるふわな感じ（直感的な理解）でしますが、深層学習でよく使われる用語については特に説明しません。

はじめに

Liangらは、ある前提条件を満たすニューラルネットワークに、ある特殊なニューロン (exponential neuron) を1つ加えると、そのニューラルネットワークの全ての局所解は大域最適な解になることを証明しました。

(本紹介はLiangらの論文の概要を知っていることを前提にしています。Liangらの論文の紹介についてはこちら)

ここでExponential neuronを加えるとは、元のネットワーク$f(x; \theta)$に対して、入力から出力へのSkip-connectionとして、Exponential neuron $a\exp(\mathbf{x}^Tx_i + b)\in \mathbb{R}$を足すことです。

Liangらの証明は深層学習の常識を塗り替え得るものでしたが、大きな制約が2つありました。

• 二値分類問題にしか使えない。
• 特殊な損失関数が必要で、現在一般的に使われている損失関数は使えない。

本研究では、Liangらの手法をベースに、2つの貢献をしています。

• Liangらの手法に対して二値分類以外の問題に使える拡張を示し、Liangらの手法が一般的なニューラルネットワークの損失関数全般でも使える（全ての局所解は大域最適解になる）ことを証明した。
• これらの手法がうまく行くケース、うまく行かないケースの両方があることを示した。

本紹介では2つの項目それぞれについて説明します。

Liangらの手法の前提条件の緩和

本研究とLiangらの研究が目指しているところは同一です。つまり、以下のような性質を証明します。

Thorem 1によると、Exponential neuronを加えたネットワークの全ての損失$\tilde{L}$の局所解は、提案手法の損失 $\tilde{L}$ の大域最適な解になります。かつ、その局所解は元の損失$L$における大域最適な解でもあります（つまり、exponential neuronを入れたことによる副作用はありません）。もっと簡単にいうと、Exponential neuronを加えると、元のニューラルネットワークの全ての局所解は消滅します。

本研究とLiangの研究の効果は同じです。さらに言えば手法も自然な拡張で、ほとんど変わりません。本研究のミソは、Liangらの手法がより緩い前提条件で、より広汎な問題に対しても前述の効果が得られることを数学的に証明したところです。本紹介では証明の細部には立ち入りませんので、どのように条件が緩和されたかに絞って説明します。

前提条件の緩和

まず、Liangらの手法では、次の形式の二値分類問題のみを対象としていました。

二値分類問題のみにしか使えない上に、このように、ニューラルネットワークの出力と正解ラベルの掛け算を入力にとる損失関数$\ell(z)$しか使えないという制限がありました（加えて他にも制約が有ります）。

本研究では次のような問題を対象にしています。

正解ラベルが多次元になっていることに注意してください。つまり、損失関数の形式は任意の次元（数）の正解ラベルと、それに対する推定結果を入力に損失を返す、となっており、多値分類問題や回帰問題に対応できるようになっています。

上記では、損失関数の入力について見ましたが、次に本研究で損失関数に要求している性質について説明します。

損失関数に、微分可能でかつ凸関数であることを要求しています。

さて、ここでLiangらの手法と、本研究で前提としている条件について整理してみましょう。

項目	Liangら	本研究
使えるタスク	二値分類のみ	$\ell(f(x_i;\theta),y_i)$を満たすタスク（回帰、多値分類など）
使える損失関数	$\ell(z)$という特殊な形	一般的な $\ell(f(x_i;\theta),y_i)$ の形
	凸関数	凸関数
	zについて二階微分可能	zについて一階微分可能
	全ての臨界点において$z<0$
	⇒普通は使われない特殊な損失関数のみ	⇒交差エントロピーやヒンジ損失など一般的な損失関数を含む広範な関数

このように、Liangらの手法より大幅に条件が緩和されており、現在よく使われているニューラルネットワークにそのまま適用できることがわかります。

二値分類問題への拡張方法

では、二値分類問題以外にはどうExponential neuronを適用するのでしょうか。それは簡単で、出力$y$の次元数分だけExponential neuronを増やします。多値分類ならば、分類ごとに1つのexponential neuronを設けてやります。

前述したとおり、自然な拡張で、手法としてはほとんど変わっていないことがわかっていただけると思います。

なお、手法自体には大きな差異がないことから、以降の説明ではLiangらの手法と、その拡張である本手法を合わせて「本手法」と呼ぶことにします。

本手法の限界

本手法がうまく行かないケース

著者らは、上記前提の緩和を証明するとともに、本手法がうまく行かないケースがあることも証明しています。

特に重要なのは"Furthermore"以降です。提案手法で追加したパラメータ$(a, b, W)$がどんな値を取ろうとも、ニューラルネットワークのパラメータ$\theta$の勾配がなくなるような$\theta$が存在するデータが存在しうることを示しています。¹

これだけではぴんとこないので、（著者らが出している）例をもとに考えてみましょう。次のように、あるニューラルネットとデータの実例における、損失とその勾配を図示してみます。◯と線で繋がれている点が図内の対応している点を表しています。左図は元のニューラルネットワークの損失と、ニューラルネットワークのパラメータの関係を示しています。真ん中の図は、左図に提案手法で追加したパラメータ$b$の軸を増やしたもので、真ん中の図の断面（b=0の場合）が左側と同じになっています。右側の図は、真ん中の図を上から見て、勾配の反対方向（つまり勾配法でパラメータが更新される方向）を⇒で示してあります。

ここで、$\theta = 0.4$、$b = 0$だとします。右図の矢印の方向パラメータは更新されるので、$\theta$はすぐに0.2のあたりになってしまいます。そうすると、右図でわかるように$\theta = 0.2$の部分では上下方向に矢印が向いていないため、$\theta$の値は動かず、$b$だけが無限に大きくなる、つまり発散してしまいます。このとき、$\theta$だけ見ると、左図のように、結局局所解$0.2$に停留しているような形になっています。

このような例はいくつも簡単に作ることができます。

これらを念頭におき、Theorem 3の前半を見てみます。Theorem 3の前半によると、提案手法のあらゆる構成において、ニューラルネットワークのパラメータ$\theta$ではない時は、提案手法で追加したパラメータ$(a, b, W)$の局所解がないということを言っています。つまり、全体最適ではない$\theta$の鞍点がもしあるとすると、このとき$(a, b, W)$の局所解はないため、$(a, b, W)$は発散します。²

つまり、このような例から、提案手法によって全ての局所解は全体最適な解になったが、その局所解にたどり着くのが不可能になる例がありうる、ということが言えます。

もちろんうまくゆく例もある

上記で提案手法がうまくゆかない例を示しましたが、もちろんうまくゆくケースもあります。特に元のニューラルネットワークの損失$L$に大域最適な解があるのであれば、$a=0$なる点のどこかに必ず局所解があります。そこに局所解があるのであれば、ちゃんと局所解に収束する可能性もあります³。

また、上記はexponential neuronを足すことで収束がうまくいかなくなるケースを示しましたが、逆に収束しやすくなるケースがあることも示唆しています。例えば、前述した例でたと、$b = 0$のとき$\theta$が超えないといけない"山"は大きいのですが(下図①)、$b$が大きくなると$\theta$の"山"が小さくなります（②）。この例はデータが1点しかないので勾配の方向は固定ですが、実際のニューラルネットワークの学習に使うミニバッチ勾配法では勾配にノイズがのるため、Exponential neuronが導入されると"山"を乗り越えられる可能性があがる（かもしれません）。

まとめ

本研究では、Exponential neuronの導入により全ての局所解が大域最適解になる現象が、より広汎な問題に対しても生じることを数学的に証明しました。また、この手法がうまく行かないケースがあることを示しました。

コメント

• この手法がうまくいかない可能性、うまくいく可能性の両方が示されたので、あとは実用上うまくいくのか、どんなときにうまくいくのかなどの研究が求められると思います。
  • LiangらもKawaguchiらも実験結果を載せていないのはうまくいかないからである可能性もある....
• 局所解に落ちる可能性があるというのは深層学習において大きな問題の1つ。仮にこのままの提案手法がうまくいかなかったとしても、後続の研究に期待したい。
• なお、本手法は解の汎化性については議論していないので注意。
  • この手法だとL2正則化を入れられない問題もある。 重みの値を予測値とみなし、ダミーラベルを入れることで論文の枠組み内で説明できそうです。(thanks @kota9)

1. ここでは、「全てのxxに対して」みたいなものがつかず、"There exists ..."だけなので、exampleが1つあれば証明は不要だったのでは? ↩

2. "つまり...発散します"は私の解釈。あっているはず。 ↩

3. Example 6の言わんとしていることの理解が悩ましいです。。これが私が読み取った理解ですが、もしかするともっと深い意味があるのかもしれません（少なくとも明言はしていませんが）... ↩