PAC学習理論

1. 概要

PAC学習（Probably Approximately Correct）は、Valiant (1984)が提唱した機械学習の数学的基盤。

• Probably：高確率で（1-δ以上）
• Approximately：近似的に正しい（誤差ε以下）
• Correct：正しい仮説を学習

1.1 基本設定

入力空間: X
出力空間: Y = {0, 1}（二値分類）
仮説クラス: H（学習者が選べる関数の集合）
真の概念: c ∈ C（学習対象）
分布: D（Xの上の未知の分布）

2. PAC学習可能性

2.1 定義

概念クラスCがPAC学習可能 ⟺

任意の ε, δ > 0 に対して、
多項式時間アルゴリズムAが存在し、
m ≥ poly(1/ε, 1/δ, n, size(c)) 個のサンプルで
P[error(h) ≤ ε] ≥ 1 - δ

ここで error(h) = P_{x~D}[h(x) ≠ c(x)]

2.2 サンプル複雑度

精度εと信頼度δを達成するために必要なサンプル数m。

3. 有限仮説クラスの学習

3.1 実現可能ケース

真の概念c ∈ H（仮説クラス内）の場合：

定理：
m ≥ (1/ε)(ln|H| + ln(1/δ)) サンプルで
一致仮説（訓練誤差0）は
確率1-δ以上で汎化誤差ε以下

証明アイデア：
- 「悪い」仮説h: error(h) > ε
- P[hがm個すべてに一致] ≤ (1-ε)^m
- Union bound: P[∃悪いhが一致] ≤ |H|(1-ε)^m ≤ δ

3.2 不可知論的（Agnostic）ケース

c ∉ H の場合でも、H内の最良仮説に近づける：

目標: error(h) ≤ min_{h*∈H} error(h*) + ε

必要サンプル数: O((1/ε²)(log|H| + log(1/δ)))

4. 計算効率

4.1 効率的PAC学習

• サンプル複雑度が多項式
• 計算時間も多項式
• 両方を満たす：効率的PAC学習可能

4.2 計算困難性

統計的には学習可能でも計算的に困難な例：

• 3-term DNF（暗号仮定下）
• Sparse parity with noise
• ニューラルネットワークの訓練（NP困難）

5. 参考文献

• Valiant (1984). "A Theory of the Learnable" CACM
• Kearns & Vazirani (1994). "An Introduction to Computational Learning Theory"
• Shalev-Shwartz & Ben-David (2014). "Understanding Machine Learning"