こんにちは。データサイエンスチームのtmtkです。
　この記事では、Chiyuan Zhangらによる論文「Understanding deep learning requires rethinking generalization」の一部を解説・追試します。

はじめに

　今回紹介する論文「Understanding deep learning requires rethinking generalization」はディープラーニングの汎化誤差（＝訓練誤差とテスト誤差の差）についての論文です。論文中では、

• Randomization tests
• The role of explicit regularization
• Finite-sample expressivity
• The role of implicit regularization

の4つの貢献が挙げられています。この記事では、このうち「Randomization tests」と「Finite-sample expressivity」の部分について解説します。
　この論文はICLR 2017でBest Paper Awardに選出されています。

Randomization tests

　「Randomization tests」の項目は、「ディープラーニングモデルの訓練データのラベルをランダムなものに入れ替えても、モデルは学習ができる」というものです。
　論文中では、著者らはCIFAR-10とImageNetのラベルをランダムに入れ替えたものをInception V3やAlexnetなどで学習させています。
　実際に追試してみましょう。今回はGoogle Colabのノートブックで、ランタイムをPython 3 + GPUにしたもので実験しています。ライブラリはKerasを使います。
　著者らはInceptionやAlexnetなどで実験していますが、今回は時間の節約のためにより小さいネットワークで実験することにします。ネットワーク構造はKerasのMNIST用CNNの例を参考にした小さなCNNです。論文と設定を似せるためにDropoutなどの正則化は除いています。
　まず必要なライブラリをimportし、定数を定義します。

import numpy as np
import keras
from keras.datasets import cifar10
from keras.models import Model
from keras.layers import Dense, Flatten
from keras.layers import Conv2D, MaxPooling2D, Input

batch_size = 128
num_classes = 10
epochs = 100

　次に、データセットとモデルを用意する関数を定義します。データとモデルを準備して返すだけです。

def prepare():
    img_rows, img_cols = 32, 32
    (x_train, y_train), (x_test, y_test) = cifar10.load_data()
    x_train = x_train.reshape(len(x_train), img_rows, img_cols, 3)
    x_test = x_test.reshape(len(x_test), img_rows, img_cols, 3)
    
    x_train = x_train.astype("float32")
    x_test = x_test.astype("float32")
    
    x_train /= 255
    x_test /= 255
    
    ipt = Input(shape=(img_rows, img_cols, 3))
    x = Conv2D(32, (3, 3), activation="relu")(ipt)
    x = Conv2D(64, (3, 3), activation="relu")(x)
    x = MaxPooling2D((2, 2))(x)
    x = Flatten()(x)
    x = Dense(128, activation="relu")(x)
    out = Dense(num_classes, activation="softmax")(x)
    
    model = Model(inputs=[ipt], outputs=[out])
    model.compile(
        loss=keras.losses.sparse_categorical_crossentropy,
        optimizer=keras.optimizers.SGD(0.01, momentum=0.9),
        metrics=["accuracy"],
    )
    
    return x_train, x_test, y_train, y_test, model

　まずは通常通りに学習をしてみます。

x_train, x_test, y_train, y_test, model = prepare()

true_labels_history = model.fit(
    x_train, y_train,
    batch_size=batch_size,
    epochs=epochs,
    verbose=1,
    validation_data=(x_test, y_test),
    callbacks=[
        keras.callbacks.LearningRateScheduler(
            lambda _, lr: lr * 0.95
        )
    ],
)
score = model.evaluate(x_test, y_test, verbose=0)
print('Test loss:', score[0])
print('Test accuracy:', score[1])

　すると、23 epoch目で訓練データに対する正確度（accuracy）が1.0000になりました。また、学習完了後、テストデータセットに対して正確度が0.6759となりました。CIFAR-10は10クラス分類なので、正確度がランダムな1/10=0.1より大きいこのモデルはランダムよりも有意に正しく分類ができていることがわかります。
　次に、ラベルを完全にランダムに振りなおして学習をします。

x_train, x_test, y_train, y_test, model = prepare()
# ランダムなラベルを振りなおす
y_train = np.random.randint(num_classes, size=len(x_train))

