手元のデータでは正解率99%なのに、本番のデータでは70%しか当たらない。機械学習をやっていると、この「訓練ではうまくいくのにテストで崩れる」現象に必ずぶつかります。逆に、たった数千枚の画像で学習したモデルが、見たこともない画像をきちんと分類できることもあります。
ここで素朴な疑問が湧きます。有限のデータしか見ていないのに、なぜ未知のデータに対しても正しく予測できる（＝汎化できる）のでしょうか？ そして、汎化できる場合とできない場合は、何が違うのでしょうか？
この問いに数学で答えるのが統計的学習理論です。その中心にあるのが、PAC学習という枠組みと、モデルの「複雑さ」を測るVC次元・Rademacher複雑度という道具立てです。これらを理解すると、次のような実務的な判断に理論的な裏付けが与えられます。
- 過学習の制御: なぜ正則化やモデルの単純化が効くのか、「複雑さ」とは何を指すのかが式で分かる。深層学習のパラメータ数とデータ量のバランスを考える土台になります。
- 必要なデータ量の見積もり: 「この精度を達成するには最低どれくらいのサンプルが要るか」という標本複雑度の見積もりに使えます。能動学習やデータ収集計画の根拠になります。
本記事の内容
- 訓練誤差とテスト誤差のギャップ（汎化ギャップ）を確率の言葉で捉える
- PAC学習の枠組みと、一様収束がなぜ必要かの直感
- 有限仮説集合・VC次元・Rademacher複雑度という3段階の「複雑さの測り方」
- 汎化バウンドの導出（対称化のアイデア）とPythonによる複雑度の実測
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
確率の集中（平均が真の値からどれだけずれるか）の感覚があるとさらに読みやすくなりますが、本文で必要な部分はそのつど説明します。
訓練誤差とテスト誤差：本当に知りたいのはどっちか
まず言葉を整理します。仮説（モデル）を $h$ と書きます。入力 $x$ に対して $h(x)$ がラベルを予測します。真のデータは未知の分布 $\mathcal{D}$ から生まれるとします。私たちが本当に小さくしたいのは、未知データ全体に対する誤差、すなわち汎化誤差（真の誤差）です。
$$ \begin{equation} R(h) = \mathbb{E}_{(x,y)\sim \mathcal{D}}\big[\,\mathbb{1}[h(x)\neq y]\,\big] \end{equation} $$
ここで $\mathbb{1}[\cdot]$ は条件が成り立てば1、そうでなければ0を返す指示関数です。つまり $R(h)$ は「ランダムに1つデータを引いたとき、$h$ が間違える確率」です。
ところが分布 $\mathcal{D}$ は分かりません。手元にあるのは $n$ 個のサンプル $S=\{(x_1,y_1),\dots,(x_n,y_n)\}$ だけです。そこで計算できるのは、訓練データ上での誤り割合、すなわち経験誤差（訓練誤差）です。
$$ \begin{equation} \hat{R}_S(h) = \frac{1}{n}\sum_{i=1}^{n}\mathbb{1}[h(x_i)\neq y_i] \end{equation} $$
学習とは、$\hat{R}_S(h)$ を小さくする $h$ を選ぶ作業にほかなりません。でも本当に欲しいのは $R(h)$ が小さいことです。この「測れる $\hat{R}$」と「欲しい $R$」のズレこそが、汎化の問題の核心です。
下の図は、モデルの複雑さを横軸にとったときの両者の典型的な振る舞いです。
この図から大事なことが2つ読み取れます。第一に、モデルを複雑にすると訓練誤差はどこまでも下がりますが、テスト誤差はある点から逆に上がります。第二に、両者の差である汎化ギャップ $R(h)-\hat{R}(h)$ は、複雑さを上げるほど開いていきます。つまり「訓練誤差を下げる」だけでは不十分で、ギャップを抑える仕組みが要る、ということです。
では、このギャップは何で決まるのでしょうか。それを確率の言葉で定式化したものがPAC学習です。
PAC学習：確率的にだいたい正しい
「有限データから学んだモデルは、絶対に正しい」とは言えません。たまたま偏ったサンプルを引けば、どんな学習法でも失敗します。だから理論が目指すのは「ほぼ確実に、ほぼ正しい」という保証です。これを定式化したのが PAC（Probably Approximately Correct）学習です。
直感はこうです。「2つの小さな許容量 $\varepsilon$（誤差の許容）と $\delta$（失敗確率の許容）を決めたとき、十分な数のデータがあれば、確率 $1-\delta$ 以上で、汎化誤差が経験誤差から $\varepsilon$ 以内に収まる」。式で書けば、私たちが欲しいのは次のような保証です。
$$ \begin{equation} \Pr_{S\sim\mathcal{D}^n}\Big[\, R(h) \le \hat{R}_S(h) + \varepsilon \,\Big] \ge 1-\delta \end{equation} $$
「Probably」が $1-\delta$（高い確率で）に、「Approximately Correct」が $R\le\hat{R}+\varepsilon$（誤差はだいたい正しい）に対応します。$\varepsilon,\delta$ を小さくするほど強い保証ですが、その分だけ必要なサンプル数 $n$ は増えます。この $n$ を標本複雑度と呼びます。
ここで気をつけたいのは、$h$ を先に固定しておけば、この保証は比較的簡単に得られるという点です。固定した1つの $h$ について、各サンプルで $h$ が間違える事象は独立で、その平均が $\hat{R}_S(h)$、期待値が $R(h)$ です。独立な0/1確率変数の平均が期待値からずれる確率は、Hoeffingの不等式で次のように抑えられます。
$$ \begin{equation} \Pr\big[\,R(h)-\hat{R}_S(h) > \varepsilon\,\big] \le e^{-2n\varepsilon^2} \end{equation} $$
この右辺を $\delta$ と置いて $\varepsilon$ について解くと、固定した1つの $h$ に対しては $\varepsilon = \sqrt{\log(1/\delta)/(2n)}$ で保証が得られます。サンプル数 $n$ を増やせば $1/\sqrt{n}$ の速さでギャップが縮む、という嬉しい結論です。
ところが、ここに大きな落とし穴があります。学習では $h$ を先に固定していないのです。次の節でその罠を見ます。
なぜ一様収束が必要か：データを見てから選ぶ罠
Hoeffingの不等式が効くのは、「サンプルを見る前に $h$ を決めておいた」場合だけです。学習アルゴリズムは逆に、サンプルを見てから、訓練誤差を最小にする $h$ を選びます。選ばれた $h$ はサンプル $S$ に依存しているので、もはや独立性の議論がそのまま使えません。
たとえるなら、宝くじを100枚買って一番当たった1枚だけを見せ、「ほら、当選確率は高いでしょう」と言うようなものです。たくさんの候補から「たまたま訓練データに一番フィットしたもの」を選べば、その訓練誤差は本来の実力よりよく見えます。これが選択バイアスです。
この罠を避けるには、「選ばれた特定の $h$」ではなく、「仮説集合 $\mathcal{H}$ のすべての $h$ について同時に」ギャップが小さいことを保証すればよい。どれを選んでも安全なら、データを見てから選んでも安全だからです。これが一様収束（uniform convergence）の考え方です。狙うのは次の量を小さく抑えることです。
$$ \begin{equation} \sup_{h\in\mathcal{H}} \big|\, R(h) – \hat{R}_S(h) \,\big| \end{equation} $$
$\sup$（上限）は「最悪の $h$ でもこれくらい」という意味です。これが $\varepsilon$ 以下なら、どんな選び方をしてもギャップは $\varepsilon$ 以下です。
ここで自然な疑問が生まれます。$\mathcal{H}$ に含まれる仮説が増えるほど、$\sup$ をとる対象が増えてギャップは緩みそうです。では「仮説の多さ＝複雑さ」をどう数値で測ればよいのでしょうか。これが本記事の主題で、3段階で精密化していきます。まず一番単純な、仮説が有限個の場合から始めます。
有限仮説集合：union boundで素朴に数える
仮説集合 $\mathcal{H}$ が有限個、$|\mathcal{H}|$ 個の仮説からなるとします。各 $h$ について「ギャップが $\varepsilon$ を超える」という悪い事象を $A_h$ と呼びます。一様収束が破れるのは、どれか1つでも $A_h$ が起きるときです。すなわち $A_h$ の和集合が起きるときです。
和集合の確率は、それぞれの確率の和で上から抑えられます。これがunion bound（和集合上界）です。
図のように、悪事象が重なっていても重なりを無視して足し上げるので、得られる上界は緩いですが、必ず正しい安全側の見積もりになります。式で書くと次の通りです。
$$ \begin{equation} \Pr\Big[\,\exists h:\ R(h)-\hat{R}_S(h)>\varepsilon\,\Big] = \Pr\Big[\,\bigcup_{h} A_h\,\Big] \le \sum_{h\in\mathcal{H}} \Pr[A_h] \end{equation} $$
各 $\Pr[A_h]$ は固定 $h$ の話なのでHoeffingが使えて、$\Pr[A_h]\le e^{-2n\varepsilon^2}$ です。これを $|\mathcal{H}|$ 個足すと、右辺は $|\mathcal{H}|\,e^{-2n\varepsilon^2}$ になります。これ全体を失敗確率 $\delta$ で抑えたいので、次の式から始めます。
$$ |\mathcal{H}|\,e^{-2n\varepsilon^2} \le \delta $$
両辺の対数をとると $\log|\mathcal{H}| – 2n\varepsilon^2 \le \log\delta$ となります。$\varepsilon^2$ について整理すると $\varepsilon^2 \ge \dfrac{\log|\mathcal{H}| + \log(1/\delta)}{2n}$ です。最後に平方根をとって、汎化ギャップの上界が得られます。
$$ \begin{equation} \varepsilon = \sqrt{\frac{\log|\mathcal{H}| + \log(1/\delta)}{2n}} \end{equation} $$
この式は3つのことを教えてくれます。第一に、ギャップは $\sqrt{\log|\mathcal{H}|/n}$ のオーダーで縮みます。仮説の数が効くのは対数を通してなので、仮説が10倍に増えてもペナルティはわずかしか増えません。第二に、$n$ を増やせば $1/\sqrt{n}$ で縮みます。第三に、$\delta$ を小さくする（より確実にする）コストも $\log(1/\delta)$ と軽いです。
下の図は、$|\mathcal{H}|$ を変えたときにギャップ上界が $n$ とともにどう縮むかを描いたものです。
仮説数が $10$ でも $10^6$ でも、曲線は同じ $1/\sqrt{n}$ の形で下がり、両者の差は縦に少しずれるだけです。これは $\log|\mathcal{H}|$ という対数依存のおかげで、仮説数の爆発がバウンドをそれほど壊さないことを目で見せています。
しかし現実の仮説集合は、線形分類器のように無限個あります。$|\mathcal{H}|=\infty$ では $\log|\mathcal{H}|=\infty$ となり、この式は無意味になってしまいます。次は無限の仮説をどう測るかを考えます。
VC次元：無限の仮説を「区別できる点の数」で測る
線形分類器は連続的に動かせるので無限個ありますが、有限個のデータ点 $x_1,\dots,x_n$ に対する振る舞いで見れば、区別できるパターンは有限です。$n$ 点へのラベル付けは最大でも $2^n$ 通りしかないからです。「仮説集合が $n$ 点に対して実際に作り出せるラベル付けの場合の数」を成長関数 $\Pi_{\mathcal{H}}(n)$ と呼びます。
ある $n$ 点の配置について、$\mathcal{H}$ がすべての $2^n$ 通りのラベル付けを実現できるとき、「$\mathcal{H}$ はその $n$ 点をshatter（粉砕）する」と言います。どんな赤青の塗り分けにも対応できる、という意味です。
平面上の3点（一直線上にない）は、直線分類器ですべての $2^3=8$ 通りに分離できます。各パネルの破線が、その塗り分けを実現する境界線です。つまり直線分類器は3点をshatterできます。
ところが4点になると話が変わります。
対角線上の2点を同じ色にする「XOR配置」では、どんな直線を引いても赤と青を分けられません。実は平面上のどんな4点配置でも、必ず実現できないラベル付けが存在します。つまり直線分類器は4点をshatterできません。
そこで定義です。$\mathcal{H}$ がshatterできる点の最大数をVC次元（Vapnik–Chervonenkis次元） $d_{\mathrm{VC}}$ と呼びます。平面上の直線分類器なら $d_{\mathrm{VC}}=3$ です。一般に $\mathbb{R}^d$ のバイアス付き線形分類器の VC次元は $d+1$ になります。
図のように、入力の次元を上げるとVC次元も比例して増えます。これは「次元が高い＝表現力が高い＝複雑」という直感と一致します。VC次元はモデルの自由度の良い目安です。
VC次元が威力を発揮するのは、成長関数を抑える次のSauer–Shelahの補題があるからです。VC次元が $d$ なら、成長関数は次の多項式で抑えられます。
$$ \begin{equation} \Pi_{\mathcal{H}}(n) \le \sum_{i=0}^{d}\binom{n}{i} \le \left(\frac{en}{d}\right)^{d} \end{equation} $$
この補題が驚きなのは、$n\le d$ までは成長関数が $2^n$（指数）で増えるのに、$n>d$ を超えた途端に $n^d$（多項式）に折れ曲がる点です。証明（二重帰納法）は記事末の補遺 (E) で全行たどります。
赤線の $2^n$（もし常にshatterできるなら）に対し、青線の成長関数は $n=d=3$ までは赤線と一致し、それ以降は緑の多項式 $n^d$ に沿って穏やかに増えます。指数から多項式への「相転移」が、無限仮説でも汎化を可能にする鍵です。
この多項式の成長関数を union bound の $|\mathcal{H}|$ の代わりに使うと、無限仮説集合に対するVCバウンドが得られます（細かい定数は流儀で違いますが、形は次の通りです）。
$$ \begin{equation} R(h) \le \hat{R}_S(h) + O\!\left(\sqrt{\frac{d_{\mathrm{VC}}\,\log n}{n}}\right) \end{equation} $$
$\log|\mathcal{H}|$ が $d_{\mathrm{VC}}\log n$ に置き換わった形です。VC次元が有限なら、$n\to\infty$ でギャップは0に収束します。これが「VC次元が有限なら学習可能（PAC学習可能）」という統計的学習理論の金字塔です。
ただしVC次元には弱点があります。ラベルの値だけを見る0/1の組合せ量なので、データ分布を無視した最悪ケース評価になりがちで、しばしば過度に悲観的です。もっとデータに即して、しかも実際に推定できる複雑さの尺度が欲しい。それがRademacher複雑度です。
Rademacher複雑度：ランダムノイズへのfit度で複雑さを測る
Rademacher複雑度の発想は、驚くほど直接的です。「ランダムに振ったコイン（＝でたらめなラベル）に、そのモデルがどれだけうまくフィットできるか」で複雑さを測ります。なんでも当てはめられる柔軟なモデルは、意味のないノイズにすら合わせられる。逆に、シンプルなモデルはノイズに合わせられません。この「ノイズへのフィット度」こそ過学習しやすさそのものだ、というアイデアです。
具体的には、各サンプルに独立なRademacher変数 $\sigma_i\in\{+1,-1\}$（コイン投げで等確率）を割り当てます。経験Rademacher複雑度は次で定義されます。
$$ \begin{equation} \hat{\mathfrak{R}}_S(\mathcal{H}) = \mathbb{E}_{\sigma}\left[\, \sup_{h\in\mathcal{H}} \frac{1}{n}\sum_{i=1}^{n}\sigma_i\, h(x_i) \,\right] \end{equation} $$
中身を読み解きましょう。$\frac{1}{n}\sum_i \sigma_i h(x_i)$ は、$h$ の出力 $h(x_i)$ とランダム符号 $\sigma_i$ の相関です。$h$ がランダム符号にぴったり合えば（$h(x_i)$ の符号が $\sigma_i$ と一致すれば）この和は大きくなります。$\sup_h$ で「$\mathcal{H}$ の中で一番うまく合わせられる $h$」を選び、$\mathbb{E}_\sigma$ でコインの引き方を平均します。結局これは「仮説集合がランダムラベルに合わせられる平均的な能力」を表します。値は $0$（まったく合わせられない）から $1$（どんなノイズにも完璧に合わせられる）の範囲になります。
この量はデータ $x_1,\dots,x_n$ さえあれば（ラベル $y$ がなくても）モンテカルロで推定できます。次の図は、複雑さの異なるモデルでランダムラベルへのfit度を実測したものです。
データを区間に分けて各区間に定数ラベルを割り当てる分類器を、分割数を増やしながら比べました。区間が細かいほど（＝複雑なほど）ランダムラベルへのfit度が上がり、各点を自由にラベル付けできる最も複雑なモデルではfit度が $1.0$ に達します。複雑なモデルほどノイズに合わせられる＝Rademacher複雑度が高い、という主張が数値で確認できます。
Rademacher複雑度の良いところは、union boundやSauer–Shelahのような組合せの近似を経由せず、汎化バウンドに直接つながることです。次にその橋渡しを見ます。
汎化バウンドの導出：対称化でRademacherが現れる
ゴールは、Rademacher複雑度を使って一様収束を保証する次のバウンドを示すことです。確率 $1-\delta$ 以上で、すべての $h\in\mathcal{H}$ について次が成り立ちます。
$$ \begin{equation} R(h) \le \hat{R}_S(h) + 2\,\mathfrak{R}_n(\mathcal{H}) + \sqrt{\frac{\log(1/\delta)}{2n}} \end{equation} $$
導出の流れは2段階です。第1段：集中。一様収束のギャップ $\Phi(S)=\sup_h(R(h)-\hat{R}_S(h))$ は、サンプルを1つ入れ替えても大きくは変わりません（1点の影響は高々 $1/n$）。このような「入力の1成分を変えても出力が少ししか動かない関数」は、その期待値の周りに鋭く集中します。これを保証するのがMcDiarmidの不等式で、確率 $1-\delta$ 以上で次が成り立ちます。
$$ \Phi(S) \le \mathbb{E}_S[\Phi(S)] + \sqrt{\frac{\log(1/\delta)}{2n}} $$
これでバウンドの最後の項（信頼項）が出ました。残るは期待値 $\mathbb{E}_S[\Phi(S)]$ を $2\mathfrak{R}_n(\mathcal{H})$ で抑えることです。
第2段：対称化（symmetrization）。$\Phi(S)$ の中には真の誤差 $R(h)=\mathbb{E}[\cdots]$ という、直接は触れない期待値が入っています。そこで頭の中だけでもう1組の独立なサンプル $S’$（ゴースト標本）を用意し、$R(h)$ をこのゴースト標本上の経験誤差で置き換えます。すると2つのサンプル $S$ と $S’$ は対称（どちらも同じ分布から独立に引いた）なので、各点で「$S$ と $S’$ のどちらを使うか」を入れ替えても分布は変わりません。この入れ替えを表すのが、まさにランダム符号 $\sigma_i\in\{\pm1\}$ です。
この対称化の操作を経ると、扱いにくかった「真の誤差を含むギャップの期待値」が、ランダム符号との相関の期待値、すなわち $2\mathfrak{R}_n(\mathcal{H})$ で上から抑えられます。図の3つの箱が、その橋渡しの流れです。係数の $2$ は、$S$ と $S’$ の2組から来ています。2段階を合わせると、先のバウンドが得られます。McDiarmidで「$\Phi$ が1標本あたり $1/n$ しか動かない」ことの証明、対称化でJensenと符号反転を使う各行、そして係数 $3$ がどこから来るかは、記事末の補遺 (B)(C)(D) で省略なく追います。
このバウンドの形は、有限仮説やVCのときと本質的に同じ「経験誤差＋複雑さの項＋信頼の項」という3層構造です。違いは、複雑さの項が $\sqrt{\log|\mathcal{H}|/n}$ でも $\sqrt{d_{\mathrm{VC}}\log n/n}$ でもなく、データに即した $\mathfrak{R}_n(\mathcal{H})$ で測られている点です。
図は3要素の積み上げです。経験誤差（青）はモデルの実力で決まりますが、複雑度項（オレンジ）と信頼項（緑）は $n$ が増えるほど $1/\sqrt{n}$ で縮みます。データを増やせばバウンド全体が下がる、という汎化の本質が一目で分かります。
ここまでで「複雑さがバウンドを緩める」ことが分かりました。では複雑さは小さければ小さいほど良いのでしょうか。最後にそのトレードオフを整理します。
表現力と汎化のトレードオフ
バウンド $R(h) \le \hat{R}_S(h) + (\text{複雑さの項})$ を眺めると、相反する2つの力が見えます。
- 経験誤差 $\hat{R}_S(h)$ を下げたい → モデルを複雑にして表現力を上げたい
- 複雑さの項を下げたい → モデルを単純にして複雑度を下げたい
この綱引きが、おなじみのバイアス・バリアンスのトレードオフの正体です。単純すぎるモデルは経験誤差が高く（高バイアス）、複雑すぎるモデルは複雑度の項が大きくギャップが開きます（高バリアンス）。両者の和は中間でU字の最小をとります。
図の黒い実線（テスト誤差の上界）が、近似誤差（青の破線、下がる）と複雑度ペナルティ（赤の破線、上がる）の和としてU字を描き、緑の点で最小になります。最適なモデルの複雑さは、データ量 $n$ に応じて決まるのです。$n$ が増えれば複雑度項が縮むので、より複雑なモデルを許せる。これが「データが多いほど大きなモデルを使える」という経験則の理論的な説明です。
正則化やearly stopping、モデルサイズの制限はすべて、この複雑度の項を制御してギャップを抑える操作だと理解できます。次は、ここまでの話をPythonで実際に手を動かして確かめます。
Pythonで実装：Rademacher複雑度を測る
理論の主張「複雑なモデルほどランダムラベルへのfit度（Rademacher複雑度）が高い」を、モンテカルロ推定で確かめます。1次元データを区間に分割して各区間に定数ラベルを割り当てる分類器の族を考え、分割数を複雑さのつまみとして動かします。
まずデータと、ランダムラベルへの最良フィットを計算する関数を用意します。
import numpy as np
rng = np.random.default_rng(42)
n = 20
x = np.sort(rng.uniform(0, 1, n)) # 1次元データ点
def best_fit_kpiece(sigma, k):
"""ソート済みn点を連続するk区間に等分割し、各区間で多数決ラベルを置く。
k区間に定数ラベルを割り当てる区分一定分類器の表現力に対応する。
戻り値はランダム符号 sigma への最良一致率。"""
cells = np.array_split(np.arange(n), k)
correct = 0
for c in cells:
if len(c) == 0:
continue
s = sigma[c]
# その区間を +1 にするか -1 にするか、多い方を採用
correct += max((s == 1).sum(), (s == -1).sum())
return correct / n
array_split で点を連続するブロックに分けるのがポイントです。区間が細かいほど（$k$ が大きいほど）、各区間で別々のラベルを選べるので、でたらめな $\sigma$ にも合わせやすくなります。
次に、各分割数についてランダム符号を何度も振り、経験Rademacher複雑度 $\hat{\mathfrak{R}}_S$ を推定します。最良一致率 $p$ と相関の関係は $\frac{1}{n}\sum_i \sigma_i h(x_i) = 2p – 1$ です（全一致で $p=1\Rightarrow 1$、半々で $p=0.5\Rightarrow 0$）。
trials = 4000
ks = [2, 5, 10, n]
labels = ["区間2分割", "区間5分割", "区間10分割", "各点自由 (n分割)"]
rad_means = []
for k in ks:
vals = []
for _ in range(trials):
sigma = rng.choice([-1, 1], size=n)
p = best_fit_kpiece(sigma, k) # 最良一致率
vals.append(2 * p - 1) # 相関 = Rademacher の中身
rad_means.append(np.mean(vals))
for lab, r in zip(labels, rad_means):
print(f"{lab:16s}: R_hat = {r:.3f}")
実行すると、おおよそ次の値が得られます（seed=42）。
区間2分割 : R_hat = 0.245
区間5分割 : R_hat = 0.376
区間10分割 : R_hat = 0.502
各点自由 (n分割) : R_hat = 1.000
分割数を増やすほど経験Rademacher複雑度が単調に増え、各点を自由にラベル付けできる最も複雑なモデルでちょうど $1.0$ に達します。「複雑なモデルほどノイズに合わせられる＝Rademacher複雑度が高い」という理論の主張が、数値で再現できました。各点自由のモデルが $1.0$ なのは、どんな $\sigma$ にも完璧に一致できる（過学習し放題）ことを意味します。
最後に、この複雑度がそのまま汎化バウンドにどう効くかを、サンプル数 $n$ を変えて確認します。経験Rademacher複雑度はおおよそ $1/\sqrt{n}$ で縮むので、バウンド全体も縮みます。
import numpy as np
def rademacher_kpiece(n, k, trials=2000, seed=0):
rng = np.random.default_rng(seed)
vals = []
for _ in range(trials):
sigma = rng.choice([-1, 1], size=n)
cells = np.array_split(np.arange(n), k)
correct = sum(max((sigma[c] == 1).sum(), (sigma[c] == -1).sum())
for c in cells if len(c) > 0)
vals.append(2 * (correct / n) - 1)
return np.mean(vals)
delta = 0.05
emp_err = 0.10 # 仮の経験誤差
print(" n | R_hat | バウンド上界")
for n in [50, 200, 1000]:
r = rademacher_kpiece(n, k=4, seed=1)
bound = emp_err + 2 * r + np.sqrt(np.log(1 / delta) / (2 * n))
print(f"{n:5d} | {r:.3f} | {bound:.3f}")
実行結果はおおよそ次の通りです。
n | R_hat | バウンド上界
50 | 0.227 | 0.727
200 | 0.112 | 0.411
1000 | 0.051 | 0.240
サンプル数が $50\to1000$ と増えるにつれ、経験Rademacher複雑度が $0.23\to0.05$ と縮み、汎化バウンドの上界も $0.73\to0.24$ と下がります。複雑さを固定しても、データを増やせばギャップが閉じていく、という汎化の本質がそのまま数値に現れました。理論の3層構造（経験誤差＋複雑度項＋信頼項）のうち、後ろの2項が $n$ とともに消えていく様子が確認できます。
ここまでで全体の流れと直感はそろいました。しかし本文ではいくつかの定理（Hoeffding、McDiarmid、対称化、Sauer–Shelah）を「成り立つもの」として使ってきました。この分野が初めての読者でも、補題から1行ずつ自分でたどれるように、以下の補遺で主要な証明をすべて埋めます。ここを読めば、本記事だけで汎化バウンドを最後まで自力で再構成できます。
補遺：飛ばした証明をすべて埋める
この補遺は読み飛ばしても大丈夫です。 ここから先は、本文で結果だけ使った定理を補題から一行ずつ証明する部分です。前半までで「なぜ汎化するのか」のイメージは押さえられているので、結論を使えれば十分という方は次の節へ進んでください。証明を自分の手で追いたい方、論文の付録を読めるようになりたい方のための部分です。
ここからは、本文で結果だけ使った定理を、標準的な教科書（Mohri Foundations of Machine Learning、Shalev-Shwartz & Ben-David Understanding Machine Learning）に沿って全行たどります。読む順番は本文と同じで、(A) 有限仮説集合の一様収束 → (B) McDiarmidの不等式 → (C) 対称化補題 → (D) Rademacher汎化バウンドの完成 → (E) Sauer–Shelahの補題 → (F) Massartの有限補題、と積み上げます。最後に (E)(F) を合流させると、成長関数からVCバウンド $\varepsilon\sim\sqrt{d\log n / n}$ までが一本の論理でつながります。
記号を最初に確認します。損失を $\ell(h,z)\in[0,1]$（$z=(x,y)$ は1つのサンプル）と書き、$R(h)=\mathbb{E}_{z}[\ell(h,z)]$（真の誤差）、$\hat{R}_S(h)=\frac{1}{n}\sum_{i=1}^n \ell(h,z_i)$（経験誤差）とします。0/1損失 $\ell(h,z)=\mathbb{1}[h(x)\neq y]$ はこの $[0,1]$ の特別な場合です。$z_1,\dots,z_n$ は分布 $\mathcal{D}$ から独立同分布（i.i.d.）に引いたものとします。
補題0：Hoeffdingの不等式（道具の確認）
すべての出発点はHoeffdingの不等式です。本記事では証明済みの道具として使いますが、形だけ明示しておきます。$U_1,\dots,U_n$ が独立で $U_i\in[a_i,b_i]$、$\bar U=\frac1n\sum_i U_i$ とすると、任意の $t>0$ で
$$ \begin{equation} \Pr\big[\,\bar U – \mathbb{E}[\bar U] > t\,\big] \le \exp\!\left(-\frac{2n^2 t^2}{\sum_{i=1}^n (b_i-a_i)^2}\right) \end{equation} $$
が成り立ちます（証明はマルコフの不等式＋指数モーメント＋Hoeffdingの補題による。詳細は前提記事の集中不等式を参照）。いまは $\ell(h,z_i)\in[0,1]$ なので $b_i-a_i=1$、$\sum_i(b_i-a_i)^2=n$ です。$U_i=\ell(h,z_i)$ とおくと $\bar U=\hat R_S(h)$、$\mathbb{E}[\bar U]=R(h)$。$t=\varepsilon$ を代入すると
$$ \begin{equation} \Pr\big[\,R(h)-\hat R_S(h) > \varepsilon\,\big]=\Pr\big[\,\hat R_S(h)-R(h) < -\varepsilon\,\big]\le e^{-2n\varepsilon^2} \end{equation} $$
を得ます（左右どちら向きの偏差も同じ形）。これが本文の固定 $h$ に対するバウンドの正体です。
(A) 有限仮説集合の一様収束：union bound × Hoeffding
主張：$\mathcal{H}$ が有限で $|\mathcal{H}|<\infty$ のとき、
$$ \begin{equation} \Pr\Big[\,\sup_{h\in\mathcal{H}} \big(R(h)-\hat R_S(h)\big) > \varepsilon\,\Big] \le |\mathcal{H}|\,e^{-2n\varepsilon^2} \end{equation} $$
証明（全行）。各 $h$ について悪い事象を $A_h=\{R(h)-\hat R_S(h)>\varepsilon\}$ と定義します。「最悪の $h$ でも $\varepsilon$ を超える」という事象 $\{\sup_h (R(h)-\hat R_S(h))>\varepsilon\}$ は、$\mathcal{H}$ が有限なので「どれか1つの $h$ で $A_h$ が起きる」、すなわち和集合 $\bigcup_{h\in\mathcal{H}} A_h$ とちょうど一致します（上限を超えるものが存在する $\iff$ ある $h$ で超える）。よって
$$ \Pr\Big[\sup_{h}(R(h)-\hat R_S(h))>\varepsilon\Big]=\Pr\Big[\bigcup_{h\in\mathcal{H}}A_h\Big]. $$
ここで確率の劣加法性（union bound）を使います。任意の事象の列に対し $\Pr[\bigcup_h A_h]\le \sum_h \Pr[A_h]$ が成り立ちます（証明：$\Pr[A\cup B]=\Pr[A]+\Pr[B]-\Pr[A\cap B]\le \Pr[A]+\Pr[B]$ を帰納的に繰り返すだけ）。これを適用すると
$$ \Pr\Big[\bigcup_{h}A_h\Big]\le \sum_{h\in\mathcal{H}}\Pr[A_h]. $$
各 $A_h$ は固定された $h$ の事象なので補題0が使えて $\Pr[A_h]\le e^{-2n\varepsilon^2}$。これを $|\mathcal{H}|$ 個足し上げると $\sum_h \Pr[A_h]\le |\mathcal{H}|\,e^{-2n\varepsilon^2}$ となり、主張を得ます。$\blacksquare$
$\varepsilon$ を解く。右辺を失敗確率 $\delta$ で抑えたいので $|\mathcal{H}|\,e^{-2n\varepsilon^2}\le\delta$ から出発します。両辺の自然対数をとると（対数は単調増加なので不等号の向きは保たれます）
$$ \log|\mathcal{H}| – 2n\varepsilon^2 \le \log\delta. $$
$-2n\varepsilon^2$ を右辺へ、$\log\delta$ を左辺へ移すと $\log|\mathcal{H}|+\log(1/\delta)\le 2n\varepsilon^2$（$-\log\delta=\log(1/\delta)$ を使いました）。両辺を $2n$ で割って平方根をとると、確率 $1-\delta$ 以上ですべての $h\in\mathcal{H}$ について
$$ \begin{equation} R(h)\le \hat R_S(h)+\sqrt{\frac{\log|\mathcal{H}|+\log(1/\delta)}{2n}}\;,\qquad \varepsilon\sim\sqrt{\frac{\log|\mathcal{H}|}{n}}. \end{equation} $$
これで本文の有限仮説バウンドが補題0から全行で出ました。仮説数 $|\mathcal{H}|$ は対数を通してしか効かない、というのがこの導出の核心です。
(B) McDiarmidの不等式と「1標本変えても $\Phi$ は $1/n$ しか動かない」
無限仮説へ進む前に、汎化バウンドの「信頼項」を生むMcDiarmidの不等式（有界差分不等式）を準備します。
主張（McDiarmid）：関数 $f(z_1,\dots,z_n)$ が有界差分条件を満たす、すなわち各 $i$ について、$i$ 番目の引数だけを $z_i\to z_i’$ と変えても値の変化が高々 $c_i$、
$$ \sup_{z_1,\dots,z_n,z_i’}\big|f(\dots,z_i,\dots)-f(\dots,z_i’,\dots)\big|\le c_i, $$
とする。このとき独立な $z_1,\dots,z_n$ に対し、任意の $t>0$ で
$$ \begin{equation} \Pr\big[\,f-\mathbb{E}[f] > t\,\big]\le \exp\!\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right). \end{equation} $$
（証明はDoob martingale差分列 $V_i=\mathbb{E}[f\mid z_1,\dots,z_i]-\mathbb{E}[f\mid z_1,\dots,z_{i-1}]$ を作り、各 $|V_i|\le c_i$ を示してAzuma–Hoeffdingを適用する。詳細は前提記事の集中不等式に譲り、ここでは結果を使います。Hoeffdingは $f=\frac1n\sum U_i$ という特別な場合に対応します。）
$\Phi$ への適用。一様収束のギャップを $\Phi(S)=\Phi(z_1,\dots,z_n)=\sup_{h\in\mathcal{H}}\big(R(h)-\hat R_S(h)\big)$ と定義します。これが有界差分条件を $c_i=1/n$ で満たすことを示します。$i$ 番目だけ $z_i\to z_i’$ と差し替えたサンプルを $S’$ とします。任意の関数 $g$ について $\sup_h g_1(h)-\sup_h g_2(h)\le \sup_h\big(g_1(h)-g_2(h)\big)$ が成り立つ（上限の差は差の上限以下）ので、
$$ \Phi(S)-\Phi(S’)\le \sup_{h}\Big[\big(R(h)-\hat R_S(h)\big)-\big(R(h)-\hat R_{S’}(h)\big)\Big]=\sup_h\big(\hat R_{S’}(h)-\hat R_S(h)\big). $$
ここで $R(h)$ は $S$ にも $S’$ にも依らず同じなので相殺しました。経験誤差の差は、変えた1点 $i$ の損失の差だけで決まります。
$$ \hat R_{S’}(h)-\hat R_S(h)=\frac1n\big(\ell(h,z_i’)-\ell(h,z_i)\big). $$
損失は $[0,1]$ なので $\ell(h,z_i’)-\ell(h,z_i)\le 1$、したがって $\hat R_{S’}(h)-\hat R_S(h)\le 1/n$ がすべての $h$ で成り立ち、$\sup$ をとっても $\le 1/n$ です。同じ議論を $S$ と $S’$ を入れ替えて行えば $\Phi(S’)-\Phi(S)\le 1/n$ も得られるので、
$$ \big|\Phi(S)-\Phi(S’)\big|\le \frac1n\qquad(\text{有界差分条件 }c_i=1/n). $$
これが「1標本変えても $\Phi$ は高々 $1/n$ しか動かない」という、本文で口頭説明した事実の証明です。McDiarmidを $c_i=1/n$ で適用すると $\sum_i c_i^2=n\cdot(1/n)^2=1/n$ なので、$\exp(-2t^2/(1/n))=\exp(-2nt^2)$。右辺を $\delta$ と置いて $t$ を解くと $t=\sqrt{\log(1/\delta)/(2n)}$。よって確率 $1-\delta$ 以上で
$$ \begin{equation} \Phi(S)\le \mathbb{E}_S[\Phi(S)]+\sqrt{\frac{\log(1/\delta)}{2n}}. \end{equation} $$
これがバウンドの信頼項です。残りは期待値 $\mathbb{E}_S[\Phi(S)]$ を Rademacher 複雑度で抑えることで、それを担うのが次の対称化補題です。
(C) 対称化（symmetrization）補題：ゴースト標本とRademacher変数
主張：
$$ \begin{equation} \mathbb{E}_S[\Phi(S)]=\mathbb{E}_S\Big[\sup_{h}\big(R(h)-\hat R_S(h)\big)\Big]\le 2\,\mathfrak{R}_n(\mathcal{H}), \end{equation} $$
ただし $\mathfrak{R}_n(\mathcal{H})=\mathbb{E}_{S,\sigma}\Big[\sup_h \frac1n\sum_{i=1}^n \sigma_i\,\ell(h,z_i)\Big]$ は（損失クラスの）Rademacher複雑度、$\sigma_i\in\{+1,-1\}$ は等確率独立なRademacher変数です。
なぜゴースト標本か（初見向けの動機）。困りごとは $\Phi$ の中の $R(h)=\mathbb{E}_{z}[\ell(h,z)]$ が「未知分布上の期待値」で、直接は手が出せない点です。アイデアは、この触れない期待値を、頭の中だけで用意したもう1組の独立サンプル $S’=\{z_1′,\dots,z_n’\}$（ゴースト標本、実在しなくてよい）の経験平均で置き換えることです。$S’$ も同じ分布から i.i.d. なので $\mathbb{E}_{S’}[\hat R_{S’}(h)]=R(h)$。これで「期待値」を「もう1つの経験平均」に化けさせ、$S$ と $S’$ という対称な2つの標本の差に持ち込みます。対称だからこそ、各点で「どちらの標本を引いたことにするか」を入れ替えても分布が変わらない——その入れ替えを表すのが符号 $\sigma_i\in\{\pm1\}$ です。
証明（全行）。まず $R(h)=\mathbb{E}_{S’}[\hat R_{S’}(h)]$ を $\Phi$ の定義に代入します。
$$ \mathbb{E}_S[\Phi(S)]=\mathbb{E}_S\Big[\sup_h\big(\mathbb{E}_{S’}[\hat R_{S’}(h)]-\hat R_S(h)\big)\Big]. $$
$\hat R_S(h)$ は $S’$ に依らない定数なので期待値 $\mathbb{E}_{S’}$ の中に入れられ、上限と期待値の順序交換ではJensenの不等式（$\sup$ は凸、$\sup_h \mathbb{E}_{S’}[\cdot]\le \mathbb{E}_{S’}[\sup_h \cdot]$）を使って期待値を外へ出します。
$$ \mathbb{E}_S[\Phi(S)]\le \mathbb{E}_{S,S’}\Big[\sup_h\big(\hat R_{S’}(h)-\hat R_S(h)\big)\Big]=\mathbb{E}_{S,S’}\Big[\sup_h \frac1n\sum_{i=1}^n\big(\ell(h,z_i’)-\ell(h,z_i)\big)\Big]. $$
ここが対称化の山場です。$z_i$ と $z_i’$ はどちらも同じ分布から独立に引いた、交換しても同時分布が変わらないペアです。よって各項 $\ell(h,z_i’)-\ell(h,z_i)$ を $\ell(h,z_i)-\ell(h,z_i’)$ に符号反転しても、$(S,S’)$ 全体の分布は不変です。この「項ごとに独立に符号を反転してよい」という自由度を、独立なRademacher変数 $\sigma_i\in\{\pm1\}$ で表します。すなわち任意の固定符号列に対して期待値が等しいので、$\sigma$ についても平均してよく、
$$ \mathbb{E}_{S,S’}\Big[\sup_h \frac1n\sum_i\big(\ell(h,z_i’)-\ell(h,z_i)\big)\Big] =\mathbb{E}_{S,S’,\sigma}\Big[\sup_h \frac1n\sum_i \sigma_i\big(\ell(h,z_i’)-\ell(h,z_i)\big)\Big]. $$
最後に上限を2つに分けます。$\sup_h(a(h)+b(h))\le \sup_h a(h)+\sup_h b(h)$ より、
$$ \begin{aligned} &\mathbb{E}_{S,S’,\sigma}\Big[\sup_h \frac1n\sum_i \sigma_i\,\ell(h,z_i’)\Big] +\mathbb{E}_{S,S’,\sigma}\Big[\sup_h \frac1n\sum_i (-\sigma_i)\,\ell(h,z_i)\Big]. \end{aligned} $$
第1項は $z’$ だけ、第2項は $z$ だけに依存します。$-\sigma_i$ も $\sigma_i$ と同分布（$\pm1$ 等確率）なので符号を吸収でき、2つの項はどちらも $\mathbb{E}_{S,\sigma}[\sup_h \frac1n\sum_i\sigma_i\ell(h,z_i)]=\mathfrak{R}_n(\mathcal{H})$ に等しくなります。よって合計は $2\mathfrak{R}_n(\mathcal{H})$。これで主張が示せました。$\blacksquare$ 係数の $2$ が、$S$ と $S’$ という2組から来ていることがはっきり見えます。
(D) Rademacher汎化バウンドの完成
(B) のMcDiarmid
$$ \Phi(S)\le \mathbb{E}_S[\Phi(S)]+\sqrt{\frac{\log(1/\delta)}{2n}}\quad(\text{確率 }1-\delta\text{ 以上}) $$
に、(C) の対称化 $\mathbb{E}_S[\Phi(S)]\le 2\mathfrak{R}_n(\mathcal{H})$ を代入すると、確率 $1-\delta$ 以上で
$$ \sup_h\big(R(h)-\hat R_S(h)\big)=\Phi(S)\le 2\mathfrak{R}_n(\mathcal{H})+\sqrt{\frac{\log(1/\delta)}{2n}}. $$
左辺が上限なので、これはすべての $h\in\mathcal{H}$ について $R(h)-\hat R_S(h)$ がこの値以下、という意味です。移項すると本文のバウンド
$$ \begin{equation} R(h)\le \hat R_S(h)+2\mathfrak{R}_n(\mathcal{H})+\sqrt{\frac{\log(1/\delta)}{2n}} \end{equation} $$
を得ます。さらに、経験Rademacher複雑度 $\hat{\mathfrak{R}}_S(\mathcal{H})$（$S$ を固定して $\sigma$ だけで平均した量）は $S$ の関数として再び有界差分 $c_i=1/n$ を満たすので、もう一度McDiarmidを適用すると $\mathfrak{R}_n(\mathcal{H})\le \hat{\mathfrak{R}}_S(\mathcal{H})+\sqrt{\log(2/\delta)/(2n)}$ が確率 $1-\delta/2$ で成り立ちます。両方を失敗確率 $\delta/2$ ずつで束ねる（再びunion bound）と、確率 $1-\delta$ 以上でデータから計算できる経験版
$$ \begin{equation} R(h)\le \hat R_S(h)+2\hat{\mathfrak{R}}_S(\mathcal{H})+3\sqrt{\frac{\log(2/\delta)}{2n}} \end{equation} $$
が得られます。係数 $3$ は、$2$ 回のMcDiarmid（信頼項が $1$ 回ぶん＋Rademacherの集中で $2$ 倍ぶん）を $\delta/2$ で合算したことから来ます。これが本文タスクで挙げた $R(h)\le\hat R(h)+2\mathfrak{R}_S(\mathcal{H})+3\sqrt{\log(2/\delta)/2n}$ の形です。
ここまでで「Rademacher複雑度さえ抑えられれば汎化する」ことが全行で示せました。残る仕事は、無限仮説のRademacher複雑度を成長関数→VC次元で抑えることです。そのために必要な2つの補題（Sauer–Shelah と Massart）を埋めます。
(E) Sauer–Shelahの補題：成長関数は $\sum_{i=0}^d\binom{n}{i}$ 以下
まずshatter（粉砕）の定義を明示します。仮説集合 $\mathcal{H}$ が点集合 $C=\{x_1,\dots,x_m\}$ を shatter するとは、$C$ 上で実現できるラベル付け（$\pm1$ の付け方）が $2^m$ 通りすべてそろうこと、すなわち $|\mathcal{H}|_C|=2^m$（$\mathcal{H}|_C$ は $\mathcal{H}$ を $C$ 上に制限したラベルパターンの集合）。VC次元 $d=\mathrm{VCdim}(\mathcal{H})$ は、$\mathcal{H}$ が shatter できる点集合の最大サイズです。成長関数 $\Pi_{\mathcal{H}}(n)=\max_{|C|=n}|\mathcal{H}|_C|$ は、$n$ 点上で作れるラベルパターン数の最大値です。
主張（Sauer–Shelah）：VC次元が $d$ なら、すべての $n$ で
$$ \begin{equation} \Pi_{\mathcal{H}}(n)\le \sum_{i=0}^{d}\binom{n}{i}. \end{equation} $$
証明（$n$ と $d$ に関する二重帰納法）。集合系の言葉に翻訳します。$C=\{x_1,\dots,x_n\}$ を固定し、$\mathcal{F}=\mathcal{H}|_C$ を $C$ の部分集合族（各ラベルパターンを「+1 にする点の集合」と同一視）とみなします。「$\mathcal{F}$ が集合 $A\subseteq C$ を shatter する」とは $\{F\cap A: F\in\mathcal{F}\}=2^A$ のこと。示したいのは、
$\mathcal{F}$ が shatter する集合がすべてサイズ $\le d$ なら $|\mathcal{F}|\le \sum_{i=0}^d\binom{n}{i}$。
実際にはより強いSauer–Shelah–Pajorの形「$|\mathcal{F}|\le |\{A\subseteq C:\ \mathcal{F}\text{ は }A\text{ を shatter する}\}|$」を帰納法で示すと、上の主張は系として出ます（shatterされる集合はサイズ $\le d$ なので、その個数は $\sum_{i=0}^d\binom{n}{i}$ 以下）。
帰納法の土台：$n=0$ なら $\mathcal{F}\subseteq\{\emptyset\}$ で $|\mathcal{F}|\le 1=\binom{0}{0}$、shatterされる集合は $\emptyset$ のみで主張は成立。$d=0$（どの1点も shatter できない）なら、各点で $\mathcal{F}$ のラベルは一定なので $|\mathcal{F}|\le 1=\binom{n}{0}$。
帰納段階：点 $x_n$ を1つ選び、$x_n$ を除いた $C’=\{x_1,\dots,x_{n-1}\}$ への制限を考えます。2つの族を作ります。
$$ \mathcal{F}_1=\mathcal{F}|_{C’}=\{F\setminus\{x_n\}: F\in\mathcal{F}\},\qquad \mathcal{F}_2=\{F\subseteq C’: \text{both } F \text{ and } F\cup\{x_n\}\in\mathcal{F}\}. $$
$\mathcal{F}_1$ は $x_n$ を「忘れた」族、$\mathcal{F}_2$ は「$x_n$ を入れても入れなくても $\mathcal{F}$ にある」ペアの $C’$ 側です。重要な数え上げの等式は
$$ |\mathcal{F}|=|\mathcal{F}_1|+|\mathcal{F}_2|. $$
理由：$C’$ 上の各パターン $G$ について、$\mathcal{F}$ がそれを実現する仕方は「$x_n$ なし」「$x_n$ あり」の最大2通り。$\mathcal{F}_1$ はそのパターンを1回だけ数え、もし両方ある（2通り）なら $\mathcal{F}_2$ が追加で1回数えるので、合計でちょうど $\mathcal{F}$ の元数になります。
次に shatter の対応を見ます。$\mathcal{F}_1$（$=\mathcal{F}$ の $C’$ への制限）が shatter する集合は $\mathcal{F}$ も shatter します（$C’\subseteq C$ なので）。一方、$\mathcal{F}_2$ が集合 $A\subseteq C’$ を shatter するなら、定義より $A$ の各パターンが「$x_n$ あり/なし」両方で実現できるので、$\mathcal{F}$ は $A\cup\{x_n\}$ を shatter します。つまり $\mathcal{F}_2$ の shatter する集合 $A$ には、$\mathcal{F}$ の shatter する集合 $A\cup\{x_n\}$ が一対一対応します。
帰納法の仮定を $C’$（$n-1$ 点）に適用すると、
$$ |\mathcal{F}_1|\le \#\{A\subseteq C’:\ \mathcal{F}_1\text{ が shatter}\},\qquad |\mathcal{F}_2|\le \#\{A\subseteq C’:\ \mathcal{F}_2\text{ が shatter}\}. $$
足し合わせると、$\mathcal{F}_1$ が shatter する集合（$x_n$ を含まない）と、$\mathcal{F}_2$ 由来の $A\cup\{x_n\}$（$x_n$ を含む）はかぶらないので、
$$ |\mathcal{F}|=|\mathcal{F}_1|+|\mathcal{F}_2|\le \#\{A\subseteq C:\ \mathcal{F}\text{ が shatter}\}. $$
これでPajor版が示せ、shatterされる集合はサイズ $\le d$ ゆえその個数は $\sum_{i=0}^d\binom{n}{i}$ 以下。よって $|\mathcal{F}|=\Pi_{\mathcal{H}}(n)\le\sum_{i=0}^d\binom{n}{i}$。$\blacksquare$
多項式オーダーへ。$n\ge d\ge 1$ のとき $\sum_{i=0}^d\binom{n}{i}\le \left(\frac{en}{d}\right)^d$ を示します。$(d/n)^d\le (d/n)^i$（$i\le d$、かつ $d/n\le 1$）を使って各項を膨らませると、
$$ \Big(\frac{d}{n}\Big)^d\sum_{i=0}^d\binom{n}{i}\le \sum_{i=0}^d\binom{n}{i}\Big(\frac{d}{n}\Big)^i\le \sum_{i=0}^{n}\binom{n}{i}\Big(\frac{d}{n}\Big)^i=\Big(1+\frac{d}{n}\Big)^n\le e^{d}, $$
最後は二項定理と $1+x\le e^x$（$x=d/n$ を $n$ 乗）を使いました。両辺を $(d/n)^d$ で割ると $\sum_{i=0}^d\binom{n}{i}\le (en/d)^d$ を得ます。これで成長関数は $O(n^d)$、すなわち $n>d$ で指数 $2^n$ から多項式へ折れ曲がることが証明されました。
(F) Massartの有限補題 → 有限クラスのRademacher複雑度
最後のピースは、「ラベルパターンが有限個（$\le \Pi_{\mathcal{H}}(n)$ 通り）」という事実をRademacher複雑度のバウンドに変換することです。鍵はMassartの有限補題です。
主張（Massartの有限補題）：有限集合 $A\subseteq\mathbb{R}^n$、$|A|=N$、すべての $a\in A$ で $\|a\|_2\le r$ とする。$\sigma=(\sigma_1,\dots,\sigma_n)$ を独立Rademacher変数とすると、
$$ \begin{equation} \mathbb{E}_\sigma\Big[\max_{a\in A}\ \sum_{i=1}^n \sigma_i a_i\Big]\le r\sqrt{2\log N}. \end{equation} $$
証明（MGF経由・全行）。任意の $\lambda>0$ について、まずJensenの不等式（$\exp$ は凸、$\lambda\,\mathbb{E}[\max]\le \log\mathbb{E}[\exp(\lambda\max)]$）を使い、$\max$ を $\sum$（和）で上から抑えます。
$$ \exp\Big(\lambda\,\mathbb{E}_\sigma\big[\max_a \textstyle\sum_i\sigma_i a_i\big]\Big) \le \mathbb{E}_\sigma\Big[\exp\big(\lambda\max_a \textstyle\sum_i\sigma_i a_i\big)\Big] =\mathbb{E}_\sigma\Big[\max_a \exp\big(\lambda\textstyle\sum_i\sigma_i a_i\big)\Big]. $$
$\max$ は和で抑えられる（非負の項を全部足す方が大きい）ので、
$$ \le \sum_{a\in A}\mathbb{E}_\sigma\Big[\exp\big(\lambda\textstyle\sum_i\sigma_i a_i\big)\Big] =\sum_{a\in A}\prod_{i=1}^n \mathbb{E}_{\sigma_i}\big[e^{\lambda\sigma_i a_i}\big], $$
最後は $\sigma_i$ が独立なので期待値が積に分解できることを使いました。各因子は $\sigma_i=\pm1$ 等確率より $\mathbb{E}[e^{\lambda\sigma_i a_i}]=\frac12(e^{\lambda a_i}+e^{-\lambda a_i})=\cosh(\lambda a_i)$。ここで初等不等式 $\cosh(x)\le e^{x^2/2}$ を使うと（Taylor展開で $\cosh x=\sum x^{2k}/(2k)!\le \sum (x^2/2)^k/k!=e^{x^2/2}$）、
$$ \prod_{i=1}^n \cosh(\lambda a_i)\le \prod_{i=1}^n e^{\lambda^2 a_i^2/2}=\exp\Big(\frac{\lambda^2}{2}\sum_i a_i^2\Big)=\exp\Big(\frac{\lambda^2}{2}\|a\|_2^2\Big)\le \exp\Big(\frac{\lambda^2 r^2}{2}\Big). $$
これを $N$ 個足すと右辺は $N\exp(\lambda^2 r^2/2)$。両辺の対数をとり $\lambda$ で割ると
$$ \mathbb{E}_\sigma\big[\max_a\textstyle\sum_i\sigma_i a_i\big]\le \frac{\log N}{\lambda}+\frac{\lambda r^2}{2}. $$
右辺を $\lambda$ について最小化します。$\frac{d}{d\lambda}\big(\frac{\log N}{\lambda}+\frac{\lambda r^2}{2}\big)=-\frac{\log N}{\lambda^2}+\frac{r^2}{2}=0$ より $\lambda^\star=\frac{\sqrt{2\log N}}{r}$。代入すると2項がそろって $\frac{\log N}{\lambda^\star}=\frac{r\sqrt{2\log N}}{2}$、$\frac{\lambda^\star r^2}{2}=\frac{r\sqrt{2\log N}}{2}$ となり、和は $r\sqrt{2\log N}$。$\blacksquare$
Rademacher複雑度への適用。仮説出力が $h(x_i)\in\{-1,+1\}$ のとき、$\mathcal{H}$ が $n$ 点上で作るベクトル $a^{(h)}=(h(x_1),\dots,h(x_n))$ は高々 $\Pi_{\mathcal{H}}(n)$ 種類しかありません（同じラベルパターンは同じベクトル）。各ベクトルのノルムは $\|a^{(h)}\|_2=\sqrt{\sum_i 1}=\sqrt{n}$。よって $A=\{a^{(h)}\}$ に対し $N\le \Pi_{\mathcal{H}}(n)$、$r=\sqrt{n}$ としてMassartを使うと、
$$ \hat{\mathfrak{R}}_S(\mathcal{H})=\frac1n\,\mathbb{E}_\sigma\Big[\max_{h}\sum_i\sigma_i h(x_i)\Big]\le \frac1n\cdot\sqrt{n}\,\sqrt{2\log \Pi_{\mathcal{H}}(n)}=\sqrt{\frac{2\log \Pi_{\mathcal{H}}(n)}{n}}. $$
特に有限仮説集合（$\Pi_{\mathcal{H}}(n)\le|\mathcal{H}|$）なら $\hat{\mathfrak{R}}_S(\mathcal{H})\le\sqrt{2\log|\mathcal{H}|/n}$、これがタスクで求めた有限クラスのRademacherバウンドです。
(E)+(F) 合流：成長関数 → Rademacher → VCバウンド
これで一本につながります。Massart適用で得た $\hat{\mathfrak{R}}_S(\mathcal{H})\le\sqrt{2\log\Pi_{\mathcal{H}}(n)/n}$ に、Sauer–Shelah $\Pi_{\mathcal{H}}(n)\le(en/d)^d$ を代入すると、$\log\Pi_{\mathcal{H}}(n)\le d\log(en/d)=d\,(\log n + \log(e/d))=O(d\log n)$ なので
$$ \hat{\mathfrak{R}}_S(\mathcal{H})\le \sqrt{\frac{2d\log(en/d)}{n}}=O\!\left(\sqrt{\frac{d\log n}{n}}\right). $$
これを (D) のRademacher汎化バウンドに入れると、確率 $1-\delta$ 以上ですべての $h$ について
$$ \begin{equation} R(h)\le \hat R_S(h)+O\!\left(\sqrt{\frac{d_{\mathrm{VC}}\log n}{n}}\right)+\sqrt{\frac{\log(2/\delta)}{2n}}, \end{equation} $$
すなわち本文のVCバウンド $\varepsilon\sim\sqrt{d_{\mathrm{VC}}\log n/n}$ が、補題0（Hoeffding）から出発して全行で導けました。論理の鎖は Hoeffding → (union bound で) 有限一様収束、別ルートで McDiarmid + 対称化 → Rademacherバウンド、そして Sauer–Shelah + Massart → 成長関数をRademacherに変換 → VCバウンド です。3つの「複雑さの測り方」が、すべて同じ集中不等式の上に立っていることが見えます。
補遺の数値確認
最後に、補遺で証明した2つの不等式——Sauer–Shelahの多項式バウンドとMassartの有限補題——が本当に成り立つかを数値で確かめます。前者は組合せ和と $(en/d)^d$ を直接比較し、後者は有限クラスの経験Rademacher複雑度をモンテカルロ推定してバウンド $\sqrt{2\log|\mathcal{H}|/n}$ と比べます。
import numpy as np
from math import comb, log, sqrt
# (E) Sauer-Shelah: sum_{i=0}^d C(n,i) <= (en/d)^d （かつ 2^n より遥かに小さい）
print("Sauer-Shelah sum C(n,i) vs (en/d)^d")
for (n, d) in [(10, 3), (20, 3), (50, 5), (100, 10)]:
lhs = sum(comb(n, i) for i in range(d + 1))
rhs = (np.e * n / d) ** d
print(f" n={n:3d} d={d:2d}: LHS={lhs:.3e} RHS={rhs:.3e} LHS<=RHS? {lhs <= rhs} 2^n={2.0**n:.2e}")
# (F) Massart -> 有限クラスの経験Rademacher複雑度 <= sqrt(2 log|H| / n)
rng = np.random.default_rng(0)
def emp_rademacher_finite(H, trials=20000):
n = H.shape[1]
s = rng.choice([-1, 1], size=(trials, n)) # ランダム符号を多数振る
corr = (s @ H.T) / n # 各仮説との相関 (trials, |H|)
return corr.max(axis=1).mean() # 各試行で最良の仮説を選び平均
print("Massart empirical R_hat vs sqrt(2 log|H| / n)")
for (m, n) in [(5, 20), (20, 20), (100, 30), (500, 30)]:
H = rng.choice([-1, 1], size=(m, n)) # |H|=m 個の +-1 ラベルパターン
emp = emp_rademacher_finite(H)
bound = sqrt(2 * log(m) / n)
print(f" |H|={m:4d} n={n:3d}: R_hat={emp:.3f} bound={bound:.3f} R_hat<=bound? {emp <= bound}")
実行すると、おおよそ次の出力が得られます。
Sauer-Shelah sum C(n,i) vs (en/d)^d
n= 10 d= 3: LHS=1.760e+02 RHS=7.439e+02 LHS<=RHS? True 2^n=1.02e+03
n= 20 d= 3: LHS=1.351e+03 RHS=5.951e+03 LHS<=RHS? True 2^n=1.05e+06
n= 50 d= 5: LHS=2.370e+06 RHS=1.484e+07 LHS<=RHS? True 2^n=1.13e+15
n=100 d=10: LHS=1.942e+13 RHS=2.203e+14 LHS<=RHS? True 2^n=1.27e+30
Massart empirical R_hat vs sqrt(2 log|H| / n)
|H|= 5 n= 20: R_hat=0.255 bound=0.401 R_hat<=bound? True
|H|= 20 n= 20: R_hat=0.414 bound=0.547 R_hat<=bound? True
|H|= 100 n= 30: R_hat=0.451 bound=0.554 R_hat<=bound? True
|H|= 500 n= 30: R_hat=0.541 bound=0.644 R_hat<=bound? True
上段のSauer–Shelahでは、組合せ和 $\sum_{i=0}^d\binom{n}{i}$ が $(en/d)^d$ で確かに上から抑えられ、しかも $2^n$ より桁違いに小さいことが見えます（$n=100,d=10$ で $10^{13}$ 対 $10^{30}$）。これが「指数から多項式への折れ曲がり」の数値的な姿です。下段のMassartでは、有限クラスの経験Rademacher複雑度がすべてのケースでバウンド $\sqrt{2\log|\mathcal{H}|/n}$ 以下に収まり、$|\mathcal{H}|$ を増やすと両者がともに増える（ただしバウンドが必ず上を行く）ことが確認できます。証明した不等式が、実際の乱数実験でも破られないことを目で確かめられました。
まとめ
本記事では、「なぜ機械学習は汎化するのか」という問いを、統計的学習理論の道具で解き明かしました。
- PAC学習は「確率 $1-\delta$ で誤差が $\varepsilon$ 以内」という確率的な保証を目標にする枠組みです。固定した1つの仮説ならHoeffingで簡単に保証できます。
- しかし学習はデータを見てから仮説を選ぶため、選択バイアスを避けるには $\sup_h|R-\hat{R}|$ を抑える一様収束が必要です。
- 仮説の「複雑さ」は3段階で測れます。有限仮説集合では $\sqrt{\log|\mathcal{H}|/n}$、VC次元では成長関数とSauer–Shelahを通じて $\sqrt{d_{\mathrm{VC}}\log n/n}$、Rademacher複雑度ではランダムラベルへのfit度として直接 $2\mathfrak{R}_n(\mathcal{H})$。
- 汎化バウンドはどれも「経験誤差＋複雑さの項＋信頼の項」の3層構造で、後ろ2項は $1/\sqrt{n}$ で縮みます。複雑さを上げると経験誤差は下がるがバウンドは緩む、という表現力と汎化のトレードオフが本質です。
統計的学習理論は、正則化やモデル選択、必要データ量の見積もりといった実務判断に、確率の言葉で裏付けを与えてくれます。深層学習ではこれらの古典バウンドが緩すぎる場合もあり、より精密な複雑度（ノルムベースの複雑度など）の研究が今も続いていますが、出発点はいつもこのRademacher複雑度です。
次のステップとして、以下の記事も参考にしてください。