経験過程

同義語:empirical process

概要

経験過程(empirical process)とは、独立同分布の標本の経験測度 $P_n$ と真の分布 $P$ の差を、関数の族 $\mathcal F$ で添字づけた確率過程 $\mathbb G_nf=\sqrt n(P_nf-Pf)$ として見たものである。有限個の $f$ では中心極限定理により共分散 $Pfg-PfPg$ の Gauss 過程($P$-Brown 橋)に収束する。族を有限個の括弧で近似できるか、VC 次元が有限な集合族なら、大数の法則が族の上で一様に成り立ち(Glivenko–Cantelli 族)、分布関数の一様収束や中央値の一致性が従う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 強大数の法則, 中心極限定理, Borel–Cantelliの補題, Kolmogorov–Smirnov検定

経験過程(empirical process)は、独立同分布の標本から作った経験分布と真の分布の差を、関数の族で添字づけた確率過程として見たものである。標本 $X_1,\dots,X_n$ の 経験測度 $P_n$ は各点に重さ $1/n$ をのせた測度で、関数 $f$ の積分 $P_nf=\frac1n\sum_if(X_i)$ は標本平均である。$f$ を 1 つ固定すれば、$P_nf\to Pf$ は大数の法則、$\sqrt n(P_nf-Pf)$ の分布の収束は中心極限定理である。経験過程の理論は、これらが 関数の族 $\mathcal F$ の上で一様に 成り立つための条件を調べる。
一様性が要る典型は、分布関数の推定である。経験分布関数 $F_n(t)=P_n\mathbf 1_{(-\infty,t]}$ が真の分布関数 $F$ に一様に近づくこと(Glivenko–Cantelliの定理)は Kolmogorov–Smirnov検定 の基礎であり、推定量の一致性、機械学習の汎化誤差の評価、ブートストラップ法の正当化も、同じ「一様な大数の法則」「一様な中心極限定理」の形をとる。
この記事では次のことを示す。

  • 経験過程の有限次元分布が、共分散 $Pfg-PfPg$ の Gauss 過程($P$-Brown 橋)に収束すること(prop-ep-fidi)。
  • 主定理:族を有限個の「括弧」で近似できれば、一様な大数の法則が成り立つ(thm-ep-bracket)。分布関数の場合の Glivenko–Cantelli の定理(cor-ep-gc)と、中央値の一致性(ex-ep-median)がここから従う。
  • VC 次元が有限な集合族では、収束の速さの評価つきで一様な大数の法則が成り立つこと(thm-ep-vc)。
  • 族が大きすぎる・可積分でない・独立でない場合に一様性が成り立たなくなること(反例の表)。
    分布関数の場合の一様な中心極限定理(thm-ep-donsker)は主張を述べ、出典を示す。

定義と使える条件

$(S,\mathcal S)$ を可測空間、$P$ をその上の確率測度とし、$X_1,X_2,\dots$ を確率空間 $(\Omega,\mathcal A,\Pr)$ の上の $S$ に値をとる確率変数とする。可測関数 $f\colon S\to\mathbb R$ で $\int\lvert f\rvert\,dP< \infty$ のものについて $Pf=\int f\,dP$ と書く。

経験測度と経験過程

$X_1,\dots,X_n$ の 経験測度 を
$$ P_n=\frac1n\sum_{i=1}^n\delta_{X_i},\qquad P_nf=\frac1n\sum_{i=1}^nf(X_i) $$
と定める($\delta_x$ は $x$ に重さ $1$ をのせた測度)。可積分な関数の族 $\mathcal F$ について、確率変数の族
$$ \mathbb G_nf=\sqrt n\,(P_nf-Pf)\qquad(f\in\mathcal F) $$
を $\mathcal F$ で添字づけた 経験過程 という。集合 $C\in\mathcal S$ については $P_n(C)=P_n\mathbf 1_C$、$\mathbb G_n(C)=\mathbb G_n\mathbf 1_C$ と書く。

$S=\mathbb R$、$\mathcal F=\{\mathbf 1_{(-\infty,t]}\mid t\in\mathbb R\}$ のとき、$P_n\mathbf 1_{(-\infty,t]}=F_n(t)$ は 経験分布関数、$\mathbb G_n$ は $\sqrt n(F_n(t)-F(t))$ である($F$ は $P$ の分布関数)。