random_labels_history = model.fit(
    x_train, y_train,
    batch_size=batch_size,
    epochs=epochs,
    verbose=1,
    validation_data=(x_test, y_test),
    callbacks=[
        keras.callbacks.LearningRateScheduler(
            lambda _, lr: lr * 0.95
        )
    ],
)
score = model.evaluate(x_test, y_test, verbose=0)
print('Test loss:', score[0])
print('Test accuracy:', score[1])

　今度は63 epoch目で訓練データに対する正確度が1.0000になりました。なお、学習完了後のテストデータセットに対する正確度は0.0979でした。ランダムなラベルを学習しているので、テストデータについている正常なラベルについては当然何も学習ができていません。
　これら2つの場合について、学習の推移を可視化すると以下のようになります。

　収束までのエポック数に差はありますが、ラベルや画素をランダム化した場合でも損失関数がほぼ0に収束しています。実際、どちらの場合でも訓練データに対する正確度が100%に達していました。
　つまり、この畳み込みニューラルネットワークは、ラベルがランダムな場合であっても学習データのサンプルすべてのラベルを記憶することができるということになります。
　この研究は、Mikhail Belkinらによる従来のU字型のbias-variance trade-offの「先」の現象があると主張する「Reconciling modern machine learning practice and the bias-variance trade-off」などに発展しているようです。

　なお、元の論文中では、サンプルの一部に対してラベルをランダム化する実験や、画像中の画素の位置をランダムに入れ替える実験なども行われています。また、VC次元などとの関連も議論されています。より詳しくは、元の論文をご覧ください。

（元論文の図1）

　元論文では行われていませんが、画素をランダムな一様分布から生成した場合（ x_train = np.random.random(x_train.shape) ）にも、同様に訓練誤差が0近くに収束し訓練データに対する正確度が100%に達しました。収束の様子は真のラベルの場合とランダムなラベルの場合の中間くらいでした。元の論文中の「Gaussian」（正規分布から生成した画素で学習）や「Random pixels」（画像ごとに画像内でランダムに画素を並び替えたもので学習）と同じような結果だと思います。

Finite-sample expressivity

　「Finite-sample expressivity」は、普遍近似定理（Universal approximation theorem）のサンプルサイズ有限の場合といった内容です。
　普遍近似定理はGeorge Cybenko「Approximations by superpositions of sigmoidal functions」のものが有名です。これは「[latex]\sigma \colon \mathbb{R} \to \mathbb{R}[/latex]をシグモイド関数とする。[latex]I^n = [0, 1]^n[/latex]上の任意の連続関数[latex]f \colon I^n \to \mathbb{R}[/latex]と任意の正数[latex]\epsilon > 0[/latex]に対して、[latex]\sup_{x \in I^n} |G(x) – f(x)| < \epsilon[/latex]を満たす[latex]G(x) = \sum_{j=1}^N \alpha_j \sigma(\beta_j^\mathrm T x + \theta_j) \quad (\alpha_j, \theta_j \in \mathbb{R}, \beta_j\in\mathbb{R}^n)[/latex]の形の関数が存在する」というものです。標語的にいえば、「隠れ層が1層のニューラルネットワークを使えば、隠れ層のユニット数を大きくしていくことで、『理想のモデル』にいくらでも近いモデルを（訓練や最適化さえうまくいけば）作ることができる」という感じの内容です。
　普遍近似定理で考えられている状況は、[latex]I^n[/latex]上に分布する母集団上の関数[latex]f\colon I^n \to \mathbb R[/latex]をニューラルネットワークでモデリングしているというものです。それに対して論文中で議論されている「Finite-sample expressivity」は、母集団から既に抽出されたサイズ有限のラベル付きサンプル[latex]\{(x^{(1)}, y^{(1)}), \ldots, (x^{(n)}, y^{(n)})\} \subset \mathbb{R}^d \times \mathbb{R}[/latex]があって、それを表現する関数[latex]f \colon \{x^{(1)}, \ldots, x^{(n)}\} \to \mathbb{R}; f(x^{(i)}) = y^{(i)} \quad(i = 1, \ldots, n)[/latex]をニューラルネットワークとして構成することを考えています。
　さて、本題に入ります。この論文で述べられている「Finite-sample expressivity」に関する定理は、次のものです。

Theorem 1.

There exists a two-layer neural network with ReLU activations and [latex]2n + d[/latex] weights that can represent any function on a sample of size [latex]n[/latex] in [latex]d[/latex] dimensions.

---

定理1

