2 EFFECTIVE CAPACITY OF NEURAL NETWORKS

訳文

我々の目標は, フィードフォワードニューラルネットワークの効果的なモデル能力を理解することである. この目標を達成するために, 我々はノンパラメトリックランダム化テストに着想を得た方法論を選択する. 具体的には, 候補となるアーキテクチャを用いて, 真のデータと真のラベルをランダムラベルで置き換えたデータのコピーの両方で訓練を行う. 2 つ目のケースでは, インスタンスとクラスラベルの間にはもはや何の関係もない. その結果, 学習は不可能となる. 直感的には, この不可能性は学習中に明らかに現れるはずで, 例えば, 学習が収束しなかったり, 学習が大幅に遅くなったりする. 驚いたことに, 複数の標準的なアーキテクチャの学習プロセスのいくつかの特性は, このラベルの変換によってほとんど影響を受けない. このことは概念的な課題を提起している. そもそも小さな一般化誤差を期待していた私たちの正当化は, もはやランダムラベルの場合には適用されない.

この現象をより深く理解するために, ラベルノイズがない場合とラベルが完全に破損している場合の連続性を探るために, さまざまなレベルのランダム化を実験している. また, 入力 (ラベルではなく) の異なるランダム化を試し, 同じ一般的な結論に達した.

実験は, 2 つの画像分類データセット, CIFAR10 データセット (Krizhevsky & Hinton, 2009) と ImageNet (Russakovsky et al., 2015) ILSVRC 2012 データセットで実行される. 我々は, ImageNet 上で Inception V3 (Szegedy et al., 2016) アーキテクチャをテストし, CIFAR10 上で Inception, Alexnet (Krizhevsky et al., 2012), MLP のより小さなバージョンをテストする. 実験セットアップの詳細については, 付録のセクション A を参照.

2.1 FITTING RANDOM LABELS AND PIXELS

ラベルと入力画像を以下のように変更して実験を行う.

True labels: 修正なしのオリジナルのデータセット.
Partially corrupted labels: 確率 $p$ で独立して, 各画像のラベルが一様なランダムクラスとして破損する.
Random labels: すべてのラベルがランダムなものに置き換えられる.
Shuffled pixels: ピクセルのランダムな並べ替えが選択され, トレーニングセットとテストセットの両方のすべての画像に同じ並び替えが適用される.
Random pixels: 各画像に個別に異なるランダムな並べ替えが適用される.
Gaussian: 各画像のランダムなピクセルを生成するために, (元の画像データセットと一致する平均と分散を持つ) ガウス分布が用いられる.

驚くべきことに, ハイパーパラメータ設定を変更しない確率的勾配降下法は, ランダムラベルが画像とラベルの関係を完全に破壊してしまうにもかかわらず, ランダムラベルに完全に適合するように重みを最適化することができる. さらに, 画像のピクセルをシャッフルしたり, ランダムなピクセルをガウス分布から完全にサンプリングし直したりすることで, 画像の構造を破壊している. しかし, 我々がテストしたネットワークはまだ適合することができる.

図 1a は, CIFAR10 データセットにおける Inception モデルの学習曲線を様々な設定で示している. すべての学習サンプルのラベル割り当てが最初は無相関であるため, ランダムなラベルで目的関数が減少し始めるまでに時間がかかると予想される. そのため, 大きな予測誤差がバックプロパゲーションされ, パラメータ更新のための大きな勾配が作られる. しかし, ランダムラベルは固定でエポック間で一貫しているので, ネットワークは訓練セットを複数回通過した後にフィッティングを開始する. a) 学習率のスケジュールを変更する必要がない; b) 一旦フィッティングが始まると, それは素早く収束する; c) 訓練セットに完全に (オーバー) フィットするように収束する. また, "ランダムピクセル" や "ガウシアン" は "ランダムラベル" よりも早く収束し始めることにも注目する必要がある. これは, ランダムピクセルの場合, 元々同じカテゴリに属する自然画像よりも, 入力が互いに分離されているため, 任意のラベル割り当てのネットワークを構築しやすいからかもしれない.

