論文紹介: Adding One Neuron Can Eliminate All Bad Local Minima

tl; dr

• Liang et al., 2018. Adding One Neuron Can Eliminate All Bad Local Minima. NIPS.
• ある前提条件を満たすニューラルネットワークに、ある特殊なニューロン (exponential neuron) を1つ加えると、そのニューラルネットワークの局所解は大域最適な解になる
  • 前提条件:
    • 二値分類問題
    • 特殊な損失関数（Cross entropyなどはダメ）
  • Exponential neuron: $a \exp(\mathbf{w}^Tx + b)$ を入力から出力層へのskip connectionとして追加
• 提案手法を数学的に証明（実験はなし）
• 大域最適な解の汎化性、提案手法を導入したことによる局所解に至るまでの時間の変化については議論していないので注意。

@incollection{NIPS2018_7688,
title = {Adding One Neuron Can Eliminate All Bad Local Minima},
author = {LIANG, SHIYU and Sun, Ruoyu and Lee, Jason D and Srikant, R.},
booktitle = {Advances in Neural Information Processing Systems 31},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {4355--4365},
year = {2018},
publisher = {Curran Associates, Inc.},
url = {http://papers.nips.cc/paper/7688-adding-one-neuron-can-eliminate-all-bad-local-minima.pdf}
}

Disclaimer

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

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

解説

本論文の主張はある前提条件を満たすニューラルネットワークに、ある特殊なニューロン (exponential neuron) を1つ加えると、そのニューラルネットワークの局所解は大域最適な解になるというものです。このような特性を数学的に証明しています。

本紹介では、前述した「ある前提条件」、「exponential neuron」、そしてその効果について順番に説明します。また、本論文では、提案手法の亜種をいくつか紹介しています。本紹介では網羅しませんが、重要と思われるものについては紹介します。

提案手法の前提条件

提案手法には3つの前提条件があります。1つ目の条件は2値分類であることです。次のような式で既定されるニューラルネットワークを前提としています。

右側の$R_n(\theta;f)$は$1 - Accuracy$の値です。

正解ラベルが$y_i = -1$のとき、ニューラルネットワークの出力$f(x_i;\theta)$が$1$ならば$\ell(-1 \times -1 \times 1) = \ell(1)$、出力が$-1$ならば$\ell(-1)$という具合に、正解ならば損失関数$\ell$の中身が負の値になります。

2つ目の条件として次があります。

つまり損失関数$\ell(z)$に次の条件を要求しています。

• 単調増加(非減少)
• $z$について二階微分可能
• 全ての臨界点は大域最小
• 全ての臨界点（=大域最小な解）において$z < 0$

たとえば、よく使われるsigmoid cross entropy損失はこの形を満たしていないため、本手法では対象外です。hinge損失 ($\ell(z) = max(0, z)$)は2つ目の条件を満たさないのでやはり対象外です。$\ell(z) = max(z + 1, 0)^p$、$p \geq 3$などの損失関数はこの条件を満たします¹。

3つ目の条件は下記です。

つまり、全ての学習データを正しく分類できるようなパラメータが存在するということです。このような条件を満たすには、まず、入力特徴量が全く一緒($x_i = x_j$)ならば、その正解ラベルも一緒である必要があります($y_i = y_j$)。この条件さえ揃えば、over parameterization (パラメータ数のほうがデータ数よりも多い、最近よくみられる) をしてしまえばこの条件は満たすことができます²。

本研究では、他の研究でよく前提とされている以下のような条件を前提にしていません。

• 活性化関数の種類（本研究ではReLUだろうがなんだろうがOK）
• 全結合ニューラルネットワークのみ（本研究ではCNNだろうがResNetだろうがOK）
• データの入力分布

提案手法 (exponential neuron)

ずばり、exponential neuronを入力からのskip-connectionとしてネットワークに入れるだけです (
$\mathbf{w}^Tx \in \mathbb{R}$）。

損失には、$a$に関する正則化項を入れます。

これで終わり。これだけです。

効果

このようなニューロンを1ついれると次のようなことが数学的に証明できます。

前述した提案手法の局所解は、提案手法の損失 $\tilde{L}_n(\tilde{\theta})$ の大域最適な解になります。

かつ、その局所解は元の損失$L_n(\theta)$における大域最適な解でもあります（つまり、exponential neuronを入れたことによる副作用はありません）。このことは、Corollary 1でも述べられおり、Corollary 1によると、局所解に至った時、元のネットワーク$f$と、exponential neuronを加えたあとのネットワーク$\tilde{f}$は同じ挙動になります (exponential neuronの係数$a$が0になるため）。

また、局所解では誤答率$R_n$も最小になります。Assumption 2によるとこのネットワークの大域最適な解は全てのデータを正しく分類できるので、分類精度は100%になります。

提案手法の限界

なお、ここで議論しているのは学習データにおける大域最適です。近年の研究では、同じ損失の局所解でも、汎化性能が違うことがわかってきていますが、本研究では汎化性能については一切議論していません。

また、上記の効果の証明は、提案手法の損失 $\tilde{L}_n(\tilde{\theta})$が局所解に至ったところを起点に、その局所解の性質を確かめる形でしています。exponential neuronを加える前後で、局所解に到るまでの時間がどのように変わるかなどはやはり議論していません³。

亜種1: スキップコネクションをなくす

前述した提案手法では、入力から予測までのスキップコネクションを設けています。著者らはスキップコネクションを設けなくとも同様の性質を得られる亜種についても提案しています。

この亜種においては、2つ条件が追加されています。

• 全結合層が積み重なったニューラルネットワークであることが前提となっています（CNNやResNet構造はダメ）。
• 各層の活性化関数は微分可能でなければならない。

このとき次のように、各全結合層に1つずつexponential neuronを追加します。

また、前述した$a$ではなく、exponential neuronに関する重みについて正則化項を設けます。

こうすることで、前述した提案手法と同様に、提案手法の局所解においては、提案手法の損失 $\tilde{L}_n$ の大域最小となり、それは元の損失$L_n$においても大域最適な解となります。

亜種2: Assumption 2を緩和する

著者らはAssumption 2（= 全てのデータを正しく分類できるようなパラメータが存在する）を緩和する方法を提案しています。Assumption 2の代わりに損失関数が凸関数であることを追加で仮定すれば⁴、前述した提案手法と同様に、提案手法の局所解は元の損失$L_n$における大域最適な解となります。もちろん、どんなに頑張っても80%しか出しようがないモデル・データにexponential neuronを追加したとしても、得られる精度は80%までです。

コメント

• 損失関数に関する制約が結構きつい。例えば正則化項をいれるとこの手法はなりたたないはず。
• 基本的に数学的検討のみで実験は一切ない。
• この論文はKawaguchi and Kaelbling. 2019. Elimination of All Bad Local Minima in Deep Learning. ArXiV.を読むための布石として読んだ。この論文ではこの手法の限界などについても述べている。（近日中に紹介予定。）

1. この関数は劣微分だけど、微分は不可能な気がする。まあ著者が例と出しているくらいなので、劣微分でもOKなのかな... ↩

2. もちろん、途中で接続が切れているなど、over parameterizationした上で条件を満たさないネットワークを考えつくこともできますが、普通の設計をしていれば成り立つはずです。 ↩

3. 論文内では言及されていませんが、SGDの性質上いつかは必ず局所解には落ち着くと思われます。なので、exponential neuronを加えた結果局所解にすら到れなくなるということはないような気がします。 ↩

4. Assumption 1を満たした上で、convexでないことなんてありうるの？ ↩