ラデマッハ複雑度

計算学習理論（機械学習と計算理論）において、ハンス・ラーデマッハーにちなんで名付けられたラーデマッハー複雑度は、確率分布に関する集合のクラスの豊かさを測定します。この概念は、実数値関数にも拡張できます。

集合Aが与えられたとき、Aのラデマッハ複雑性は次のように定義される: ^{[1] [2] : 326}${\displaystyle A\subseteq \mathbb {R} ^{m}}$

${\displaystyle \operatorname {Rad} (A):={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{a\in A}\sum _{i=1}^{m}\sigma _{i}a_{i}\right]}$

ここで、 は、ラデマッハ分布から抽出された独立したランダム変数です。つまり、 、 の場合です。著者によっては、最大値を取る前に合計の絶対値を取る人もいますが、が対称である場合は違いはありません。 ${\displaystyle \sigma _{1},\sigma _{2},\dots ,\sigma _{m}}$${\displaystyle \Pr(\sigma _{i}=+1)=\Pr(\sigma _{i}=-1)=1/2}$${\displaystyle i=1,2,\dots ,m}$${\displaystyle a=(a_{1},\ldots ,a_{m})}$${\displaystyle A}$

を点のサンプルとし、 上の実数値関数の関数クラスを考えます。すると、の経験的ラデマッハ複雑度は次のように定義されます。 ${\displaystyle S=\{z_{1},z_{2},\dots ,z_{m}\}\subset Z}$${\displaystyle {\mathcal {F}}}$${\displaystyle Z}$${\displaystyle {\mathcal {F}}}$${\displaystyle S}$

${\displaystyle \operatorname {Rad} _{S}({\mathcal {F}})={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{f\in {\mathcal {F}}}\sum _{i=1}^{m}\sigma _{i}f(z_{i})\right]}$

これは、前の定義を使って次のように書くこともできる: ^{[2] : 326}

${\displaystyle \operatorname {Rad} _{S}({\mathcal {F}})=\operatorname {Rad} ({\mathcal {F}}\circ S)}$

ここで は関数の合成を表します。つまり、 ${\displaystyle {\mathcal {F}}\circ S}$

${\displaystyle {\mathcal {F}}\circ S:=\{(f(z_{1}),\ldots ,f(z_{m}))\mid f\in {\mathcal {F}}\}}$

を 上の確率分布とします。サンプルサイズに対する関数クラスのラーデマッハ複雑度は次のようになります。 ${\displaystyle P}$${\displaystyle Z}$${\displaystyle {\mathcal {F}}}$${\displaystyle P}$${\displaystyle m}$

${\displaystyle \operatorname {Rad} _{P,m}({\mathcal {F}}):=\mathbb {E} _{S\sim P^{m}}\left[\operatorname {Rad} _{S}({\mathcal {F}})\right]}$

ここで、上記の期待値は、に従って生成された同一独立分布（iid）サンプルに対して取られます。 ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})}$${\displaystyle P}$

ラデマッハ複雑度は、通常、分類に使用されるモデルの関数クラスに適用され、任意のラベル付けの下で確率空間から抽出された点を分類する能力を測定することを目的としています。関数クラスが十分に豊富な場合、期待値の下でのランダムな抽出によってシミュレートされたラベルの各配置に適切に適応できる関数が含まれ、合計のこの量が最大化されます。 ${\displaystyle \sigma_{i}}$

1.には単一のベクトル（例： ）が含まれます。 ${\displaystyle A}$${\displaystyle A=\{(a,b)\}\subset \mathbb {R} ^{2}}$

${\displaystyle \operatorname {Rad} (A)={1 \over 2}\cdot \left({1 \over 4}\cdot (a+b)+{1 \over 4}\cdot (ab)+{1 \over 4}\cdot (-a+b)+{1 \over 4}\cdot (-ab)\right)=0}$

