サンプルの複雑さ

機械学習アルゴリズムのサンプル複雑度は、ターゲット関数を正常に学習するために必要なトレーニング サンプルの数を表します。

より正確には、サンプル複雑度は、アルゴリズムによって返される関数が、可能な限り最良の関数の任意の小さな誤差内に収まり、確率が 1 に任意に近くなるように、アルゴリズムに提供する必要があるトレーニング サンプルの数です。

サンプルの複雑さには 2 つの種類があります。

• 弱い変種は特定の入出力分布を固定します。
• 強力なバリアントは、すべての入出力分布で最悪のケースのサンプル複雑度を採用します。

以下で説明する「ノーフリーランチ定理」は、一般に強いサンプルの複雑度は無限であること、つまり有限の数のトレーニングサンプルを使用してグローバルに最適なターゲット関数を学習できるアルゴリズムは存在しないことを証明します。

しかし、特定のクラスのターゲット関数（例えば線形関数のみ）にのみ興味がある場合、サンプルの複雑さは有限であり、ターゲット関数のクラスのVC次元に線形に依存します。 ^[1]

を入力空間と呼ぶ空間とし、を出力空間と呼ぶ空間とし、積 を表すものとします。たとえば、バイナリ分類の設定では、は通常、有限次元ベクトル空間であり、は集合 です。 ${\displaystyle X}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle X\times Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \{-1,1\}}$

関数 の仮説空間を固定します。 上の学習アルゴリズムは、からへの計算可能な写像です。言い換えれば、有限のトレーニング サンプル シーケンスを入力として受け取り、 から への関数を出力するアルゴリズムです。一般的な学習アルゴリズムには、Tikhonov 正則化の有無にかかわらず、経験的リスク最小化が含まれます。 ${\displaystyle {\mathcal {H}}}$${\displaystyle h\colon X\to Y}$${\displaystyle {\mathcal {H}}}$${\displaystyle Z^{*}}$${\displaystyle {\mathcal {H}}}$${\displaystyle X}$${\displaystyle Y}$

損失関数、例えば の二乗損失を固定する。上の分布が与えられた場合、仮説（関数）の期待リスクは ${\displaystyle {\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}}$${\displaystyle {\mathcal {L}}(y,y')=(y-y')^{2}}$${\displaystyle h(x)=y'}$${\displaystyle \rho }$${\displaystyle X\times Y}$${\displaystyle h\in {\mathcal {H}}}$

${\displaystyle {\mathcal {E}}(h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}(h(x),y)\,d\rho (x,y)}$

この設定では、 が成り立ちます。ここでは学習アルゴリズム、 はすべて から独立して抽出されたベクトルのシーケンスです。各サンプル サイズに対して、最適なリスクセットを定義します。はランダム変数であり、分布 から抽出されたランダム変数 に依存します。アルゴリズムが に確率的に収束する場合、そのアルゴリズムは一貫性があると呼ばれます。言い換えると、すべての に対して、すべてのサンプル サイズ に対して、次の式が成り立つよう な正の整数 が存在するということです。${\displaystyle h={\mathcal {A}}(S_{n})}$${\displaystyle {\mathcal {A}}}$${\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}$${\displaystyle \rho }$$${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).}$$${\displaystyle h_{n}={\mathcal {A}}(S_{n})}$ ${\displaystyle n}$${\displaystyle h_{n}}$${\displaystyle S_{n}}$${\displaystyle \rho ^{n}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {E}}(h_{n})}$${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$${\displaystyle \epsilon ,\delta >0}$${\displaystyle N}$${\displaystyle n\geq N}$

$${\displaystyle \Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .}$$の サンプル複雑度は、 、およびの関数として、これが成り立つ最小値です。のこの値が、およびに依存することを強調するために、サンプル複雑度を と書きます。 が と一致しない場合は、 と設定します。 が有限である のアルゴリズムが存在する場合、仮説空間は学習可能であると言えます。 ${\displaystyle {\mathcal {A}}}$${\displaystyle N}$${\displaystyle \rho ,\epsilon }$${\displaystyle \delta }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle N}$${\displaystyle \rho ,\epsilon }$${\displaystyle \delta }$${\displaystyle {\mathcal {A}}}$${\displaystyle N(\rho ,\epsilon ,\delta )=\infty }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle {\mathcal {H}}}$

言い換えれば、サンプルの複雑さはアルゴリズムの一貫性の率を定義します。つまり、望ましい精度と信頼度が与えられた場合、出力関数のリスクが可能な限り最良の範囲内にあり、少なくとも確率が であることを保証するためにデータポイントをサンプルする必要があります。^[2]${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle \epsilon }$${\displaystyle \delta }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle \epsilon }$${\displaystyle 1-\delta }$

おそらく近似的に正しい (PAC) 学習では、サンプル複雑度が多項式 であるかどうか、つまり がおよび の多項式によって制限されるかどうかが問題になります。 が何らかの学習アルゴリズムに対して多項式である場合、仮説空間は PAC 学習可能であると言えます。これは、学習可能であることよりも強い概念です。 ${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle 1/\epsilon }$${\displaystyle 1/\delta }$${\displaystyle N(\rho ,\epsilon ,\delta )}$${\displaystyle {\mathcal {H}}}$

