おそらくおおよそ正しい学習

計算学習理論において、おそらく近似的に正しい（PAC）学習は、機械学習の数学的分析のための枠組みである。これは1984年にレスリー・ヴァリアントによって提案された。^{[ 1 ]}

この枠組みでは、学習者はサンプルを受け取り、特定の関数群の中から一般化関数（仮説と呼ばれる）を選択する必要があります。目標は、高い確率（「おそらく」の部分）で、選択された関数の一般化誤差（「ほぼ正しい」の部分）が低くなることです。学習者は、任意の近似比、成功確率、またはサンプルの分布が与えられた場合でも、概念を学習できなければなりません。

このモデルは後に、ノイズ（誤分類されたサンプル）を処理するように拡張された。

PACフレームワークの重要な革新の一つは、機械学習に計算複雑性理論の概念を導入した点である。具体的には、学習器は効率的な関数（時間および空間要件がサンプルサイズの多項式に制限される）を見つけることが期待され、学習器自身も効率的な手順（近似値と尤度制限によって修正された、概念サイズの多項式に制限されるサンプル数を必要とする）を実装する必要がある。

PAC学習可能なものの定義を与えるためには、まずいくつかの用語を導入する必要があります。^{[ 2 ]}

以下の定義では、2 つの例を使用します。1 つ目は、配列が与えられたときの文字認識の問題です。${\displaystyle n}$バイナリ値画像をビットで符号化する。もう一つの例は、区間内の点を正、区間外の点を負として正しく分類できる区間を見つける問題である。

させて${\displaystyle X}$すべてのサンプルのインスタンス空間またはエンコーディングと呼ばれる集合です。文字認識問題では、インスタンス空間は${\displaystyle X=\{0,1\}^{n}}$区間問題では、インスタンス空間は、${\displaystyle X}$は、 のすべての有界区間の集合です。${\displaystyle \mathbb {R} }$、 どこ${\displaystyle \mathbb {R} }$は、すべての実数の集合を表します。

概念は部分集合である${\displaystyle c\subset X}$1つの概念は、ビットのすべてのパターンの集合です。${\displaystyle X=\{0,1\}^{n}}$文字「P」の画像をエンコードする。2 番目の例の概念の例は、開区間の集合である。${\displaystyle \{(a,b)\mid 0\leq a\leq \pi /2,\pi \leq b\leq {\sqrt {13}}\}}$それぞれに肯定的な点のみが含まれている。概念クラス${\displaystyle C}$は、概念の集合体です。${\displaystyle X}$これは、スケルトン化された4 接続のビット配列のすべての部分集合の集合である可能性があります(フォントの幅は 1 です)。

させて${\displaystyle \operatorname {EX} (c,D)}$例を示す手順である。${\displaystyle x}$確率分布を用いて${\displaystyle D}$正しいラベルが付けられます${\displaystyle c(x)}$つまり、1 の場合${\displaystyle x\in c}$それ以外の場合は0。

さて、${\displaystyle 0<\epsilon ,\delta <1}$アルゴリズムが存在すると仮定します${\displaystyle A}$そして多項式${\displaystyle p}$で${\displaystyle 1/\epsilon ,1/\delta }$（およびクラスのその他の関連パラメータ）${\displaystyle C}$）したがって、サイズ のサンプルが与えられた場合${\displaystyle p}$に従って描かれた${\displaystyle \operatorname {EX} (c,D)}$そして、少なくとも${\displaystyle 1-\delta }$、${\displaystyle A}$仮説を出力する${\displaystyle h\in C}$平均誤差が以下${\displaystyle \epsilon }$の上${\displaystyle X}$同じ分布で${\displaystyle D}$さらに、上記のアルゴリズムに関する記述が${\displaystyle A}$すべての概念に当てはまる${\displaystyle c\in C}$そして各分布について${\displaystyle D}$以上${\displaystyle X}$、そしてすべての${\displaystyle 0<\epsilon ,\delta <1}$ それから${\displaystyle C}$は（効率的に）PAC学習可能（または分布フリーPAC学習可能）である。また、次のように言うこともできる。${\displaystyle A}$PAC学習アルゴリズムは${\displaystyle C}$。

いくつかの正則条件の下では、これらの条件は同等である: ^{[ 3 ]}

1. 概念クラスCはPAC学習可能である。
2. CのVC次元は有限である。
3. Cは一様グリベンコ・カンテリ類である。
4. Cはリトルストーンとウォーマスの意味で圧縮可能である。

• データマイニング
• エラー耐性（PAC学習）
• オッカムの学習
• サンプルの複雑さ

• M. Kearns、U. Vazirani。『計算学習理論入門』 MIT Press、1994年。教科書。
• M. Mohri、A. Rostamizadeh、A. Talwalkar著。『機械学習の基礎』 MIT Press、2018年。第2章では、PAC学習可能性について詳細に解説しています。出版社からオープンアクセスで閲覧可能です。
• D. Haussler著。「おそらく近似的に正しい（PAC）学習フレームワークの概要」。このトピックの紹介。
• L. ヴァリアント著『おそらくほぼ正しい』（Probably Almost Correct）。ベーシックブックス、2013年。本書の中でヴァリアントは、PAC学習は生物がどのように進化し学習するかを説明するものであると主張している。
• Littlestone, N.; Warmuth, MK (1986年6月10日) 「データ圧縮と学習可能性の関係」（PDF） 。2017年8月9日にオリジナル（PDF）からアーカイブされました。
• Moran, Shay; Yehudayoff, Amir (2015). "VCクラスのサンプル圧縮方式". arXiv : 1503.06960 [ cs.LG ].

• PAC学習のインタラクティブな説明