この記事では，K-means クラスタリングの一致性について でも使った Van der Vaart (1998) Theorem 5.14 を証明しようと思います．
準備
はじめに，以降で用いる記法を準備します．
- $P$ を集合 $\mathfrak{X}$ 上の確率測度とします．
- $X_{1},\dots,X_{n}\overset{i.i.d.}{\sim}P$ に対し，その経験分布を $\mathbb{P}_{n}$ で表します．点 $x\in\mathbb{R}^{d}$ における Dirac 測度を $\delta_{x}$ とすると，$\mathbb{P}_{n}=n^{-1}\sum_{i=1}^{n}\delta_{X_{i}}$ です．
- 可測関数 $f:\mathbb{R}^{d}\to\mathbb{R}$ の $P$ に関する期待値を $P[f],Pf,P[f(x)]$ と表します．経験分布 $\mathbb{P}_{n}$ に関する期待値も同様に $\mathbb{P}_{n}[f],\mathbb{P}_{n}f,\mathbb{P}_{n}[f(x)]$ などと表します．
- 確率1での収束を $\overset{a.s.}{\to}$ で表します．
- 拡大実数を $\overline{\mathbb{R}}$ で表します．
- 関数 $f$ に対し，$f^{+}:=\max\{f,0\},f^{-}:=-\min\{f,0\}$ とします．
証明する定理は次の通りです．
Van der Vaart (1998) Theorem 5.14
$\Theta$ 上の各点で定義された可測関数 $m_{\theta}:\mathfrak{X}\to\overline{\mathbb{R}}$ は，
- 任意の $\theta\in\Theta$ において，$\theta\mapsto m_{\theta}(x)$ は a.s. で上半連続，すなわち，$\limsup_{\theta’\to\theta}m_{\theta’}(x)\leq m_{\theta}(x)$ が a.s. で成立．
- ある $\delta>0$ が存在して，任意の半径 $\delta$ 以下の開球 $U\subset\Theta$ に対し，$\sup_{\theta\in U} m_{\theta}$ は可測で，$P\sup_{\theta\in U}m_{\theta}<\infty$．
- $\Theta_{0}:=\{\theta_{0}\in\Theta\mid Pm_{\theta_{0}}=\sup_{\theta\in\Theta}Pm_{\theta}\}\neq\emptyset$．
を満たすと仮定する．
ある $\theta_{0}\in\Theta_{0}$ に対し， $\mathbb{P}_{n}m_{\hat\theta_{n}}\geq \mathbb{P}_{n}m_{\theta_{0}}-o_{p}(1)$ を満たす任意の推定量 $\hat\theta_{n}$ は任意の $\varepsilon>0$ とコンパクト集合 $K\subset\Theta$ に対し，
$$\operatorname{P}(d(\hat\theta_{n},\Theta_{0})\geq\varepsilon,\hat\theta_{n}\in K)\to0$$
を満たす．
この定理は M 推定量の一致性に関するものです．$\mathbb{P}_{n}m_{\theta}$ を最大化するような推定量 $\hat\theta$ のことを M 推定量といいます．例えば，$m_{\theta}$ として対数尤度を選ぶと M 推定量は最尤推定量です．他にも，$m_{\theta}(x)=-\|x-\theta\|$ に関する M 推定量は最小二乗推定量になります．このように M 推定は広いクラスの推定量を含んでいます．
定理の証明に使ういくつかの定理，補題を準備します．
Durrett (2019) Theorem 2.4.5
$X_1,\dots,X_n$ は i.i.d. で $E[X_{1}^+]=\infty,E[X_{1}^{-}]<\infty$ とする．
$S_n:=X_1+\dots+X_n$ とすると，$S_n/n\overset{a.s.}{\to}\infty$ が成立．
証明
$M>0$ に対し，$X_{i}^M:=\min\{X_{i},M\}$ とすると，$X_{i}^M$ は i.i.d. で $E[|X_{i}^M|]<\infty$ を満たす．$S_{n}^{M}:=X_{1}^{M}+\dots+X_{n}^{M}$ とすると，大数の強法則から，$S_{n}^{M}\to E[X_{1}^{M}]$ a.s. である．$X_{i}\geq X_{i}^{M}$ なので，
$$
\liminf_{n\to\infty} S_{n}/n \geq \liminf_{n\to\infty} S_{n}^{M}=E[X_{1}^{M}]
$$
が a.s. で成り立つ．非負単調収束定理より，
$$
E[(X_{i}^{M})^{+}]\nearrow E[(X_{i})^{+}]=\infty\quad (M\nearrow\infty)
$$
が成立．よって，$E[X_{1}^{M}]=E[(X_{1}^{M})^{+}]-E[(X_{1}^{M})^{-}]=E[(X_{1}^{M})^{+}]-E[X_{1}^{-}]\nearrow\infty\quad(M\nearrow\infty)$ である．以上より，
$$
\liminf_{n\to\infty} S_n/n\geq \lim_{M\to\infty}E[X_{1}^{M}]=\infty\enspace\text{a.s.}
$$
が成立．これは，$S_n/n\overset{a.s.}{\to}\infty$ を意味する（証明終わり）．
補題1
$\limsup_{n\to\infty}X_{n}<X$ a.s. $\Rightarrow\limsup_{n\to\infty}\operatorname{P}(X_{n}\geq X+o_{p}(1))=0.$
証明
$Y_{n}=o_{p}(1)$ とする．任意の $\varepsilon>0$ に対し，
\begin{align*}
\operatorname{P}(X_{n}\geq X+Y_{n})
&\leq\operatorname{P}(X_{n}-X\geq Y_{n},Y_{n}\geq-\varepsilon)+\operatorname{P}(X_{n}-X\geq Y_{n},Y_{n}<-\varepsilon)\\
&\leq\operatorname{P}(X_{n}-X\geq-\varepsilon)+\operatorname{P}(Y_{n}<-\varepsilon).
\end{align*}
ここで，Van der Vaart (1998) Lemma 2.2 より，
$$
\limsup_{n\to\infty}\operatorname{P}(X_{n}-X\geq-\varepsilon)
\leq\operatorname{P}\left(\limsup_{n\to\infty}X_{n}-X\geq-\varepsilon\right)
\to0\quad(\varepsilon\searrow0).
$$
また，$\operatorname{P}(Y_{n}<-\varepsilon)\leq\operatorname{P}(|Y_{n}|\geq\varepsilon)\to0$ である．したがって，$\limsup_{n\to\infty}\operatorname{P}(X_{n}\geq X+Y_{n})\leq0$（証明終わり）．
補題2
$\limsup_{x'\to x}f(x')\leq f(x)\Rightarrow \sup_{x'\in B_\delta(x)}f(x')\searrow f(x)\enspace(\delta\searrow0).$
証明
$\limsup_{x'\to x}f(x'):=\lim_{\delta\searrow0}\sup_{x'\in B_\delta(x)\backslash\{x\}}f(x')$ である．仮定より，$\delta\searrow0$ とすると，
g_\delta:=\sup_{x'\in B_\delta(x)\backslash\{x\}}f(x')\searrow g_{0}:=\limsup_{x'\to x}f(x')\leq f(x).
一方，
$$
\sup_{x'\in B_{\delta}(x)}f(x')
=\max{f(x),g_\delta}\searrow\max{f(x),g_{0}}\leq f(x).
$$
よって，$\max{f(x),g_{0}}=f(x)$（証明終わり）．
定理の証明
任意の $\theta\in\Theta$ に対し，$Pm_{\theta}=-\infty$ の場合：
$\Theta_{0}=\Theta$ より，任意の推定量 $\hat\theta_{n}$ に対し， $d(\hat\theta_{n},\Theta_{0})=0$ である．よって
$$
\operatorname{P}(d(\hat\theta_{n},\Theta_{0})\geq\varepsilon,\hat\theta_{n}\in K)=0.
$$
ある $\theta\in\Theta$ が存在して，$Pm_\theta>-\infty$ の場合：
ステップ1
任意の $\theta_{0}\in\Theta_{0}$ に対し，$P|m_{\theta_{0}}|<\infty$ を示す．
仮定より，$Pm_{\theta_{0}}>-\infty$ である．これは，$Pm_{\theta}^{-}<\infty$ を意味する．さらに条件2より，
$$
Pm_{\theta_{0}}= P\sup_{\theta\in B_\delta(\theta_{0})}m_\theta<\infty
$$
であり，これは $Pm_{\theta_{0}}^{+}<\infty$ を意味する．したがって，
$$
P|m_{\theta_{0}}|=Pm_{\theta_{0}}^{+}+Pm_{\theta_{0}}^{-}<\infty
$$
が成立．
ステップ2
$m_{B_{\delta}(\theta)}(x):=\sup_{\theta’\in B_{\delta}(\theta)}m_{\theta}(x)$ とする．任意の $\theta\in\Theta$ に対し，$Pm_{B_{\delta}(\theta)}\searrow Pm_{\theta}$ を示す．補題2より，任意の $\theta\in\Theta$ に対し，$m_{B_{\delta}(\theta)}(x)\searrow m_{\theta}(x)\enspace(\delta\searrow0)$ が成立するので，単調収束定理より，$Pm_{B_{\delta}(\theta)}\searrow Pm_{\theta}$．
$B=\{\theta\in K\mid d(\theta,\Theta_{0})\geq\varepsilon\}$ とする．$\theta\not\in\Theta_{0}\Rightarrow Pm_{\theta}<Pm_{\theta_{0}}$ である．
前の結果から，$\varepsilon'=(Pm_{\theta_{0}}-Pm_{\theta})/2$ に対し，ある $\eta>0$ が存在して，$Pm_{B_{\eta}(\theta)}-Pm_{\theta}<\varepsilon'$ が成立．ここで，$Pm_{\theta}+\varepsilon<Pm_{\theta_{0}}$ を満たすように，$\varepsilon'$ を選んでいるので，$Pm_{B_{\eta}(\theta)}<Pm_{\theta_{0}}$ が成立．$U_{\theta}:=B_{\eta}(\theta)$ とする．
$\{U_{\theta}\}_{\theta\in B}$ は $B$ の開被覆である．$B$ はコンパクトなので，有限部分被覆 ${U_{\theta_{j}}}$ が存在する．
ステップ3
$\limsup_{n\to\infty}\sup_{\theta\in B}\mathbb{P}_{n}m_{\theta}\leq\sup_{j}Pm_{U_{\theta_{j}}}$ a.s. が成立することを示す．
大数の強法則より，
\begin{align*}
\limsup_{n\to\infty}\sup_{\theta\in B}\mathbb{P}_{n}m_{\theta}
&=\limsup_{n\to\infty}\sup_{j}\sup_{\theta\in U_{\theta_{j}}}\mathbb{P}_{n}m_{\theta}\\
&\leq\limsup_{n\to\infty}\sup_{j}\sup_{\theta\in U_{\theta_{j}}}\mathbb{P}_{n}m_{U_{{\theta}_{j}}}\\
&=\limsup_{n\to\infty}\sup_{j}\mathbb{P}_{n}m_{U_{{\theta}_{j}}}\\
&=\sup_{j}Pm_{U_{\theta_{j}}}\enspace\text{a.s.}
\end{align*}
$Pm_{U_{\theta_j}}>-\infty$ ならば，$m_{U_{\theta_j}}$ は可積分なので通常の大数の強法則が適用できます．$Pm_{U_{\theta_j}}=-\infty$ の場合は，$-m_{U_{\theta_j}}$ に対し，Durrett (2019) Theorem 2.4.5 を適用することで，$\mathbb{P}_{n}m_{U_{\theta_j}}\overset{a.s.}{\to} Pm_{U_{\theta_j}}=-\infty$ がいえます．
ステップ4
$\lim_{n\to\infty}\operatorname{P}(\hat\theta_{n}\in B)=0$ を示す．
$\hat\theta_{n}\in B$ ならば，$\sup_{\theta\in B}\mathbb{P}_{n}m_{\theta}\geq \mathbb{P}_{n}m_{\hat\theta_{n}}\geq \mathbb{P}_{n}m_{\theta_{0}}-o_{p}(1)=Pm_{\theta_{0}}-o_{p}(1)$ である．また，$\sup_{j}Pm_{U_{\theta_{j}}}<Pm_{\theta_0}$ より，$\limsup_{n\to\infty}\sup_{\theta\in B}\mathbb{P}_{n}m_{\theta}<Pm_{\theta_0}$ a.s. である．補題1より，
\limsup_{n\to\infty}\operatorname{P}(\hat\theta_{n}\in B)\leq
\limsup_{n\to\infty}\operatorname{P}\left(\sup_{\theta\in B}\mathbb{P}_{n}m_{\theta}\geq Pm_{\theta_{0}}-o_{p}(1)\right)=0
が成り立つ．
参考文献
Durrett, Richard (2019). "Probability: Theory and Examples. Fifth edition". Cambridge University Press.
Van der Vaart, Aad W (1998). "Asymptotic Statistics". Cambridge University Press.
付録
K-means クラスタリングの一致性の証明で用いた Problem 5.23 も証明しておきます．
Van der Vaart (1998) Problem 5.23
Van der Vaart (1998) Theorem 5.14 の $\hat{\theta}_{n}$ の収束は
- $\Theta$ はコンパクト
- $M_{n}(\hat\theta_{n})\geq M_{n}(\theta_{0})-o(1)$
を仮定すると，a.s. の収束になる．
証明
Theorem 5.14 の証明のステップ3までは同様．$d(\hat\theta_n,\Theta_0)\overset{a.s.}{\to}0$ を示す．
$B=\{\theta\in\Theta\mid d(\theta,\Theta_0)\geq\varepsilon\}$ とする．いま，$\hat\theta_n\in B$ ならば，$\sup_{\theta\in B}\mathbb{P}_{n}m_\theta\geq\mathbb{P}_{n}m_{\hat\theta_n}\geq\mathbb{P}_nm_{\theta_0}-o(1)$ である．また，$\limsup_{n\to\infty}\sup_{\theta\in B}\mathbb{P}_{n}m_\theta<Pm_{\theta_0}$ a.s. である．したがって，
Pm_{\theta_0}>\limsup_{n\to\infty}\sup_{\theta\in B}\mathbb{P}_{n}m_\theta
\geq\limsup_{n\to\infty}\mathbb{P}_{n}m_{\theta_0}
=Pm_{\theta_0}\enspace\text{a.s.}
である．$\varepsilon$ は任意なので，$\limsup_{n\to\infty}d(\hat\theta_n,\Theta_0)=0$ a.s. である（証明終わり）．