確率における一様収束

確率の一様収束は、統計的漸近理論および確率論における確率の収束の一種である。これは、特定の条件下で、特定のイベント ファミリ内のすべてのイベントの経験的頻度が、理論上の確率に収束することを意味します。確率の一様収束は、統計学習理論の一部として、統計だけでなく機械学習にも応用されています。

大数の法則によれば、各単一イベントについて、一連の独立した試行におけるその経験的頻度は（高い確率で）その理論的確率に収束する。しかし、多くの応用では、1つの同じサンプルからクラス全体のイベントの確率を同時に判断する必要が生じる。さらに、イベントの相対頻度がイベントのクラス全体にわたって一様に確率に収束することが求められる^[1]一様収束定理は、この収束が成り立つための十分な条件を与える。大まかに言えば、イベントファミリーが十分に単純であれば（そのVC次元が十分に小さい場合）、一様収束が成り立つ。 ${\displaystyle A}$${\displaystyle S}$${\displaystyle S}$

集合とサンプル集合 （ ）上で定義された述語 のクラスについて、 におけるの経験的頻度は ${\displaystyle H}$${\displaystyle X}$${\displaystyle x=(x_{1},x_{2},\dots ,x_{m})}$${\displaystyle x_{i}\in X}$${\displaystyle h\in H}$${\displaystyle x}$

${\displaystyle {\widehat {Q}}_{x}(h)={\frac {1}{m}}|\{i:1\leq i\leq m,h(x_{i})=1\}|.}$

の理論的な確率は次のように定義される。${\displaystyle h\in H}$${\displaystyle Q_{P}(h)=P\{y\in X:h(y)=1\}.}$

一様収束定理は、大まかに言えば、が「単純」で、任意の分布に従ってから独立して（復元ありで）サンプルを抽出した場合、高い確率で、経験的頻度は理論的な確率である期待値に近くなることを述べています。^[2]${\displaystyle H}$${\displaystyle X}$${\displaystyle P}$

ここで「単純」とは、クラスのVapnik–Chervonenkis 次元がサンプルのサイズに比べて小さいことを意味します。言い換えると、十分に単純な関数の集合は、小さなランダム サンプルに対しても、分布全体に対してもほぼ同じように動作します。 ${\displaystyle H}$

一様収束定理は、成長関数の概念を用いてVapnikとChervonenkis ^[1]によって初めて証明されました。

一様収束定理の記述は次の通りである: ^[3]

が集合上で定義された - 値関数の集合であり、が 上の確率分布である場合、および正の整数 に対して、次が成り立ちます。${\displaystyle H}$${\displaystyle \{0,1\}}$${\displaystyle X}$${\displaystyle P}$${\displaystyle X}$${\displaystyle \epsilon >0}$${\displaystyle m}$

${\displaystyle P^{m}\{|Q_{P}(h)-{\widehat {Q_{x}}}(h)|\geq \varepsilon {\text{ for some }}h\in H\}\leq 4\Pi _{H}(2m)e^{-\varepsilon ^{2}m/8}.}$

ここで、任意の に対して、${\displaystyle x\in X^{m},}$

