Understanding deep learning requires rethinking generalization【1 INTRODUCTION】【論文 DeepL 翻訳】

この記事は自分用のメモみたいなものです.
ほぼ [DeepL](https://www.deepl.com/home) 翻訳でお送りします.
間違いがあれば指摘していだだけると嬉しいです.

翻訳元
[Understanding deep learning requires rethinking generalization](https://arxiv.org/abs/1611.03530)

前: [【Abstract】](https://qiita.com/tomato_/items/9a140a43859509cb1b84)
次: [【2 EFFECTIVE CAPACITY OF NEURAL NETWORKS】](https://qiita.com/tomato_/items/63837ecdc578aec5cd39)

# 1 INTRODUCTION

### 訳文

ディープな人工ニューラルネットワークは, 多くの場合, 訓練されるサンプル数よりもはるかに多くの訓練可能なモデルパラメータを持っている. それにもかかわらず, これらのモデルの中には, 非常に小さな一般化誤差, すなわち "訓練誤差" と "テスト誤差" の差を示すものがある. 同時に, 一般化が悪い自然なモデルアーキテクチャを思いつくことは確かに容易である. では, 一般化の良いニューラルネットワークとそうでないニューラルネットワークを区別するのは何だろうか? この質問に満足のいく答えが得られれば, ニューラルネットワークをより解釈しやすくするだけでなく, より原理的で信頼性の高いモデルアーキテクチャの設計につながるかもしれない.

このような疑問に答えるために, 統計的学習理論は, 一般化誤差を制御することができる多くの異なる複雑度尺度を提案してきた. これらには、VC 次元 (Vapnik, 1998), Rademacher 複雑度 (Bartlett & Mendelson, 2003), 一様安定性 (Mukherjee et al., 2002; Bousquet & Elisseeff, 2002; Poggio et al., 2004) が含まれる. さらに, パラメータの数が多い場合, 理論的には, 小さな汎化誤差を保証するために何らかの形の正則化が必要であることが示唆されている. また, early stopping の場合のように, 正則化は暗黙のうちに行われることもある.

## 1.1 OUR CONTRIBUTIONS

本研究では, 一般化性能が根本的に異なるニューラルネットワークを区別することができないことを示すことで, 従来の一般化観を問題化している.

**Randomization tests.** 我々の方法論の中心にあるのは, ノンパラメトリック統計学 (Edgington & Onghena, 2007) からのよく知られている randomization test の変形である. 最初の実験では, 真のラベルがランダムラベルで置き換えられたデータのコピー上で, いくつかの標準アーキテクチャを訓練する. 我々の中心的な発見は以下のように要約できる:

ディープニューラルネットワークは, ランダムラベルを簡単に適合させることができる.

より正確には, 真のデータの完全にランダムなラベリングで訓練した場合, ニューラルネットワークは訓練誤差 0 を達成する. もちろん, 訓練ラベルとテストラベルの間には相関がなく, テストエラーはランダムチャンスよりも良くない. 言い換えれば, ラベルをランダムにするだけで, モデル, サイズ, ハイパーパラメタ, オプティマイザを変更することなく, モデルの一般化誤差を大幅にジャンプアップさせることができる. 我々は, CIFAR10 と ImageNet 分類ベンチマークで訓練されたいくつかの異なる標準アーキテクチャについて, この事実を立証する. 述べるのは簡単だが, この観察は統計的学習の観点から深遠な意味を持っている.

1. ニューラルネットワークの有効容量は, データセット全体を記憶するのに十分である.
2. ランダムラベルの最適化も簡単である. 実際, 学習時間は真のラベルでの学習と比較して, わずかな定数の要因でしか増加しない.
3. ラベルのランダム化はデータ変換のみであり, 学習問題の他のすべての特性は変更されない.

この最初の実験セットを拡張して, 真の画像を完全にランダムなピクセル (例えば, ガウスノイズ) で置き換え, 畳み込みニューラルネットワークが訓練誤差ゼロでデータに適合し続けることを観察する. このことは, その構造にもかかわらず, 畳み込みニューラルネットがランダムノイズに適合することができることを示している. 我々はさらにランダム化の量を変化させ, ノイズがない場合と完全なノイズの場合の間を滑らかに補間する. これにより, ラベルにある程度のレベルの信号が残っている中間学習問題の範囲が得られる. 我々は, ノイズレベルを増加させると, 一般化誤差が着実に悪化することを観察している. このことは, ニューラルネットワークがデータ中に残っている信号を捕捉し, 同時にブルートフォースを用いてノイズのある部分を適合させることができることを示している.

我々は, これらの観測が, 最先端のニューラルネットワークの一般化性能の可能性のある説明として, VC 次元, Rademacher 複雑度, 一様安定性のすべてを排除する方法を以下でさらに詳細に議論する.

**明示的な正則化の役割.** モデルアーキテクチャ自体が十分な正則化器でない場合, 明示的な正則化がどれだけ役立つかを見極める必要がある. 我々は, 重み減衰, ドロップアウト, データオーギュメンテーションなどの明示的な正則化の形態が, ニューラルネットワークの一般化誤差を適切に説明しないことを示す. 別の言い方をすれば:

明示的な正規化は一般化の性能を向上させるかもしれないが, 一般化誤差を制御するためには必要でもそれ自体が十分でもない.

些細な解を除外するために明示的な正則化が必要な古典的な凸型経験的リスク最小化とは対照的に, 正則化がディープラーニングではかなり異なる役割を果たすことを発見した. 正則化は, モデルの最終的なテスト誤差を改善するのに役立つことが多いチューニングパラメータのようだが, すべての正則化が存在しないからといって, 必ずしも一般化誤差が悪いというわけではない. Krizhevsky et al. (2012) が報告しているように, $l_2$正則化 (重み減衰) は時に最適化を助けることさえあり, ディープラーニングにおける正則化の本質があまり理解されていないことを示している.

**有限サンプルの表現力.** 一般的に大規模なニューラルネットワークが訓練データの任意のラベリングを表現できることを示す理論的な構築によって, 我々の経験的な観察を補完する. より正式には, 我々は $p = 2n + d$ パラメータを持つ非常に単純な 2 層 ReLU ネットワークを示す. Livni et al. (2014) による以前の構築は, はるかに多くのパラメータ, すなわち $O(dn)$ で同様の結果を達成した。我々の深さ 2 のネットワークは必然的に幅が大きくなるが, 各層が $O(n/k)$ のパラメータのみを持つ深さ $k$ のネットワークも考えられる.

先行する表現力の結果は, ニューラルネットが領域全体にわたってどのような関数を表現できるかに焦点を当てていたが, 我々は代わりに有限サンプルに関してニューラルネットの表現力に焦点を当てている. 関数空間における既存の深度分離 (Delalleau & Bengio, 2011; Eldan & Shamir, 2016; Telgarsky, 2016; Cohen & Shashua, 2016) とは対照的に, 我々の結果は, 線形サイズの深度 2 ネットワークでさえ, 訓練データの任意のラベリングを既に表現できることを示している.

**暗黙の正則化の役割.** ドロップアウトや重み減衰のような明示的な正則化は一般化には不可欠ではないかもしれないが, 訓練データによく適合するすべてのモデルがよく一般化するわけではないことは確かである. 実際, ニューラルネットワークでは, ほとんどの場合, 確率的勾配降下の出力としてモデルを選択する. 線形モデルに着目して, SGD が暗黙の正則化器としてどのように機能するかを分析する. 線形モデルの場合, SGD は常にノルムの小さい解に収束する. したがって, アルゴリズム自体が暗黙のうちに解を正則化していることになる. 実際, ガウスカーネル法であっても, 正則化を行わなくても十分に一般化できることが, 小さなデータセットで示されている. これは, 特定のアーキテクチャが他のアーキテクチャよりも一般化しやすい理由を説明するものではないが, SGD を使って訓練されたモデルにどのような特性が継承されているのかを正確に理解するためには, さらなる調査が必要であることを示唆している.

## 1.2 RELATED WORK

Hardt et al. (2016), 確率的勾配降下で訓練されたモデルの一般化誤差の上限を, 勾配降下にかかったステップ数の観点から与えている. 彼らの分析は, 一様安定性の概念 (Bousquet & Elisseeff, 2002) を経由している. この研究で指摘しているように, 学習アルゴリズムの一様安定性は学習データのラベリングに依存しない. したがって, この概念は, 真のラベルで訓練されたモデル (一般化誤差が小さい) とランダムラベルで訓練されたモデル (一般化誤差が大きい) を区別するのに十分ではない. このことは, Hardt et al. (2016) の非凸最適化に関する分析が, データの通過回数が非常に少ないという悲観的なものであった理由をも浮き彫りにしている. 我々の結果は, 経験的にニューラルネットワークを訓練しても, データを何度も通過しても一様に安定しないことを示している. その結果, より弱い安定性の概念が必要となる.

ニューラルネットワークの表現力については, 多層パーセプトロンの普遍近似定理から始まる多くの研究が行われてきた (Cybenko, 1989; Mhaskar, 1993; Delalleau & Bengio, 2011; Mhaskar & Poggio, 2016; Eldan & Shamir, 2016; Telgarsky, 2016; Cohen & Shashua, 2016). これらの結果はすべて, ニューラルネットワークの特定のファミリーが, ドメイン全体にわたってどのような数学的機能を表現できるかを特徴づける母集団レベルのものである. 代わりに, 我々はサイズ $n$ の有限サンプルに対するニューラルネットワークの表現力を研究する. これは, $O(n)$ サイズの 2 層パーセプトロンでさえも普遍的な有限サンプル表現力を持つことを非常に簡単に証明することにつながる.

Bartlett (1998) はシグモイド活性度を持つ多層パーセプトロンの fat shattering 次元の境界を各ノードの重みの $l_1$ ノルムで証明した. この重要な結果は, ネットワークサイズに依存しないニューラルネットの一般化境界を与える. しかし, RELU ネットワークでは, $l_1$-ノルムはもはや参考にならない. このことは, 大規模なニューラルネットの一般化誤差を制限する別の形態の容量制御があるのかどうかという疑問につながる. この疑問は, Neyshabur et al. (2014) の示唆に富む研究で提起されたもので, 彼は実験を通して, ネットワークサイズがニューラルネットワークの容量制御の主な形態ではないことを主張している. 行列因数分解への類推により, 暗黙の正則化の重要性が説明された.

### 原文

Deep artificial neural networks often have far more trainable model parameters than the number of samples they are trained on. Nonetheless, some of these models exhibit remarkably small generalization error, i.e., difference between “training error” and “test error”. At the same time, it is certainly easy to come up with natural model architectures that generalize poorly. What is it then that distinguishes neural networks that generalize well from those that don’t? A satisfying answer to this question would not only help to make neural networks more interpretable, but it might also lead to more principled and reliable model architecture design.

To answer such a question, statistical learning theory has proposed a number of different complexity measures that are capable of controlling generalization error. These include VC dimension (Vapnik, 1998), Rademacher complexity (Bartlett & Mendelson, 2003), and uniform stability (Mukherjee et al., 2002; Bousquet & Elisseeff, 2002; Poggio et al., 2004). Moreover, when the number of parameters is large, theory suggests that some form of regularization is needed to ensure small generalization error. Regularization may also be implicit as is the case with early stopping. 

## 1.1 OUR CONTRIBUTIONS

In this work, we problematize the traditional view of generalization by showing that it is incapable of distinguishing between different neural networks that have radically different generalization performance.

**Randomization tests.** At the heart of our methodology is a variant of the well-known randomization test from non-parametric statistics (Edgington & Onghena, 2007). In a first set of experiments, we train several standard architectures on a copy of the data where the true labels were replaced by random labels. Our central finding can be summarized as:

Deep neural networks easily fit random labels.

More precisely, when trained on a completely random labeling of the true data, neural networks achieve 0 training error. The test error, of course, is no better than random chance as there is no correlation between the training labels and the test labels. In other words, by randomizing labels alone we can force the generalization error of a model to jump up considerably without changing the model, its size, hyperparameters, or the optimizer. We establish this fact for several different standard architectures trained on the CIFAR10 and ImageNet classification benchmarks. While simple to state, this observation has profound implications from a statistical learning perspective:

1. The effective capacity of neural networks is sufficient for memorizing the entire data set.
2. Even optimization on random labels remains easy. In fact, training time increases only by a small constant factor compared with training on the true labels.
3. Randomizing labels is solely a data transformation, leaving all other properties of the learning problem unchanged.

Extending on this first set of experiments, we also replace the true images by completely random pixels (e.g., Gaussian noise) and observe that convolutional neural networks continue to fit the data with zero training error. This shows that despite their structure, convolutional neural nets can fit random noise. We furthermore vary the amount of randomization, interpolating smoothly between the case of no noise and complete noise. This leads to a range of intermediate learning problems where there remains some level of signal in the labels. We observe a steady deterioration of the generalization error as we increase the noise level. This shows that neural networks are able to capture the remaining signal in the data, while at the same time fit the noisy part using brute-force. 

We discuss in further detail below how these observations rule out all of VC-dimension, Rademacher complexity, and uniform stability as possible explanations for the generalization performance of state-of-the-art neural networks.

**The role of explicit regularization.** If the model architecture itself isn’t a sufficient regularizer, it remains to see how much explicit regularization helps. We show that explicit forms of regularization, such as weight decay, dropout, and data augmentation, do not adequately explain the generalization error of neural networks. Put differently:

Explicit regularization may improve generalization performance, but is neither necessary nor by itself sufficient for controlling generalization error.

In contrast with classical convex empirical risk minimization, where explicit regularization is necessary to rule out trivial solutions, we found that regularization plays a rather different role in deep learning. It appears to be more of a tuning parameter that often helps improve the final test error of a model, but the absence of all regularization does not necessarily imply poor generalization error. As reported by Krizhevsky et al. (2012), $l_2$-regularization (weight decay) sometimes even helps optimization, illustrating its poorly understood nature in deep learning.

**Finite sample expressivity.** We complement our empirical observations with a theoretical construction showing that generically large neural networks can express any labeling of the training data. More formally, we exhibit a very simple two-layer ReLU network with $p = 2n + d$ parameters that can express any labeling of any sample of size n in d dimensions. A previous construction due to Livni et al. (2014) achieved a similar result with far more parameters, namely, $O(dn)$. While our depth 2 network inevitably has large width, we can also come up with a depth $k$ network in which each layer has only $O(n/k)$ parameters.

While prior expressivity results focused on what functions neural nets can represent over the entire domain, we focus instead on the expressivity of neural nets with regards to a finite sample. In contrast to existing depth separations (Delalleau & Bengio, 2011; Eldan & Shamir, 2016; Telgarsky, 2016; Cohen & Shashua, 2016) in function space, our result shows that even depth-2 networks of linear size can already represent any labeling of the training data. 

**The role of implicit regularization.** While explicit regularizers like dropout and weight-decay may not be essential for generalization, it is certainly the case that not all models that fit the training data well generalize well. Indeed, in neural networks, we almost always choose our model as the output of running stochastic gradient descent. Appealing to linear models, we analyze how SGD acts as an implicit regularizer. For linear models, SGD always converges to a solution with small norm. Hence, the algorithm itself is implicitly regularizing the solution. Indeed, we show on small data sets that even Gaussian kernel methods can generalize well with no regularization. Though this doesn’t explain why certain architectures generalize better than other architectures, it does suggest that more investigation is needed to understand exactly what the properties are inherited by models that were trained using SGD.

## 1.2 RELATED WORK

Hardt et al. (2016) give an upper bound on the generalization error of a model trained with stochastic gradient descent in terms of the number of steps gradient descent took. Their analysis goes through the notion of uniform stability (Bousquet & Elisseeff, 2002). As we point out in this work, uniform stability of a learning algorithm is independent of the labeling of the training data. Hence, the concept is not strong enough to distinguish between the models trained on the true labels (small generalization error) and models trained on random labels (high generalization error). This also highlights why the analysis of Hardt et al. (2016) for non-convex optimization was rather pessimistic, allowing only a very few passes over the data. Our results show that even empirically training neural networks is not uniformly stable for many passes over the data. Consequently, a weaker stability notion is necessary to make further progress along this direction.

There has been much work on the representational power of neural networks, starting from universal approximation theorems for multi-layer perceptrons (Cybenko, 1989; Mhaskar, 1993; Delalleau & Bengio, 2011; Mhaskar & Poggio, 2016; Eldan & Shamir, 2016; Telgarsky, 2016; Cohen & Shashua, 2016). All of these results are at the population level characterizing which mathematical functions certain families of neural networks can express over the entire domain. We instead study the representational power of neural networks for a finite sample of size $n$. This leads to a very simple proof that even $O(n)$-sized two-layer perceptrons have universal finite-sample expressivity.

Bartlett (1998) proved bounds on the fat shattering dimension of multilayer perceptrons with sigmoid activations in terms of the $l_1$-norm of the weights at each node. This important result gives a generalization bound for neural nets that is independent of the network size. However, for RELU networks the $l_1$-norm is no longer informative. This leads to the question of whether there is a different form of capacity control that bounds generalization error for large neural nets. This question was raised in a thought-provoking work by Neyshabur et al. (2014), who argued through experiments that network size is not the main form of capacity control for neural networks. An analogy to matrix factorization illustrated the importance of implicit regularization.