汎化誤差バウンド - yuuk1's Digital Garden

# 汎化誤差バウンド Navigation: [[index]] | [[_index|concepts]] ## 定義汎化誤差バウンド(generalization bound)とは、機械学習モデルの経験損失(訓練データ上の損失平均)と真のリスク(データ分布全体の期待損失)の差である**汎化誤差** $|R(\Theta^*) - \hat{R}_n(\Theta^*)|$ を、高確率で上界から抑える不等式のことである。「なぜ訓練データで性能が出れば未見データでも性能が期待できるのか」を理論的に正当化する枠組みである。(Source: [[joisino-機械学習理論入門-2025|@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: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) ## 有限仮説クラスのバウンド仮説候補が $m$ 個の有限集合の場合、**ユニオンバウンド**と集中不等式を組み合わせることで「全候補で同時に経験損失が真のリスクに近い」(**一様収束**, uniform convergence)を保証できる。ヘフディングの不等式を使えば各候補の確率が指数的に小さいため、候補数の対数に比例する程度のサンプルサイズで十分な保証が得られる。(Source: [[joisino-機械学習理論入門-2025|@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: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) ## 深層学習(過パラメータ化)での問題深層学習では $d \gg n$ が典型であり、上記のバウンドが $\ge 1$ となって意味をなさない。損失地形の「盆地」構造(広大な平坦極小)に着目し、本質的な盆地の個数 $K$ を定数と仮定すると、パラメータ次元 $d$ に依存しないバウンドが得られる可能性がある。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) ## VC次元によるバウンド(ESL第7章) [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.9は、カバリングナンバーとは別系統の複雑度指標であるVC次元(関数族がshatterできる最大点数)を使って、$N$個の訓練点をVC次元$h$の関数族で当てはめたときの汎化誤差バウンドを与える。2値分類では確率$1-\eta$以上で $\text{Err}_T \le \text{err} + \frac{\epsilon}{2}\left(1+\sqrt{1+\frac{4\cdot\text{err}}{\epsilon}}\right), \quad \epsilon = a_1\frac{h[\log(a_2N/h)+1]-\log(\eta/4)}{N}$ という形の上界が成り立つ。この上界は特定の関数$f(x,\alpha)$に対する期待楽観性ではなく、関数族全体に**同時に**成り立つ確率的上界であり、AICの補正項$d/N$と定性的に一致する。Vapnikの構造リスク最小化(SRM)は、VC次元が増加する入れ子のモデル列を当てはめてこの上界を最小化するモデルを選ぶ。ただしVC次元の計算困難性が実用上の主な弱点である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.9, 式7.46-7.47) ## 横断的知見 - 汎化誤差バウンドの導出において集中不等式 → ユニオンバウンド → カバリングナンバーという3段階の論理は、有限 → 有限(大規模) → 無限の仮説クラスへと順に拡張できる普遍的なパターンをなしている。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) - 古典的なバウンド(パラメータ次元 $d$ に依存)と深層学習の実験的成功の乖離は、深層学習理論の主要な未解決問題のひとつであり、損失地形・フラットミニマ・ベンチマーク一般化の観点から活発に研究されている。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) - **カバリングナンバー由来のバウンドとVC次元由来のバウンドは、同じ「無限仮説クラスへの拡張」という目的を、異なる複雑度指標で達成する姉妹関係にある**: joisino2025のカバリングナンバー由来バウンド($|\hat R_n-R|\le O(\sqrt{d\log(\cdot)/n})$)はパラメータ空間$\mathbb{R}^d$の$\varepsilon$-被覆に基づき、損失の$L$-リプシッツ連続性を前提とする。ESL第7章のVC次元由来バウンドはパラメータ次元によらず「関数族がshatterできる点数」で複雑度を測り、リプシッツ連続性を前提としない代わりにVC次元自体の計算が一般に困難という別の代償を払う。前者は連続パラメータ空間の幾何(距離)に依拠し、後者は関数族の組合せ論的な表現力に依拠するという、複雑度の測り方の違いが両バウンドの適用範囲・強さの違いに直結する。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]], [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.9) - ESL第7章は、上記のVC次元バウンドと並行して、訓練誤差の楽観性$\omega=\frac{2}{N}\sum_i\text{Cov}(\hat y_i,y_i)$を実効パラメータ数$\text{trace}(S)$で解析的に補正する$C_p$/AIC/BIC/MDLという**別系統(期待値ベース)**の誤差推定も提示する。VC次元バウンドが「族全体に同時に成り立つ確率的上界」であるのに対し、$C_p$/AICは「特定モデルの期待楽観性」を推定するにとどまり、探索(モデル選択)を行う場合はVC次元バウンドの方が理論的に厳密だが、実測比較(§7.9.1)ではAIC・BICがSRMと同等以上に良好な結果を示すこともあり、理論的な厳密さと実務的な有効性が必ずしも一致しない。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.5-§7.9) - **ESL第7章がAIC/BICを「訓練誤差の楽観性を補正する経験的公式」として天下り的に提示するのに対し、[[@2020__Cambridge__Mathematics for Machine Learning - Chapter 8 When Models Meet Data]] §8.6.4はAIC・BICをベイズモデル選択のエビデンス(周辺尤度)の近似として導出し、両者を1本の系譜に位置づける**: MML第8章は、モデル集合$\mathcal M=\{M_1,\ldots,M_K\}$への一様事前分布のもとでモデルの事後確率がエビデンス$p(D\mid M_k)=\int p(D\mid\theta_k)p(\theta_k\mid M_k)\,d\theta_k$で決まることを示し、赤池情報量規準AIC$=\log p(x\mid\theta)-M$(パラメータ数$M$による罰則)とベイズ情報量規準BIC$=\log p(x\mid\theta)-\frac12M\log N$(データ数$N$も加味、指数型分布族に適用可能)を、最尤推定のみに基づくエビデンスの近似的な代替として位置づける(BICは周辺尤度のラプラス近似的な導出を持つ)。これはESL第7章がAIC・BICを訓練誤差$\overline{\text{err}}$の楽観性の解析的補正としてのみ導入するのと**異なる導出の起点**であり、ESLの「訓練誤差の期待値を補正する」という頻度主義的な正当化と、MMLの「モデルエビデンス(積分して1になる確率という制約からベイズが自動的に導く複雑さへの罰則)を近似する」というベイズ的な正当化が、同じAIC・BICという式に対して独立に成り立つ2通りの理論的根拠を与えていることが、2ソースの突き合わせで明らかになる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.5-§7.7, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 8 When Models Meet Data]] §8.6.2, §8.6.4) - **MML第8章のベイズモデル選択(エビデンスによる自動オッカムの剃刀)は、ESL第7章のVC次元バウンド(Vapnikの構造リスク最小化, SRM)と同じ「複雑さへの自動的なペナルティ」という目的を、頻度主義とベイズ主義という異なる原理で達成する姉妹関係にある**: ESL第7章のVC次元バウンドは、関数族全体に同時に成り立つ確率的な上界を明示的な複雑度指標(VC次元)として構成し、これを最小化するSRMという頻度主義的な手続きでモデル複雑さを制御する。一方MML第8章§8.6.2は、モデルに複雑さへの罰則を明示的に設計しなくても、確率が全データ空間$D$にわたって積分して1になるという制約だけから、単純なモデルほど狭い範囲の$D$に確率を集中させ複雑なモデルほど広く薄く分散させるという構造(図8.14)によって、複雑さへのペナルティ(オッカムの剃刀)が自動的に具現化されることを示す。両者は「訓練誤差だけでは検出できないモデル複雑さの罰則をどう与えるか」という同じ問題に対し、VC次元という組合せ論的な複雑度指標(頻度主義)と、周辺尤度という確率の正規化制約(ベイズ主義)という、出自の異なる2つの答えを与えている。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.9, [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 8 When Models Meet Data]] §8.6.2) - **入門書(ch.2)は、ユニオンバウンドに基づく一様収束の議論を、数式なしの平易な仮説数カウントとして提示し、汎化誤差バウンドの直観を非専門読者に橋渡しする**: joisino2025・ESL第7章はいずれも有限仮説クラスの一様収束をヘフディングの不等式・ユニオンバウンド・VC次元といった数式で定式化するが、[[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3は同じ現象を「検証する仮説数が少なければ成立した仮説が真である可能性が高いが、仮説数が多いほどたまたま成立するだけの誤った仮説が選ばれやすくなる」という頻度論的な直観(図2.6、朝食のカレーと試合勝敗の疑似相関の例)として説明し、過学習対策として「訓練データを増やす」「仮説数を減らす」の2つだけを挙げる。これは数式レベルでは本ページの有限仮説クラスバウンド($m$個の候補に対しサンプルサイズが$\log m$のオーダーで足りる)と同一の主張だが、対数($\log m$)の効果それ自体には触れず、仮説数と訓練データ数の相対関係という定性的な形で提示している点で、本ページが集約する形式的なバウンド群への平易な入口になる。さらにch.2の同じ節にあるコラム「連続値のパラメータから成るモデルの仮説数」は、パラメータが連続値の場合は仮説数を直接数えられないことを認め、その対処としてラデマッハ複雑度・VC次元を名指しで挙げており、本ページのVC次元バウンド節・[[カバリングナンバー]]が扱う「無限仮説クラスへの拡張」という主題を、詳細を伏せたまま予告する役割も果たす。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3, [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) - **続巻ch.2は、本ページが「深層学習(過パラメータ化)での問題」節で名前だけ挙げるPAC-Bayesバウンドに、フラットな解というニューラルネットワーク固有の性質を介した具体的な導出経路を与える**: 本ページは「損失地形の『盆地』構造に着目し、本質的な盆地の個数$K$を定数と仮定すると、パラメータ次元$d$に依存しないバウンドが得られる可能性がある」と述べるにとどまり、PAC-Bayesがどのようにこの盆地構造と結びつくかには立ち入らない。[[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 2 ディープラーニングの汎化]] §2.2は、PAC-Bayesの汎化性能評価が学習前の事前分布から学習後の事後分布までのKLダイバージェンスで与えられ、このKLダイバージェンスが目的関数のパラメータについてのヘシアンのトレース(対角成分の和、つまり現在位置での目的関数の曲がり具合)として計算できることを示し、フラットな解(曲がりが小さい解)ほどKLダイバージェンスが小さく高い汎化性能が期待できると結論づける。これは「パラメータ次元$d$に依存しないバウンドが得られる可能性がある」という本ページの推測に対し、ヘシアンのトレースという具体的な量を介した機構的な説明を与えるものであり、$d$依存性が消える理由(平坦な解ではヘシアンの固有値の多くがほぼ0になり、実効的な自由度がパラメータ次元$d$よりずっと小さくなる)を補う。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]], [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 2 ディープラーニングの汎化]] §2.2) - **入門書(前巻ch.2)の平易な仮説数カウントに続き、続巻ch.2はバイアス-バリアンス分解という第2の直観的経路で、同じ「なぜモデルの複雑さを抑える必要があるか」を補強する**: 前巻ch.2 §2.3は一様収束の直観を「仮説数が多いほど疑似相関が選ばれやすい」という頻度論的な数え上げで説明したが(本ページ既存の横断的知見)、[[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 2 ディープラーニングの汎化]] §2.1は同じ動機を、[[バイアス-バリアンストレードオフ]]([[@2009__Springer__The Elements of Statistical Learning - Chapter 2 Overview of Supervised Learning]] §2.9とも同型の分解)を使って「モデルの表現力を上げるとバイアスが下がりバリアンスが上がるため、汎化誤差はモデルの複雑さに対してU字型になる」という異なる直観的経路から補強する。前巻ch.2の仮説数カウントは有限仮説クラスの一様収束(本ページのユニオンバウンド節)に対応し、続巻ch.2のバイアス-バリアンス分解は連続パラメータ空間での複雑度と誤差の関係に対応するという点で、同じ「複雑さと汎化誤差の関係」を異なる粒度の道具立てで説明する、相補的な2つの入り口になっている。(Source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3, [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 2 ディープラーニングの汎化]] §2.1) ## 未解決の問い - 深層ニューラルネットワークの損失地形における「本質的な盆地の個数」が定数であることはいつ、どの条件下で成立するのか。 - 過パラメータ化されたモデルがなぜ汎化するのかを、既存の枠組みを超えて理論的に説明する手法は何か(二重降下現象、暗黙正則化との関係)。 - Rademacher 複雑度や VC 次元による汎化バウンドと、カバリングナンバーによるバウンドを、共通の統一的な枠組み(例: 両者を特殊ケースとして含む一般的な複雑度尺度)のもとで比較できるか。ESL第7章とjoisino2025はそれぞれ独立にVC次元・カバリングナンバーを用いるが、両者を橋渡しする議論はまだ本ページにない。 - MML第8章はAIC・BICをベイズエビデンスの近似として位置づけ、ESL第7章は訓練誤差の楽観性補正として位置づける。この2つの導出が同一のAIC・BICの式に収束することの形式的な証明(ラプラス近似の詳細な導出過程)は、両ソースいずれにも十分な式変形が示されておらず本ページでは未検証のまま引き継いでいる。 - ベイズファクターがJeffreys-Lindleyのパラドックスにより拡散事前分布のもとで常に単純なモデルを優遇する傾向(MML第8章§8.6.3)は、ESL第7章のVC次元バウンド(SRM)やAIC・BICにも同様の「単純さへの系統的な偏り」が存在するか。両者を横断して比較した議論はまだ本ページにない。 ## 関連 - [[集中不等式]] — マルコフ・チェビシェフ・ヘフディングの不等式(バウンドの基礎部品) - [[PAC学習]] — 汎化誤差バウンドを形式化する枠組み - [[カバリングナンバー]] — 無限仮説クラスへの拡張手法 - [[深層学習の汎化]] — 過パラメータ化と損失地形の盆地 - [[交差検証]] — 入れ子の交差検証によるモデル選択とモデル評価の分離(頻度主義的な代替経路) - [[バイアス-バリアンストレードオフ]] — 続巻ch.2が一様収束と並んで用いるもう一つの直観的経路 - [[暗黙的正則化]] — フラットな解とPAC-Bayesバウンドを結ぶ機構(続巻ch.2) - source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] — VC次元バウンド・SRM・AIC/BIC系列の解析的誤差推定 - source: [[@2020__Cambridge__Mathematics for Machine Learning - Chapter 8 When Models Meet Data]] — ベイズモデル選択・エビデンス・AIC/BICの周辺尤度近似としての導出 - source: [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] — 仮説数カウントによる平易な直観、ラデマッハ複雑度・VC次元の予告 - source: [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 2 ディープラーニングの汎化]] — PAC-Bayesバウンドとフラットな解(ヘシアンのトレース)を結ぶ機構、バイアス-バリアンス分解による直観 ## 出典 - [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]] — 佐藤竜馬、2025-03-17 - [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.5-§7.9 - Deisenroth, M. P., Faisal, A. A., Ong, C. S., *Mathematics for Machine Learning*, Cambridge University Press, 2020, Chapter 8, §8.6.2-§8.6.4 - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第2章, §2.3. - 岡野原大輔, 『ディープラーニングを支える技術〈2〉ニューラルネットワーク最大の謎』, 技術評論社, 2022, 第2章, §2.1-§2.2.