${\displaystyle Q_{P}(h)=P\{(y\in X:h(y)=1\},}$

${\displaystyle {\widehat {Q}}_{x}(h)={\frac {1}{m}}|\{i:1\leq i\leq m,h(x_{i})=1\}|}$

そして、 は、分布からの iid 抽出で構成される確率が引き継がれることを示します。${\displaystyle |x|=m}$${\displaystyle P^{m}}$${\displaystyle x}$${\displaystyle m}$${\displaystyle P}$

${\displaystyle \Pi_{H}}$は次のように定義されます:および上の任意の 値関数に対して、${\displaystyle \{0,1\}}$${\displaystyle H}$${\displaystyle X}$${\displaystyle D\subseteq X}$

${\displaystyle \Pi _{H}(D)=\{h\cap D:h\in H\}.}$

そして、任意の自然数に対して、破砕数は次のように定義されます。 ${\displaystyle m}$ ${\displaystyle \Pi _{H}(m)}$

${\displaystyle \Pi _{H}(m)=\max |\{h\cap D:|D|=m,h\in H\}|.}$

学習理論の観点からは、インスタンス セット上で定義された概念/仮説クラスであると考えることができます。定理の証明の詳細に入る前に、証明に必要な Sauer の補題を述べます。 ${\displaystyle H}$${\displaystyle X}$

ザウアー・シェラーの補題^[4]は、破砕数をVC次元に関連付けます。 ${\displaystyle \Pi _{h}(m)}$

補題: 、ここで は概念クラス のVC 次元です。 ${\displaystyle \Pi _{H}(m)\leq \left({\frac {em}{d}}\right)^{d}}$${\displaystyle d}$${\displaystyle H}$

帰結: . ${\displaystyle \Pi _{H}(m)\leq m^{d}}$

^[1]と^{[3]は以下の証明の出典です。}一様収束定理の証明の詳細に入る前に、証明の概要を説明します。

1. 対称化: を解析する問題をを解析する問題に変換します。ここで、 と は分布 に従って抽出されたサイズの iid サンプルです。 は長さ の元のランダムに抽出されたサンプルと見なすことができますが、 はを推定するために使用されるテストサンプルと考えることができます。${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{x}(h)|\geq \epsilon }$${\displaystyle |{\widehat {Q}}_{r}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2}$${\displaystyle r}$${\displaystyle s}$${\displaystyle m}$${\displaystyle P}$${\displaystyle r}$${\displaystyle m}$${\displaystyle s}$${\displaystyle Q_{P}(h)}$
2. 順列:と は同一かつ独立に選択されるため、それらの間で要素を交換しても、およびの確率分布は変化しません。そこで、結合標本の順列の特定の集合の効果を考慮して、ある に対する の確率を制限してみます。具体的には、のサブセット内でと を交換する順列を検討します。記号は、との連結を意味します。^[要出典]${\displaystyle r}$${\displaystyle s}$${\displaystyle r}$${\displaystyle s}$${\displaystyle |{\widehat {Q}}_{r}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2}$${\displaystyle h\in H}$${\displaystyle x=r||s}$${\displaystyle \sigma (x)}$${\displaystyle x_{i}}$${\displaystyle x_{m+i}}$${\displaystyle {1,2,...,m}}$${\displaystyle r||s}$${\displaystyle r}$${\displaystyle s}$
3. 有限クラスへの縮小:関数クラスを固定されたジョイント サンプルに制限できるようになりました。したがって、VC 次元が有限である場合、問題は有限関数クラスを含む問題に縮小されます。${\displaystyle H}$${\displaystyle H}$

証明の技術的な詳細を紹介します。

補題: と${\displaystyle V=\{x\in X^{m}:|Q_{P}(h)-{\widehat {Q}}_{x}(h)|\geq \varepsilon {\text{ for some }}h\in H\}}$

${\displaystyle R=\{(r,s)\in X^{m}\times X^{m}:|{\widehat {Q_{r}}}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2{\text{ for some }}h\in H\}.}$

次に、 については、です。 ${\displaystyle m\geq {\frac {2}{\varepsilon ^{2}}}}$${\displaystyle P^{m}(V)\leq 2P^{2m}(R)}$

証明: 三角不等式により、
の場合、 となります。 ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon }$${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2}$${\displaystyle |{\widehat {Q}}_{r}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2}$

したがって、

${\displaystyle {\begin{aligned}&P^{2m}(R)\\[5pt]\geq {}&P^{2m}\{\exists h\in H,|Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon {\text{ and }}|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2\}\\[5pt]={}&\int _{V}P^{m}\{s:\exists h\in H,|Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon {\text{ and }}|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2\}\,dP^{m}(r)\\[5pt]={}&A\end{aligned}}}$

