確率的で近似的に正しい学習

確率的で近似的に正しい学習（）やPAC学習（）とは、機械学習の計算論的学習理論において、機械学習の数学的解析フレームワークの1つである。Leslie Valiant が1984年に提唱した。
このフレームワークにおいて、学習アルゴリズムは標本を受け取り、仮説と呼ばれる汎化した関数をある関数クラスの中から選択する必要がある。目標は、高い確率で、選択した関数が小さな汎化誤差になる事である。学習アルゴリズムは、与えられた近似比率、成功率、標本分布から概念を学習する必要がある。
このモデルは後にノイズ（誤分類された標本）を扱えるように拡張された。
PACフレームワークの重要なイノベーションは、計算論的学習理論という概念を機械学習にもたらしたことである。特に、学習アルゴリズムは（時間計算量と空間計算量が訓練データサイズの多項式サイズの制限の元で）適切な関数を見つけ出すことが期待され、学習アルゴリズムは（訓練データサイズが仮説空間サイズの多項式サイズに収まっているなど）効率的な手順を実装する必要がある。
定義.
二値分類問題を対象とする。評価関数は誤分類率。以下のように記号を定義する。
仮説集合 H が PAC 学習可能とは、任意の formula_1 と formula_2 に対して、formula_6 の時、つまり、学習アルゴリズムが必要とする訓練データ数以上の訓練データがある時に、確率 formula_7 以上で、評価データでの誤分類率が formula_1 以下となる学習アルゴリズムが存在する時、PAC 学習可能という。