2. 計算論的学習理論の歴史 • 極限における同定 – 訓練データが無限個与えられた場合に学習可能なクラス (文法) を議論 • PAC学習 – 仮説集合𝐻の学習問題において，危険率𝛿で汎化誤差𝜖の予測 器を学習するために必要な訓練データ数の下界を求める枠組み • [証明が入ります] • VC理論 – PAC学習の枠組みを無限の仮説集合へ拡張 – マージン最大化により汎化誤差が抑えられることを証明 [ゴール] 2 4. 極限における同定 • 主に文法学習を対象 • 帰納推論の成功基準 [Gold 67] – 無限の事例が与えられる (完全提示) 場合に完全学習可能な文法ク ラスを議論する研究分野 – 無限個だったら汎化する必要ないのでは? • 多項式時間など，収束の速さも同時に議論 • 文法の場合は全データを有限時間内に完全網羅することは不可能 • 正例と負例が十分にないと学習可能な