GROKKING: GENERALIZATION BEYOND OVERFITTING ON SMALL ALGORITHMIC DATASETS

[e4exp]

• https://mathai-iclr.github.io/papers/papers/MATHAI_29_paper.pdf
• 2021 ICLR

本論文では、アルゴリズムで生成された小さなデータセット上でのニューラルネットワークの一般化を研究することを提案する。 この設定では、データの効率、記憶、一般化、学習の速度に関する問題を非常に詳細に研究することができる。 いくつかの状況では、ニューラルネットワークは、データ内のパターンを「グルーキング」するプロセスを通じて学習し、ランダムな偶然のレベルから完全な汎化へと汎化性能を向上させ、この汎化の向上はオーバーフィットの時点をはるかに超えて起こりうることを示す。 また，データセットのサイズによる汎化の違いを調べたところ，データセットが小さいほど，汎化のための最適化が必要になることがわかった． これらのデータセットは、深層学習のあまり理解されていない側面を研究するための肥沃な土壌を提供していると我々は主張する。

[e4exp]

1 はじめに

オーバーパラメータ化されたニューラルネットワークの汎化は，古典的な学習理論から導かれる直観に反しているため，機械学習のコミュニティでは長い間関心の的となってきた． 本論文では，アルゴリズムによって生成された小規模なデータセットを用いてネットワークを学習すると，学習セットの性能とは明らかに切り離された異常な汎化パターンを確実に示すことができることを示している． このような実験は、1台のGPUですぐに再現することができるため、一般化理論のテストベッドとしても便利です。

ここで、a、b、cは内部構造を持たない離散的な記号であり、◦は二項演算である。 二項演算の例としては、足し算、並べ替えの合成、二変数多項式などがある。 全ての可能な方程式の適切なサブセットに対するニューラルネットワークのトレーニングは、数独パズルを解くように、二項演算表のブランクを埋めることになります。 その例を図1の右に示します。 式に含まれるすべての要素a、b、cにはそれぞれ異なる抽象的な記号を使用しているため、ネットワークは要素の内部構造を認識せず、他の要素との相互作用からのみその特性を知ることになります。 例えば、ネットワークは10進数表記の数字や、線分表記の順列を見ることはありません。

我々の貢献は以下の通りです。

• ニューラルネットワークは、様々な二項演算表の空のスロットに一般化できることを示している。
• 重度のオーバーフィッティングを行った後、検証精度が偶然レベルから完全な一般化に向けて突然上がり始めることがあることを示す。この現象を「Grokking」と呼ぶ。その例を図1に示す。
• 様々な二項演算のデータ効率曲線を示している。
• データセットのサイズが小さくなると、一般化のために必要な最適化の量が急速に増加することを経験的に示している。
• そこで，様々な最適化手法を比較し，データ効率への影響を測定した．その結果，我々が研究しているタスクにおいては，重み減衰が一般化の改善に特に有効であることがわかった．
• また、これらのネットワークが学習したシンボルエンベッディングを可視化したところ、シンボルが表す数学的オブジェクトの認識可能な構造を発見することができた。

[e4exp]

2 METHOD

今回の実験では，a ◦ b = c という形式の方程式のデータセットで学習した小さな変換器を使用しました． 演算、アーキテクチャ、学習ハイパーパラメータ、トークン化の詳細は、付録A.1に記載されています。

3 実験

3.1 オーバーフィッティングを超えた一般化

ディープラーニングの実践者は、検証損失の減少が止まった後、検証精度が少しずつ向上することに慣れています。 検証損失の二重下降はいくつかの状況で記録されていますが、実務者の間では珍しいと考えられています（Nakkiran et al. 我々が研究している小規模なアルゴリズムのデータセットでは、初期のオーバーフィッティング後の一般化の改善が、様々なモデル、オプティマイザー、データセットのサイズで発生しており、場合によってはこれらの効果が極めて顕著に現れている。 その典型的な例が、図1のモジュール式分割である。

ここでは、トレーニングの精度が最適に近づくために必要な最適化ステップの1000倍のステップを経て初めて、検証精度がチャンスレベルを超えて向上し始めることがわかります。 また、図4では学習損失と検証損失をプロットしていますが、検証損失が2倍になっているのがわかります。 割り当てられた最適化予算内でネットワークが一般化する最小のデータセットサイズに近いデータセットサイズの場合、すべての二項演算においてこのような挙動が典型的であることがわかりました。 データセットサイズが大きくなると、学習曲線と検証曲線はより密接に追従する傾向があります。

3.1.1 学習時間曲線

