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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/08/16 05:33 UTC 版)

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

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

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

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

定義

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

• X - データの母集団。
• D - データを抽出する際の確率分布。訓練データも評価データも X から同じ確率分布に従って抽出する。
• m - 訓練データ数
• H - 仮説集合。学習アルゴリズムは訓練データを使い、H の中から仮説 h を選択する。
• $\epsilon$ この項目は、統計学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。