Welcome to ml-formulas's documentation!¶
集中不等式¶
Markovの不等式¶
ステートメント¶
$X$を非負の確率変数とする，任意の$t> 0$に対して
$$ \mathbb{P} (X \geq t) \leq \frac{\mathbb{E}\left[X\right]}{t} $$ が成り立つ．
証明の概要¶
任意の$t\geq 0$に対して，
$$ X \geq t\mathbb{1}_{\{X\geq t\}} $$ が成り立つので，期待値を取って，
$$ \mathbb{E}\left[X\right] \geq \mathbb{E}\left[t\mathbb{1}_{\{X\geq t\}} \right] = t \mathbb{P} (X\geq t). $$
両辺を$t$で割れば不等式が得られる．
コメント¶
- 集中不等式と呼ばれる類の一連の不等式の出発点となる．
- Markovの不等式からChebyshevの不等式やExponential版のChebyshevの不等式が示せる．
- 文献によっては，Chebyshevの不等式のことをMarkovの不等式と呼ぶこともある．
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Chebyshevの不等式¶
ステートメント¶
$X$を確率変数とする，任意の$t>0$に対して $$ \mathbb{P} \{|X - \mathbb{E}| \geq t\} \leq \frac{\mathrm{Var}(X)}{t^2} $$ が成り立つ．
証明の概要¶
Markovの不等式から証明可能
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Chernoff Bound¶
ステートメント¶
$X$を確率変数とする，任意の$t>0$と$\lambda \in \mathbb{R}$に対して $$ \mathbb{P}\{ |X - \mathbb{E}X| \geq t\} \leq e^{\psi_{X}(\lambda)-\lambda t}. $$ ここで，$\psi_{X}$は$X$の生成母関数の対数，$\psi_{X}(\lambda):=\log \mathbb{E}\left[e^{\lambda X} \right]$．
証明の概要¶
Markovの不等式から証明できる
コメント¶
この不等式により，期待値周りの確率集中は生成母関数の対数$\psi_X$を評価することに帰着される
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Hoeffdingの不等式¶
ステートメント¶
$X_1, \ldots, X_N$が独立な確率変数であり，$X_i$はalmost sureで実数軸上の区間$[a_i, b_i] (a_i \leq b_i)$ に値を取ると仮定する．$S = \sum_{i=1}^{N} X_i$とすると，任意の$t\geq 0$に対し，
$$ \mathbb{P} \{ S - \mathbb{E}S \geq t \} \leq \exp\left( - \frac{2 t^2}{\sum_{i=1}^N(b_i - a_i)^2} \right) $$
コメント¶
この定理と「sub Gaussian性の必要十分条件」から，有界で独立な確率変数達の和はsub Gaussianであることがわかる．
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Bennettの不等式¶
ステートメント¶
$X_1, \ldots, X_N$を独立な確率変数であり，$\mathbb{E}X_i^2 < \infty$かつ，ある$b > 0$が存在して$X_i < b$ a.s. であると仮定する．$S := \sum_{i=1}^{N} X_i$とすると，任意の$\lambda > 0$に対して，
$$ \psi_S(\lambda) \leq \frac{v}{b^2} \phi (b\lambda) $$
が成立する．ここで，$\psi_S$は確率変数の生成母関数の対数，すなわち$\psi_S(\lambda) := \mathrm{\log} \mathbb{E}\left[ e^{\lambda S} \right]$，$v := \sum_{i=1}^N \mathbb{E}[X_i^2]$，$\phi(u) := e^u-u-1$である．
さらに，任意の$t>0$に対して，
$$ \mathbb{P}\left(S \geq t\right) \leq \exp\left( -\frac{v}{b} h\left( \frac{bt}{v}\right) \right) $$
が成立する．ここで，$h(u) := (1+u)\log (1+u) - u (u>0)$である．
コメント¶
- Hoeffdingの不等式を使うには，確率変数$X_i$達の値域が両側が抑えられている必要があるが，Bennettの不等式は片側だけ抑えられていれば使える．そのかわり各確率変数の分散が有限でないといけない．
- 2つ目の不等式は1つ目の不等式とChernoff boundから導かれる．その際，$\phi(u)$は$Z$をパラメータ$1$のポアソン分布とした時，$Z-1$の生成母関数の対数であり，$h$は$\phi$のCramer変換である（参考）ことを用いる．
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Bernsteinの不等式¶
ステートメント¶
$X_1, \ldots, X_N$を独立な確率変数であり，$\mathbb{E}X_i^2 < \infty$かつ，ある$b > 0$が存在して$X_i < b$ a.s. であると仮定する． $S = \sum_{i=1}^{N} X_i$とすると，任意の$t>0$に対して，
$$ \mathbb{P}\left(S \geq t\right) \leq \exp\left( -\frac{t^2}{2(v + \frac{bt}{3})} \right) $$
が成立する．ここで，$h(u) = (1+u)\log (1+u) - u (u>0)$である．
証明の概要¶
Bennettの不等式と不等式 $$ h(u) \geq \frac{u^2}{2(1 + \frac{u}{3})} $$ から導かれる．
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Poisson分布の生成母関数とそのCramer変換¶
ステートメント¶
$X$をパラメータ$v$のポアソン分布とする，$Y=X-v$の生成母関数の対数$\psi_{Y}(\lambda) := \mathbb{E} e^{\lambda (Y)}$は
$$ \psi_{Y} (\lambda) = v\phi(\lambda), $$ ここで，$\phi(u) := e^u-u-1$である．さらに，$\psi_Y$のCramer変換，$\psi_Y^{\ast}(t) := \sup_{\lambda>0} e^{\psi_Y (\lambda) -\lambda t}$ は
$$ \psi_Y^{\ast}(t) = vh\left(\frac{t}{v}\right) $$ である，ここで$h(u) := (1+u)\log (1+u) - u (u>0)$である．
コメント¶
- Bennetの不等式の証明にこの事実を使える
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
最大不等式¶
ステートメント (sub-Gaussian)¶
$X_1, \ldots, X_n$ は分散パラメータ $\sigma_i^2$ ($i = 1, \ldots, n$) をもつsub-Gaussian確率変数であるとする．このとき， $$ \mathbb{E} \max_{1 \leq i \leq n} X_i \leq \sqrt{2 \log n} \max_{i} \sigma_i^2 $$ および $$ \mathbb{E} \max_{1 \leq i \leq n} |X_i| \leq \sqrt{2 \log 2n} \max_{i} \sigma_i^2 $$ が成り立つ．
ステートメント (chi-squared)¶
$X_1, \ldots, X_n$ は，互いに独立とは限らない自由度 $p$ のカイ二乗確率変数とする．このとき， $$ \mathbb{E} \max_{1 \leq i \leq n} X_i \leq p + 2 \sqrt{p \log n} + 2\log n $$ が成り立つ．
コメント¶
- 有限個の確率変数の最大値に関するバウンドを最大不等式と呼ぶことがある．一般論については，Boucheron, et al. (2013) Section 2.5などを参照．
- $n$ 個のsub-Gaussian確率変数の最大値の期待値は，相関の有無にかかわらず $O(\sqrt{\log n})$ で上から抑えることができる．
- カイ二乗分布の最大不等式は，sub-Gamma確率変数に関する最大不等式の特別な場合である (Boucheron, et al. (2013) Corollary 2.6).
- 無限集合への拡張についてはDudleyのエントロピーバウンドを参照．
- 最大値の期待値どうしの大小比較はSlepianの不等式を参照．
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Dudleyのエントロピーバウンド¶
ステートメント¶
$T$ を可算集合として，$\{ X_t: t \in T \}$ を $T$ で添字づけられた平均0のガウス過程とする．つまり，それぞれの $X_t$ は同じ確率空間で定義された正規確率変数で，$\mathbb{E} X_t = 0$ を満たすものとする．$T$ に $X_t$ から誘導される擬距離 $d_X$ を $$ d_X(s, t) = \sqrt{\mathbb{E} (X_s - X_t)^2} $$ のように定める．任意の $\epsilon > 0$ に対して，$M(\epsilon, T, d_X)$ を擬距離 $d_X$ による $T$ の $\epsilon$-パッキングナンバーとする．
このとき， $$ \mathbb{E} \sup_{t \in T} X_t \leq C \int_{0}^\infty \sqrt{\log M(\epsilon, T, d_X)} d \epsilon $$ が成り立つ．ただし，$C > 0$ は普遍的な定数である．
コメント¶
- Dudley's entropy bound (またはchaining) と呼ばれている不等式は，(sub)-Gaussian processの最大値の期待値を，カバリングナンバーまたはパッキングナンバーの積分によって上から抑える形の不等式である．
- 上のステートメントは Talagrand (2014), (2.38) 式から取った．
- $T$ を非可算集合にすることもできる．この場合，厳密には $\sup_{t \in T} X_t$ の部分の可測性を気にする必要がある．
- $X_t$ をsub-Gaussian processにすることもできる．
- Modulus of continuity $\mathbb{E} \sup_{d(s, t) \leq \delta} |X_s - X_t|$ を上からおさえる形のステートメントもある．
- 最大不等式を無限集合に拡張したもの．(sub-)Gaussian processの最大値を上から抑えたいときに，添字集合の距離エントロピー (カバリングナンバーやパッキングナンバー) の評価に帰着させることができる．
- 下から抑えたいときはSudakov minorationがある．
- よりタイトな不等式として，Generic chainingと呼ばれるものが知られている．
出典¶
- Talagrand. Upper and Lower bound for Stochastic Processes. Springer, 2014.
- van der Vaart and Wellner. Weak Convergence and Empirical Processes. Springer, 1996.
- Gine and Nickl. Mathematical Foundations of Infinite-Dimensional Statistical Models. Cambridge University Press, 2015.
Sudakov minoration¶
ステートメント (a)¶
$T$ を可算集合として，$\{ X_t: t \in T \}$ を $T$ で添字づけられた平均0のガウス過程とする．つまり，それぞれの $X_t$ は同じ確率空間で定義された正規確率変数で，$\mathbb{E} X_t = 0$ を満たすものとする．$T$ に $X_t$ から誘導される擬距離 $d_X$ を $$ d_X(s, t) = \sqrt{\mathbb{E} (X_s - X_t)^2} $$ のように定める．任意の $\epsilon > 0$ に対して，$M(\epsilon, T, d_X)$ を擬距離 $d_X$ による $T$ の $\epsilon$-パッキングナンバーとする．
このとき， $$ \mathbb{E} \sup_{t \in T} X_t \geq C \epsilon \sqrt{\log M(\epsilon, T, d_X)} $$ が成り立つ．ただし，$C > 0$ は普遍的な定数である．
ステートメント (b)¶
$\mathbb{R}^d$ の任意の部分集合 $T$ に対して，$T$ のガウス幅 (Gaussian width) を $$ w(T) := \mathbb{E} \sup_{t \in T} \langle t, Z \rangle $$ によって定義する．ただし，$Z$ は $d$ 次元の標準正規分布にしたがう確率変数とする．また，$\sup_t$ による可測性の問題はここでは考えないとする．
このとき，任意の $\epsilon > 0$ に対して $$ w(T) \geq C \epsilon \sqrt{\log M(\epsilon, T, \lVert \cdot \rVert_2)} $$ が成り立つ．ただし，$C > 0$ は普遍的な定数である．
コメント¶
ガウス過程のsupの期待値を，距離エントロピーを使って下からおさえる不等式である．特に，Dudleyのエントロピーバウンドと合わせると，ガウス過程の最大値の期待値は $$ C_1 \epsilon \sqrt{\log M(\epsilon, T, d_X)} \leq \mathbb{E} \sup_{t \in T} X_t \leq C_2 \int_0^\infty \sqrt{\log M(\epsilon, T, d_X)} d \epsilon $$ のように上下からバウンドできると主張している．直感的には，Dudley積分を，「幅 $\epsilon$」「高さ $\sqrt{\log M(\epsilon, T, d_X)}$」の長方形の面積で近似した形になっている．
Sudakov minorationによる下界はオーダーの意味でタイトではない場合がある．このギャップはgeneric chainingと呼ばれる方法を利用することで埋まる．
ステートメント(b)のように，ガウス幅のオーダーを下から見積もることに役にたつ．
出典¶
- Dudley. Uniform Central Limit Theorems. 2nd edition (2014).
- Gine and Nickl. Mathematical Foundations of Infinite-Dimensional Statistical Models (2015).
Generic chaining¶
ステートメント¶
準備¶
$(T, d)$ を距離空間とする．
$T$ の部分集合 $A$ の直径を $\mathrm{diam}(A) = \sup_{s, t \in A} d(s, t)$ と表す．
$T$ の分割 $\mathcal{A}$ とは，互いに交わらない $T$ の有限個の部分集合の族 $\mathcal{A} = { A_1, \ldots, A_m }$ で，$\bigcup_i A_i = T$ となるものである．$T$ の分割 $\mathcal{A}$ および点 $t \in T$ に対して，$\mathcal{A}(t)$ によって $t$ を含む $\mathcal{A}$ の唯一の要素を表すとする．
$T$ の分割からなる列 $\mathcal{A}_0, \mathcal{A}_1, \ldots$ がネストしているとは，任意の $k \geq 1$ に対して $\mathcal{A}_{k}$ が $\mathcal{A}_{k-1}$ の細分になっていることをいう． 分割の列 $\mathcal{A}_{0}, \mathcal{A}_{1}, \ldots$ がTalagrand列 (または許容列) であるとは，任意の $k \geq 1$ に対して，
$$ 1 \leq |\mathcal{A}_{k}| \leq 2^{2^k} $$
が成り立つこととする．
以上の用語のもとで，$\gamma_2(T, d)$ を
$$ \inf \sup_{t \in T} \sum_{k = 0}^\infty 2^{k/2} \mathrm{diam}(\mathcal{A}_{k}(t)) $$
によって定義する．ただし，infはすべてのTalagrand列の全体にわたってとる．
定理の主張¶
$(T, d)$ を距離空間として，確率過程 $\{ X_t: t \in T \}$ を距離 $d$ に関するsub-Gaussian processとする．つまり，任意の $s, t \in T$ と $u > 0$ に対して $$ \mathbb{P}(|X_s - X_t| \geq u) \leq 2 \exp \left( - \frac{u^2}{2 d(s, t)^2} \right) $$ が成り立つものとする．
このとき， $$ C_1 \gamma_2(T, d) \leq \mathbb{E} \sup_{t \in T} X_t \leq C_2 \gamma_2(T, d) $$ が成り立つ．ただし，$C_1, C_2 > 0$ は普遍的な定数である．
コメント¶
- (劣)ガウス過程の最大値の期待値について，定数倍を許してタイトな上下界を与えた定理．Majorizing measure theoremともいう (Talagrand (2014), Theorem 2.4.1).
- これに対して，Dudleyのエントロピーバウンド および Sudakov minoration によって得られる上下界はタイトでない例が存在する．例えば，$T$ が $\mathbb{R}^m$ の楕円体であるとき，Dudleyのバウンドよりも本質的によい上界が存在する (Talagrand (2014), Section 2.5).$T$ が $\mathbb{R}^m$ の部分集合のとき，Dudleyのバウンドによる上界は，最適なものと比較すると高々 $O(\log (m + 1))$ のギャップを生じうる．
出典¶
- Talagrand. Upper and Lower bound for Stochastic Processes. Springer, 2014.
- Dudley. Uniform Central Limit Theorems. 2nd edition (2014).
Efron--Steinの不等式¶
ステートメント¶
$\mathcal{X}$を測度空間，$X_1, \ldots, X_N$を$\mathcal{X}$に値を取る独立な確率分布，$f: \mathcal{X}^N\to \mathbb{R}$を2乗可積分な関数とする． $Z=f(X_1, \ldots, X_N)$ とすると，
$$ \mathrm{Var}(Z) \leq \frac{1}{2} \sum_{i=1}^N \mathbb{E}\left[(Z - Z_i)^2\right]. $$
ここで， $X_i'$を$X_i$の独立なコピーとし， $Z_i = f(X_1, \ldots, X_i', \ldots, X_N)$とした．
証明の概要¶
Boucheron et al. (2013)3章では，
$$ \Delta_i := \mathbb{E}i Z - \mathbb{E}{i-1}Z $$
によりDoobマルチンゲール列 $\{\Delta_i \}_{i=1}^N$を構成し，$Z$の分散が$\Delta_i$達の分散の和で書けることから証明している． ここで$\mathbb{E}_i$は$X_1, \ldots, X_i$で条件づけた期待値である．
コメント¶
- $f$の2乗可積分性の仮定は分散を定義するために課している．
- $\mathrm{Var}^{(i)}$を$X^{(i)} := (X_1, \ldots, X_i, X_{i+1}, \ldots X_N)$で条件づけた分散，すなわち，$\mathrm{Var}^{(i)}(Z) := \mathbb{E}^{(i)}\left[ (Z - \mathbb{E}^{(i)}Z)^2 \right]$とした時（ここで，$\mathbb{E}^{(i)}$は$X^{(i)}$で条件づけた期待値），ステートメントの右辺は$\sum_{i=1}^N \mathbb{E}\left[ \mathrm{Var}^{(i)} (Z) \right]$と書ける（元のステートメントと異なり，係数$1/2$がないことに注意）．従って，Efron--Steinの定理は一定の条件で分散が劣加法性を持つことを主張していると見ることもできる．
- 入力確率変数達に同分布性は仮定しないが独立性は仮定する．独立性は仮定せずに分散を評価する方法としてGauss--Poincare不等式があるが，これは同分布性より更に強く，入力確率変数達は標準正規分布であることを仮定している．
- Efron--Steinでは$Z$の分散を評価することはできるが，分布が指数的に減少することを示すことためのには使えない（Boucheron et al. (2013) 6章）．
出典¶
- Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
エントロピーの劣加法性¶
ステートメント¶
$\mathcal{X}$を測度空間，$X_1, \ldots, X_N$を$\mathcal{X}$に値をとる独立な確率分布，$f\colon \mathcal{X}^N \to [0, 1]$を可測関数とし，$Z = f(X_1, \ldots, X_N)$とする．
$Z$のエントロピー$\mathrm{Ent}(Z)$と$X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{N}$で条件づけたエントロピー$\mathrm{Ent}^{(i)}(Z)$をそれぞれ
$$ \mathrm{Ent}(Z)\colon = \mathbb{E}\left[\Phi(Z)\right] - \Phi(\mathbb{E}Z)\\ \mathrm{Ent}^{(i)}(Z)\colon = \mathbb{E}^{(i)}\left[\Phi(Z)\right] - \Phi(\mathbb{E}^{(i)}Z) $$
と定義する．ここで，$\mathbb{E}^{(i)}$は，$X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_{N}$で条件づけた期待値（すなわち，$X_i$についてのみ期待値を取る），$\Phi(x) \colon = x\log x (x\geq 0)$である（$0\log 0=0$と約束する）． この時，
$$ \mathrm{Ent}(Z) \leq \sum_{i=1}^N \mathbb{E}\left[ \mathrm{Ent}^{(i)} Z\right] $$
が成立する．
証明の方針¶
$\mathcal{X}$が有限集合の場合には，$(X_1, \ldots, X_N)$の分布関数$p$と$q\colon = fp$のKLダイバージェンスにHanの不等式を適用することで得られる．一般の場合には，エントロピーのvariational formulaを経由して示せる(Boucheron et al. 2013)4章．
コメント¶
- 確率測度$P$と$P$に絶対連続な確率測度$Q$に対して，$Q$の$P$に関するKLダイバージェンス（相対エントロピー）$\mathrm{KL}(Q|P)=\mathrm{Ent}\left(\frac{dP}{dQ} \right)$である．
- エントロピーを定義するのに用いた$\Phi(x)=x\log x$を，「アファイン関数」または「$\Phi''>0$かつ$1/\Phi''$が凹」な2階微分な関数$\Phi$に一般化することで$\Phi$-エントロピーが定義でき，通常のエントロピーと同様に劣加法性が成立する（Rafał and Oleszkiewicz 2000）．
出典¶
- Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
- Latała Rafał, and Krzysztof Oleszkiewicz. "Between sobolev and poincaré." Geometric aspects of functional analysis. Springer, Berlin, Heidelberg, 2000. 147-168.
Gauss集中不等式 （Gaussian Concentration inequality）¶
ステートメント¶
$X_1, \ldots, X_N$を独立同分布で，各$X_i$は標準正規分布に従うとする． $L>0$とし，$f: \mathbb{R}^N \to \mathbb{R}$を$L-$リプシッツ関数とする． $Z=f(X)$とした時，任意の$t>0$に対し，
$$ \mathbb{P}\{Z -\mathbb{E}Z \geq t \} \leq e^{-\frac{t^2}{2L^2}} $$ が成立する．
証明の概要¶
- いくつかの証明方法がある．1つの方法として，対数ソボレフ不等式から，$Z$の生成母関数の対数を評価し，$Z$が$L$-sub Gaussianであることを示す方法が挙げられる． この一連の証明方法をHerbstの議論（Herbst's argument）という．
- ガウス過程に関する不等式Tsirelson-Ibragimov-Sudakov（TIS）の定理の特別な場合とみなせる．
出典¶
- Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
- Evarist Giné and Richard Nickl, Mathematical Foundations of Infinite-Dimensional Statistical Models (2015)
ブーリアン関数¶
Hypercontractive不等式¶
ステートメント¶
関数$f\colon{-1,1}^n \to \mathbb{R}$と実数$\rho \in [-1,1]$に対し， $$ T_\rho f(x)=\mathbb{E}{y∼N\rho(x)}[f(y)] $$ と定義する． ここで$y∼N_\rho(x)$とは，各$i \in {1,\ldots,n}$について独立に $$ y_i = \begin{cases} x_i & \text{確率 } \frac{1+\rho}{2}\ -x_i & \text{確率 } \frac{1-\rho}{2} \ \end{cases} $$ と選ぶことを指す．
このとき関数$f: {-1,1}^n \to \mathbb{R}$と，$0 \leq \rho \leq \sqrt{\frac{p-1}{q-1}}$なる実数$1 \leq p \leq q \leq \infty$に対して， $$ |T_\rho f|_q \leq |f|_p $$ が成り立つ．
出典¶
- R. O'Donnell. Analysis of Boolean Functions (2014).
凸幾何学¶
Brunn--Minkowskiの不等式¶
ステートメント¶
$\mu$ を $\mathbb{R}^n$ のLebesgue測度とする．$A, B \subseteq \mathbb{R}^n$ を空でないコンパクト集合とし，$\lambda \in [0, 1]$ とする．このとき $$ \mu( (1 - \lambda) A + \lambda B)^{1/n} \geq (1 - \lambda) \mu(A)^{1/n} + \lambda \mu(B)^{1/n} $$ が成り立つ．ただし，集合 $A, B \subseteq \mathbb{R}^n$ に対して，$A + B$ はMinkowski和を表し，$\lambda A = \{ \lambda x: x \in A \}$ とする．
コメント¶
凸幾何における基本的な不等式のひとつ．(TODO: 応用例)
証明の概要¶
$\lambda = 1/2$，$n = 1$ とした不等式 $\mu(A + B) \geq \mu(A) + \mu(B)$ は容易に示すことができる．多次元の場合は，Prekopa--Leindlerの不等式を経由する方法が知られている (Boucheron, Lugosi and Massart (2013)).
出典¶
Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)
Precopa--Leindlerの不等式¶
ステートメント¶
$\lambda \in (0, 1)$ とする．$f, g, h: \mathbb{R}^n \to [0, \infty)$ は可測関数で，任意の $x, y \in \mathbb{R}^n$ に対して $$ h((1 - \lambda) x + \lambda y) \geq f(x)^{1 - \lambda} g(y)^{\lambda} $$ を満たすものとする．このとき， $$ \int_{\mathbb{R}^n} h(x) d x \geq \left( \int_{\mathbb{R}^n} f(x) d x \right)^{1 - \lambda} \left( \int_{\mathbb{R}^n} g(x) d x \right)^{\lambda} $$ が成り立つ．
コメント¶
$\mathbb{R}^n$ 上の絶対連続な確率測度で，密度関数 $\phi$ の対数が凹関数であるもの，すなわち $$ \phi((1 - \lambda)x + \lambda y) \geq \phi(x)^{1 - \lambda}\phi(y)^{\lambda} $$ を満たすものを対数凹分布という．Prekopa--Leindlerの不等式から，対数凹分布のいろいろな性質が示せる．
まず，対数凹性は周辺化によって保存する．$\mathbb{R}^{n_1 \times n_2}$ 上の対数凹分布で，密度関数 $\phi(x, y)$ をもつものを考える．$y$ について周辺化した $\mathbb{R}^{n_1}$ 上の確率密度を $$ \phi_{x}(x) = \int_{\mathbb{R}^{n_2}} \phi(x, y) d y $$ とする．ここで，$x_1, x_2 \in \mathbb{R}^{n_1}$ を固定し，$h(y) = \phi((1 - \eta)x_1 + \eta x_2)$, $f(y) = \phi(x_1, y)$, $g(y) = \phi(x_2, y)$ に対してPrekopa--Leindlerの不等式を適用すると， $$ \phi_x((1 - \eta)x_1 + \eta x_2) \geq \phi_x(x_1)^{1 - \eta} \phi_x(x_2)^\eta $$ が成り立つ．
また，$\mu$ が密度 $\phi$ をもつ対数凹分布であるとき， $$ \mu((1 - \lambda) A + \lambda B) \geq \mu(A)^{1 - \lambda} \mu(B)^{\lambda} $$ が成り立つ．これを確認するには，$h(x) = \phi(x) 1_{(1 - \lambda) A + \lambda B}(x)$, $f(x) = \phi(x) 1_{A}$, $g(x) = \phi(x) 1_{B}$ にPrekopa--Leindlerの不等式を適用すればよい．特に，$\mu$ が $\mathbb{R}^n$ の一様測度のときにも成立し，ここから多次元のBrunn--Minkowskiの不等式が示せる (Boucheron, Lugosi and Massart (2013), Section 4.14)．また，低次元の線形部分空間に縮退したGauss測度でも同様のことが示せる (Gine and Nickl (2015), Theorem 2.4.3).
出典¶
- Boucheron, Lugosi and Massart. Concentration inequalities: A Nonasymptotic Theory of Independence (2013).
- Gine and Nickl. Mathematical Foundations of Infinite-Dimensional Statistical Models (2015).
確率論¶
Slepianの不等式¶
ステートメント¶
$X = (X_1, \ldots, X_n)$ と $Y = (Y_1, \ldots, Y_n)$ はそれぞれ平均 $0$ の正規分布を同時分布としてもつ確率変数列とする．$i, j \in { 1, \ldots, n }$ について $$ \mathbb{E}[X_i^2] = \mathbb{E}[Y_i^2] $$ および $$ \mathbb{E}[X_i X_j] \leq \mathbb{E}[Y_i Y_j] $$ が成り立つとする．
このとき， $$ \mathbb{E} \max_{1 \leq i \leq n} Y_i \leq \mathbb{E} \max_{1 \leq i \leq n} X_i $$ が成り立つ．
コメント¶
平均 $0$ のガウス過程 $X_i$ ($i = 1, \ldots, n$) について，分散 $\mathbb{E}X_i^2$ の値が各時刻で同じなら，異なる時刻間の相関が小さいほど最大値の期待値は大きい．
ガウス過程の最大値の期待値どうしを比較したり，下から抑えたいときに役立つ．Sudakov minorationも参照．
出典¶
- Dudley. Uniform Central Limit Theorems. 2nd edition (2014).
- Boucheron, Lugosi and Massart. Concentration inequalities: A Nonasymptotic Theory of Independence (2013).
Berry--Esseenの定理¶
ステートメント¶
$X_1, \ldots, X_n$ は独立同分布にしたがう確率変数であって，$\mathbb{E} X_1 = 0$, $\mathbb{E} X_1^2 = \sigma^2 < \infty$, $\mathbb{E} |X_1|^3 = \rho < \infty$ を満たすものとする． $$ S_n = \frac{\sum_{i=1}^n X_i}{\sigma \sqrt{n}} $$ として，$F_n: \mathbb{R} \to [0, 1]$ を $S_n$ の累積分布関数とする．また，$\Phi: \mathbb{R} \to [0, 1]$ を標準正規分布の累積分布関数とする．
このとき， $$ \sup_{x \in \mathbb{R}} |F_n(x) - \Phi(x)| \leq \frac{C \rho}{\sigma^3 \sqrt{n}} $$ が成り立つ．ここで，$C > 0$ は普遍的な定数である．
コメント¶
中心極限定理の主張は，$S_n$ が標準正規分布に分布収束するというものである．一様中心極限定理とは，この収束がKolmogorov距離 $$ \sup_{x \in \mathbb{R}} |F_n(x) - \Phi(x)| $$ に関して成り立つということを主張したものである．Berry--Esseenの定理は，一様中心極限定理がさらに有限サンプルで成り立つように定量化を行ったものである．
Dvoretzki--Kiefer--Wolfowitzの不等式 (DKW不等式)¶
ステートメント¶
$X$ を $\mathbb{R}$ に値をとる任意の確率変数とし，$F: \mathbb{R} \to [0, 1]$ をその分布関数とする．$X_1, \ldots, X_n$ を $X$ の独立なコピーとして，$F_n$ をそれらの経験分布関数とする．このとき，ある定数 $0 < C < +\infty$ が存在して，任意の $t > 0$ に対して $$ \mathbb{P}(\sqrt{n} \sup_{x \in \mathbb{R}} |F_n(x) - F(x)| > t) \leq C \exp( - 2 t^2) $$ が成り立つ．
コメント¶
Massart (1990) によると，DKW不等式は $C = 2$ で成り立つ (Dudley (2014))．
DKW不等式は，i.i.d.確率変数の分布関数に対する一様大数の法則 (Glivenko--Cantelliの定理) の有限サンプル版といえる．ちなみに，$x \in \mathbb{R}$ を固定すると，$|F_n(x) - F(x)|$ の集中不等式はHoeffdingの不等式から示すことができる．
一様中心極限定理の有限サンプル版については，Berry--Esseenの定理を参照．
出典¶
R. M. Dudley. Uniform Central Limit Theorems. 2nd edition (2014).
情報理論¶
ミニマックス理論におけるLe Camの方法¶
ステートメント¶
$\mathcal{P}$ を可測空間 $(\mathcal{X}, \mathcal{A})$ 上の確率測度の集合とする．任意の $P \in \mathcal{P}$ に対して，(擬) 距離空間 $(\Theta, d)$ の値 $\theta(P)$ が対応しているとする．$\hat{\theta}: \mathcal{X} \to \Theta$ を任意の可測写像とする．
2つの確率測度 $P_{1}, P_{2} \in \mathcal{P}$ を，$d(\theta (P_{1}), \theta (P_{2})) \geq 2\delta > 0$ を満たすようにとる．このとき，
$$ \sup_{P \in \mathcal{P}} \mathbb{E}_{P} d(\hat{\theta}, \theta(P)) \geq \delta (1 - d\sb{\mathrm{TV}}(P_1, P_2)). $$
コメント¶
- ミニマックスリスクを，「2つの仮説 $P_1$, $P_2$ の見分けにくさ」に基づいて下から抑える不等式である．
- より多くの仮説に基づいたミニマックスリスク下界については，Fanoの不等式 のコメントを参照．
証明の方針¶
仮説検定の枠組みに基づいた解説はTsybakov (2009)を参照．ここでは，Yu (1997) にならって，より直接的な証明を与える．
$\theta_i := \theta(P_i)$ ($i = 1, 2$) と表す．また，$P_i$ による期待値を $\mathbb{E}_i$ などと書く．
三角不等式より，
$$ d(\hat{\theta}(X), \theta_1) + d(\hat{\theta}(X), \theta_2) \geq d(\theta_1, \theta_2) \geq 2\delta $$
である．よって，$i = 1, 2$ に対して
$$ f_i(X) := \frac{d(\hat{\theta}(X), \theta_i)}{2\delta} $$
とおくと，$f_i$ は非負可測関数で $f_1 + f_2 \geq 1$ が成り立つ．したがって，
$$ \begin{align} 2 \sup_{P \in \mathcal{P}} \mathbb{E}\sb{P} d(\hat{\theta}, \theta(P)) & \geq \mathbb{E}\sb{1} d(\hat{\theta}, \theta_1) + \mathbb{E}\sb{2} d(\hat{\theta}, \theta_2) \nl & \geq 2 \delta \inf_{f_i \geq 0, f_1 + f_2 = 1} (\mathbb{E}\sb{1} f_1 + \mathbb{E}\sb{2} f_2 ) \nl & = 2 \delta (1 - d\sb{\mathrm{TV}}(P_1, P_2)). \end{align} $$
出典¶
- A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer, (2009).
- B. Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, Springer, 1997.