Glivenko–Cantelli 族

$X_1,X_2,\dots$ が独立にどれも $P$ に従うとする。可積分な関数の族 $\mathcal F$ が $P$-Glivenko–Cantelli 族($P$-GC 族)であるとは、$\Pr(\Omega_0)=1$ となる事象 $\Omega_0$ があって、$\Omega_0$ の上で
$$ \sup_{f\in\mathcal F}\lvert P_nf-Pf\rvert\to0\qquad(n\to\infty) $$
となることをいう。

$\mathcal F$ が非可算だと $\sup_f\lvert P_nf-Pf\rvert$ が可測とは限らない。そこで定義は「確率 $1$ の事象の上で $0$ に近づく」形にしてある。$\mathcal F$ が可算なら上限は可測で、通常の概収束と同じである。

括弧

可積分な関数 $l\le u$ について、$l\le f\le u$(各点で)をみたす $f$ 全体を 括弧 $[l,u]$ といい、$P(u-l)$ をその 大きさ という。族 $\mathcal F$ が 有限個の括弧で近似できる とは、どの $\varepsilon>0$ についても、大きさが $\varepsilon$ 未満の有限個の括弧 $[l_1,u_1],\dots,[l_N,u_N]$ で $\mathcal F$ を覆えることをいう。

$l_j,u_j$ は $\mathcal F$ に属さなくてよい。この記事の定理を使う条件は次のとおりである。

  • (i) 独立同分布:$X_1,X_2,\dots$ は独立で、どれも分布 $P$ に従う(反例の表の 3 行目)。
  • (ii) 可積分性:すべての $f\in\mathcal F$ について $P\lvert f\rvert< \infty$(反例の表の 2 行目)。中心極限定理を使う prop-ep-fidi では $Pf^2< \infty$ とする。
  • (iii) 族の大きさ:$\mathcal F$ が有限個の括弧で近似できる(thm-ep-bracket)か、VC 次元が有限な集合族の指示関数の族である(thm-ep-vc)。各 $f$ ごとの収束だけでは一様性は出ない(反例の表の 1 行目)。

有限次元分布と $P$-Brown 橋

各 $n$ について、$f,g$ が $Pf^2,Pg^2< \infty$ をみたせば
$$ \operatorname{Cov}(\mathbb G_nf,\mathbb G_ng)=\frac1n\sum_{i=1}^n\operatorname{Cov}\bigl(f(X_i),g(X_i)\bigr)=Pfg-Pf\,Pg $$
である($i\ne j$ の項は独立性で $0$)。共分散は $n$ によらない。

$P$-Brown 橋

$\mathcal F\subset L^2(P)$ とする。平均 $0$、共分散 $E[\mathbb G_P f\,\mathbb G_P g]=Pfg-Pf\,Pg$ の Gauss 過程 $(\mathbb G_Pf)_{f\in\mathcal F}$ を $P$-Brown 橋 という。

$Pfg-PfPg$ は確率変数 $f(X_1)$、$g(X_1)$ の共分散なので半正定値な核であり、Gauss過程 の定理「Gauss 過程の存在と一意性」によりこの過程は存在し、有限次元分布は一意に決まる。$P$ が $[0,1]$ の一様分布、$f=\mathbf 1_{[0,s]}$、$g=\mathbf 1_{[0,t]}$ なら共分散は $\min(s,t)-st$ で、これは Brown 運動 $B$ から作る Brown 橋 $B_t-tB_1$ の共分散である(Brown運動)。

有限次元分布の収束

(i) を仮定し、$f_1,\dots,f_k\in L^2(P)$ とする。$n\to\infty$ のとき
$$ (\mathbb G_nf_1,\dots,\mathbb G_nf_k)\ \text{は}\ (\mathbb G_Pf_1,\dots,\mathbb G_Pf_k)\sim N_k(0,\Sigma),\quad\Sigma_{jl}=Pf_jf_l-Pf_j\,Pf_l $$
に分布収束する。

