# PAC 学習 Navigation: [[index]] | [[_index|concepts]] ## 定義 PAC 学習(Probably Approximately Correct learning)とは、Valiant(1984)が提唱した統計的学習理論の基礎的枠組みである。学習アルゴリズムが「高い確率($\ge 1-\delta$)で、誤差が $\varepsilon$ 以下のモデルを出力できる」という条件を、サンプルサイズ $n$ や仮説クラスの複雑度との関係で定量化する。"Probably"(確率的保証)と"Approximately"(近似的正確さ)の組み合わせが名称の由来。 PAC 学習の主問は、精度 $\varepsilon$ と失敗確率 $\delta$ を達成するために何サンプル必要か(サンプル複雑度)、である。 ## 佐藤 2025 との接続 佐藤竜馬の記事 [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]] は PAC の語を明示的に使わないが、以下の構成要素が PAC フレームワークに対応する。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) | 記事の表現 | PAC 用語 | |---|---| | 「ほぼ確実に(例: 99% の確率で)」 | $1 - \delta$($\delta = 0.01$) | | 「経験損失と母リスクの差が $k$ 以内」 | 近似精度 $\varepsilon$ | | 「サンプルサイズ $n$ を大きくする」 | サンプル複雑度の解析 | | 有限仮説クラスでの一様収束 | 有限 PAC 学習 | | カバリングナンバーを用いた拡張 | 無限仮説クラスの PAC 学習 | ## PAC 学習と仮説クラスの複雑度 古典的な PAC 学習では、仮説クラスの複雑度を VC 次元(Vapnik-Chervonenkis dimension)や Rademacher 複雑度で測定し、サンプル複雑度と関連付ける。佐藤 2025 ではカバリングナンバーを用いたアプローチが示されており、これはエントロピー数と呼ばれる別の複雑度尺度に相当する。 ## 限界と深層学習 古典的 PAC 理論では、深層学習のようにパラメータ次元 $d$ がサンプルサイズ $n$ を大きく超える過パラメータ化の状況で自明な(情報を持たない)バウンドしか得られない。深層学習の実践的成功を説明するには、PAC フレームワークを拡張した PAC-Bayes 理論・均一安定性(uniform stability)・暗黙正則化などの枠組みが研究されている。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) ## 横断的知見 - 記事の「評価と訓練の非対称性」(パラメータがデータに依存することで独立性が崩れる)は、PAC 学習理論においても一様収束が本質的な道具立てである理由を説明している。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]]) - **入門書(ch.2)の「訓練データを増やす」「仮説数を減らす」という過学習対策2条は、PAC学習のサンプル複雑度と仮説クラスサイズのトレードオフを、数式なしでそのまま言い当てている**: PAC学習の主問(精度$\varepsilon$・失敗確率$\delta$を達成するために何サンプル必要か)は、有限仮説クラスでは必要サンプル数が仮説クラスのサイズ$m$の対数($\log m$)に比例する形で定式化される(本ページ「PAC学習と仮説クラスの複雑度」節)。[[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3は同じ関係を「訓練データを増やす」(サンプル数を増やす)か「検証する仮説数を必要最低限に抑える」(仮説クラスを小さくする)かという、過学習を防ぐ2つの独立な対策として提示する。これはPAC学習のサンプル複雑度の式が持つ「サンプル数と仮説クラスサイズは代替可能」という関係(仮説数を減らせば必要なサンプル数は減る)を、数式を経由せず操作的な指針として述べたものであり、本ページが列挙するVC次元・Rademacher複雑度・カバリングナンバーという複雑度指標のいずれもが「なぜモデルの複雑さを抑える必要があるのか」を説明する動機を、平易な言葉で補う。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]], [[@2022__Gihyo__ディープラーニングを支える技術 - Chapter 2 ［入門］機械学習]] §2.3) - **続巻ch.2は、本ページが「限界と深層学習」節で名前だけ挙げるPAC-Bayes理論を、フラットな解というニューラルネットワーク固有の性質と結びつけて具体化する**: 本ページは「深層学習の実践的成功を説明するには、PACフレームワークを拡張したPAC-Bayes理論……などの枠組みが研究されている」と述べるにとどまるが、[[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 2 ディープラーニングの汎化]] §2.2は、PAC-Bayesによる汎化性能評価が学習前の事前分布から学習後の事後分布へのKLダイバージェンス(目的関数のヘシアンのトレースとして計算できる)で与えられ、フラットな解(曲がりが小さい解)ほどこのKLダイバージェンスが小さく、高い汎化性能が期待できると述べる。これは本ページが挙げるPAC-Bayes理論が「なぜ」過パラメータ化されたニューラルネットワークに有効なバウンドを与えうるかについて、[[暗黙的正則化]]が扱うフラットな解への到達という具体的な機構を介した回答の一つを与える。(Source: [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]], [[@2022__Gihyo__ディープラーニングを支える技術〈2〉 - Chapter 2 ディープラーニングの汎化]] §2.2) ## 未解決の問い - VC 次元・Rademacher 複雑度・カバリングナンバー(エントロピー数)はそれぞれどのような状況で最も有効なバウンドを与えるか。 - PAC-Bayes 理論は深層学習の過パラメータ化をどこまで説明できるか。続巻ch.2はフラットな解のKLダイバージェンス(ヘシアンのトレース)による説明を与えたが、これを定量的なサンプル複雑度の式にまで落とし込む議論は本ページではまだ追えていない。 ## 関連 - [[汎化誤差バウンド]] — PAC フレームワークで得られる定量的保証 - [[集中不等式]] — PAC 学習の証明技法 - [[カバリングナンバー]] — 無限仮説クラスの複雑度の定量化 - [[暗黙的正則化]] — フラットな解を介したPAC-Bayesバウンドの具体化(続巻ch.2) ## 出典 - [[joisino-機械学習理論入門-2025|@2025__joisino__絶対に分かる機械学習理論]] — 佐藤竜馬、2025-03-17 - 岡野原大輔, 『ディープラーニングを支える技術』, 技術評論社, 2022, 第2章, §2.3. - 岡野原大輔, 『ディープラーニングを支える技術〈2〉 ニューラルネットワーク最大の謎』, 技術評論社, 2022, 第2章, §2.2.