# PAC 学習 Navigation: [[index]] | [[_index|concepts]] ## 定義 PAC 学習(Probably Approximately Correct learning)とは、Valiant(1984)が提唱した統計的学習理論の基礎的枠組みである。学習アルゴリズムが「高い確率($\ge 1-\delta$)で、誤差が $\varepsilon$ 以下のモデルを出力できる」という条件を、サンプルサイズ $n$ や仮説クラスの複雑度との関係で定量化する。"Probably"(確率的保証)と"Approximately"(近似的正確さ)の組み合わせが名称の由来。 PAC 学習の主問は、精度 $\varepsilon$ と失敗確率 $\delta$ を達成するために何サンプル必要か(サンプル複雑度)、である。 ## 佐藤 2025 との接続 佐藤竜馬の記事 [[@2025__joisino__絶対に分かる機械学習理論]] は PAC の語を明示的に使わないが、以下の構成要素が PAC フレームワークに対応する。(Source: [[@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: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 横断的知見 - 記事の「評価と訓練の非対称性」(パラメータがデータに依存することで独立性が崩れる)は、PAC 学習理論においても一様収束が本質的な道具立てである理由を説明している。(Source: [[@2025__joisino__絶対に分かる機械学習理論]]) ## 未解決の問い - VC 次元・Rademacher 複雑度・カバリングナンバー(エントロピー数)はそれぞれどのような状況で最も有効なバウンドを与えるか。 - PAC-Bayes 理論は深層学習の過パラメータ化をどこまで説明できるか。 ## 関連 - [[汎化誤差バウンド]] — PAC フレームワークで得られる定量的保証 - [[集中不等式]] — PAC 学習の証明技法 - [[カバリングナンバー]] — 無限仮説クラスの複雑度の定量化 ## 出典 - [[@2025__joisino__絶対に分かる機械学習理論]] — 佐藤竜馬、2025-03-17