シャッタリングと VC 次元

仮説空間が無限になるとき

m ≥ (1/ε)(ln|H| + ln(1/δ)) という上限は |H| = ∞ のときに破綻する。実用的な仮説クラス（ℝᵈ における線形分類器、決定木、ニューラルネットなど）はほとんど無限の候補を含む。Vapnik と Chervonenkis は 1971 年頃に、より豊かな複雑さの尺度として VC 次元 を導入してこの問題を解決した。

シャッタリング

仮説クラス H が n 個の点の集合を シャッタリング するとは、H がその n 点のすべての可能なラベル付け（2ⁿ 通りの二値分類）を生成できることを意味する。ℝ² における線形分類器は、一般の位置にある任意の 3 点をシャッタリングする。つまり、それら 3 点の 8 通りの +/− ラベル付けのそれぞれに対して、正しく分離する直線が存在する。

しかし、ℝ²における線形分類器は、XOR配置の4点をshatterすることはできません。対角線上の点の組と反対角線上の点の組を分離する直線は存在しません。

VC次元

VC(H) = Hがshatterできる点集合の最大のサイズn。2次元線形分類器の場合：VC = 3。2次元軸平行矩形の場合：VC = 4。重み数Wのニューラルネットワークの場合：VC ≤ O(W² log W)（Bartlett & Anthony 1999）。

VC次元を用いたサンプル複雑度

PAC境界式中のln|H|をVC次元dに置き換える：

m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))

VC次元は、無限の仮説クラスにおける「実効的な複雑さ」を表します。VC次元が小さい仮説クラスは少数のサンプルから汎化可能ですが、VC次元が大きいクラスはより多くのデータを必要とします。

VC次元を実効的な仮説数として捉える

ニューラルネットワークの重み数が W = 10⁹ であるとします。Bartlett-Anthonyの限界により VC ≤ O(W² log W) となります。VC ≈ W² log₂ W と近似します。

実現可能性の仮定を外す — 仮説上の事後分布

2つの重要な一般化

古典的なPAC学習では、目標概念 c が仮説クラス H の中に存在すると仮定していました。しかし現実のデータにはノイズや誤ラベル、H が表現できない概念が含まれます。これらを扱うために2つの拡張を行います。

分布非依存 PAC

c ∈ H という仮定を捨てる。代わりに、H 内の最良仮説 h* = argmin_{h ∈ H} risk(h) と競合する。バウンドの形が変わる：完全な正解に近づくのではなく、H 内で到達可能な最良性能に近づく。

分布非依存バウンド: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ サンプル数 m = O(1/ε² × (VC(H) + log(1/δ)))。分母が ε ではなく ε² になっている点に注意：分布非依存学習では同じ精度を得るために、より多くのサンプルが必要になる。

PAC-Bayes (McAllester 1999)

単一の仮説を選ぶのではなく、仮説の分布を選ぶことに移行する。事前分布 P から始め、データを観測して事後分布 Q を導出する。PAC-Bayes では Q の下での期待リスクをバウンドする：

𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]

KL(Q‖P)は、事後分布が事前分布からどれだけ移動したかを表す。2つの解釈がある：

1. 圧縮の観点。 事前分布に近い事後分布（KLが小さい）は汎化性能が良い — 情報コストが小さい = 汎化ギャップが小さい。

2. ベイズの観点。 強い事前分布 + 弱いデータ更新 = 厳しい上界；弱い事前分布 + 大きなデータ更新 = 緩い上界。

PAC-Bayesが重要な理由。 経験的PAC-Bayes上界（Catoni 2007, Dziugaite & Roy 2017）は、古典的なPAC上界が意味をなさない実用的なニューラルネットワークに対して、数値的に意味のある汎化保証を与える。これらは過剰パラメータ化されたモデルの汎化に対する最も厳密な理論的手段であり続けている。

PAC-Bayes 境界の読み方