CIFAR10データセットでは, Alexnet と MLP はすべてトレーニングセットの損失がゼロに収束する. 表 1 の斜線の行は, 正確な数値と実験設定を示している. また, ImageNet データセットでランダムラベルのテストも行った. 付録の表 2 の最後の 3 行に示されているように, 完全な 100% のトップ 1 の精度には達していないが, 1000 のカテゴリからの 100 万個のランダムラベルに対して 95.20% の精度はまだ非常に驚くべきものである. 真のラベルからランダムラベルに切り替える際に, ハイパーパラメータのチューニングを行っていないことに注意する必要がある. ハイパーパラメータを変更することで, ランダムラベルでも完全な精度が得られる可能性がある. このネットワークは, 明示的な正則化器をオンにしても、$\sim$ 90% のトップ 1 の精度を達成することができる.

Partially corrupted labels 我々はさらに, CIFAR10 データセット上のラベル破損のレベルを 0 (破損なし) から 1 (完全なランダムラベル) まで変化させたニューラルネットワーク訓練の挙動を検査する. ネットワークはすべてのケースで破損した訓練セットに完全に適合していた. 図 1b は, ラベルノイズのレベルが高くなるにつれて収束時間が遅くなることを示している. 図 1c は収束後のテスト誤差を示している. 訓練誤差は常に 0 なので, テスト誤差は一般化誤差と同じである. ノイズレベルが 1 に近づくにつれて, 一般化誤差は90%に収束する.

図 1: CIFAR10 上のランダムラベルとランダムピクセルのフィット. (a) は, 様々な実験設定の訓練損失が訓練ステップとともに減衰していく様子を示している. (b)は, ラベル破損率を変えた場合の相対的な収束時間を示す. (c)は, 異なるラベル破損率の下でのテスト誤差 (訓練誤差は0なので一般化誤差も含む) を示す.

2.2 IMPLICATIONS

ランダム化実験の結果を踏まえて, 我々の発見が, 一般化についての推論のためのいくつかの伝統的なアプローチにどのような課題を投げかけているのかを議論する.

Rademacher complexity and VC-dimension. Rademacher complexity は, 仮説クラスの複雑さを表す尺度として一般的に用いられている. データセット $\{x_1, \cdots , x_n\}$ 上の仮説クラス $\mathcal{H}$ の経験的な Rademacher complexity は次のように定義される

$$\hat{\mathfrak{R}} _n(\mathcal{H}) = \mathbb{E} _{\sigma} [\sup _{h \in \mathcal{H}} \frac{1}{n} \sum^n _{i=1} \sigma _i h(x _i)]$$

ここで $\sigma_1, \cdots , \sigma_n \in$ {$\pm$ 1} は i.i.d.の一様ランダム変数である. この定義は, 我々のランダム化テストに近い. 具体的には, $\hat{\mathfrak{R}}_n(\mathcal{H})$ は, $\mathcal{H}$ がランダムな $\pm$1 のバイナリラベル割り当てに適合する能力を測定する. 我々は多クラス問題を考えているが, 同じ実験結果が保持されている関連する二値分類問題を考えるのは簡単である. 我々のランダム化テストは, 多くのニューラルネットワークがランダムなラベルで訓練セットに完全に適合することを示唆しているので, 対応するモデルクラス $\mathcal{H}$ の $\hat{\mathfrak{R}} _n(\mathcal{H}) \approx$ 1を期待する. これは, もちろん, Rademacher complexity に対する些細な上限であり, 現実的な環境では, 一般化のための有用な上限にはならない. 同様の推論は, ネットワークをさらに制限しない限り, VC-dimension とその連続的なアナログ fat-shattering dimension にも適用される. Bartlett (1998) は, ネットワークの重みに対する $l _1$ ノルム境界の観点から fat-shattering dimension の境界を証明しているが, この境界はここで考える ReLU ネットワークには適用されない. この結果は, Neyshabur et al. (2015) によって他のノルムにも一般化されたが, これらのノルムでさえ, 我々が観察している一般化の振る舞いを説明できないようである.

