Attribute of machine learning models
機械学習 アルゴリズムの サンプル 複雑度は、 ターゲット関数を正常に学習するために必要なトレーニング サンプルの数を表します。
より正確には、サンプルの複雑さは、アルゴリズムによって返される関数が可能な限り最良の関数の任意の小さな誤差内に収まり、確率が 1 に任意に近くなるように、アルゴリズムに提供する必要があるトレーニング サンプルの数です。
サンプルの複雑さには 2 つの種類があります。
弱い変種は特定の入出力分布を固定します。 強力なバリアントは、すべての入出力分布にわたって最悪のケースのサンプル複雑度を採用します。 以下で説明する「 ノーフリーランチ定理」 は、一般に、強いサンプルの複雑度は無限であること、つまり、有限の数のトレーニング サンプルを使用してグローバルに最適なターゲット関数を学習できるアルゴリズムは存在しないことを証明します。
しかし、特定のクラスの対象関数（例えば線形関数のみ）にのみ関心がある場合、サンプルの複雑さは有限であり、対象関数のクラスの VC次元 に線形に依存します。 [1]
意味 を入力空間と呼ぶ空間とし、 を 出力空間と呼ぶ空間とし、 積 を表すものとします 。例えば、二項分類の設定では、 は通常有限次元ベクトル空間であり、 は集合 となります 。 X {\displaystyle X} Y {\displaystyle Y} Z {\displaystyle Z} X × Y {\displaystyle X\times Y} X {\displaystyle X} Y {\displaystyle Y} { − 1 , 1 } {\displaystyle \{-1,1\}}
関数 の 仮説空間を固定する 。 上の学習アルゴリズムは、 から へ の計算可能な写像である 。言い換えれば、有限個の訓練サンプル列を入力として受け取り、 から への関数を出力するアルゴリズムである 。代表的な学習アルゴリズムには、 ティホノフ正則化 の有無にかかわらず、 経験的リスク最小化 が ある。 H {\displaystyle {\mathcal {H}}} h : X → Y {\displaystyle h\colon X\to Y} H {\displaystyle {\mathcal {H}}} Z {\displaystyle Z} H {\displaystyle {\mathcal {H}}} X {\displaystyle X} Y {\displaystyle Y}
損失関数 （例えば、 の二乗損失 ）を固定する。 上の 与えられた分布に対して 、 仮説（関数）の 期待リスク は L : Y × Y → R ≥ 0 {\displaystyle {\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}} L ( y , y ′ ) = ( y − y ′ ) 2 {\displaystyle {\mathcal {L}}(y,y')=(y-y')^{2}} h ( x ) = y ′ {\displaystyle h(x)=y'} ρ {\displaystyle \rho } X × Y {\displaystyle X\times Y} h ∈ H {\displaystyle h\in {\mathcal {H}}}
E ( h ) := E ρ [ L ( h ( x ) , y ) ] = ∫ X × Y L ( h ( x ) , y ) d ρ ( x , y ) {\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)} この設定では、 が成り立ちます。 ここで は学習アルゴリズム、 は すべて から独立に抽出されたベクトルの列です。 各 サンプルサイズ に対して、最適なリスク セットを定義します 。は 確率変数 であり、 分布 から抽出された 確率変数 に依存します 。このアルゴリズムは、 確率的に に収束する 場合、 一貫性がある と呼ばれます 。言い換えれば、すべての に対して 、正の整数 が存在し 、すべてのサンプルサイズ に対して 、次の式が成り立ちます
。 h = A ( S n ) {\displaystyle h={\mathcal {A}}(S_{n})} A {\displaystyle {\mathcal {A}}} S n = ( ( x 1 , y 1 ) , … , ( x n , y n ) ) ∼ ρ n {\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}} ρ {\displaystyle \rho } E H ∗ = inf h ∈ H E ( h ) . {\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).} h n = A ( S n ) {\displaystyle h_{n}={\mathcal {A}}(S_{n})} n {\displaystyle n} h n {\displaystyle h_{n}} S n {\displaystyle S_{n}} ρ n {\displaystyle \rho ^{n}} A {\displaystyle {\mathcal {A}}} E ( h n ) {\displaystyle {\mathcal {E}}(h_{n})} E H ∗ {\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}} ϵ , δ > 0 {\displaystyle \epsilon ,\delta >0} N {\displaystyle N} n ≥ N {\displaystyle n\geq N}
Pr ρ n [ E ( h n ) − E H ∗ ≥ ε ] < δ . {\displaystyle \Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .} の サンプル 複雑度 は、 、および の 関数として、これが成り立つ 最小値です。 のこの値が 、および に依存することを強調するため に、サンプル複雑度を と書きます。 が と 一致しない 場合 は 、 と設定します 。 が有限であるアルゴリズムが存在する場合、仮説空間は 学習可能で ある と言えます 。 A {\displaystyle {\mathcal {A}}} N {\displaystyle N} ρ , ϵ {\displaystyle \rho ,\epsilon } δ {\displaystyle \delta } N ( ρ , ϵ , δ ) {\displaystyle N(\rho ,\epsilon ,\delta )} N {\displaystyle N} ρ , ϵ {\displaystyle \rho ,\epsilon } δ {\displaystyle \delta } A {\displaystyle {\mathcal {A}}} N ( ρ , ϵ , δ ) = ∞ {\displaystyle N(\rho ,\epsilon ,\delta )=\infty } N ( ρ , ϵ , δ ) {\displaystyle N(\rho ,\epsilon ,\delta )} H {\displaystyle {\mathcal {H}}}
言い換えれば、サンプルの複雑さは アルゴリズムの一貫性の速度を定義します。つまり、望ましい精度 と信頼度が与えられた場合、出力関数のリスクが 可能な限り最良の範囲内にあり、少なくとも確率が である ことを保証するためにデータポイント をサンプリングする必要があります 。 [2] N ( ρ , ϵ , δ ) {\displaystyle N(\rho ,\epsilon ,\delta )} ϵ {\displaystyle \epsilon } δ {\displaystyle \delta } N ( ρ , ϵ , δ ) {\displaystyle N(\rho ,\epsilon ,\delta )} ϵ {\displaystyle \epsilon } 1 − δ {\displaystyle 1-\delta }
おそらく近似的に正しい（PAC）学習 では 、サンプル複雑度が 多項式 であるかどうか、つまり が および において多項式で有界であるかどうかが 問題 となります 。 ある学習アルゴリズムにおいて が多項式である場合、仮説空間は PAC 学習可能で あるといいます 。これは、学習可能であることよりも強い概念です。 N ( ρ , ϵ , δ ) {\displaystyle N(\rho ,\epsilon ,\delta )} 1 / ϵ {\displaystyle 1/\epsilon } 1 / δ {\displaystyle 1/\delta } N ( ρ , ϵ , δ ) {\displaystyle N(\rho ,\epsilon ,\delta )} H {\displaystyle {\mathcal {H}}}
無制限の仮説空間：無限のサンプル複雑性 強い意味でサンプル複雑度が有限であるような学習アルゴリズムが存在するかどうか、つまり、指定された目標誤差を持つ入出力空間上の任意の分布をアルゴリズムが学習するために必要なサンプル数に上限があるかどうかという問いがある。より正式には、すべての に対して、すべての に対して、次式を満たす正の整数が存在するような学習アルゴリズムが存在するかどうかという 問い が ある 。 A {\displaystyle {\mathcal {A}}} ϵ , δ > 0 {\displaystyle \epsilon ,\delta >0} N {\displaystyle N} n ≥ N {\displaystyle n\geq N}
sup ρ ( Pr ρ n [ E ( h n ) − E H ∗ ≥ ε ] ) < δ , {\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,} ここで 、は 上記の通りである。 ノー・フリー・ランチ定理に よれば、仮説空間に制約がなければ 、これは当てはまらない。つまり、標本複雑度が任意に大きい「悪い」分布が常に存在する。 [1] h n = A ( S n ) {\displaystyle h_{n}={\mathcal {A}}(S_{n})} S n = ( ( x 1 , y 1 ) , … , ( x n , y n ) ) ∼ ρ n {\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}} H {\displaystyle {\mathcal {H}}}
したがって、量の収束速度について述べるためには 、 sup ρ ( Pr ρ n [ E ( h n ) − E H ∗ ≥ ε ] ) , {\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}
確率分布の空間を制約する （例えばパラメトリックアプローチによる） ρ {\displaystyle \rho } 分布フリーアプローチと同様に、 仮説の空間を制約します。 H {\displaystyle {\mathcal {H}}}
制限された仮説空間：有限サンプル複雑度 後者のアプローチは、 VC次元 や ラデマッハー複雑性 といった、 空間の複雑性を制御する概念につながる 。仮説空間が小さいほど推論プロセスにバイアスがかかり、 より大きな空間で実現可能な最善のリスクよりも大きくなる可能性がある。しかし、仮説空間の複雑性を制限することで、アルゴリズムはより均一で一貫性のある関数を生成することが可能になる。このトレードオフが 正則化 の概念につながる。 [2] H {\displaystyle {\mathcal {H}}} E H ∗ {\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}
VC理論 の定理によれば 、仮説空間に対して次の3つのステートメントは同等である 。 H {\displaystyle {\mathcal {H}}}
H {\displaystyle {\mathcal {H}}} PAC 学習可能です。 の VC 次元 は有限です。 H {\displaystyle {\mathcal {H}}} H {\displaystyle {\mathcal {H}}} は一様な グリベンコ・カンテリ類 である。 これにより、特定の仮説空間が PAC 学習可能であり、さらには学習可能であることを証明する方法が提供されます。
PAC学習可能な仮説空間の例 X = R d , Y = { − 1 , 1 } {\displaystyle X=\mathbb {R} ^{d},Y=\{-1,1\}} とし、 を 上のアフィン関数の空間 、つまり に対しての形をとる関数の空間とします 。これはオフセット学習を伴う線形分類問題です。正方形内の4つの共面点は、いかなるアフィン関数によっても分割されることはありません。なぜなら、対角線上の2つの頂点で正、残りの2つの頂点で負となるアフィン関数は存在しないからです。したがって、 のVC次元は であり、有限です。上記のPAC学習可能クラスの特性から、 は PAC学習可能であり、拡張して学習可能であること がわかります。 H {\displaystyle {\mathcal {H}}} X {\displaystyle X} x ↦ ⟨ w , x ⟩ + b {\displaystyle x\mapsto \langle w,x\rangle +b} w ∈ R d , b ∈ R {\displaystyle w\in \mathbb {R} ^{d},b\in \mathbb {R} } H {\displaystyle {\mathcal {H}}} d + 1 {\displaystyle d+1} H {\displaystyle {\mathcal {H}}}
サンプル複雑度の境界 が二項関数（ から への関数）のクラスである とする 。すると、 は サンプルサイズ で -PAC 学習可能である： [3] ここで は の VC 次元 である 。さらに、 に対する任意の -PAC 学習アルゴリズムは サンプル複雑度を持つ必要がある： [4] したがって、サンプル複雑度は仮説空間の VC 次元 の線形関数である。 H {\displaystyle {\mathcal {H}}} { 0 , 1 } {\displaystyle \{0,1\}} H {\displaystyle {\mathcal {H}}} ( ϵ , δ ) {\displaystyle (\epsilon ,\delta )} N = O ( V C ( H ) + ln 1 δ ϵ ) {\displaystyle N=O{\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}} V C ( H ) {\displaystyle VC({\mathcal {H}})} H {\displaystyle {\mathcal {H}}} ( ϵ , δ ) {\displaystyle (\epsilon ,\delta )} H {\displaystyle {\mathcal {H}}} N = Ω ( V C ( H ) + ln 1 δ ϵ ) {\displaystyle N=\Omega {\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}
が の範囲を持つ実数値関数のクラスである とする 。このとき、 は サンプルサイズ で -PAC 学習可能である: [5] [6] ここで は のポラード擬次元 である 。 H {\displaystyle {\mathcal {H}}} [ 0 , T ] {\displaystyle [0,T]} H {\displaystyle {\mathcal {H}}} ( ϵ , δ ) {\displaystyle (\epsilon ,\delta )} N = O ( T 2 P D ( H ) ln T ϵ + ln 1 δ ϵ 2 ) {\displaystyle N=O{\bigg (}T^{2}{\frac {PD({\mathcal {H}})\ln {T \over \epsilon }+\ln {1 \over \delta }}{\epsilon ^{2}}}{\bigg )}} P D ( H ) {\displaystyle PD({\mathcal {H}})} H {\displaystyle {\mathcal {H}}}
その他の設定 教師あり学習の設定に加えて、サンプル複雑性は、 能動学習 [7]を含む 半教師あり学習の 問題にも関連しています。能動学習 では、アルゴリズムは特定の入力に対してラベルを要求することで、多くのラベルを取得するコストを削減できます。サンプル複雑性の概念は 、 強化学習 [ 8] 、 オンライン学習、そして 辞書学習 などの教師なしアルゴリズムにも見られます 。 [9]
ロボット工学における効率性 サンプル複雑度が高いということは、 モンテカルロ木探索を 実行するために多くの計算が必要となることを意味します。 [10]これは、状態空間における モデルフリーの総当たり 探索と同等です 。対照的に、高効率アルゴリズムはサンプル複雑度が低くなります。 [11] サンプル複雑度を低減する可能性のある技術としては、 計量学習 [12] とモデルベース強化学習 [13]が挙げられます。
参照
参考文献 ^ ab Vapnik, Vladimir (1998)、 「統計学習理論」 、ニューヨーク：Wiley。 ^ ab Rosasco, Lorenzo (2014)、 「一貫性、学習可能性、および正規化」 、MITコース9.520の講義ノート。 ^ Steve Hanneke (2016). 「PAC学習における最適なサンプル複雑度」 J. Mach. Learn. Res . 17 (1): 1319– 1333. arXiv : 1507.00473 . ^ Ehrenfeucht, Andrzej; Haussler, David; Kearns, Michael; Valiant, Leslie (1989). 「学習に必要な例の数に関する一般的な下限値」. Information and Computation . 82 (3): 247. doi : 10.1016/0890-5401(89)90002-3 . ^ アンソニー・マーティン著、バートレット・ピーター・L.著 (2009). ニューラルネットワーク学習：理論的基礎 . ISBN 9780521118620 。 ^ Morgenstern, Jamie ; Roughgarden, Tim (2015). 近似最適オークションの擬似次元について. NIPS. Curran Associates. pp. 136– 144. arXiv : 1506.03684 . ^ Balcan, Maria-Florina ; Hanneke, Steve; Wortman Vaughan, Jennifer (2010). 「能動学習における真のサンプル複雑性」. 機械学習 . 80 ( 2–3 ): 111–139 . doi : 10.1007/s10994-010-5174-y . ^ Kakade, Sham (2003)、「強化学習のサンプル複雑性について」 (PDF) 、博士論文、ユニバーシティ・カレッジ・ロンドン: Gatsby Computational Neuroscience Unit。 ^ Vainsencher, Daniel; Mannor, Shie; Bruckstein, Alfred (2011). 「辞書学習におけるサンプル複雑性」 (PDF) . Journal of Machine Learning Research . 12 : 3259–3281 . ^ Kaufmann, Emilie and Koolen, Wouter M (2017). 最良アーム識別によるモンテカルロ木探索 . ニューラル情報処理システムの進歩. pp. 4897– 4906. {{cite conference }}: CS1 maint: multiple names: authors list (link )^ フィデルマン、ペギー、ストーン、ピーター (2006). 「あごつねり：脚付きロボットのスキル学習に関する事例研究」 . ロボットサッカーワールドカップ. シュプリンガー. pp. 59– 71. {{cite conference }}: CS1 maint: multiple names: authors list (link )^ Verma, Nakul、Branson, Kristin (2015). マハラノビス距離指標の学習におけるサンプル複雑性 . ニューラル情報処理システムの進歩. pp. 2584– 2592. {{cite conference }}: CS1 maint: multiple names: authors list (link )^ クルタック、タナルドとクラベラ、イグナシとドゥアン、ヤンとタマル、アビブとアッビール、ピーター (2018)。 「モデル アンサンブルの信頼領域ポリシーの最適化」。 arXiv : 1802.10592 [cs.LG]。 {{cite arXiv }}: CS1 maint: multiple names: authors list (link )
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98594a59eb6e7d6681c3ffded4aff29a40d662d6)
![{\displaystyle \Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c54209269901f58dc3a95ead678ff35ad78b89)
![{\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59e467d266a5e5a021a14cec001e9cc0818f60f7)
![{\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b31b53ba029c8441130ee6c7d23b5a00df160580)
![{\displaystyle [0,T]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35ccef2d3dc751e081375d51c111709d8a1d7ac6)
