ポイントクラウド上の二項分類

シャッタリングはどのように見えるか

平面にn個のポイントを配置します。仮説クラスを選択します（線形分類器=直線）。このクラスがこれらのn個のポイントをラベル付けできる異なる方法の数を数えます（各側の+/-）。この数をΠ_H(n)と呼びます。

Π_H(n) = 2ⁿの場合、クラスはそのポイント集合をシャッタリングします — すべての可能なラベル付けを生成できます。Π_H(n) < 2ⁿの場合、いくつかのラベル付けは発生しません。

一般的位置の3つのポイント

ℝ²の線形分類器は、任意の3つの非共線ポイントをシャッタリングします。2³ = 8のラベル付け；すべて8つは何らかの直線で達成可能。任意の3つのポイントを選択します；各±/-ラベル付けについて、正と負を分離する直線を描きます。

4つのポイントはシャッタリングを拒否します

正方形の角に4つのポイントを配置します。対角線ペアを正としてラベル付けし、反対角線ペアを負としてラベル付けしてみてください（XORラベル付け）。直線はそれらを分離しません。したがって、Π_H(4) ≤ 14 < 16 = 2⁴です。

VC次元を最大シャッタリングサイズとして

VC(線形ℝ²) = 3。我々は3つのポイントをシャッタリングできます；4つはできません。VCは仮説クラスの最大二項分類容量をカウントします。

幾何学的直感

より高いVC = クラスがより精密な決定境界を描きます。線形（VC = d+1をd次元で）ハイパープレーンを描きます。多項式は曲線を描きます。ニューラルネットワークは非常に折り畳まれた多様体を描きます。より多くの折り畳み可能性=より多くの二項分類=より高いVC=より高いサンプル要件。

二項分類をカウントする

ℝ²の線形分類器（直線）を検討します。一般的位置に配置された5つのポイント（3つ共線ではない、冗長ではない）があります。

仮説多様体上の確率質量

PAC-Bayesを図示する

仮説空間を高次元多様体として想像します。この多様体上のすべてのポイントは、ニューラルネットワークの1つの重み設定に対応しています。事前分布Pは、この多様体全体に確率分布を割り当てます（多くの場合、初期化中心のガウス分布）。事後分布Qは、訓練データが重みを駆動した場所に確率質量を集中させます。

KL発散を幾何学的距離として

KL(Q‖P)はQがPからどれだけ漂流したかを測定します。幾何学的読み方：事後クラウドが事前クラウドからどれだけ移動したか、各事後領域が事前分布の下でどの程度ありそうにないかによって重み付けされます。

小さいKL = Qはnightlyと大きく重複します。事後はほぼ移動しません。一般化ギャップは小さいままです。

大きいKL = Q はPが小さい質量を割り当てた領域に集中しています。事後は多く移動しました。一般化ギャップは成長します。

この幾何学が重要な理由

SGDを仮説多様体全体の検索軌跡として想像してください。軌跡は訓練損失が低い盆地で終わります。PAC-Bayesは問います：この盆地はどのくらい広いですか？

広い盆地 = 低い訓練損失を達成する多くの隣接する重み設定。事後分布Qは広い領域に広がり、低リスクを保つことができます。KL(Q‖P)は限定されたままです。一般化ギャップは小さいです。

狭い盆地 = 低損失を達成する重みの細い集合のみ。事後は鋭く集中する必要があります。KLが成長します。一般化ギャップが広がります。

これは、平坦対鋭い最小値の議論に直接つながります（Hochreiter & Schmidhuber 1997、Keskar et al 2017）。平坦な最小値はより広い事後分布をサポートできるため、より小さいKLでより良く一般化できます。

盆地幅を読む

2つの訓練されたモデルは同じ訓練損失に達しますが、異なる盆地に存在します：

- モデルA： 平坦な盆地、事後分布がKL(Q_A‖P) = 50 natsの領域に広がります。

- モデルB： 鋭い盆地、事後分布がKL(Q_B‖P) = 500 natsに集中します。

両方ともn = 10,000の例で訓練され、経験的リスク0.05、δ = 0.05。

理論が上昇を予測したが実際には低下する曲線

古典的なU字曲線

水平軸にモデル容量をプロット。垂直軸にテストリスクをプロット。古典的なバイアス分散理論は予測します：

- 低容量：高バイアス、高テストリスク（アンダーフィット）

- 中容量：低バイアス+低分散、低テストリスク（スイートスポット）

- 高容量：低バイアス、高分散、高テストリスク（オーバーフィット）

結果：U字型曲線。容量をその底に選択します。

Belkin et al (2019)が観測したもの

内挿閾値を過ぎて（モデルがゼロエラーで訓練データに正確に適合する容量）、テストリスクは再び低下します。曲線は読みます：下降→内挿ピーク→2番目の下降。2つの下降、1つの曲線。

2番目の下降の幾何学的読み方

内挿閾値では、モデルはちょうど訓練データに適合する容量を持っています — 1つ（またはいくつか）の内挿解のみが存在し、それらはギザギザになる傾向があります。一般化は苦しみます。なぜなら選択されたソリューションは強制されているからです。

内挿閾値を過ぎて、多くの内挿ソリューションが存在します。SGDは滑らかなもの（最小ノルム、低曲率）を選ぶ自由があります。幾何学的像：ソリューション多様体はより広くより平坦になります。SGDの暗黙的正則化は、この平坦な多様体から良性ソリューションを選択します。テストリスクは低下します。

