PAC学習とVC次元：学習可能性の理論

なぜ「学習できる」を定義する必要があるのか

「データを増やせば精度が上がる」「複雑なモデルほど過学習する」——これらは経験則として知られていますが（→ 過学習と汎化）、どれだけデータがあれば、どの程度の誤差を、どれだけの確からしさで保証できるか を定量的に言えなければ理論にはなりません。PAC学習（Probably Approximately Correct） は、この「学習できる／できない」を確率と誤差で形式化した枠組みです。そして VC次元（Vapnik-Chervonenkis dimension） は、仮説集合の表現力をたった1つの整数で測り、必要なデータ量を予言します。本記事はこの2つを軸に、なぜ複雑なモデルが多くのデータを要するかを導きます。

設定と記号

入力 x にラベル y を対応させる真の関数（概念）が存在し、データは未知の分布 D から独立に n 個サンプリングされるとします。学習器は 仮説集合 H（使える分類器の候補すべて）から1つの仮説 h を選びます。評価したいのは2種類の誤差です。

真の誤差（汎化誤差）  R(h)    = Pr_{x~D} [ h(x) ≠ y ]      未知分布上での誤り率
経験誤差（訓練誤差）  R_emp(h) = (1/n) Σ 1[ h(xi) ≠ yi ]   手元のn点での誤り率

学習器は R_emp しか観測できませんが、本当に小さくしたいのは R です。両者のズレ（汎化ギャップ）を確率的に抑えることが、学習理論の核心になります。

PAC学習の定義：Probably Approximately Correct

PAC学習は、2つの「許し」を導入して学習可能性を定義します。Approximately（近似的） は「誤差ゼロでなく ε 以下でよい」、Probably（確率的） は「常にでなく確率 1-δ で成功すればよい」という緩和です。完璧さを要求すると有限データでは不可能なので、この二重の緩和が本質的です。

この定義に必要なサンプル数 n(ε, δ) を サンプル複雑度（sample complexity） と呼びます。学習理論の主目的は、このサンプル複雑度を仮説集合の性質で見積もることです。

有限な仮説集合：和集合上界による最初の見積もり

まず H が有限（要素数 |H|）の場合を考えます。狙いは「経験誤差ゼロの仮説を選んだのに、真の誤差が ε より大きい（=悪い仮説）」という事故が起きる確率を抑えることです。

ある固定した悪い仮説（R(h) > ε）が、n 個の点をすべて正しく分類してしまう確率は、各点で正答する確率が 1-ε 未満なので高々 (1-ε)^n ≤ e^{-εn} です。悪い仮説は最大 |H| 個あるので、和集合上界（union bound） で全体を抑えます。

Pr[ いずれかの悪い仮説が経験誤差ゼロ ]  ≤  |H| · e^{-εn}

これを δ 以下にしたい：  |H| · e^{-εn} ≤ δ
両辺を整理して n について解くと：

    n  ≥  (1/ε) · ( ln|H| + ln(1/δ) )

これが有限仮説集合のサンプル複雑度です。読み取れる事実は3つあります。第一に、必要データ量は |H| の 対数 でしか増えません（候補が2倍でも ln|H| は +ln2 だけ）。第二に、信頼度 δ を上げる（小さくする）コストも ln(1/δ) と対数的で安い。第三に、精度 ε を上げるコストは 1/ε に比例し、こちらは高くつきます。

無限集合の壁とshatter（細分）

実用的な仮説集合は無限です。直線で2クラスを分ける線形分類器は、係数が連続値なので候補が無限個あり |H| = ∞。すると ln|H| が発散して上の式は無意味になります。しかし直感的には「平面上の直線」と「あらゆる曲線」では表現力が違うはずで、無限でも実効的な複雑さには差があります。これを捉えるのが shatter（細分／粉砕） の概念です。

例として、2次元平面の 線形分類器 を考えます。一般の位置にある3点なら、2^3 = 8 通りのラベル付けをすべて直線で分離でき、shatter できます。しかし4点になると、有名な XOR配置（対角の2点が正、残り2点が負）は1本の直線では分離できません。つまり2次元線形分類器は3点まで shatter できるが4点はできない——この「できる最大数」が次のVC次元です。

VC次元：表現力を1つの整数で測る

VC次元は仮説集合の 本質的な自由度 を表します。代表例を整理します。

重要な洞察は、d 次元線形分類器のVC次元が d+1、すなわち パラメータ数とほぼ一致する ことです（→ SVMとカーネル法 のマージン理論もこの容量制御と表裏一体）。一方、凸多角形のように頂点数を無制限に増やせる集合はVC次元が無限大で、有限データからは（最悪ケースで）学習を保証できません。VC次元が有限であることが、無限集合を学習可能にする条件 なのです。