ネットワークを n = 50,000 個のラベル付きサンプルで学習したとします。学習後、重みに関する事後分布 Q の、ガウス事前分布 P に対する KL(Q‖P) = 200 nats でした。Q における経験リスクは 0.10 です。δ = 0.05 とします。

過剰パラメータ化とダブルディセント

古典的PACの予測する災厄

古典的PACは予測する：パラメータ数がサンプル数を超えると破滅的な過学習が発生する。訓練データでは完全に学習し、テストデータではランダムに汎化する。VC限界は「学習せずに暗記する」ことを予測する。

現代のニューラルネットワークは、訓練サンプル数の10倍から1000倍ものパラメータを持ちながら、依然として汎化する。これは古典理論では起こるはずのない現象だ。しかし実際に起こっている。

我々が教わったU字曲線

古典的なバイアス-バリアンス：モデル容量が増加するにつれて訓練誤差は単調に減少する。テスト誤差は最初に減少し（アンダーフィッティングの解消）、最小値に達した後、再び上昇する（オーバーフィッティング）。このU字型はVC理論によって予測される。

実際に起こること — ダブルディセント

Belkin et al (2019) は、テスト誤差が 補間閾値（容量 = サンプル数）までは古典的なU字曲線に従うことを示した。しかし、その閾値を超えると再び誤差が低下する。極めて過剰パラメータ化されたモデルは、ちょうど十分な大きさのモデルよりも より良く 汎化する。

古典的PACがこれを見逃す理由

1. 分布自由な仮定が悲観的すぎる。 実データには構造（低内在次元、マニフォールド幾何）がある。PACバウンドは最悪ケースの分布に対して成り立つが、実分布はSGDも利用する構造を活用している。

2. 暗黙的正則化。 過剰パラメータ化されたネットワークに対するSGDは、任意の補間解ではなく、最小ノルムまたは最小複雑度の補間解を見つけ出す。古典的理論は最悪ケースの経験的リスク最小化を仮定するが、実際のアルゴリズムは良質な解を選ぶ。

3. 仮説クラスの定義が誤っている。 SGDが探索する実効的な仮説クラスは、名目上の重み空間よりもはるかに小さい。PAC-Bayes事後分布はこの点を捉えるが、VC次元は捉えない。

現代の理論研究（Bartlett, Long, Lugosi, Tsigler 2020の良質過適合に関する研究、Nakkiran et al 2020のダブルディセントに関する研究）は、過剰パラメータ化レジームを考慮したPAC以降の汎化理論を構築している。

古典的PACの失敗の診断

ある研究チームが、100,000個のラベル付きサンプルに対して10億パラメータのネットワークを訓練した。古典的PACは空虚な境界を予測するが、経験的にはテスト精度が95%に達する。

Kaplan, Chinchilla, & Sizing Automated General Intelligence [BLOCK_TYPE SECTION/STEP]

From Bounds to Empirical Scaling Laws

Classical PAC predicts dataset size theoretically & runs vacuous. Empirical scaling laws predict dataset size from observation & actually work. They have replaced PAC as our practical sizing tool for large models. [BLOCK_TYPE SECTION/STEP]

[BLOCK_TYPE SECTION/STEP]

Kaplan et al (2020)

損失はパラメータ数 N、データセットのトークン数 D、計算量 C に対してべき乗則に従う：

L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC

パラメータ数を2倍にすると損失は一定の乗法係数だけ低下する。データ量を2倍にすると損失は別の一定の係数だけ低下する。これらの指数（αN、αD、αC）は、多くの桁にわたるフロンティアの振る舞いを測定・予測する。

Hoffmann et al 2022 (Chinchilla)

ChinchillaはKaplanの指数がパラメータをデータに対して過大評価していたことを示した。計算最適な学習では、パラメータ1つあたり約20トークンが必要である：

D_opt ≈ 20 × N

GPT-3（175Bパラメータ）は約300Bトークンで学習されたが、Chinchillaの計算によれば大幅に過少学習である。計算最適な175Bパラメータモデルには約3.5兆トークンが必要となる。