同じことがすべてのシングルトン仮説クラスにも当てはまります。^{[3] : 56}

2.には2 つのベクトル (例: ) が含まれます。 ${\displaystyle A}$${\displaystyle A=\{(1,1),(1,2)\}\subset \mathbb {R} ^{2}}$

${\displaystyle {\begin{aligned}\operatorname {Rad} (A)&={1 \over 2}\cdot \left({1 \over 4}\cdot \max(1+1,1+2)+{1 \over 4}\cdot \max(1-1,1-2)+{1 \over 4}\cdot \max(-1+1,-1+2)+{1 \over 4}\cdot \max(-1-1,-1-2)\right)\\[5pt]&={1 \over 8}(3+0+1-2)={1 \over 4}\end{aligned}}}$

Rademacher 複雑度は、関数クラスの学習可能性に関するデータ依存の上限を導出するために使用できます。直感的には、Rademacher 複雑度が小さい関数クラスの方が学習が容易です。

機械学習では、サンプルデータの真の分布を表すトレーニングセットが必要です。これは、代表性の概念を使用して定量化できます。サンプルが抽出される確率分布をで表します。仮説（潜在的な分類器）の集合をで表し、対応する誤差関数の集合をで表します。つまり、すべての仮説に対して、各トレーニングサンプル（特徴、ラベル）を分類器の誤差にマッピングする関数が存在します（この場合、仮説と分類器は同じ意味で使用されます）。たとえば、がバイナリ分類器を表す場合、誤差関数は0–1損失関数です。つまり、誤差関数は、サンプルを正しく分類する場合は0を返し、そうでない場合は1を返します。基礎となる仮説が無関係な場合は、インデックスを省略して、代わりにを記述します。定義： ${\displaystyle S}$${\displaystyle P}$${\displaystyle H}$${\displaystyle F}$${\displaystyle h\in H}$${\displaystyle f_{h}\in F}$${\displaystyle h}$${\displaystyle h}$${\displaystyle f_{h}}$${\displaystyle h}$${\displaystyle f}$${\displaystyle f_{h}}$

${\displaystyle L_{P}(f):=\mathbb {E} _{z\sim P}[f(z)]}$–実分布上の何らかの誤差関数の期待誤差。${\displaystyle f\in F}$${\displaystyle P}$

${\displaystyle L_{S}(f):={1 \over m}\sum _{i=1}^{m}f(z_{i})}$–サンプル上の何らかの誤差関数の推定誤差。${\displaystyle f\in F}$${\displaystyle S}$

およびに関するサンプル の代表性は次のように定義されます。 ${\displaystyle S}$${\displaystyle P}$${\displaystyle F}$

${\displaystyle \operatorname {Rep} _{P}(F,S):=\sup _{f\in F}(L_{P}(f)-L_{S}(f))}$

代表性は小さいほど良いです。これは、過剰適合を回避する方法を提供するためです。つまり、分類器の実際の誤差が推定誤差よりそれほど高くないことを意味し、推定誤差が低い分類器を選択すると、実際の誤差も低くなります。ただし、代表性の概念は相対的であるため、異なるサンプル間で比較することはできません。

サンプルの代表性の期待値は、関数クラスのラデマッハ複雑度によって制限される：^{[2] ：326}

$${\displaystyle \mathbb {E} _{S\sim P^{m}}[\operatorname {Rep} _{P}(F,S)]\leq 2\cdot \mathbb {E} _{S\sim P^{m}}[\operatorname {Rad} (F\circ S)]}$$

ラデマッハ複雑度が小さい場合、経験的リスク最小化を使用して仮説クラス H を学習することが可能です。

例えば、（バイナリ誤差関数の場合）^{[2] ：328}あらゆる に対して、少なくとも の確率で、あらゆる仮説に対して： ${\displaystyle \delta >0}$${\displaystyle 1-\delta }$${\displaystyle h\in H}$

