確かく率りつ的てきで近似きんじ的てきに正ただしい学習がくしゅう

確かく率りつ的てきで近似きんじ的てきに正ただしい学習がくしゅう（英えい: probably approximately correct learning）やPAC学習がくしゅう（英えい: PAC learning）とは、機械きかい学習がくしゅうの計算けいさん論ろん的てき学習がくしゅう理論りろんにおいて、機械きかい学習がくしゅうの数学すうがく的てき解析かいせきフレームワークの1つである。Leslie Valiant が1984年ねんに提唱ていしょうした。

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

このモデルは後のちにノイズ（誤あやま分類ぶんるいされた標本ひょうほん）を扱あつかえるように拡張かくちょうされた。

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 学習がくしゅう可能かのうという。