# 汎化誤差バウンド Navigation: [[index]] | [[_index|concepts]] ## 定義 汎化誤差バウンド(generalization bound)とは、機械学習モデルの経験損失(訓練データ上の損失平均)と真のリスク(データ分布全体の期待損失)の差である**汎化誤差** $|R(\Theta^*) - \hat{R}_n(\Theta^*)|$ を、高確率で上界から抑える不等式のことである。「なぜ訓練データで性能が出れば未見データでも性能が期待できるのか」を理論的に正当化する枠組みである。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) 主な登場人物: - $\hat{R}_n(\theta) = \frac{1}{n}\sum_i \ell(X_i;\theta)$: 経験損失(empirical risk) - $R(\theta) = \mathbb{E}_{X \sim D}[\ell(X;\theta)]$: 真のリスク(population risk) - $\Theta^* = \mathrm{argmin}_\theta \hat{R}_n(\theta)$: 訓練によって得られたパラメータ ## 評価と訓練の非対称性 評価(パラメータ固定)の場合、損失値 $Z_i = \ell(X_i;\theta)$ は互いに独立であり、集中不等式を直接適用して $|\hat{R}_n - R|$ を高確率で小さく抑えられる。 訓練の場合、$\Theta^*$ がデータを見た後に決まる確率変数であるため $Z_i = \ell(X_i;\Theta^*)$ が独立でなくなり、同じ議論が直接成立しない。この非対称性が汎化理論の根本的な困難である。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 有限仮説クラスのバウンド 仮説候補が $m$ 個の有限集合の場合、**ユニオンバウンド**と集中不等式を組み合わせることで「全候補で同時に経験損失が真のリスクに近い」(**一様収束**, uniform convergence)を保証できる。ヘフディングの不等式を使えば各候補の確率が指数的に小さいため、候補数の対数に比例する程度のサンプルサイズで十分な保証が得られる。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## カバリングナンバーを用いた連続空間へのバウンド拡張 パラメータが $\mathbb{R}^d$ 上の連続空間をとる場合、$\varepsilon$-被覆と**カバリングナンバー** $N(\varepsilon, \mathcal{H})$ を使って有限の代表点集合に帰着させる。$L$-リプシッツ連続な損失と正則化による $\|\theta\| \le R$ の仮定のもと、99% 以上の確率で: $|\hat{R}_n(\Theta^*) - R(\Theta^*)| \le 2\sqrt{\frac{d\log(200\lceil4\sqrt{d}RnL\rceil)}{2n}}$ このバウンドはサンプルサイズ $n$ の平方根に反比例して小さくなり、有用な保証を得るには $n$ がパラメータ次元 $d$ 以上のオーダーである必要がある。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 深層学習(過パラメータ化)での問題 深層学習では $d \gg n$ が典型であり、上記のバウンドが $\ge 1$ となって意味をなさない。損失地形の「盆地」構造(広大な平坦極小)に着目し、本質的な盆地の個数 $K$ を定数と仮定すると、パラメータ次元 $d$ に依存しないバウンドが得られる可能性がある。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 横断的知見 - 汎化誤差バウンドの導出において集中不等式 → ユニオンバウンド → カバリングナンバーという3段階の論理は、有限 → 有限(大規模) → 無限の仮説クラスへと順に拡張できる普遍的なパターンをなしている。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) - 古典的なバウンド(パラメータ次元 $d$ に依存)と深層学習の実験的成功の乖離は、深層学習理論の主要な未解決問題のひとつであり、損失地形・フラットミニマ・ベンチマーク一般化の観点から活発に研究されている。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 未解決の問い - 深層ニューラルネットワークの損失地形における「本質的な盆地の個数」が定数であることはいつ、どの条件下で成立するのか。 - 過パラメータ化されたモデルがなぜ汎化するのかを、既存の枠組みを超えて理論的に説明する手法は何か(二重降下現象、暗黙正則化との関係)。 - Rademacher 複雑度や VC 次元による汎化バウンドと、カバリングナンバーによるバウンドの関係・強弱はどうなるか。 ## 関連 - [[集中不等式]] — マルコフ・チェビシェフ・ヘフディングの不等式(バウンドの基礎部品) - [[PAC学習]] — 汎化誤差バウンドを形式化する枠組み - [[カバリングナンバー]] — 無限仮説クラスへの拡張手法 - [[深層学習の汎化]] — 過パラメータ化と損失地形の盆地 ## 出典 - [[@2025__joisino__絶対に分かる機械学習理論]] — 佐藤竜馬、2025-03-17