多変量の中心極限定理

$Y_i=\bigl(f_1(X_i)-Pf_1,\dots,f_k(X_i)-Pf_k\bigr)\in\mathbb R^k$ とおく。(i) より $Y_1,Y_2,\dots$ は独立同分布で、平均は $0$ である。Cauchy–Schwarz の不等式から $P\lvert f_jf_l\rvert\le(Pf_j^2\,Pf_l^2)^{1/2}< \infty$ なので、$Y_1$ の共分散行列は有限で、その $(j,l)$ 成分は $E[(f_j(X_1)-Pf_j)(f_l(X_1)-Pf_l)]=Pf_jf_l-Pf_jPf_l=\Sigma_{jl}$ である。
$$ (\mathbb G_nf_1,\dots,\mathbb G_nf_k)=\frac1{\sqrt n}\sum_{i=1}^nY_i $$
だから、$\mathbb R^k$ での中心極限定理(Dur19 Theorem 3.10.7、p. 200)により、これは $N_k(0,\Sigma)$ に分布収束する。右辺の正規分布は、定義により $(\mathbb G_Pf_1,\dots,\mathbb G_Pf_k)$ の分布である。

$\mathbb G_n$ は $f$ について 1 次($\mathbb G_n(af+bg)=a\mathbb G_nf+b\mathbb G_ng$)なので、有限個の $f$ の 1 次結合の極限もこの命題で分かる。たとえば互いに素な集合 $A,B$ では $\operatorname{Cov}(\mathbb G_n(A),\mathbb G_n(B))=-P(A)P(B)\le0$ で、$P(A)P(B)>0$ なら、Brown 運動と違って重ならない部分の増分は独立でない。

主定理:括弧による一様な大数の法則

括弧による Glivenko–Cantelli の定理

(i) を仮定し、$\mathcal F$ が有限個の括弧で近似できるとする。このとき $\mathcal F$ は $P$-Glivenko–Cantelli 族である。

括弧の端 $l_j,u_j$ は可積分なので、(ii) は自動的に成り立つ。この定理は Pol84 Theorem II.2(p. 8)と同じ内容である。

有限個の関数に大数の法則を使う

$\varepsilon>0$ を固定し、大きさが $\varepsilon$ 未満の括弧 $[l_1,u_1],\dots,[l_N,u_N]$ で $\mathcal F$ を覆う。$f\in\mathcal F$ が $[l_j,u_j]$ に入るとする。$f\le u_j$ と $P_n$ が正の測度であることから $P_nf\le P_nu_j$、また $Pf\ge Pl_j$ だから
$$ P_nf-Pf\le P_nu_j-Pl_j=(P_nu_j-Pu_j)+P(u_j-l_j)< (P_nu_j-Pu_j)+\varepsilon $$
である。同じように $P_nf\ge P_nl_j$、$Pf\le Pu_j$ から
$$ P_nf-Pf\ge P_nl_j-Pu_j>(P_nl_j-Pl_j)-\varepsilon $$
である。2 つを合わせると、すべての $f\in\mathcal F$ について
$$ \lvert P_nf-Pf\rvert< \Delta_n+\varepsilon,\qquad\Delta_n:=\max_{1\le j\le N}\max\bigl(\lvert P_nu_j-Pu_j\rvert,\ \lvert P_nl_j-Pl_j\rvert\bigr) $$
となる。右辺は $f$ によらない。
$\Delta_n$ は有限個($2N$ 個)の可積分な関数についての量である。(i) より各 $u_j(X_1),u_j(X_2),\dots$ は独立同分布で可積分だから、強大数の法則 の定理「強大数の法則」により確率 $1$ で $P_nu_j\to Pu_j$ であり、$l_j$ についても同じである。有限個の確率 $1$ の事象の共通部分はまた確率 $1$ なので、確率 $1$ の事象 $\Omega_\varepsilon$ の上で $\Delta_n\to0$ である。よって $\Omega_\varepsilon$ の上で
$$ \limsup_{n\to\infty}\ \sup_{f\in\mathcal F}\lvert P_nf-Pf\rvert\le\varepsilon $$
が成り立つ(左辺が可測かどうかは使っていない。各 $\omega\in\Omega_\varepsilon$ ごとの実数の不等式である)。
最後に $\varepsilon=1/m$($m=1,2,\dots$)とし、$\Omega_0=\bigcap_m\Omega_{1/m}$ とおく。可算個の確率 $1$ の事象の共通部分なので $\Pr(\Omega_0)=1$ で、$\Omega_0$ の上では上の $\limsup$ がすべての $m$ について $1/m$ 以下、つまり $0$ である。これが $P$-Glivenko–Cantelli 族の定義である。

