エラー許容度（PAC学習）

PAC 学習では、エラー許容度とは、受け取った例が何らかの形で破損している場合にアルゴリズムが学習する能力を指します。実際、多くのアプリケーションではノイズのないデータにアクセスすることができないため、これは非常に一般的で重要な問題です。ノイズはさまざまなレベルで学習プロセスを妨げる可能性があります。アルゴリズムが誤ってラベル付けされたデータを受け取ったり、入力に誤った情報が含まれていたり、例の分類が悪意を持って改ざんされたりする可能性があります。

以下では、を - 次元の入力空間とします。を 上で定義された- 値の対象関数を学習するために使用したい関数のクラスとします。を 上の入力の分布とします。学習アルゴリズムの目標は、を最小化する最適な関数を選択することです。の複雑さを測定できる関数があるとします。を、呼び出されるたびに例とその正しいラベルを返すオラクルとします。 ${\displaystyle X}$${\displaystyle n}$${\displaystyle {\mathcal {H}}}$${\displaystyle \{0,1\}}$${\displaystyle f}$${\displaystyle X}$${\displaystyle {\mathcal {D}}}$${\displaystyle X}$${\displaystyle {\mathcal {A}}}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle error(h)=P_{x\sim {\mathcal {D}}}(h(x)\neq f(x))}$${\displaystyle size(f)}$${\displaystyle f}$${\displaystyle {\text{Oracle}}(x)}$${\displaystyle x}$${\displaystyle f(x)}$

ノイズによってデータが破損していない場合、Valiant設定で学習を定義できます。^{[1] [2]}

定義:および任意の および に対して、 で制限されるオラクルへの呼び出し回数で、少なくとも条件 を満たす関数を出力するような多項式にアクセスできる学習アルゴリズムが存在する場合、 Valiant設定でを使用して が効率的に学習可能であると言います。 ${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x)}$${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot )}$${\displaystyle 0<\varepsilon \leq 1}$${\displaystyle 0<\delta \leq 1}$${\displaystyle p\left({\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,{\text{size}}(f)\right)}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle 1-\delta }$${\displaystyle {\text{error}}(h)\leq \varepsilon }$

以下では、データが何らかの変更を受けた場合の学習可能性を定義します。^{[3] [4] [5]}${\displaystyle f}$

分類ノイズモデル^[6]では、ノイズ率 が導入されています。すると、たとえば の正しいラベルを常に返すの代わりに、アルゴリズム は、確率 でのラベルを反転する誤ったオラクルしか呼び出せません。Valiant の場合と同様に、学習アルゴリズムの目標はを最小化する最適な関数を選択することです。アプリケーションでは の実際の値にアクセスすることは困難ですが、その上限 にアクセスできると仮定しています。^[7]ノイズ率を にすると、どのラベルもターゲット関数に関する情報を伝えないため、どのような計算時間でも学習が不可能になることに注意してください。 ${\displaystyle 0\leq \eta <{\frac {1}{2}}}$${\displaystyle {\text{Oracle}}(x)}$${\displaystyle x}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\eta )}$${\displaystyle x}$${\displaystyle \eta }$${\displaystyle {\mathcal {A}}}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle error(h)=P_{x\sim {\mathcal {D}}}(h(x)\neq f(x))}$${\displaystyle \eta }$${\displaystyle \eta _{B}}$${\displaystyle 1/2}$

定義:および任意の に対して となる多項式にアクセスできる学習アルゴリズムが存在し、 で制限されるオラクルへの呼び出し回数で、少なくとも条件 を確率で満たす関数を出力する場合、分類ノイズ モデルでを使用して が 効率 的に学習可能であると言います。 ${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\eta )}$${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot )}$${\displaystyle 0\leq \eta \leq {\frac {1}{2}}}$${\displaystyle 0\leq \varepsilon \leq 1}$${\displaystyle 0\leq \delta \leq 1}$${\displaystyle p\left({\frac {1}{1-2\eta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,size(f)\right)}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle 1-\delta }$${\displaystyle error(h)\leq \varepsilon }$

統計的クエリ学習^[8]は能動学習問題の一種であり、学習アルゴリズムは関数が例 に正しくラベルを付ける可能性に関する情報を要求するかどうかを決定し、許容値 内で正確な回答を受け取ることができる。正式には、学習アルゴリズムがオラクル を呼び出すたびに、フィードバック確率 として を受け取り、 となる。 ${\displaystyle {\mathcal {A}}}$${\displaystyle P_{f(x)}}$${\displaystyle f}$${\displaystyle x}$${\displaystyle \alpha }$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\alpha )}$${\displaystyle Q_{f(x)}}$${\displaystyle Q_{f(x)}-\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha }$

