確率的で近似的に正しい学習
二値分類問題を対象とする。評価関数は誤分類率。以下のように記号を定義する。
X - データの母集団。
D - データを抽出する際の確率分布。訓練データも評価データも X から同じ確率分布に従って抽出する。
m - 訓練データ数
H - 仮説集合。学習アルゴリズムは訓練データを使い、H の中から仮説 h を選択する。
ε {\displaystyle \epsilon } - 0より大きく1より小さい実数で、許容される誤分類率。PAC という言葉の「近似的に正しい」の部分に対応する。
δ {\displaystyle \delta } - 0より大きく1より小さい実数で確率値。詳細は後述。PAC という言葉の「確率的で」の部分に対応する。
m H ( ε , δ ) {\displaystyle m_{H}(\epsilon ,\delta )} - 学習に必要な訓練データ数。学習アルゴリズムの一部。
仮説集合 H が PAC 学習可能とは、任意の ε {\displaystyle \epsilon } と δ {\displaystyle \delta } に対して、 m ≥ m H ( ε , δ ) {\displaystyle m\geq m_{H}(\epsilon ,\delta )} の時、つまり、学習アルゴリズムが必要とする訓練データ数以上の訓練データがある時に、確率 1 − δ {\displaystyle 1-\delta } 以上で、評価データでの誤分類率が ε {\displaystyle \epsilon } 以下となる学習アルゴリズムが存在する時、PAC 学習可能という。