証明が使うのは「有限個の関数での大数の法則」と「上下からはさむ近似」だけである。族がどれほど大きくても、各 $\varepsilon$ で有限個の括弧に収まれば、有限個の場合に帰着する。

分布関数の一様収束(Glivenko–Cantelli の定理)

$X_1,X_2,\dots$ が独立で同じ分布関数 $F$ に従うとき、確率 $1$ で $\sup_{t\in\mathbb R}\lvert F_n(t)-F(t)\rvert\to0$ である。$F$ の連続性は仮定しない。

分位点で括弧を作る

整数 $k\ge2$ について、$t_0=-\infty$、$t_k=+\infty$、$1\le i\le k-1$ について $t_i=\inf\{t\mid F(t)\ge i/k\}$ とおき、各 $i$ で括弧 $[\mathbf 1_{(-\infty,t_{i-1}]},\ \mathbf 1_{(-\infty,t_i)}]$ を作ると、大きさは $1/k$ 以下で、族 $\{\mathbf 1_{(-\infty,t]}\}$ を覆う。

確かめを開く

$0< i/k< 1$ なので $t_i$ は有限の実数で、$t_1\le t_2\le\cdots$ である。$\mathbf 1_{(-\infty,-\infty]}=0$、$\mathbf 1_{(-\infty,+\infty)}=1$ と読む。どの実数 $t$ も、ある $i$ について $t_{i-1}\le t< t_i$ をみたし、このとき $\mathbf 1_{(-\infty,t_{i-1}]}\le\mathbf 1_{(-\infty,t]}\le\mathbf 1_{(-\infty,t_i)}$ である。括弧の大きさは $F(t_i-)-F(t_{i-1})$ である。$t< t_i$ なら $F(t)< i/k$ なので $F(t_i-)\le i/k$、$F$ の右連続性から $F(t_{i-1})\ge(i-1)/k$($i=1$ では $0$)となり、大きさは $1/k$ 以下である。$\varepsilon>0$ に対し $1/k< \varepsilon$ ととれば thm-ep-bracket の仮定がみたされる。

これは Kolmogorov–Smirnov検定 の定理「Glivenko–Cantelliの定理」と同じ主張で、証明の分位点の分け方も同じである。

VC 族と収束の速さ

括弧は分布 $P$ ごとに作る。分布によらない条件として、VC次元 が有限な集合族がある。集合族 $\mathcal C$ の VC 次元とは、指示関数の族 $\{\mathbf 1_C\mid C\in\mathcal C\}$ の VC 次元のことである。

VC 族の一様な大数の法則

(i) を仮定する。$\mathcal C\subset\mathcal S$ の VC 次元を $d$($1\le d< \infty$)とし、$\mathcal C$ は可算であるか、可算な部分族 $\mathcal C_0$ があって各 $\mathbf 1_C$($C\in\mathcal C$)が $\mathcal C_0$ の元の指示関数の列の各点収束の極限になるとする。

  1. $n\ge d$、$0< \delta< 1$ のとき、確率 $1-\delta$ 以上で
    $$ \sup_{C\in\mathcal C}\lvert P_n(C)-P(C)\rvert\le2\sqrt{\frac{2d\log(en/d)}n}+\sqrt{\frac{\log(2/\delta)}{2n}}. $$
  2. $\mathcal C$ はどの確率測度 $P$ についても $P$-Glivenko–Cantelli 族である。
Rademacher 複雑度と Borel–Cantelli の補題

1 は Rademacher複雑度 の主定理を指示関数の族とその符号を変えた族に当てて得る。2 は 1 で $\delta=n^{-2}$ とし、Borel–Cantelli の補題を使う。