古典理論がこれを逃す理由

VC次元はソリューション集合容量をカウントしますが、どのソリューションが選択されるかを無視します。古典的なバウンドは最悪の場合の経験的リスク最小化を想定しています。現実：SGDは確実に最も平坦で滑らかな内挿ソリューションを選択します。全ソリューションではなくSOLVER-CHOSEN ソリューションをカウントすると、2番目の下降が理にかなっています。

幾何学的テイクホーム

容量はソリューション幾何学よりも少なく重要です。広い平坦な盆地（内挿後）は狭い鋭い盆地（内挿時）よりもよく一般化します。現代の理論は、パラメータ数ではなく盆地幅によって一般化をバウンドしようとしています。

2つの下降を位置付ける

ダブルディセント曲線では、3つの領域が重要です：（1）パラメータ化不十分なレジーム、（2）内挿ピーク、（3）パラメータ化過剰なレジーム。

パラメータトークン空間のべき乗則曲面

3D曲面

水平軸1つにパラメータNをプロット。水平軸2つにトークンDをプロット。垂直にロスLをプロット。経験的ロスはこの(N, D)平面全体にべき乗則曲面を刻みます：

L(N, D) ≈ (Nc/N)^αN + (Dc/D)^αD + L∞

曲面はNまたはDが成長するにつれて下向きに傾斜します。スロープは対数直線べき乗則に従います（ログログプロット内の直線）。漸近線L∞は正のままです — モデルが過ぎさることができない既約損失。

コンピュート最適なリッジ

総コンピュート予算C ∝ N × D（パラメータ×トークン、大体）を修正します。この制約に沿って曲面を切ります。スライストレースは3D曲面を通る2D曲線を切ります。この曲線の底=コンピュート最適なポイント。

Chinchilla（Hoffmann et al 2022）は分析的にこの底を計算しました：D_opt ≈ 20 × N。コンピュート予算に沿った曲線=リッジ。リッジに沿った移動：等コンピュート、低下するロス。リッジから離れて移動（20倍のトークンより多いパラメータ、またはより少ない）：浪費されたコンピュート。

GPT-3対Chinchillaの幾何学的読み方

GPT-3：175Bパラメータ、300Bトークン。Chinchilla最適なら175B × 20 = 3500Bトークンを望みます。GPT-3はパラメータ側方向の計算最適なリッジからはるかに外れて位置しています。Chinchilla自体：70Bパラメータ、1400Bトークンで訓練。1400 / 70 = 20 — 正確にリッジ上。Chinchillaはパラメータ数が半分未満で、幾何学的最適値に座ることによってGPT-3を破りました。

データウォールを垂直平面として

公開ウェブ〜10¹³の使用可能なトークン。これはパラメータトークン平面のD = 10¹³で垂直ウォールとしてプロット。このウォールを超えて、コンピュート最適訓練にはN ≤ D / 20 = 5 × 10¹¹パラメータが必要です。N = 5 × 10¹¹を超えるウォールは、オフリッジ（アンダートレイン）を実行するか、ウォールを外側に押し出すために合成/マルチモーダル/RLデータが必要です。

コンピュート最適なリッジを歩く

我々はGPT-3座標に位置します：N = 175Bパラメータ、D = 300Bトークン。コンピュートプロキシC = N × D = 5.25 × 10²² パラメータトークン。

ベータ事後分布が針に収縮

[0, 1]上の確率密度

Beta(α, β)は単位区間[0, 1]上の確率密度です。変数：ε =真の誤差率。形状：αは高ε側の質量を制御；βは低ε側の質量を制御します。

Beta(1, 1)： 均一 — 情報なし、[0, 1]全体のフラット密度。

Beta(α, β) withα + β大： α / (α + β)で集中したピーク。

ベータピークの幅は1/√(α+β)として収縮します。100の観測を事前に追加すると、ピークは√100 = 10倍による収縮。10000の観測を追加すると、√10000 = 100倍による収縮。

監査実行の幾何学的読み方

開始：Beta(1, 1) = [0, 1]上のフラット矩形。εについての最大不確実性。

200クエリー後8つの偽造：Beta(9, 193)。平均= 9/202 ≈ 0.045。密度は約0.045に中心化された鋭いこぶで、特性的な幅σ ≈ 0.014。

2000クエリー後80の偽造：Beta(81, 1921)。平均はまだ≈ 0.045ですが、幅σ ≈ 0.0046。こぶは3倍鋭い。

200,000クエリー後8000の偽造：Beta(8001, 192,001)。平均≈ 0.040、幅σ ≈ 0.0004。こぶは針になります。

点質量への幾何学的収束

n → ∞として、ベータ事後分布は真のεでのディラックデルタに崩壊します。幾何学：矩形→広いこぶ→狭いこぶ→針→点。各クエリーは1/√nによって我々の分布を厳密にします。

これが理論的PACバウンドを上回る理由

理論的PACバウンドは仮説クラスサイズに基づく静的なε推定を与えます。ベータ事後分布は、すべての観測に厳密にされ、実世界分布に対して較正される動的なε推定を与えます。理論的なバウンド=最悪ケース仮定の下での保証。経験的監査=実際の現実の測定。

信用区間を半分にするにはいくつのクエリーが必要ですか？

我々は現在Beta(9, 193)に位置します200クエリー後：平均ε ≈ 0.045、σ ≈ 0.014。信用区間幅を σ ≈ 0.007に半分にしたい。