確率的で近似的に正しい学習
確率的で近似的に正しい学習(英: probably approximately correct learning)やPAC学習(英: PAC learning)とは、機械学習の計算論的学習理論において、機械学習の数学的解析フレームワークの1つである。Leslie Valiant が1984年に提唱した。
このフレームワークにおいて、学習アルゴリズムは標本を受け取り、仮説と呼ばれる汎化した関数をある関数クラスの中から選択する必要がある。目標は、高い確率で、選択した関数が小さな汎化誤差になる事である。学習アルゴリズムは、与えられた近似比率、成功率、標本分布から概念を学習する必要がある。
このモデルは後にノイズ(誤分類された標本)を扱えるように拡張された。
PACフレームワークの重要なイノベーションは、計算論的学習理論という概念を機械学習にもたらしたことである。特に、学習アルゴリズムは(時間計算量と空間計算量が訓練データサイズの多項式サイズの制限の元で)適切な関数を見つけ出すことが期待され、学習アルゴリズムは(訓練データサイズが仮説空間サイズの多項式サイズに収まっているなど)効率的な手順を実装する必要がある。