証明を開く

1。 $\mathcal F=\{\mathbf 1_C\mid C\in\mathcal C\}$ は $[0,1]$ に値をとり、仮定は Rademacher複雑度 の条件 (i)〜(iii) にあたる。標本 $x_1,\dots,x_n$ を固定すると、ベクトル $(\mathbf 1_C(x_1),\dots,\mathbf 1_C(x_n))$ の種類は Sauer–Shelahの補題 の系「成長関数の評価」により $\sum_{i=0}^d\binom ni$ 以下で、$n\ge d$ ではこれは $(en/d)^d$ 以下である(Rademacher複雑度 の系「VC 次元による評価」の証明と同じ計算)。各ベクトルの Euclid ノルムは $\sqrt n$ 以下なので、同じ記事の命題「Massart の補題」により経験 Rademacher 複雑度は $\sqrt{2d\log(en/d)/n}$ 以下で、その期待値 $\mathfrak R_n(\mathcal F)$ も同じ値以下である。同じ記事の定理「一様な偏差の上界」の 1 を $c=1$、確率 $\delta/2$ で使うと、確率 $1-\delta/2$ 以上ですべての $C$ について $P(C)-P_n(C)\le2\mathfrak R_n(\mathcal F)+\sqrt{\log(2/\delta)/(2n)}$ である。$-\mathcal F$ は $[-1,0]$ に値をとり、命題「基本の性質」の 2 により Rademacher 複雑度は $\mathcal F$ と同じなので、確率 $1-\delta/2$ 以上で $P_n(C)-P(C)$ も同じ値以下である。両方が成り立つ確率は $1-\delta$ 以上で、1 を得る。
2。 1 の右辺を $\delta=n^{-2}$ で $b_n$ と書くと $b_n=2\sqrt{2d\log(en/d)/n}+\sqrt{\log(2n^2)/(2n)}\to0$ である。可測性の仮定により上限は $\mathcal C_0$ でとってよく、事象 $A_n=\{\sup_C\lvert P_n(C)-P(C)\rvert>b_n\}$ は可測で、$\sum_{n\ge d}\Pr(A_n)\le\sum_nn^{-2}< \infty$ である。Borel–Cantelliの補題 の定理「第 1 の Borel–Cantelli の補題」により、確率 $1$ で $A_n$ は有限個の $n$ でしか起こらず、十分大きな $n$ で上限は $b_n$ 以下となって $0$ に近づく。

半直線の族 $\{(-\infty,t]\}$ は VC 次元 $1$ で、有理数の $t$ の族が可算な部分族の役をする($t_k\downarrow t$ なら $\mathbf 1_{(-\infty,t_k]}\to\mathbf 1_{(-\infty,t]}$)。よって cor-ep-gc は thm-ep-vc からも従い、さらに速さの評価がつく。$\mathbb R^m$ の閉半空間の族(VC 次元 $m+1$)や平面の軸に平行な長方形の族(VC 次元 $4$)にも使える(VC次元 の例「半平面と半空間」「軸に平行な長方形」)。一方、平面の凸集合の族は VC 次元が無限である。

一様な中心極限定理

prop-ep-fidi は有限個の $f$ についての収束である。分布関数の場合は、過程全体が $P$-Brown 橋に収束する。

経験過程の中心極限定理(分布関数の場合)

$X_1,X_2,\dots$ が独立で同じ分布関数 $F$ に従うとき、$E_n(t)=\sqrt n(F_n(t)-F(t))$ は、$[-\infty,\infty]$ 上の右連続で左極限をもつ関数の空間 $D[-\infty,\infty]$(一様ノルム)に値をとる確率要素として、平均 $0$、共分散 $E[E(s)E(t)]=F(s)-F(s)F(t)$($s\le t$)の Gauss 過程 $E$ に分布収束する。

証明の所在

この記事では証明しない(Pol84 Theorem V.11、p. 97。分布収束の意味と可測性の扱いは同書に従う。一様分布の場合に帰着させ、分位点変換で一般の $F$ へ移す)。

