おそらくほぼ正しい学習

計算学習理論において、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} }$

概念は のサブセットです。概念の 1 つは、文字「P」の絵をエンコードする のビットのすべてのパターンの集合です。 2 番目の例の概念の例は、それぞれ正の点のみを含む開区間の集合 です。概念クラスは上の概念のコレクションです。 これは、スケルトン化された4 連結のビット配列のすべてのサブセットの集合である可能性があります(フォントの幅は 1)。 ${\displaystyle c\subset X}$${\displaystyle X=\{0,1\}^{n}}$${\displaystyle \{(a,b)\mid 0\leq a\leq \pi /2,\pi \leq b\leq {\sqrt {13}}\}}$ ${\displaystyle C}$${\displaystyle X}$

を、確率分布を使用して例 を描画し、正しいラベル（ の場合は 1 、それ以外の場合は 0）を与える手順とします。 ${\displaystyle \operatorname {EX} (c,D)}$${\displaystyle x}$${\displaystyle D}$${\displaystyle c(x)}$${\displaystyle x\in c}$

ここで、 が与えられている場合、 （およびクラス の他の関連パラメータ）にアルゴリズムと多項式があり、に従って抽出されたサイズのサンプルが与えられると、 の確率以上で、において平均誤差が 未満か に​​等しい仮説が同じ分布 で出力されると仮定します。さらに、 アルゴリズム に関する上記のステートメントが、 のすべての概念と 上のすべての分布、およびすべて に対して真である場合、は（効率 的に）PAC 学習可能（または分布フリー PAC 学習可能）です。は に対するPAC 学習アルゴリズムであると言うこともできます。 ${\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}$${\displaystyle A}$${\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. ヴァリアント。おそらくほぼ正しい。Basic Books、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学習のインタラクティブな説明