${\displaystyle L_{P}(h)-L_{S}(h)\leq 2\operatorname {Rad} (F\circ S)+4{\sqrt {2\ln(4/\delta ) \over m}}}$

ラデマッハ複雑度は小さいほど良いので、様々な関数集合のラデマッハ複雑度の上限を持つことは有用である。集合のラデマッハ複雑度の上限を決めるには、以下の規則を使用することができる。^{[2] : 329–330}${\displaystyle A\subset \mathbb {R} ^{m}}$

1. 内のすべてのベクトルが定数ベクトルによって変換される場合、Rad( A )は変化しません。 ${\displaystyle A}$${\displaystyle a_{0}\in \mathbb {R} ^{m}}$

2. 内のすべてのベクトルにスカラーを掛けると、Rad( A )に が掛けられます。 ${\displaystyle A}$${\displaystyle c\in \mathbb {R} }$${\displaystyle |c|}$

3. . ^{[3] : 56}${\displaystyle \operatorname {Rad} (A+B)=\operatorname {Rad} (A)+\operatorname {Rad} (B)}$

4. (Kakade & Tewari Lemma) 内のすべてのベクトルがLipschitz 関数によって操作される場合、 Rad( A ) は (最大で)関数のLipschitz 定数で乗算されます。特に、内のすべてのベクトルが収縮マッピングによって操作される場合、 Rad( A ) は厳密に減少します。 ${\displaystyle A}$${\displaystyle A}$

5.の凸包のラデマッハ複雑度はRad( A )に等しい。 ${\displaystyle A}$

6. (マサートの補題) 有限集合のラーデマッハ複雑度は集合の大きさとともに対数的に増大する。正式には、を のベクトルの集合とし、を のベクトルの平均とすると、次のようになる。 ${\displaystyle A}$${\displaystyle N}$${\displaystyle \mathbb {R} ^{m}}$${\displaystyle {\bar {a}}}$${\displaystyle A}$

${\displaystyle \operatorname {Rad} (A)\leq \max _{a\in A}\|a-{\bar {a}}\|\cdot {{\sqrt {2\log N}} \over m}}$

特に、がバイナリベクトルの集合である場合、ノルムは最大で となるため、次のようになります。 ${\displaystyle A}$${\displaystyle {\sqrt {m}}}$

${\displaystyle \operatorname {Rad} (A)\leq {\sqrt {2\log N \over m}}}$

VC 次元 が である 集合族を仮定します。の成長関数は次のように制限されることが知られています。 ${\displaystyle H}$${\displaystyle d}$${\displaystyle H}$

全員：${\displaystyle m>d+1}$${\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}}$

これは、最大で個の要素を持つすべての集合に対して、が成り立つことを意味します。集合族は上の 2 値ベクトルの集合として考えることができます。これを Massart の補題に代入すると、次のようになります。 ${\displaystyle h}$${\displaystyle m}$${\displaystyle |H\cap h|\leq (em/d)^{d}}$${\displaystyle H\cap h}$${\displaystyle \mathbb {R} ^{m}}$

${\displaystyle \operatorname {Rad} (H\cap h)\leq {\sqrt {2d\log(em/d) \over m}}}$

より高度な技術（ダドリーのエントロピー境界とハウスラーの上限^[4]）を用いると、例えば、定数が存在し、ヴァプニク・チェルヴォネンキス次元を持つ任意のクラスのラデマッハ複雑度の上限が であることを示すことができます。 ${\displaystyle C}$${\displaystyle \{0,1\}}$ ${\displaystyle d}$${\displaystyle C{\sqrt {\frac {d}{m}}}}$

以下の境界は、内のベクトルの定数集合に対する線形演算に関連している。^{[2] : 332–333}${\displaystyle S}$${\displaystyle m}$${\displaystyle \mathbb {R} ^{n}}$

1.単位球内のベクトルと内のベクトルのドット積の集合を定義します。次に、 ${\displaystyle A_{2}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{2}\leq 1\}=}$${\displaystyle S}$