共分散を比べると、$E$ は Brown 橋 $B^\circ$ から作った $B^\circ(F(t))$ と同じ有限次元分布をもつ。$F$ が連続なら、連続写像により $\sqrt n\sup_t\lvert F_n(t)-F(t)\rvert$ は $\sup_{0\le u\le1}\lvert B^\circ(u)\rvert$ に分布収束し、これが Kolmogorov–Smirnov検定 の定理「Kolmogorov の極限定理」である。ランダムウォークの折れ線についての類似は Donskerの定理 である。

公式の表

量式備考
経験測度の積分$P_nf=\frac1n\sum_{i=1}^nf(X_i)$$E[P_nf]=Pf$
経験過程$\mathbb G_nf=\sqrt n(P_nf-Pf)$$f$ について 1 次
分散$\operatorname{Var}(\mathbb G_nf)=Pf^2-(Pf)^2$$n$ によらない
共分散$\operatorname{Cov}(\mathbb G_nf,\mathbb G_ng)=Pfg-Pf\,Pg$極限の $P$-Brown 橋と同じ
集合の場合$\operatorname{Cov}(\mathbb G_n(A),\mathbb G_n(B))=P(A\cap B)-P(A)P(B)$互いに素なら $-P(A)P(B)$
一様分布の半直線$\operatorname{Cov}(\mathbb G_n[0,s],\mathbb G_n[0,t])=\min(s,t)-st$Brown 橋の共分散
VC 族の上界$2\sqrt{2d\log(en/d)/n}+\sqrt{\log(2/\delta)/(2n)}$thm-ep-vc、$n\ge d$
KS の 5% 点(漸近)$1.358/\sqrt n$Kolmogorov–Smirnov検定

図: 左は一様分布の 20 個の標本の経験分布関数の階段と、対角線の真の分布関数。右は標本数 20、200、2000 の経験過程の標本路 1 本ずつで、値はどれもおよそ マイナス 0.8 から 0.5 の範囲にあり、標本数が増えると跳びが細かくなって連続な Brown 橋の道に近づく 図: 左は一様分布の 20 個の標本の経験分布関数の階段と、対角線の真の分布関数。右は標本数 20、200、2000 の経験過程の標本路 1 本ずつで、値はどれもおよそ マイナス 0.8 から 0.5 の範囲にあり、標本数が増えると跳びが細かくなって連続な Brown 橋の道に近づく

計算の手順

族 $\mathcal F$ が一様な大数の法則をみたすかを調べるには、次の順に確かめる。

  1. 標本の独立性と同分布性を確かめる((i))。時系列のように依存がある標本には、この記事の定理はそのまま使えない。
  2. 族が分布によらず小さいかを見る。集合族なら VC 次元を計算し、有限なら thm-ep-vc を使う。速さの評価も得られる。
  3. そうでなければ、$P$ を使って括弧を作る。パラメータで連続に動く族なら、パラメータの格子点で上下の関数を作り、括弧の大きさ $P(u-l)$ を格子の間隔で抑える(ex-ep-median)。
  4. 分布の収束まで要るときは、prop-ep-fidi で有限次元分布の極限を求め、分布関数の族なら thm-ep-donsker を使う。

例題

一様分布での収束の速さ

$P$ を $[0,1]$ の一様分布、$D_n=\sup_t\lvert F_n(t)-t\rvert$ とする。乱数で $E[D_n]$ を見積もると、$n=10,100,1000,10000$ で $\sqrt n\,E[D_n]\approx0.819,\ 0.853,\ 0.866,\ 0.864$ となり、$D_n$ はおよそ $0.87/\sqrt n$ の大きさで $0$ に近づく。極限の値は Kolmogorov 分布の平均 $\int_0^\infty(1-K(x))\,dx\approx0.869$ である($K$ は Kolmogorov–Smirnov検定 の定理「Kolmogorov の極限定理」の分布関数)。

中央値の一致性

$P\lvert X\rvert< \infty$ とし、$M(\theta)=E\lvert X-\theta\rvert$、$M_n(\theta)=P_n\lvert x-\theta\rvert$ とおく。$M$ の最小点 $m$(母集団の中央値。確率分布の中央値)がただ 1 つなら、$M_n$ の最小点(標本中央値)$\hat m_n$ は確率 $1$ で $m$ に収束する。

