論文読み：DEEP DOUBLE DESCENT

# DEEP DOUBLE DESCENT:WHERE BIGGER MODELS AND MORE DATA HURT
## どんな論文？
- 2019年12月にsubmitされた論文です。arXivは[こちら](https://arxiv.org/abs/1912.02292.pdf)
- 近年、深層学習では「Double Descent」という、不可思議な現象が起きることが報告されており、それが起きる条件や、示唆されることについて考察した論文になります。

**いくつかの注意点**

- 本記事内の画像・表は本論文より引用したものになります。
- 今の所は直訳ですが、改めて読みやすくしたものに修正していくつもりです。
- 今はAbstract,Introduction,Discussion&Conclusionだけですが、各実験の章についても、後ほど追加します。

## 超速まとめ
- 本研究は、学習プロシージャ全体に対しての複雑度 **Effective Model Complexity** を定義した。
- この概念を利用すると、テストエラーが減少・増加・減少のプロセスをたどるDouble-Descentに対して、一貫した仮説を立てることができる。
- 従来はデータが増えるほど良い結果になると考えられていたが、モデルのサイズと学習時間によってはパフォーマンスが下がることがあるので、注意する必要がある。
- 従来は大きいモデルは過学習を起こすと考えられていたが、学習時間を延ばすことで、過学習を修正することができる可能性が示唆された。


## 0.Abstract
本研究では、様々な深層学習タスクで観測されている*double-descent*という、はじめにパフォーマンスが低下した後に再び良くなっていくという現象は、モデルサイズを大きくした時に生じることを示す。加えて、double-descentは、モデルサイズだけではなく、学習のエポック数の関数でもあることを示す。

私たちは、*effective model complexity*という新しい量を定義することによって、上記の現象を統合し、この量を利用して一般化されたdouble-descentを推測する。
更に私たちは、この新しいモデルの複雑さの概念によって、学習サンプルを増やしていくような学習レジームは、モデルのテストパフォーマンスを劣化させることを特定した。

## 1.Introduction
*bias-variance trade-off*は古典的な統計学習理論において重要な概念である。これは、モデルの複雑度が増すとバイアスを小さく抑えることができるが、高いバリアンスを持つ、というものである。
この理論に従うと、一度モデルの複雑度がある閾値を超えると、モデルはバリアンス項が大部分を占めるテストエラーを得る(過学習する)ようになり、それ以上モデルの複雑度を増すと、パフォーマンスは落ちるのみである、と考えられる。したがって、古典的な統計理論において習慣的に得られている知見として、*larger models are worse(大きいモデルほど悪い)*、というものがある。

しかし、最近のニューラルネットワークは、上記とは異なる挙動を示す。ランダムなラベルにフィットするのに必要以上のパラメータを持つモデルが、それよりも小さいモデルよりも良いパフォーマンスを達成している研究もある。事実、応用研究者の間の知見としては、*larger models are better(大きいモデルほど良い)*、というものもある。
また、学習時間のテストパフォーマンスへの効果についても、最近では議論の対象になっている。
ある状況下ではearly-stoppingはテストパフォーマンスを向上させるが、一方ではトレーニングエラーが0になったニューラルネットワークの学習でのみパフォーマンスが向上する、という状況もある。
もし統計理論の研究者・深層学習の応用研究者の、どちらもが同意するものがあるとしたら、*more data is always better*である。

私たちの研究では、上記のような従来の知見に関して再考・挑戦するような実験的な根拠を示す。
多くの深層学習の状況設定は、二つの異なるレジームを持つ。
一つは*under-parameterized regime*である。これはモデルの複雑度が学習サンプルに比べて小さく、テストエラーがモデルの複雑度に従うU字型の挙動を示すようなものである。
しかし、一度モデルの複雑度が、interpolateするのに十分なものになった(学習データに対して、最適な予測ができる)あとに、更に複雑度をあげると、テストエラーが減少していく、つまり*larger models are better*に従うような挙動が発生する。
この現象は、Belkin(2018)らによって、*double-descent*と名付けられた現象で、決定木や二層のニューラルネットワークなどを、MNISTやCIFAR-10などの様々なタスクに適用した際に発生することが示された。

### Main contributions
私たちは、double-descentが、モデル構造やタスク、最適化手法によらない現象であることを示す。
更に、私たちは、パラメータ数以外の要素も含んだ、より一般化された*double-descent*の概念を提案する。私たちは、学習するプロシージャの複雑度のことを、モデルのトレーニングエラーがほぼ0になりうる最大のサンプル数として定義し、これを*Effective Model Complexity(実効モデル複雑度)*と定義する。
EMCはモデル構造やデータ分布だけでなく、学習プロシージャにも依存する。特に学習時間が伸びるとEMCも増加する。(学習時間が長いほど、モデルは多くのサンプルにフィッティングすることができ、よく予測できるサンプル数が増えるということ。)

私たちは、多くの自然なモデルや学習プロシージャで観測されるdouble-descentはEMCの関数であるという仮説を提案する。事実、モデルを固定し、学習時間を延長するとdouble-descentが発生した(epoch-wise double-descent)。この当然の帰結として、early-stoppingは、比較的狭いパラメータレジームにおいてのみ、モデルの学習を手助けすることがわかる。(モデルのパラメータが大きい学習プロシージャにおいては、学習時間を伸ばすこと、すなわちEMCを大きくすることで、double-descentが起きてテストパフォーマンスが改善する可能性がある。そのため、early-stoppingはモデルパラメータが小さく、トレーニングエラーをほぼ0にするのが難しいような状況でつかう、という選択が合理的。)

### Sample non-monotonicity
最終的に、テストパフォーマンスが学習サンプル数の関数であることを示す。
EMCとサンプル数がマッチする点(under-parameterizationからover-parameterizationの遷移が起きるところ)の周辺でテストエラーのピークを持つため、学習サンプル数を増やすことは、テストエラーのピーク位置を右にシフトすることになる。
多くの状況ではサンプル数が増えるとテストエラーも低下するが、このシフトは*more data is worse*を引き起こすこともある。以下にその例を示す。

![スクリーンショット 2020-07-24 10.04.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/391968/85450af9-4278-4e13-e3b9-9f61545bd50e.png)

上図は、異なるサンプルサイズの学習プロシージャに対して、モデルサイズを横軸に、テストエラーを縦軸に示したものである。
サンプル数が多い(18k Samples)の方が、多くの場合でサンプル数が少ない場合よりも低いテストエラーを記録している。 しかし、サンプル数が多いと大きいモデルが要求されるので、テストエラーのピークが右側(モデルの複雑度が高い)にシフトしている。したがって、あるモデルではサンプル数が多い場合では、サンプル数が小さい場合よりも悪いパフォーマンスに陥ることがわかる。

## 2.Our Results
私たちの仮説を厳密に記述するために、*effective model complexity*を定義する。

*学習プロシージャ T*を、入力にラベル付けされた学習サンプル$S = \{ (x_1,y_1),...,(x_n,y_n) \}$を持ち、データからラベルを予測する分類器$T(S)$の出力を行うとする。
この時、私たちは*学習プロシージャT*の*effective model complexity*を、*T*のトレーニングエラーがほぼ0となるようなサンプル数$n$の最大値として定義する。
![スクリーンショット 2020-07-24 10.27.59.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/391968/0308ad5c-c2de-b2cb-121d-d8c3eee8d772.png)


私たちの主な仮説の表現は以下のようなものになる。

### Generalized Double Descent hypotesis, informal
任意の自然なデータ分布D、ニューラルネットワークベースの学習プロシージャT、小さい正数イプシロン$\epsilon$に対して、Dから得られたn個のサンプルに基づいてラベルの予測を行うとする。このとき、

**Under-parameterized regime**
学習プロシージャTのEMC(実効モデル複雑度)が、サンプル数nよりも十分に小さい場合、EMCを増加させる任意の学習プロシージャTの摂動は、テストエラーを小さくする。

**Over-parameterized regime**
学習プロシージャTのEMCが、サンプル数nよりも十分に大きい場合、EMCを増加させる任意の学習プロシージャTの摂動は、テストエラーを小さくする。

**Critically parameterized regime**
学習プロシージャTのEMCが、サンプル数nと近い場合、EMCを増加させる学習プロシージャTの摂動は、テストエラーを小さくするしたり大きくしたりする。

私たちは、イプシロンの適切な選択方法がわからないので、本研究の実験では$\epsilon = 0.1$で行なっている。
また、「十分に小さい・大きい」といった表現も、厳密にどれくらいの値が、どのように影響してくるかが、まだ十分に判明していないことを示している。
私たちの実験では、*interpolation threshold*の周辺には*critical interval*が存在していることを提案している。そのcritical intervalより大きい・小さい値であると、モデルの複雑度を大きくすることがパフォーマンスの改善につながるが、その区間の中にある(critical interval)場合は、パフォーマンスの低下につながる、というものである。
critical intervalの幅は、データ分布と学習プロシージャの両方に依存しており、その挙動については完全に理解はできていない。

### Model-wise Double Descent → *bigger models are worse*
Section5では、大きな値で固定した最適化ステップ(学習時間)に対して、モデルのサイズを大きくさせた時のテストエラーの挙動について実験した。その中で、様々なデータセット・モデル構造・最適化手法・学習サンプル数・学習プロシージャにおいて、*model-wise double-descent*が発生することを示す。
さらに、テストエラーのピークは、interpolation thresholdの部分でシステマティックに生じることも示す。

### Epoch-wise Double Descent → *training longer can correct overfitting*
Section6では、固定された大きなモデルに対して、学習時間を変化させた時の挙動について実験した。その中で、トレーニングエラーがほぼ0になるような時にテストエラーのピークが生じる、という上記に似た状況が観測された。
大きなモデルのテストエラーは、はじめに減少し(at the beginning of training)、その後(around the critical regime)増加し、再び減少に転じる(at the end of training)。つまり、長い学習は過学習を修正する可能性がある、ということである。


### Sample-wise Non-monotonicity → *more data actually hurts*
Section7では、固定されたモデルサイズと学習プロシージャに対して、学習サンプル数を変化させた時の挙動について実験した。一般化double-descentの仮説に反せず、テストエラーはcritical regimeで特徴的な挙動を示した。これは、モデルによってはデータ数を増やすことが必ずしも学習を助けない、という主張につながる。

### Remarks on Label Noise
私たちの実験において、Label Noiseがあるときは上記のすべてのdouble-descentが強まることが示された。しかし、ある現実的ないくつかの設定では、Label Noiseがない場合でさえテストエラーのピークが示された。Label Noiseに関する詳細な議論は、Section8で行う。

## 3.Related work
最近の研究では、Model-wise double-descentに対する解析を行うものなどが増えてきているが、本研究は以下の2点において、既往研究と異なる。
1. モデルのパラメータ数だけでなく、学習プロシージャも含めた複雑度をEffective Model Complexityとして定義し、新しい概念を提案した。
2. 近年利用されている深層学習で見られる設定(データセット、モデル構造、最適化手法...)で、様々な実験結果を提供した。

Related workについてはAppendix Cで議論する。


## 8.Conclusion and Discussion
私たちは、以下のような、一般化double-descent仮説を紹介した。
*Effective Model Complexityが、学習サンプルと同程度であるようなモデルと学習レジームは、異常な挙動を示す。*
私たちは、上記の仮説を裏付けるような証拠を発見し、またそれがデータセット・モデル構造・学習レジームに対してロバストなものであることも示した。

特に、大きなモデルほどパフォーマンスが悪くなる*model-wise double-descent*と、今まで提案されていなかった*epoch-wise double-descent*について示した。
最終的には、double-descentが、より多くのデータで学習するほどテストパフォーマンスが下がるというレジームを引き起こすことを示した。他の大事な結果としては、ある一つの固定したモデルに対して正則化を変更してもdouble-descentが発生するということがある。

私たちの研究は、実応用においても有益であると信じている。
もしあるモデルと学習プロシージャが、かろうじて学習データにフィットするならば、モデルや学習プロシージャの些細な変更が、予期しない挙動の変化を生み出しかねない、ということである。(例えば、モデルを少し大きくする・小さくすること、正則化手法を変更すること、などなどがテストパフォーマンスを低下させることにつながる、ということである。)

### Early stopping
最適なearly-stoppingをおこなうと、double-descentが発生しなくなることが多くなる、ということも実験的にわかった。しかし、これは私たちの一般化double-descentに反する結果ではない。もしearly-stoppingがモデルが学習誤差0になることを防ぐ場合は、double-descentを観察することは期待できないであろう。というのもEMCが学習サンプル数に到達しないからである。

さらに、私たちはmodel-wise double-descentは、ある状況下においては最適なearly-stoppingを利用していても発生しうることを発見した。
また、最適なearly-stoppingが利用されているときに、多くのデータを利用することでテストパフォーマンスが低下するような状況は観察されなかった。
しかし、early-stoppingとdouble-descentの関係性については、まだわからないことが多く、今後の課題とする。

### Label Noise
私たちの実験では、Label Noiseがあるような状況だと、double-descentが最も強く発生することが観察された。しかし、これはLabel Noiseが根本的な理由ではなく、*model mis-specification*によるものであると考えている。
例えば、Label Noiseが完全にランダムではなく、pseudo-randomに発生している(ランダムに見えるが、実際は決定的であり、避けることができないようなもの)ような状況を考える。この時、ベイズ最適な分類器であればパフォーマンスは変化しないが、もしLabel Noiseが完全にランダムであったならば、double-descentを観測することもあるだろう。

### Other Notions of Model Complexity
私たちの提案する、*Effective Model Complexity*は、ラデマッハ複雑度のような古典的な複雑さの概念と関連している点がある一方で、以下の2点で異なる。

1. EMCはデータ分布の*true labels*に依存する
2. EMCはモデル構造だけでなく、学習プロシージャにも依存する

上記の二つの要素を持たない複雑度の概念、例えばラデマッハ複雑度とVC次元は、ラベルの分布に依存しないため、double-descentのピーク位置を特徴付けることが難しいと考えられる。
というのも私たちのLabel Noiseを加えた実験によって、double-descentのピーク位置がシフトすることが示されたからである。
加えて、上記の二つの古典的な複雑度は、モデル族とデータ分布に依存するが、学習プロシージャは考慮していない。したがって、これらの指標はtrain-time double-descent効果、つまりepoch-wise double-descentやデータ拡張(data augmentation)によるピーク位置のシフトを捉えることができない。