とは独立しているからです。 ${\displaystyle r}$${\displaystyle s}$

ここで、となる を固定します。これについては、次のことを示します。 ${\displaystyle r\in V}$${\displaystyle h\in H}$${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon }$${\displaystyle h}$

${\displaystyle P^{m}\left\{|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq {\frac {\varepsilon }{2}}\right\}\geq {\frac {1}{2}}.}$

したがって、任意の に対して となり、したがって となります。したがって、高レベルのアイデアの最初のステップを実行します。 ${\displaystyle r\in V}$${\displaystyle A\geq {\frac {P^{m}(V)}{2}}}$${\displaystyle P^{2m}(R)\geq {\frac {P^{m}(V)}{2}}}$

は 期待値と分散を持つ二項確率変数であることに注意。チェビシェフの不等式により、${\displaystyle m\cdot {\widehat {Q}}_{s}(h)}$${\displaystyle m\cdot Q_{P}(h)}$${\displaystyle m\cdot Q_{P}(h)(1-Q_{P}(h))}$

${\displaystyle P^{m}\left\{|Q_{P}(h)-{\widehat {Q_{s}(h)}}|>{\frac {\varepsilon }{2}}\right\}\leq {\frac {m\cdot Q_{P}(h)(1-Q_{P}(h))}{(\varepsilon m/2)^{2}}}\leq {\frac {1}{\varepsilon ^{2}m}}\leq {\frac {1}{2}}}$

上の前述の境界について。ここでは、についてという事実を使います。 ${\displaystyle m}$${\displaystyle x(1-x)\leq 1/4}$${\displaystyle x}$

を の何らかのサブセット内でとを入れ替えるのすべての順列の集合とします。 ${\displaystyle \Gamma _{m}}$${\displaystyle \{1,2,3,\dots ,2m\}}$${\displaystyle i}$${\displaystyle m+i}$ ${\displaystyle \forall i}$${\displaystyle \{1,2,3,\ldots ,2m\}}$

補題:を の任意の部分集合とし、上の任意の確率分布とする。すると、 ${\displaystyle R}$${\displaystyle X^{2m}}$${\displaystyle P}$${\displaystyle X}$

${\displaystyle P^{2m}(R)=E[\Pr[\sigma (x)\in R]]\leq \max _{x\in X^{2m}}(\Pr[\sigma (x)\in R]),}$

ここで、期待値はに従って過剰に選択され、確率はから一様過剰に選択されます。 ${\displaystyle x}$${\displaystyle P^{2m}}$${\displaystyle \sigma }$${\displaystyle \Gamma _{m}}$

証明: いかなる${\displaystyle \sigma \in \Gamma _{m},}$

${\displaystyle P^{2m}(R)=P^{2m}\{x:\sigma (x)\in R\}}$

(座標置換は積分布を保存するため) ${\displaystyle P^{2m}}$

${\displaystyle {\begin{aligned}\therefore P^{2m}(R)={}&\int _{X^{2m}}1_{R}(x)\,dP^{2m}(x)\\[5pt]={}&{\frac {1}{|\Gamma _{m}|}}\sum _{\sigma \in \Gamma _{m}}\int _{X^{2m}}1_{R}(\sigma (x))\,dP^{2m}(x)\\[5pt]={}&\int _{X^{2m}}{\frac {1}{|\Gamma _{m}|}}\sum _{\sigma \in \Gamma _{m}}1_{R}(\sigma (x))\,dP^{2m}(x)\\[5pt]&{\text{(because }}|\Gamma _{m}|{\text{ is finite)}}\\[5pt]={}&\int _{X^{2m}}\Pr[\sigma (x)\in R]\,dP^{2m}(x)\quad {\text{(the expectation)}}\\[5pt]\leq {}&\max _{x\in X^{2m}}(\Pr[\sigma (x)\in R]).\end{aligned}}}$