一般的な教師付き学習問題では，最適化手順が学習データを補間することができる場合，学習データの量を減らすとモデルの収束した汎化性能が低下する． しかし，我々の設定では，収束性能は訓練データセットサイズの範囲内で100%で一定であるが，その性能を達成するために必要な最適化時間は，データセットサイズが小さくなるにつれて急激に増加するという，異なる現象が観察された． 図1（中央）は，抽象度グループS5の製品について，検証性能が最初に99%に達するまでの最適化ステップ数の中央値を示しています． データ量が25～30%の付近では，学習データが1%減少すると，一般化までの時間の中央値が40～50%増加します． 検証精度＞99％になるまでのステップ数は、データセットサイズの減少に伴って急速に増加しますが、訓練精度が最初に99％になるまでのステップ数は、データセットサイズの減少に伴って概ね減少傾向にあり、最適化ステップ数103～104の範囲に留まります。 データセットサイズが小さくなると、ネットワークが一般化するまでの最適化時間が指数関数的に増加するという同様のパターンが、ネットワークを一般化させることができたすべてのアルゴリズムタスクで観察されました。

3.2 様々な問題でのGROKKING

付録A.1.1に記載されている様々な二項演算について、利用可能なすべての方程式の異なる分数からなるトレーニングデータセットについて、3回の実行での平均精度を測定しました。 その結果を図2（右）に示します． 演算子はニューラルネットワークには無関係な抽象的な記号として提示されるため，素数pと非ゼロのx，yとの演算x+y（mod p-1）とx∗y（mod p）はニューラルネットワークの視点からは区別がつきません（同様にx - y（mod p - 1）とx/y（mod p）も同様）． これは、素数を基準としたゼロでない残基はすべて、原始根の累乗として表現できるからです。

図2（右）を見ると、x - yとx/yは、一般化するために必要なデータ量がほぼ同じであることがわかります。 また、図2（右）に示した演算の中には、オペランドの順番が対称となっているものがある（x + y、x ＊ y、x 2 + y 2、x 2 + xy + y 2）。 このような演算は、非対称な演算（x - y, x/y, x 2 + xy + y 2 + x）に比べて、一般化に必要なデータ量が少なくなる傾向があります。 この効果は、部分的にアーキテクチャに依存していると考えられます。 というのも、位置の埋め込みを無視してオペランドの対称関数を学習することは、変換器にとって容易なことだからです。 いくつかの操作（例えば、x 3 + xy2 + y (mod 97)）は、95%までのデータのどの割合においても、許容される最適化バジェット内で一般化につながりませんでした。 収束したモデルは、データの中に本当のパターンを見つけることなく、効果的にトレーニングデータセットを記憶するだけでした。 このようなモデルにとって、データは事実上ランダムです。 x/y (mod p) if y is odd, otherwise x - y (mod p)]という演算では、ネットワークはいくつかの単純な演算を組み合わせて学習する必要があります。 特に、xの役割は、偶数のyとペアになったときには加法群の残基として解釈され、奇数のyとペアになったときには乗法群の残基として解釈されなければなりません。

3.3 反復とトリック

データセット上でネットワークがよりよく一般化するように誘導するものは何かを調べるために、様々な形の正則化を試してみました。 ここでは、フルバッチ勾配降下法、確率的勾配降下法、学習率の大小、残留ドロップアウト（Srivastava et al.2014）、重み減衰（Loshchilov & Hutter, 2017）、勾配ノイズ（Neelakantan et al.2015）といった様々な介入について、特定のデータセットS5でのデータ効率曲線を示します。 その結果を図2（左）に示します。ウェイトディケイを追加すると、データ効率に非常に大きな効果があり、他のほとんどの介入に比べて、必要なサンプル量が半分以上になることがわかりました。 また、ネットワークの初期化に向けたウェイトディケイも効果的ですが、原点に向けたウェイトディケイほどの効果はないことがわかりました。 このことから，重みをほぼゼロにすることが小さなアルゴリズムのタスクに適しているという事前情報が，重み減衰の優れた性能のすべてではないが一部を説明していると考えられる．

最適化プロセスにノイズを加えると（ミニバッチを使用することによる勾配ノイズ、勾配を計算する前または後に重みに適用されるガウスノイズなど）、一般化に有益であり、このようなノイズが最適化を誘導してより一般化しやすい平坦な最小値を見つけるという考えと一致します。 汎化を実現するためには，学習率を比較的狭い範囲で調整する必要があることがわかりました（1桁以内）．

3.4 組込みの定性的な可視化

一般化するネットワークについての洞察を得るために、モジュラー加算とS5の場合の出力層の行列を可視化しました。 図3は、行ベクトルのt-SNEプロットです。 いくつかのネットワークでは、基礎となる数学的オブジェクトの構造が、プロットに明確に反映されていることがわかります。 例えば、モジュラー加算の円形トポロジーは、各要素に8を加えることで形成される「数列」で示されています。 このような構造は、ウェイトディケイを用いて最適化されたネットワークでより明らかになります。