${\displaystyle \operatorname {Rad} (A_{2})\leq {\max _{i}\|x_{i}\|_{2} \over {\sqrt {m}}}}$

2. 1 ノルムの単位球内のベクトルと 内のベクトルのドット積の集合を定義します。次に、次の操作を行います。${\displaystyle A_{1}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{1}\leq 1\}=}$${\displaystyle S}$

${\displaystyle \operatorname {Rad} (A_{1})\leq \max _{i}\|x_{i}\|_{\infty }\cdot {\sqrt {2\log(2n) \over m}}}$

次の境界は、集合のラデマッハ複雑性とその外部被覆数（和集合に が含まれるような半径のボールの数）を関連付けるものである。この境界はダドリーによるものである。^{[2] : 338}${\displaystyle A}$${\displaystyle r}$${\displaystyle A}$

が長さ（ノルム）が最大 のベクトルの集合であるとします。このとき、すべての整数 に対して次の式が成り立ちます。 ${\displaystyle A\subset \mathbb {R} ^{m}}$${\displaystyle c}$${\displaystyle M>0}$

${\displaystyle \operatorname {Rad} (A)\leq {c\cdot 2^{-M} \over {\sqrt {m}}}+{6c \over m}\cdot \sum _{i=1}^{M}2^{-i}{\sqrt {\log \left(N_{c\cdot 2^{-i}}^{\text{ext}}(A)\right)}}}$

特に、が のd次元部分空間内にある場合、次のようになります。 ${\displaystyle A}$${\displaystyle \mathbb {R} ^{m}}$

${\displaystyle \forall r>0:N_{r}^{\text{ext}}(A)\leq (2c{\sqrt {d}}/r)^{d}}$

これを前の境界に代入すると、Rademacher 複雑度の境界は次のようになります。

${\displaystyle \operatorname {Rad} (A)\leq {6c \over m}\cdot {\bigg (}{\sqrt {d\log(2{\sqrt {d}})}}+2{\sqrt {d}}{\bigg )}=O{\bigg (}{c{\sqrt {d\log(d)}} \over m}{\bigg )}}$

ガウス複雑度は、同様の物理的意味を持つ同様の複雑度であり、の代わりにランダム変数を使用してラーデマッハ複雑度から得ることができます。ここで、 は平均がゼロで分散が 1 であるガウスi.idランダム変数、つまり です。ガウス複雑度とラーデマッハ複雑度は、対数因子まで同等であることが知られています。 ${\displaystyle g_{i}}$${\displaystyle \sigma _{i}}$${\displaystyle g_{i}}$ ${\displaystyle g_{i}\sim {\mathcal {N}}(0,1)}$

集合が与えられた場合、 ^[5]が成り立ちます。 ここで はA のガウス複雑度です。例として、L1 球のラデマッハ複雑度とガウス複雑度を考えてみましょう。ラデマッハ複雑度はちょうど 1 で与えられますが、ガウス複雑度は のオーダーです(これは、サブガウスランダム変数の集合の上限の既知の特性を適用することで示せます)。^[5]${\displaystyle A\subseteq \mathbb {R} ^{n}}$
${\displaystyle {\frac {G(A)}{2{\sqrt {\log {n}}}}}\leq {\text{Rad}}(A)\leq {\sqrt {\frac {\pi }{2}}}G(A)}$
${\displaystyle G(A)}$${\displaystyle {\sqrt {\log d}}}$

• Peter L. Bartlett、Shahar Mendelson (2002) Rademacher と Gaussian Complexities: Risk Bounds and Structural Results . Journal of Machine Learning Research 3 463–482 ページ
• Giorgio Gnecco、Marcello Sanguineti (2008) Rademacher の計算量による近似誤差の境界。応用数学科学、第 2 巻、2008 年、第 4 号、153–176 ページ