ランダムな順列のもとでの確率が取り得る値の集合は有限であるため、最大値が存在することが保証されます。

補題:前の補題に基づいて、

${\displaystyle \max _{x\in X^{2m}}(\Pr[\sigma (x)\in R])\leq 4\Pi _{H}(2m)e^{-\varepsilon ^{2}m/8}}$。

証明: と を定義し、これは最大で である。これは、との間の任意の に対して となる関数が存在することを意味する。${\displaystyle x=(x_{1},x_{2},\ldots ,x_{2m})}$${\displaystyle t=|H|_{x}|}$${\displaystyle \Pi _{H}(2m)}$${\displaystyle h_{1},h_{2},\ldots ,h_{t}\in H}$${\displaystyle h\in H,\exists i}$${\displaystyle 1}$${\displaystyle t}$${\displaystyle h_{i}(x_{k})=h(x_{k})}$${\displaystyle 1\leq k\leq 2m.}$

いくつかについて がを満たす 場合に限り、 であることがわかります。したがって、 であればを定義し、それ以外の場合は を定義します。 ${\displaystyle \sigma (x)\in R}$${\displaystyle h}$${\displaystyle H}$${\displaystyle |{\frac {1}{m}}|\{1\leq i\leq m:h(x_{\sigma _{i}})=1\}|-{\frac {1}{m}}|\{m+1\leq i\leq 2m:h(x_{\sigma _{i}})=1\}||\geq {\frac {\varepsilon }{2}}}$${\displaystyle w_{i}^{j}=1}$${\displaystyle h_{j}(x_{i})=1}$${\displaystyle w_{i}^{j}=0}$

およびに対して、の が を満たす場合のみ成立する。 結合境界により、 ${\displaystyle 1\leq i\leq m}$${\displaystyle 1\leq j\leq t}$${\displaystyle \sigma (x)\in R}$${\displaystyle j}$${\displaystyle {1,\ldots ,t}}$${\displaystyle |{\frac {1}{m}}\left(\sum _{i}w_{\sigma (i)}^{j}-\sum _{i}w_{\sigma (m+i)}^{j}\right)|\geq {\frac {\varepsilon }{2}}}$

${\displaystyle \Pr[\sigma (x)\in R]\leq t\cdot \max \left(\Pr[|{\frac {1}{m}}\left(\sum _{i}w_{\sigma _{i}}^{j}-\sum _{i}w_{\sigma _{m+i}}^{j}\right)|\geq {\frac {\varepsilon }{2}}]\right)}$

${\displaystyle \leq \Pi _{H}(2m)\cdot \max \left(\Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}w_{\sigma _{i}}^{j}-\sum _{i}w_{\sigma _{m+i}}^{j}\right)\right|\geq {\frac {\varepsilon }{2}}\right]\right).}$

順列全体の分布は各 に対して均一であるため、 は等しい確率で に 等しくなります。${\displaystyle \sigma }$${\displaystyle i}$${\displaystyle w_{\sigma _{i}}^{j}-w_{\sigma _{m+i}}^{j}}$${\displaystyle \pm |w_{i}^{j}-w_{m+i}^{j}|}$

したがって、

${\displaystyle \Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}\left(w_{\sigma _{i}}^{j}-w_{\sigma _{m+i}}^{j}\right)\right)\right|\geq {\frac {\varepsilon }{2}}\right]=\Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}|w_{i}^{j}-w_{m+i}^{j}|\beta _{i}\right)\right|\geq {\frac {\varepsilon }{2}}\right],}$

ここで、右側の確率は を超えており、両方の可能性は等しくあり得ます。Hoeffdingの不等式により、これは最大で です。 ${\displaystyle \beta _{i}}$${\displaystyle 2e^{-m\varepsilon ^{2}/8}}$

最後に、証明の 3 つの部分をすべて組み合わせると、一様収束定理が得られます。