定義:および多項式 、、にアクセスできる学習アルゴリズムが存在し、任意の に対して次が成り立つ場合、統計クエリ 学習モデルでを使用して が効率的に学習可能である と言います。 ${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\alpha )}$${\displaystyle p(\cdot ,\cdot ,\cdot )}$${\displaystyle q(\cdot ,\cdot ,\cdot )}$${\displaystyle r(\cdot ,\cdot ,\cdot )}$${\displaystyle 0<\varepsilon \leq 1}$

1. ${\displaystyle {\text{Oracle}}(x,\alpha )}$時間内に評価できる。${\displaystyle P_{f(x)}}$${\displaystyle q\left({\frac {1}{\varepsilon }},n,size(f)\right)}$
2. ${\displaystyle {\frac {1}{\alpha }}}$境界は${\displaystyle r\left({\frac {1}{\varepsilon }},n,size(f)\right)}$
3. ${\displaystyle {\mathcal {A}}}$は、 で制限されるオラクルの呼び出し回数で、となるモデルを出力します。${\displaystyle h}$${\displaystyle err(h)<\varepsilon }$${\displaystyle p\left({\frac {1}{\varepsilon }},n,size(f)\right)}$

信頼度パラメータは学習の定義には現れないことに注意してください。これは、 の主な目的が、代表的でないサンプルによる学習アルゴリズムの失敗の小さな確率を許容することだからです。 は常に近似基準を満たすことが保証されるようになったため、失敗確率は不要になりました。 ${\displaystyle \delta }$${\displaystyle \delta }$${\displaystyle {\text{Oracle}}(x,\alpha )}$${\displaystyle Q_{f(x)}-\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha }$

統計的クエリモデルはPACモデルよりも厳密には弱い。効率的にSQ学習可能なクラスは分類ノイズの存在下で効率的にPAC学習可能であるが、効率的にSQ学習可能ではないパリティなどの効率的にPAC学習可能な問題も存在する。^[8]

悪意のある分類モデル^[9]では、敵対者は学習アルゴリズムを妨害するためにエラーを生成します。この設定は、限られた時間で伝送機器が繰り返し故障した場合に発生する可能性のあるエラーバーストの状況を表します。正式には、アルゴリズムは、通常どおり、確率 で入力空間上の分布から抽出された正しくラベル付けされた例を返すオラクルを呼び出しますが、確率 で、 に関連しない分布から抽出された例を返します。さらに、この悪意を持って選択された例は、 、、 、または学習アルゴリズムの現在の進行状況を知っている敵対者によって戦略的に選択される可能性があります。 ${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\beta )}$${\displaystyle x}$${\displaystyle {\mathcal {D}}}$${\displaystyle 1-\beta }$${\displaystyle \beta }$${\displaystyle {\mathcal {D}}}$${\displaystyle f}$${\displaystyle \beta }$${\displaystyle {\mathcal {D}}}$

定義:の 境界が与えられている場合、および多項式にアクセスできる学習アルゴリズムが存在し、任意の に対して、 で境界が定められたオラクルへの呼び出し回数で、少なくとも条件 を確率で満たす関数を出力する場合、悪意のある 分類モデルで を使用して が効率的に学習可能であると言えます。 ${\displaystyle \beta _{B}<{\frac {1}{2}}}$${\displaystyle 0\leq \beta <{\frac {1}{2}}}$${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\beta )}$${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot ,\cdot )}$${\displaystyle 0<\varepsilon \leq 1}$${\displaystyle 0<\delta \leq 1}$${\displaystyle p\left({\frac {1}{1/2-\beta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,size(f)\right)}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle 1-\delta }$${\displaystyle error(h)\leq \varepsilon }$

非均一ランダム属性ノイズ^{[10] [11]}モデルでは、アルゴリズムはブール関数を学習しており、悪意のあるオラクルは確率でexampleの各番目のビットを独立して反転する可能性があります。 ${\displaystyle {\text{Oracle}}(x,\nu )}$${\displaystyle i}$${\displaystyle x=(x_{1},x_{2},\ldots ,x_{n})}$${\displaystyle \nu _{i}\leq \nu }$

この種のエラーはアルゴリズムを修復不可能なほど失敗させる可能性があります。実際、次の定理が成り立ちます。

非均一ランダム属性ノイズ設定では、アルゴリズムはの場合にのみとなる関数を出力できます。 ${\displaystyle {\mathcal {A}}}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle error(h)<\varepsilon }$${\displaystyle \nu <2\varepsilon }$