成長関数とSauerの補題

shatter は「2^n 通り全部を実現できるか」という all-or-nothing でしたが、もっと細かく「実際に何通り作れるか」を測るのが 成長関数（growth function） Π_H(n) です。これは H が n 点に対して作り分けられるラベル付けの最大個数で、上限は 2^n。n がVC次元以下なら shatter できるので Π_H(n) = 2^n ですが、VC次元を超えると急にペースが落ちます。これを定量化するのが Sauerの補題（Sauer-Shelahの補題） です。

Sauerの補題：  VC(H) = d のとき、すべての n に対して

    Π_H(n)  ≤  Σ_{i=0}^{d} C(n, i)        # C(n,i) は二項係数

n ≥ d のときは多項式上界に簡約できる：

    Π_H(n)  ≤  ( e·n / d )^d  =  O(n^d)

これは学習理論で最も重要な「相転移」です。n ≤ d（VC次元以下）では成長関数は 2^n と 指数的 に増えますが、n > d を超えた瞬間、n^d の多項式 に頭打ちになります。指数から多項式へ——この抑制こそが、無限の仮説集合を有限サンプルで制御できる理由です。

汎化誤差の上界：VC次元で表す

成長関数の多項式上界を一様収束の議論（VC理論の一様大数の法則）に代入すると、無限仮説集合に対する汎化ギャップの上界が得られます。結論の形は次の通りです。

確率 1 - δ 以上で、すべての h ∈ H に対し同時に成立：

    R(h)  ≤  R_emp(h)  +  O( ルート( ( d·ln(n/d) + ln(1/δ) ) / n ) )

  R(h)     = 真の誤差（汎化誤差）
  R_emp(h) = 経験誤差（訓練誤差）
  d        = VC(H)
  n        = サンプル数

この式は学習理論のハイライトです。真の誤差は、訓練誤差にペナルティ項を足したもので上から抑えられ、ペナルティ項は おおよそ ルート（VC次元 / サンプル数） に比例します。構造を読み解きます。

• 分子の d（VC次元）：モデルの表現力。大きいほどペナルティが増える＝汎化ギャップが開きやすい。
• 分母の n（サンプル数）：データを増やせばペナルティは 1/ルートn で縮む。
• R_emp とペナルティの綱引き：複雑なモデルは R_emp を下げられるがペナルティを上げる。この和を最小化するのが 構造的リスク最小化（SRM） の発想で、正則化（→ 正則化（過学習対策））の理論的背景です。

なぜ複雑なモデルほど多くのデータを要するのか

上界式を逆に解くと、本記事の主題への答えが直接出ます。ペナルティ項を ε 以下に抑えるのに必要なサンプル数を求めると、サンプル複雑度は VC次元にほぼ比例 します。

ペナルティ ≈ ルート( d / n ) ≤ ε  を n について解くと：

    n  =  Ω( d / ε^2 )        （対数因子を除いた骨格）

  → 必要データ量は VC次元 d に線形に比例する

つまり、表現力（VC次元）が2倍のモデルは、同じ汎化誤差を保証するのに およそ2倍のデータ を要します。線形分類器ならVC次元はパラメータ数（d+1）に等しいので、パラメータを増やすほど必要データが増える という実務的直観に、理論的な根拠が与えられます。これは「自由度が高いほどノイズに合わせて訓練誤差を下げられてしまい、その分だけ汎化を保証するための証拠（データ）が余計に必要になる」という、バイアス-バリアンスの綱引き（→ バイアス-バリアンス分解と二重降下）と同じ現象を、サンプル複雑度の側から捉えたものです。

まとめ

PAC学習は「確率 1-δ で誤差 ε 以下」という二重の緩和で学習可能性を定義し、必要サンプル数をモデルの複雑さで見積もる枠組みを与えます。有限集合では ln|H| が複雑さを表し、無限集合では VC次元 がその代役を務めます。shatter できる最大点数としてのVC次元は、Sauerの補題を通じて成長関数を 2^n から n^d へ多項式化し、これが汎化上界 R(h) ≤ R_emp(h) + ルート(VC次元 / n) を可能にします。この1行が「複雑なモデルほど多くのデータを要する」を n = Ω(VC次元 / ε^2) として定量化するのです。VC理論は最悪ケースゆえ緩いものの、学習を初めて厳密に「定義」した土台であり、モデルの容量とデータ量の関係を見積もる際の出発点であり続けます。