強い意味でサンプル複雑度が有限であるような学習アルゴリズムが存在するかどうか、つまり、指定された目標誤差で入力出力空間上の任意の分布をアルゴリズムが学習するために必要なサンプル数に上限があるかどうかを問うことができます。より正式には、すべて の に対して、すべての に対して、次の正の整数が存在するような学習アルゴリズムが存在するかどうかを尋ねます。${\displaystyle {\mathcal {A}}}$${\displaystyle \epsilon ,\delta >0}$${\displaystyle N}$${\displaystyle n\geq N}$

$${\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}$$ ここで、は上記と同じである。ノーフリーランチ定理によれば、仮説空間 に制限がなければ、これは当てはまらない、つまり、サンプル複雑度が任意に大きい「悪い」分布が常に存在する。^[1]${\displaystyle h_{n}={\mathcal {A}}(S_{n})}$${\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}$${\displaystyle {\mathcal {H}}}$

したがって、量の収束速度について述べるためには 、 $${\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}$$

• 確率分布の空間を制約する（例えばパラメトリックアプローチによる）${\displaystyle \rho }$
• 分布フリーアプローチと同様に、仮説の空間を制約します。${\displaystyle {\mathcal {H}}}$

後者のアプローチは、空間の複雑さを制御するVC次元やラデマッハ複雑性などの概念につながります。仮説空間が小さいほど推論プロセスに多くのバイアスが導入され、より大きな空間での最善のリスクよりも大きくなる可能性があります。ただし、仮説空間の複雑さを制限することで、アルゴリズムがより均一で一貫した関数を生成することが可能になります。このトレードオフが正則化の概念につながります。^[2]${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$

VC 理論の定理によれば、仮説空間に対して次の 3 つのステートメントは同等です。 ${\displaystyle {\mathcal {H}}}$

1. ${\displaystyle {\mathcal {H}}}$PAC 学習可能です。
2. の VC 次元は有限です。${\displaystyle {\mathcal {H}}}$
3. ${\displaystyle {\mathcal {H}}}$は一様なグリベンコ・カンテリ類である。

これにより、特定の仮説空間が PAC 学習可能であり、ひいては学習可能であることを証明する方法が提供されます。

${\displaystyle X=\mathbb {R} ^{d},Y=\{-1,1\}}$とし、を 上のアフィン関数の空間、つまり、ある に対して の形式の関数とします。これは、オフセット学習問題による線形分類です。正方形内の 4 つの共面点は、いかなるアフィン関数によっても分割できません。これは、対角線上の 2 つの頂点で正になり、残りの 2 つの頂点で負になるアフィン関数は存在しないためです。したがって、 の VC 次元はであるため、有限です。PAC 学習可能クラスの上記の特徴付けにより、 はPAC 学習可能であり、ひいては学習可能 であることがわかります。${\displaystyle {\mathcal {H}}}$${\displaystyle X}$${\displaystyle x\mapsto \langle w,x\rangle +b}$${\displaystyle w\in \mathbb {R} ^{d},b\in \mathbb {R} }$${\displaystyle {\mathcal {H}}}$${\displaystyle d+1}$${\displaystyle {\mathcal {H}}}$

がバイナリ関数のクラス（ への関数）である とします。すると、 はサンプルサイズ で -PAC 学習可能に なります。 ^[3] ここでは のVC 次元です。さらに、の任意の -PAC 学習アルゴリズムはサンプル複雑度を持たなければなりません。^[4] したがって、サンプル複雑度は仮説空間のVC 次元の線形関数です。 ${\displaystyle {\mathcal {H}}}$${\displaystyle \{0,1\}}$${\displaystyle {\mathcal {H}}}$${\displaystyle (\epsilon ,\delta )}$ $${\displaystyle N=O{\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}$$${\displaystyle VC({\mathcal {H}})}$${\displaystyle {\mathcal {H}}}$${\displaystyle (\epsilon ,\delta )}$${\displaystyle {\mathcal {H}}}$ $${\displaystyle N=\Omega {\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}$$

が の範囲を持つ実数値関数のクラスであるとします。このとき、はサイズのサンプルで -PAC 学習可能 です: ^{[5] [6]} ここで はのポラードの擬似次元です。 ${\displaystyle {\mathcal {H}}}$${\displaystyle [0,T]}$${\displaystyle {\mathcal {H}}}$${\displaystyle (\epsilon ,\delta )}$ $${\displaystyle N=O{\bigg (}T^{2}{\frac {PD({\mathcal {H}})\ln {T \over \epsilon }+\ln {1 \over \delta }}{\epsilon ^{2}}}{\bigg )}}$$${\displaystyle PD({\mathcal {H}})}$${\displaystyle {\mathcal {H}}}$

教師あり学習の設定に加えて、サンプル複雑性は、能動学習^[7]を含む半教師あり学習の問題にも関連しており、アルゴリズムは、多くのラベルを取得するコストを削減するために、特定の入力に対するラベルを求めることができます。サンプル複雑性の概念は、強化学習^[8]、オンライン学習、および辞書学習などの教師なしアルゴリズムにも現れます。^[9]

サンプル複雑度が高いということは、モンテカルロ木探索を実行するために多くの計算が必要であることを意味します。^[10]これは、状態空間におけるモデルフリーの総当たり探索に相当します。対照的に、高効率アルゴリズムはサンプル複雑度が低くなります。^[11]サンプル複雑度を減らすための可能な技術としては、メトリック学習^[12]とモデルベース強化学習があります。^[13]

• アクティブラーニング（機械学習）