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

確率的で近似的に正しい学習（英: probably approximately correct learning）やPAC学習（英: PAC learning）とは、機械学習の計算論的学習理論において、機械学習の数学的解析フレームワークの1つである。Leslie Valiant が1984年に提唱した^[1]。

このフレームワークにおいて、学習アルゴリズムは標本を受け取り、仮説と呼ばれる汎化した関数をある関数クラスの中から選択する必要がある。目標は、高い確率で、選択した関数が小さな汎化誤差になる事である。学習アルゴリズムは、与えられた近似比率、成功率、標本分布から概念を学習する必要がある。

このモデルは後にノイズ（誤分類された標本）を扱えるように拡張された。

PACフレームワークの重要なイノベーションは、計算論的学習理論という概念を機械学習にもたらしたことである。特に、学習アルゴリズムは（時間計算量と空間計算量が訓練データサイズの多項式サイズの制限の元で）適切な関数を見つけ出すことが期待され、学習アルゴリズムは（訓練データサイズが仮説空間サイズの多項式サイズに収まっているなど）効率的な手順を実装する必要がある。

定義

二値分類問題を対象とする。評価関数は誤分類率。以下のように記号を定義する。

X - データの母集団。
D - データを抽出する際の確率分布。訓練データも評価データも X から同じ確率分布に従って抽出する。
m - 訓練データ数
H - 仮説集合。学習アルゴリズムは訓練データを使い、H の中から仮説 h を選択する。
$\epsilon$ - 0より大きく1より小さい実数で、許容される誤分類率。PAC という言葉の「近似的に正しい」の部分に対応する。
$\delta$ - 0より大きく1より小さい実数で確率値。詳細は後述。PAC という言葉の「確率的で」の部分に対応する。
$m_{H}(\epsilon ,\delta )$ - 学習に必要な訓練データ数。学習アルゴリズムの一部。

仮説集合 H が PAC 学習可能とは、任意の $\epsilon$ と $\delta$ に対して、 $m\geq m_{H}(\epsilon ,\delta )$ の時、つまり、学習アルゴリズムが必要とする訓練データ数以上の訓練データがある時に、確率 $1-\delta$ 以上で、評価データでの誤分類率が $\epsilon$ 以下となる学習アルゴリズムが存在する時、PAC 学習可能という。^[2]^[3]

参照

^ L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984.
^ スチュワートラッセル『エージェントアプローチ人工知能』共立出版、1997年。ISBN 4320028783。
^ Shalev-Shwartz, Shai (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press. ISBN 1107057132