データの壁

パラメータ数をスケーリングするには、トークン数も比例してスケーリングする必要があります。公開ウェブクロールから得られる有用なトークンは約10¹³です。仮に10¹⁵パラメータの自動化された汎用知能を想定する場合、必要となるトークンは約2×10¹⁶となり、ウェブ上のデータ量を3桁上回ります。

これが私たちのデータ壁です。 スケーリング則は、計算資源の不足に先立ってコーパスの不足に直面することを予測しています。合成データ、マルチモーダルコーパス（動画・音声・センサーデータ）、および環境からの強化学習（RL-from-environment）はいずれも、この壁を突破するための取り組みです。

古典的なPAC学習理論では（誤った予測として）10²¹サンプルが必要だとされていました。一方、スケーリング則（現実に基づく補正）では2×10¹⁶が必要だと示しています。どちらの数字も利用可能なテキスト量を超えています。最先端の研究は現在、このギャップを埋めることに取り組んでいます。

自動化された汎用知能のためのコーパス規模の推定

あるフロンティアラボが10¹⁴パラメータのモデルを提案し、これが自動化された汎用知能に到達すると主張しているとします。Chinchillaの法則を用いて、必要な学習コーパスの規模を求めます。

理論的境界から本番測定へ

境界の計算をやめ、測定を始めよう

古典的なPAC境界は空虚です。PAC-Bayes境界は検証が難しい仮定の下で厳密になります。実用的な代替策は、実際の分布でεを経験的に測定し、システムの運用中に更新することです。

アイデア1 — Coverageを経験的PACとして作成

make coverage ターゲットは、N件のホールドアウト質問をクエリシステムに実行させ、2つの割合を測定します：

- cache_hit_rate — システムが既知の回答を見つけた割合

- i_dont_know_rate — システムが正直に回答を保留した割合

各測定 = ベルヌーイ試行。観測されたカウントから、真の割合に対する Wilson 信頼区間 を計算する。例: N = 1000 クエリ、観測された i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]。上限 0.226 は、δ = 0.05 の PAC ε とまったく同じ役割を果たし、最悪ケースの理論解析ではなく、実データ・実分布から導出される。

古典的な PAC 用語（ε, δ, 信頼度）が適用できる。異なる仕組み（二項集中 vs. VC 理論）。実分布が利用可能な構造を持つため、より厳密な結果が得られる。

アイデア 2 — 反証イベントによる PAC-Bayes 監査

各反証（システムの回答が明らかに誤りであること）を、真の誤差率 ε の事後分布を更新する証拠として扱う：

1. 事前分布: ε ~ Beta(α₀, β₀)。弱い事前分布を選ぶ（例: Beta(1, 1) = 一様分布）。

2. 各クエリはベルヌーイ結果を生成する：改ざん (1) または保持 (0)。

3. n 回のクエリで k 回の改ざんが発生した後の事後分布： Beta(α₀ + k, β₀ + n − k)。

4. 事後平均： (α₀ + k) / (α₀ + β₀ + n) → n → ∞ で経験的改ざん率に収束。

5. ε に対する 95% 信用区間 は 1/√n で狭まる。

これにより得られるもの

- 最悪ケース理論ではなく、実際の運用から得られる実世界の ε₀ 推定値

- Anytime-valid alarm: 事後信用区間が契約閾値を超えたら担当者にページ

- Monotone confidence: 観測クエリ数が増えるほど CI が狭くなり、保証が強まる

関連手法: オンライン再校正付き共形予測 (Vovk), 逐次確率比検定 (Wald), オンライン PAC-Bayes (Haddouche & Guedj 2022). 同じ系統だが数学的枠組みが異なる。

Computing a Beta Posterior on Falsifications

Our team runs a coverage audit on a production query system. Prior on true error rate ε: Beta(1, 1) (uniform). After 200 held-out queries we observed 8 falsifications.