濃度不等式(concentration inequality)とは、独立な確率変数などから作った量 $f(X_1,\dots,X_n)$ が平均から $t$ 以上離れる確率を、$t$ について指数関数的に小さい量で上から抑える不等式の総称で、Markov の不等式を $e^{\lambda X}$ に当てる Chernoff の方法が基本である。独立で 2 乗可積分な変数の和で、各項の平均からの上へのずれが $b$ 以下、分散の和が $v$ なら $P(S-E[S]\ge t)\le\exp(-t^2/(2(v+bt/3)))$ が成り立つ(Bernstein の不等式)。独立な変数の関数で、$i$ 番目の座標の変化による値の変化が $c_i$ 以下なら $P(f-E[f]\ge t)\le\exp(-2t^2/\sum_ic_i^2)$ が成り立つ(McDiarmid の不等式)。
前提知識: Markovの不等式, Hoeffdingの不等式, マルチンゲール
濃度不等式(concentration inequality)は、多数の独立な(あるいは弱く依存する)確率変数から作った量 $f(X_1,\dots,X_n)$ が、その平均から $t$ 以上離れる確率を
$$
P\bigl(\lvert f(X)-E[f(X)]\rvert\ge t\bigr)\le2e^{-t^2/(2\sigma^2)}
$$
のように、$t$ について指数関数的に小さい量で上から抑える不等式の総称である。Chebyshevの不等式 は分散 $\sigma^2$ だけから $\sigma^2/t^2$ を与えるが、確率変数の有界性や独立性を十分に使うと、正規分布の裾と同じ速さの評価が得られる。独立な和に限らず、各変数への依存が小さい関数なら同じ評価が成り立つ、という点がこの理論の要である。
方法の中心は Chernoff の方法、すなわち Markovの不等式 を $e^{\lambda X}$ に当てて積率母関数を評価することである。この記事では次を扱う。
実数値の確率変数 $X$ と $t\in\mathbb{R}$ について
$$
P(X\ge t)\le\inf_{\lambda\ge0}e^{-\lambda t}E\bigl[e^{\lambda X}\bigr]
$$
である(右辺の期待値は $+\infty$ でもよい)。
$\lambda\ge0$ なら $x\mapsto e^{\lambda x}$ は非減少なので $\{X\ge t\}\subset\{e^{\lambda X}\ge e^{\lambda t}\}$ であり、Markovの不等式 から $P(X\ge t)\le e^{-\lambda t}E[e^{\lambda X}]$ である。$\lambda$ について下限をとる。$\square$
右辺の下限の対数は、累積母関数 $\Lambda(\lambda):=\log E[e^{\lambda X}]$ の Legendre 変換に負号を付けたもの $-\sup_{\lambda\ge0}(\lambda t-\Lambda(\lambda))$ である。したがって、評価の良し悪しは $\Lambda$ をどれだけ正確に上から抑えられるかで決まる。
$\sigma\ge0$ とする。実数値の確率変数 $X$ が 分散の目安 $\sigma^2$ の劣 Gauss(sub-Gaussian with variance proxy $\sigma^2$)であるとは、すべての $\lambda\in\mathbb{R}$ について
$$
E\bigl[e^{\lambda(X-E[X])}\bigr]\le e^{\lambda^2\sigma^2/2}
$$
が成り立つことをいう。
$X$ が $N(m,\sigma^2)$ に従えば等号が成り立つ。$X$ が区間 $[a,b]$ に値をとれば、Hoeffdingの不等式 の補題「Hoeffding の補題」により、$X$ は分散の目安 $(b-a)^2/4$ の劣 Gauss である。目安は分散以上である($\lambda\to0$ で両辺を 2 次まで展開する)が、等しいとは限らない。
Hoeffding の不等式は区間の幅だけを使うので、分散が幅に比べて小さい変数では粗い。値が $0$ か $1$ で $1$ になる確率 $p$ が小さい変数の分散は $p(1-p)$ だが、幅から得られる目安は $\frac14$ である。分散を使うのが次の不等式である。
$X_1,\dots,X_n$ を独立で 2 乗可積分な確率変数とし、$b>0$ があって、すべての $i$ で確率 $1$ で $X_i-E[X_i]\le b$ であるとする。$S:=\sum_iX_i$、$v:=\sum_i\operatorname{Var}(X_i)>0$ とおく。すべての $t>0$ について
$$
P\bigl(S-E[S]\ge t\bigr)\le\exp\Bigl(-\frac{t^2}{2(v+bt/3)}\Bigr)
$$
である。
1 変数の評価。 $\phi(z):=\dfrac{e^z-1-z}{z^2}$($\phi(0):=\frac12$)とおく。Taylor の定理の積分形の剰余から
$$
\phi(z)=\int_0^1(1-s)e^{sz}\,ds
$$
で、被積分関数は $z$ について増加するので、$\phi$ は増加関数である。また $u\ge0$ では $\phi(u)=\sum_{k\ge2}u^{k-2}/k!$ で、$k!\ge2\cdot3^{k-2}$($k\ge2$)から、$0\le u< 3$ なら
$$
\phi(u)\le\frac12\sum_{k\ge2}\Bigl(\frac u3\Bigr)^{k-2}=\frac1{2(1-u/3)}
$$
である。
$Y_i:=X_i-E[X_i]$ とし、$0< \lambda< 3/b$ とする。$\lambda Y_i\le\lambda b$ と $\phi$ の単調性から、確率 $1$ で
$$
e^{\lambda Y_i}=1+\lambda Y_i+\lambda^2Y_i^2\phi(\lambda Y_i)\le1+\lambda Y_i+\lambda^2Y_i^2\phi(\lambda b)
$$
である。期待値をとり $E[Y_i]=0$、$1+x\le e^x$ を使うと
$$
E\bigl[e^{\lambda Y_i}\bigr]\le1+\lambda^2\operatorname{Var}(X_i)\phi(\lambda b)\le\exp\Bigl(\frac{\lambda^2\operatorname{Var}(X_i)}{2(1-\lambda b/3)}\Bigr)
$$
である。
和と最適化。 独立性から $E[e^{\lambda(S-E[S])}]=\prod_iE[e^{\lambda Y_i}]\le\exp\bigl(\lambda^2v/(2(1-\lambda b/3))\bigr)$ で、lem-ci-chernoff から
$$
P(S-E[S]\ge t)\le\exp\Bigl(-\lambda t+\frac{\lambda^2v}{2(1-\lambda b/3)}\Bigr)
$$
である。$\lambda:=t/(v+bt/3)$ とおくと $\lambda b/3=\frac{bt/3}{v+bt/3}< 1$ で、$1-\lambda b/3=\frac v{v+bt/3}$ なので、指数は
$$
-\frac{t^2}{v+bt/3}+\frac{t^2}{(v+bt/3)^2}\cdot\frac{v}{2v/(v+bt/3)}=-\frac{t^2}{v+bt/3}+\frac{t^2}{2(v+bt/3)}=-\frac{t^2}{2(v+bt/3)}
$$
である。$\square$
右辺の形は 2 つの領域に分かれる。$t\le3v/b$ なら $v+bt/3\le2v$ なので右辺は $e^{-t^2/(4v)}$ 以下で、分散 $v$ の正規分布に近い裾である。$t\ge3v/b$ なら $e^{-3t/(4b)}$ 以下で、指数分布の型の裾である。上側だけを抑えるので、下側には $-X_i$ について同じ条件を課す。Ver18 Theorem 2.8.4(p. 38)は $\lvert X_i\rvert\le K$、平均 $0$ の両側の形 $2\exp(-\frac{t^2/2}{\sigma^2+Kt/3})$ で述べている。
$X_1,\dots,X_{1000}$ を独立で、確率 $0.01$ で $1$、それ以外で $0$ とし、$S=\sum_iX_i$(平均 $10$)が $20$ 以上になる確率を評価する($t=10$)。
| 評価 | 値 |
|---|---|
| Chebyshev(分散 $9.9$) | $0.099$ |
| Hoeffding(幅 $1$) | $e^{-0.2}\approx0.819$ |
| Bernstein($v=9.9$、$b=0.99$) | $e^{-100/26.4}\approx0.0226$ |
| Chernoff の限界(Hoeffdingの不等式) | $(e/4)^{10}\approx0.0210$ |
| 実際の確率(二項分布) | $\approx0.0033$ |
Bernstein の不等式は、分散を使う点で Hoeffding の不等式より大幅に良く、2 点分布の積率母関数を使い切る Chernoff の限界に近い。
独立な和でない量 $f(X_1,\dots,X_n)$ は、情報を 1 つずつ増やして条件付けた マルチンゲール $M_k:=E[f(X)\mid X_1,\dots,X_k]$ の増分の和 $f(X)-E[f(X)]=\sum_k(M_k-M_{k-1})$ に分解する(Doob のマルチンゲール)。増分は独立ではないが、条件付きの積率母関数が抑えられれば Chernoff の方法が使える。
$(M_k)_{0\le k\le n}$ をフィルトレーション $(\mathcal F_k)$ に関するマルチンゲールとし、$D_k:=M_k-M_{k-1}$ とする。定数 $\sigma_1,\dots,\sigma_n\ge0$ があって、すべての $k$ と $\lambda\in\mathbb{R}$ で確率 $1$ で
$$
E\bigl[e^{\lambda D_k}\bigm|\mathcal F_{k-1}\bigr]\le e^{\lambda^2\sigma_k^2/2}
$$
とする。$s^2:=\sum_k\sigma_k^2>0$ とすると、$t>0$ について $P(M_n-M_0\ge t)\le e^{-t^2/(2s^2)}$ である。
$\lambda>0$ とする。$e^{\lambda(M_k-M_0)}=e^{\lambda(M_{k-1}-M_0)}e^{\lambda D_k}$ で、第 1 因子は非負で $\mathcal F_{k-1}$-可測なので、非負の確率変数の条件付き期待値の性質から
$$
E\bigl[e^{\lambda(M_k-M_0)}\bigr]=E\Bigl[e^{\lambda(M_{k-1}-M_0)}E\bigl[e^{\lambda D_k}\bigm|\mathcal F_{k-1}\bigr]\Bigr]\le e^{\lambda^2\sigma_k^2/2}E\bigl[e^{\lambda(M_{k-1}-M_0)}\bigr]
$$
である。$k=n,n-1,\dots,1$ と繰り返すと $E[e^{\lambda(M_n-M_0)}]\le e^{\lambda^2s^2/2}$ で、lem-ci-chernoff と $\lambda=t/s^2$ から結論を得る。$\square$
$\lvert D_k\rvert\le c_k$ なら、Hoeffdingの不等式 の定理「吾妻の不等式」の証明のとおり $\sigma_k=c_k$ にとれる。増分のとる区間の 幅 が $c_k$ なら、$\sigma_k=c_k/2$ にとれて指数が 4 倍良くなる。その典型が次の不等式である。
$X_1,\dots,X_n$ を独立な確率変数とし、$X_i$ は可測空間 $S_i$ に値をとるとする。可測関数 $f\colon S_1\times\cdots\times S_n\to\mathbb{R}$ と定数 $c_1,\dots,c_n>0$ について、$i$ 番目の座標だけが異なる任意の 2 点 $x,x'$ で
$$
\lvert f(x)-f(x')\rvert\le c_i
$$
であるとする。このとき、すべての $t>0$ について
$$
P\bigl(f(X)-E[f(X)]\ge t\bigr)\le\exp\Bigl(-\frac{2t^2}{\sum_{i=1}^nc_i^2}\Bigr)
$$
であり、$-f$ に当てると下側も同じ評価になる。
準備。 座標を 1 つずつ取り替えると、任意の 2 点で $\lvert f(x)-f(x')\rvert\le\sum_ic_i$ なので $f$ は有界である。$X_i$ の分布を $\mu_i$ とし、$0\le k\le n$ について
$$
g_k(x_1,\dots,x_k):=\int f(x_1,\dots,x_k,y_{k+1},\dots,y_n)\,\mu_{k+1}(dy_{k+1})\cdots\mu_n(dy_n)
$$
とおく。Fubiniの定理 により $g_k$ は可測で、独立性から、$\mathcal F_k:=\sigma(X_1,\dots,X_k)$ について $M_k:=E[f(X)\mid\mathcal F_k]=g_k(X_1,\dots,X_k)$ である($\mathcal F_k$ の事象の上の積分を、$X_1,\dots,X_k$ の分布と残りの分布の積の測度の上で計算すればよい)。$M_0=E[f(X)]$、$M_n=f(X)$ である。
増分の条件付き評価。 $D_k=M_k-M_{k-1}$ とし、$x_{< k}:=(x_1,\dots,x_{k-1})$ と書く。$g_{k-1}(x_{< k})=\int g_k(x_{< k},y)\,\mu_k(dy)$ である。再び独立性と Fubini の定理から、確率 $1$ で
$$
E\bigl[e^{\lambda D_k}\bigm|\mathcal F_{k-1}\bigr]=\Psi(X_1,\dots,X_{k-1}),\qquad\Psi(x_{< k}):=\int e^{\lambda(g_k(x_{< k},y)-g_{k-1}(x_{< k}))}\,\mu_k(dy)
$$
である。$x_{< k}$ を固定する。$y,y'\in S_k$ について、$f$ の仮定を残りの座標で積分すると $\lvert g_k(x_{< k},y)-g_k(x_{< k},y')\rvert\le c_k$ なので、$\mu_k$ に従う $Y$ について確率変数 $Z:=g_k(x_{< k},Y)-g_{k-1}(x_{< k})$ は平均 $0$ で、$a:=\inf_{y\in S_k}g_k(x_{< k},y)-g_{k-1}(x_{< k})$($f$ が有界なので実数)について区間 $[a,a+c_k]$ に値をとる。Hoeffdingの不等式 の補題「Hoeffding の補題」から $\Psi(x_{< k})=E[e^{\lambda Z}]\le e^{\lambda^2c_k^2/8}$ である。
結論。 thm-ci-martingale を $\sigma_k=c_k/2$、$s^2=\sum_kc_k^2/4$ で使うと、右辺は $e^{-t^2/(2s^2)}=e^{-2t^2/\sum_kc_k^2}$ である。$\square$
$f(x)=\sum_ix_i$、$S_i=[a_i,b_i]$、$c_i=b_i-a_i$ とすると、McDiarmid の不等式は Hoeffding の不等式そのものである。Ver18 は $S_i=\mathbb{R}$ の場合を Theorem 2.9.1(p. 39)で主張のみ述べている。機械学習では、関数の族の上での経験平均のずれの上限に McDiarmid の不等式を当てて、汎化誤差を Rademacher複雑度 で抑える(同記事の定理「一様な偏差の上界」)。
$n$ 個の玉を $m$ 個の箱へ独立に一様に投げ、空の箱の数を $Z$ とする。$X_i$ を $i$ 番目の玉の箱とすると $Z=f(X_1,\dots,X_n)$ で、1 つの玉の箱を変えると空の箱の数は高々 $1$ しか変わらない($c_i=1$)。$E[Z]=m(1-1/m)^n$ なので、thm-ci-mcdiarmid から
$$
P\bigl(\lvert Z-m(1-1/m)^n\rvert\ge t\bigr)\le2e^{-2t^2/n}
$$
である。$m=n=1000$ では $E[Z]\approx367.7$ で、$t=60$ なら右辺は $2e^{-7.2}\approx0.0015$ である。$Z$ は独立な和ではないが(箱が空であるという事象どうしは負の相関をもつ)、ずれは $\sqrt n$ の程度にとどまる。
$X$ が $\mathbb{R}^n$ の標準正規分布に従い、$F$ が定数 $1$ の Lipschitz 関数なら、$P(F(X)-E[F(X)]\ge r)\le e^{-r^2/2}$ が 次元 $n$ によらず 成り立つ。これは 対数Sobolev不等式 の定理「Herbst の議論による集中不等式」を、同記事の定理「Gross の不等式」(標準 Gauss測度 は定数 $1$ の対数 Sobolev 不等式を満たす)と合わせたものである。たとえば $\lvert X\rvert$ は平均 $\approx\sqrt n$ のまわりの幅 $O(1)$ に集中する(同記事の例「高次元の Gauss 測度」)。McDiarmid の不等式の $c_i$ が座標ごとの影響を測るのに対し、この形は関数全体の Lipschitz 定数だけを使う。
濃度不等式の指数は改良の余地が限られている。独立同分布な和では、中心極限定理 から $P(S-E[S]\ge t)$ は $t=x\sqrt{v}$ で正規分布の裾 $\approx e^{-x^2/2}$ に近づくので、劣 Gauss の評価の指数の係数 $\frac12$ は改良できない(Hoeffding の場合の議論は Hoeffdingの不等式 の命題「指数の係数の最良性」)。$t$ が $n$ に比例する領域の正確な指数は、大偏差の理論(Sanovの定理 など)が与える。
各行は、その定理の仮定を 1 つだけ外す。
| 定理 | 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|---|
| thm-ci-bernstein | 上からの有界性 $X_i-E[X_i]\le b$ | $n=1$、$P(X>s)=s^{-3}$($s\ge1$)の Pareto 分布(分散 $\frac34$) | どの $b$ についても、$t$ が大きいと右辺 $\approx e^{-3t/(2b)}$ が実際の確率 $\approx t^{-3}$ を下回る |
| thm-ci-bernstein | 独立性 | $\varepsilon=\pm1$(確率 $\frac12$ ずつ)、$X_1=\cdots=X_n=\varepsilon$ | $P(S\ge n)=\frac12$ だが右辺は $e^{-3n/8}$($n\ge2$ で $\frac12$ 未満) |
| thm-ci-mcdiarmid | 有界差 | $n=1$、$X_1$ は平均 $1$ の指数分布、$f(x)=x$ | $P(f-1\ge t)=e^{-1-t}$ は、どの $c_1$ についても $t$ が大きいと $e^{-2t^2/c_1^2}$ を上回る |
| thm-ci-mcdiarmid | 独立性 | $\xi$ は確率 $\frac12$ ずつで $0,1$、$X_1=\cdots=X_n=\xi$、$f(x)=\sum_ix_i$($c_i=1$) | $P(f-\frac n2\ge\frac n2)=\frac12$ だが右辺は $e^{-n/2}$($n\ge2$ で $\frac12$ 未満) |
| Gauss 測度の集中 | $F$ の Lipschitz 性 | $n=1$、$F(x)=x^2$ | $P(F-1\ge r)\approx e^{-r/2}$ の程度で、$e^{-r^2/(2L^2)}$ の形のどんな評価も $r$ が大きいと成り立たない |
1 行目。 $E[X]=\int_0^\infty P(X>s)\,ds=1+\int_1^\infty s^{-3}\,ds=\frac32$、$E[X^2]=\int_0^\infty2sP(X>s)\,ds=1+\int_1^\infty2s^{-2}\,ds=3$ で、分散は $\frac34$ である。$t\ge1$ で $P(X-\frac32\ge t)=(t+\frac32)^{-3}$ は $t$ の多項式の逆数の速さでしか減らないが、Bernstein の右辺は $t\to\infty$ で $\exp(-\frac{3t}{2b}(1+o(1)))$ の速さで減る。
2 行目。 $v=n$、$b=1$、$t=n$ で、右辺は $\exp(-n^2/(2(n+n/3)))=e^{-3n/8}$ である。$n=2$ で $e^{-0.75}\approx0.472$ である。
5 行目。 $X$ が標準正規分布に従うとき $P(X^2\ge1+r)=2(1-\Phi(\sqrt{1+r}))$ で、正規分布の裾の評価からこれは $r\to\infty$ で $e^{-r/2}$ に多項式の因子を掛けた程度である。$F$ は有界な区間の上では Lipschitz だが、$\mathbb{R}$ 全体では Lipschitz でない。
分散を使う評価は S. N. Bernstein、和の積率母関数による評価の方法は H. Chernoff、有界な独立和の評価は W. Hoeffding、マルチンゲールへの拡張は吾妻一興(Kazuoki Azuma)、有界差の不等式は C. McDiarmid の名で呼ばれる。吾妻の論文は、有界なマルチンゲール差の重みつき和の積率母関数を、凸性の不等式 $e^{\lambda x}\le\cosh\lambda+x\sinh\lambda$($\lvert x\rvert\le1$)から評価している(Az67 Lemma 1、pp. 357–358)。
Bernstein の不等式($\lvert X_i\rvert\le K$、平均 $0$ の形)と有界差の不等式($S_i=\mathbb{R}$ の形)の主張は Ver18 Theorem 2.8.4(p. 38)、Theorem 2.9.1(p. 39)にある。前者の証明は同書の Exercise 2.8.5・2.8.6(p. 38)の方針($e^z$ の級数の評価)による。thm-ci-martingale の形での整理と、thm-ci-mcdiarmid の Fubini の定理による証明はこの記事の組み立てである。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する