Uniform stability. 仮説クラスの複雑さの尺度から離れて, 代わりに学習に使用されるアルゴリズムの特性を考慮することができる. これは一般的に, 一様安定性のような安定性の概念で行われる (Bousquet & Elisseeff, 2002). アルゴリズム A の一様安定性は, アルゴリズムが単一の例の置換に対してどれだけ敏感であるかを測定する. しかし, これはアルゴリズムの特性のみであり, データの特殊性やラベルの分布を考慮に入れていない. より弱い安定性の概念を定義することも可能である (Mukherjee et al., 2002; Poggio et al., 2004; Shalev-Shwartz et al., 2010). 最弱の安定性の尺度は, bounding generalization error と直接等価であり, データを考慮に入れている. しか, この弱い安定性の概念を効果的に利用することは困難であった.

原文

Our goal is to understand the effective model capacity of feed-forward neural networks. Toward this goal, we choose a methodology inspired by non-parametric randomization tests. Specifically, we take a candidate architecture and train it both on the true data and on a copy of the data in which the true labels were replaced by random labels. In the second case, there is no longer any relationship between the instances and the class labels. As a result, learning is impossible. Intuition suggests that this impossibility should manifest itself clearly during training, e.g., by training not converging or slowing down substantially. To our surprise, several properties of the training process for multiple standard achitectures is largely unaffected by this transformation of the labels. This poses a conceptual challenge. Whatever justification we had for expecting a small generalization error to begin with must no longer apply to the case of random labels.

To gain further insight into this phenomenon, we experiment with different levels of randomization exploring the continuum between no label noise and completely corrupted labels. We also try out different randomizations of the inputs (rather than labels), arriving at the same general conclusion.

The experiments are run on two image classification datasets, the CIFAR10 dataset (Krizhevsky & Hinton, 2009) and the ImageNet (Russakovsky et al., 2015) ILSVRC 2012 dataset. We test the Inception V3 (Szegedy et al., 2016) architecture on ImageNet and a smaller version of Inception, Alexnet (Krizhevsky et al., 2012), and MLPs on CIFAR10. Please see Section A in the appendix for more details of the experimental setup.

2.1 FITTING RANDOM LABELS AND PIXELS

We run our experiments with the following modifications of the labels and input images:

True labels: the original dataset without modification.
Partially corrupted labels: independently with probability $p$, the label of each image is corrupted as a uniform random class.
Random labels: all the labels are replaced with random ones.
Shuffled pixels: a random permutation of the pixels is chosen and then the same permutation is applied to all the images in both training and test set.
Random pixels: a different random permutation is applied to each image independently.
Gaussian: A Gaussian distribution (with matching mean and variance to the original image dataset) is used to generate random pixels for each image.

Surprisingly, stochastic gradient descent with unchanged hyperparameter settings can optimize the weights to fit to random labels perfectly, even though the random labels completely destroy the relationship between images and labels. We further break the structure of the images by shuffling the image pixels, and even completely re-sampling random pixels from a Gaussian distribution. But the networks we tested are still able to fit.

Figure 1a shows the learning curves of the Inception model on the CIFAR10 dataset under various settings. We expect the objective function to take longer to start decreasing on random labels because initially the label assignments for every training sample is uncorrelated. Therefore, large predictions errors are back-propagated to make large gradients for parameter updates. However, since the random labels are fixed and consistent across epochs, the network starts fitting after going through the training set multiple times. We find the following observations for fitting random labels very interesting: a) we do not need to change the learning rate schedule; b) once the fitting starts, it converges quickly; c) it converges to (over)fit the training set perfectly. Also note that “random pixels” and “Gaussian” start converging faster than “random labels”. This might be because with random pixels, the inputs are more separated from each other than natural images that originally belong to the same category, therefore, easier to build a network for arbitrary label assignments.