サイズ[latex]n[/latex]、[latex]d[/latex]次元のサンプル上の任意の関数は、[latex]2n + d[/latex]個のパラメータをもちReLUを活性化関数とする2層のニューラルネットワークで表現できる。（拙訳）

　証明は、条件を満たす2層のニューラルネットワークを具体的に構成する形で書かれています。定理の言明では「ニューラルネットワークのパラメータが[latex]2n + d[/latex]個」という部分の数え方が不明瞭ですが、証明中の構成を読むとわかります。
　論文中の証明にしたがえば、言明中のニューラルネットワークは、以下の形式で構成されます。パラメータとして[latex]w = (w_1, \ldots, w_n), b = (b_1, \ldots, b_n) \in \mathbb{R}^n, a = (a_1, \ldots, a_d)\in\mathbb{R}^d[/latex]をもち、これらのパラメータによってニューラルネットワークによる関数は

と表されます。[latex]\langle a, x\rangle[/latex]はベクトルの内積です。[latex]n[/latex]次元のパラメータが[latex]2[/latex]つと[latex]d[/latex]次元のパラメータが[latex]1[/latex]つなので、あわせて[latex]2n + d[/latex]個のパラメータをもつというわけです。
　先ほどの式は別の書き方をすると、

と書くことができます。ただしベクトルに対する[latex]ReLU(-)[/latex]はそれぞれの要素にReLU関数[latex]\mathbb{R}\ni x \mapsto \max(x, 0)\in \mathbb{R}[/latex]を適用するものとします。
　この式を踏まえて改めてこの関数をあらわすニューラルネットワークについて考えてみましょう。層の構成としては、[latex]d[/latex]ユニットの入力層と、[latex]n[/latex]ユニットの隠れ層1つと、[latex]1[/latex]ユニットの出力層からなっています。入力層から隠れ層に向けては、サイズ[latex]n\times d[/latex]の行列[latex]\begin{pmatrix}a_1 & \cdots & a_d \\ \vdots & \ddots & \vdots \\ a_1 & \cdots & a_d \end{pmatrix}[/latex]の掛け算をした後、バイアス[latex]\begin{pmatrix}b_1 \\ \vdots \\ b_n\end{pmatrix}[/latex]を足し、最後に活性化関数ReLUを通しています。隠れ層から出力層にかけては、[latex]1\times n[/latex]の行列[latex]\begin{pmatrix}w_1 \cdots w_n \end{pmatrix}[/latex]をかけて（あるいはベクトルとの内積をとって）、バイアス[latex](0)[/latex]を足し、活性化関数は使っていません（あるいは線形な活性化関数（恒等写像）を使っています）。
　注意すべき点として、階数1の行列[latex]\begin{pmatrix}a_1 & \cdots & a_d \\ \vdots & \ddots & \vdots \\ a_1 & \cdots & a_d \end{pmatrix}[/latex]について、パラメータの自由度は[latex]d[/latex]ですが行列の大きさは[latex]n \times d[/latex]であることがあります。つまり、この定理でいう「ニューラルネットワークのパラメータが[latex] 2n + d[/latex]個」というのは、ユニットの間の接続が[latex]2n+d[/latex]個なのではなく、パラメータの自由度が[latex]2n + d[/latex]だということです。
　また、隠れ層から出力層にかけての計算ではReLU関数が活性化関数として使われていないことに注意する必要があると思います。もっとも、十分大きい定数[latex]C[/latex]を用いて

とすれば、すべての層がReLU関数で活性化された[latex]2n + d + 1[/latex]個のパラメータをもつニューラルネットワークを構成することは容易です。
　論文中では、2層の場合のみならず一般に深さ[latex]k[/latex]の場合についても議論されています。こちらについても、詳細は論文をご覧ください。

まとめ

　この記事では、Chiyuan Zhangらによる論文「Understanding deep learning requires rethinking generalization」の一部を紹介・追試しました。
　ニューラルネットワークはラベルをランダムに変更して学習しても、訓練誤差を0に収束させることができます（できることがあります）。
　また、サイズ[latex]n[/latex]で[latex]d[/latex]次元のラベル付きサンプルについては、パラメータの自由度が[latex]2n + d[/latex]あれば、2層のニューラルネットワークで完全に表現することができます。
　論文では他にも正則化についてなど述べられています。詳しくは元の論文をご覧ください。