解答を開く

括弧。 $K>0$ と $\eta>0$ について、$[-K,K]$ を間隔 $\eta$ の格子点 $\theta_1,\dots,\theta_N$ で分ける。$\lvert\theta-\theta_j\rvert\le\eta$ なら三角不等式から $\lvert x-\theta_j\rvert-\eta\le\lvert x-\theta\rvert\le\lvert x-\theta_j\rvert+\eta$ で、括弧の大きさは $2\eta$ である。よって $\{\lvert x-\theta\rvert\mid\lvert\theta\rvert\le K\}$ は thm-ep-bracket により $P$-GC 族で、確率 $1$ で $\sup_{\lvert\theta\rvert\le K}\lvert M_n-M\rvert\to0$ である。
最小点。 $M$ は凸で、最小点が $m$ だけなので、$\eta>0$ について $\gamma=\min(M(m-\eta),M(m+\eta))-M(m)>0$ である。$K>\lvert m\rvert+\eta$ にとる。$\sup_{\lvert\theta\rvert\le K}\lvert M_n-M\rvert< \gamma/2$ となる $n$ では $M_n(m\pm\eta)>M_n(m)$ で、$M_n$ も凸だから、$M_n$ の最小点は $(m-\eta,m+\eta)$ の外にない(外の点 $\theta$ で $M_n(\theta)\le M_n(m)$ なら、$m$ と $\theta$ の間にある $m\pm\eta$ で凸性から $M_n\le M_n(m)$ となり矛盾)。
数値。 平均 $1$ の指数分布では $M(\theta)=\theta-1+2e^{-\theta}$($\theta\ge0$)、$m=\log2\approx0.693$ である。乱数で $\sup_{-2\le\theta\le4}\lvert M_n-M\rvert$ は $n=100,1000,10000,100000$ で $0.123,\ 0.050,\ 0.014,\ 0.004$、標本中央値は $0.665,\ 0.705,\ 0.701,\ 0.691$ だった。

VC 族の上界の大きさ

半直線の族($d=1$)で $n=10000$、$\delta=0.05$ とすると、thm-ep-vc の右辺は $2\sqrt{2\log(10000e)/10000}+\sqrt{\log40/20000}\approx0.0904+0.0136=0.104$ である。一方、Kolmogorov の極限定理による 5% 点は $1.358/\sqrt{10000}\approx0.0136$ で、乱数で求めた $D_{10000}$ の 95% 点も $0.0137$ だった。VC の上界は正しいが約 $7.7$ 倍ゆるい。分布によらず、どの VC 族にも使えることの代償である。

有限次元分布

一様分布で $s=0.3$、$t=0.7$ とすると、prop-ep-fidi の極限 $(\mathbb G_P[0,s],\mathbb G_P[0,t])$ は分散 $0.21,\ 0.21$、共分散 $0.3-0.21=0.09$ の 2 変量正規分布である。増分 $\mathbb G_P[0,t]-\mathbb G_P[0,s]=\mathbb G_P(s,t]$ の分散は $0.4\cdot0.6=0.24$ で、$\mathbb G_P[0,s]$ との共分散は $-0.3\cdot0.4=-0.12$ である。重ならない区間の増分が負の相関をもつのは、$F_n(1)=1$ という拘束(橋の両端が $0$)のためである。

使える条件と反例

外す条件反例成り立たなくなること
(iii) 族の大きさ$P$ を $[0,1]$ の一様分布、$\mathcal C$ を有限集合全体(VC 次元は無限)各 $C$ では $P_n(C)\to P(C)=0$ だが、$C=\{X_1,\dots,X_n\}$ で $P_n(C)-P(C)=1$。上限はどの $n$ でも $1$
(ii) 可積分性$P$ を標準 Cauchy 分布、$\mathcal F=\{x\}$(1 個の関数)$P_nf$ は標本平均で、どの $n$ でも標準 Cauchy 分布に従い、収束しない
(i) 独立性$X_1$ が一様分布で $X_2=X_3=\cdots=X_1$、半直線の族$F_n=\mathbf 1_{[X_1,\infty)}$ で、$\sup_t\lvert F_n(t)-t\rvert=\max(X_1,1-X_1)\ge1/2$
表の反例の確かめ