On the CIFAR10 dataset, Alexnet and MLPs all converge to zero loss on the training set. The shaded rows in Table 1 show the exact numbers and experimental setup. We also tested random labels on the ImageNet dataset. As shown in the last three rows of Table 2 in the appendix, although it does not reach the perfect 100% top-1 accuracy, 95.20% accuracy is still very surprising for a million random labels from 1000 categories. Note that we did not do any hyperparameter tuning when switching from the true labels to random labels. It is likely that with some modification of the hyperparameters, perfect accuracy could be achieved on random labels. The network also manages to reach $\sim$90% top-1 accuracy even with explicit regularizers turned on.

Partially corrupted labels We further inspect the behavior of neural network training with a varying level of label corruptions from 0 (no corruption) to 1 (complete random labels) on the CIFAR10 dataset. The networks fit the corrupted training set perfectly for all the cases. Figure 1b shows the slowdown of the convergence time with increasing level of label noises. Figure 1c depicts the test errors after convergence. Since the training errors are always zero, the test errors are the same as generalization errors. As the noise level approaches 1, the generalization errors converge to 90% — the performance of random guessing on CIFAR10.

Figure 1: Fitting random labels and random pixels on CIFAR10. (a) shows the training loss of various experiment settings decaying with the training steps. (b) shows the relative convergence time with different label corruption ratio. (c) shows the test error (also the generalization error since training error is 0) under different label corruptions.

2.2 IMPLICATIONS

In light of our randomization experiments, we discuss how our findings pose a challenge for several traditional approaches for reasoning about generalization.

Rademacher complexity and VC-dimension. Rademacher complexity is commonly used and flexible complexity measure of a hypothesis class. The empirical Rademacher complexity of a hypothesis class $\mathcal{H}$ on a dataset $\{x_1, \cdots , x_n\}$ is defined as

$$\hat{\mathfrak{R}} _n(\mathcal{H}) = \mathbb{E} _{\sigma} [\sup _{h \in \mathcal{H}} \frac{1}{n} \sum^n _{i=1} \sigma _i h(x _i)]$$

where $\sigma_1, \cdots , \sigma_n \in$ {$\pm$ 1} are i.i.d. uniform random variables. This definition closely resembles our randomization test. Specifically, $\hat{\mathfrak{R}} _n(\mathcal{H})$ measures ability of $\mathcal{H}$ to fit random $\pm$1 binary label assignments. While we consider multiclass problems, it is straightforward to consider related binary classification problems for which the same experimental observations hold. Since our randomization tests suggest that many neural networks fit the training set with random labels perfectly, we expect that $\hat{\mathfrak{R}} _n(\mathcal{H}) \approx$ 1 for the corresponding model class $\mathcal{H}$. This is, of course, a trivial upper bound on the Rademacher complexity that does not lead to useful generalization bounds in realistic settings. A similar reasoning applies to VC-dimension and its continuous analog fat-shattering dimension, unless we further restrict the network. While Bartlett (1998) proves a bound on the fat-shattering dimension in terms of $l _1$ norm bounds on the weights of the network, this bound does not apply to the ReLU networks that we consider here. This result was generalized to other norms by Neyshabur et al. (2015), but even these do not seem to explain the generalization behavior that we observe.

Uniform stability. Stepping away from complexity measures of the hypothesis class, we can instead consider properties of the algorithm used for training. This is commonly done with some notion of stability, such as uniform stability (Bousquet & Elisseeff, 2002). Uniform stability of an algorithm A measures how sensitive the algorithm is to the replacement of a single example. However, it is solely a property of the algorithm, which does not take into account specifics of the data or the distribution of the labels. It is possible to define weaker notions of stability (Mukherjee et al., 2002; Poggio et al., 2004; Shalev-Shwartz et al., 2010). The weakest stability measure is directly equivalent to bounding generalization error and does take the data into account. However, it has been difficult to utilize this weaker stability notion effectively.