1 行目は族の大きさだけを、2 行目は可積分性だけを、3 行目は独立性だけを外している。

3 行の確かめを開く

1 行目:標本は独立同分布で、各 $\mathbf 1_C$ は有界である。$C$ が有限集合なら $P(C)=0$ で、強大数の法則 により各 $C$ ごとには $P_n(C)\to0$ である。しかし $C_n=\{X_1,\dots,X_n\}$ は族に属し $P_n(C_n)=1$ なので、上限は常に $1$ である。$n$ 点の集合はどれも打ち砕かれるから VC 次元は無限で、thm-ep-vc の仮定をみたさない。
2 行目:標本は独立同分布で、族は 1 個なので族の大きさの条件はみたす。標準 Cauchy 分布の特性関数は $e^{-\lvert t\rvert}$ なので、標本平均の特性関数は $(e^{-\lvert t\rvert/n})^n=e^{-\lvert t\rvert}$ で、標本平均は標準 Cauchy 分布に従う。$\Pr(\lvert P_nf\rvert>1)=1/2$ がどの $n$ でも成り立ち(乱数でも $n=1000$ で割合は $0.500$)、分布が $n$ によらないので定数に確率収束しない。強大数の法則 の定理「可積分でない場合」により、$P_nf$ が実数に収束する事象の確率は $0$ である。
3 行目:族と分布は cor-ep-gc と同じで、独立性だけが成り立たない。$F_n(t)=\mathbf 1[X_1\le t]$ なので、$t\uparrow X_1$ で差は $X_1$ に、$t=X_1$ で $1-X_1$ に近づき、上限は $\max(X_1,1-X_1)$ である。

よくある誤り

誤り正しくはなぜ
各 $f$ で $P_nf\to Pf$ なら、$\mathcal F$ の上で一様にも収束する族が大きいと一様性は成り立たない反例の表の 1 行目
非可算の族でも $\sup_f\lvert P_nf-Pf\rvert$ を確率変数として扱う可測とは限らない。確率 $1$ の事象の上の収束で述べるか、可算な部分族で上限が決まることを確かめるdef-ep-gc、thm-ep-vc の仮定
$\mathbb G_n$ の極限は Brown 運動である極限は Brown 橋で、重ならない部分の増分は負の相関をもつex-ep-fidi
VC の上界で KS 検定の臨界値を代用する上界は約 $7.7$ 倍ゆるい。KS 検定には Kolmogorov 分布を使うex-ep-vc
有限次元分布が収束すれば $\sup$ も収束する$\sup$ の分布の収束には過程全体の収束(thm-ep-donsker)が要る有限個の点の最大値は上限と一致しない

補足

  • Donsker 族:$\mathbb G_n$ が $\mathcal F$ の上の有界関数の空間で $P$-Brown 橋に分布収束するとき、$\mathcal F$ を $P$-Donsker 族 という。thm-ep-donsker は半直線の族が Donsker 族であることを述べている。一般の族では、上限の可測性の扱いと、過程の緊密性(各 $\varepsilon$ で族を細かく分けたときの振幅の評価)が議論の中心になる。
  • 応用:最尤推定量や M 推定量の一致性は、ex-ep-median と同じく「目的関数の一様収束 + 最小点の分離」で示すことが多い。学習理論の汎化誤差の評価(PAC学習、Rademacher複雑度)は、損失関数の族についての一様な偏差の評価である。ブートストラップ法 の正当化にも経験過程の極限定理が使われる。
  • Brown 橋(Brown橋):$B^\circ(u)=B_u-uB_1$ は $B^\circ(0)=B^\circ(1)=0$ をみたし、Brown運動 を時刻 $1$ で $0$ に戻るよう条件づけたものとみなせる。

関連項目

参考文献

[1]
David Pollard, Convergence of Stochastic Processes, Springer-Verlag, 1984, §II.2 Theorem 2(p. 8)、§V.2 Theorem 11 Empirical Central Limit Theorem(p. 97)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する