McDiarmidの不等式(McDiarmid's inequality)とは、独立な確率変数 $X_1,\dots,X_n$ の可測関数 $f$ について、$i$ 番目の変数だけを取り替えたときの $f$ の変化が常に $c_i$ 以下なら、$t>0$ について $P(f(X)-E[f(X)]\ge t)\le\exp(-2t^2/\sum_ic_i^2)$ が成り立つという濃度不等式で、有界差の不等式とも呼ばれる。Doob のマルチンゲールの各増分が過去を固定すると幅 $c_i$ の区間に値をとることに Hoeffding の補題を当てて証明され、和の場合は Hoeffding の不等式に一致する。分散も $\sum_ic_i^2/4$ 以下で、ランダムグラフの彩色数、最長共通部分列、経験分布の一様な偏差の集中に使われる。
前提知識: Hoeffdingの不等式, マルチンゲール, 条件付き期待値
McDiarmid の不等式(McDiarmid's inequality)は、独立な確率変数 $X_1,\dots,X_n$ の関数 $f(X_1,\dots,X_n)$ について、$i$ 番目の変数だけを取り替えたときの $f$ の変化が定数 $c_i$ 以下なら
$$
P\bigl(f(X)-E[f(X)]\ge t\bigr)\le\exp\Bigl(-\frac{2t^2}{\sum_{i=1}^nc_i^2}\Bigr)\qquad(t>0)
$$
が成り立つ、という濃度不等式である。有界差の不等式(bounded differences inequality)とも呼ばれる。
$f$ が和 $\sum_iX_i$ で $X_i$ が幅 $c_i$ の区間に値をとるときは、これは Hoeffdingの不等式 そのものである。McDiarmid の不等式の要点は、$f$ が和でなくてもよいことにある。ランダムグラフの彩色数、2 つのランダムな文字列の最長共通部分列の長さ、経験分布の一様な偏差のように、平均の値は分からなくても、各変数への依存が小さい量は平均のまわりの幅 $O(\sqrt n)$ に集中する。証明は、情報を 1 つずつ明かしていく Doob のマルチンゲールに、Hoeffding の不等式の証明の方法を当てる。
この記事では、主定理(thm-mcd-main)を完全に証明し、分散の評価(prop-mcd-variance)と指数の係数の最良性を述べる。続いて、彩色数・最長共通部分列・一様な偏差の例を計算し、仮定を外すと結論が成り立たないことを反例で示す。
$(S_1,\mathcal S_1),\dots,(S_n,\mathcal S_n)$ を可測空間とし、$S:=S_1\times\cdots\times S_n$ に積 $\sigma$-代数を入れる。$x=(x_1,\dots,x_n)\in S$、$y\in S_i$ について、$x$ の $i$ 番目の座標だけを $y$ に替えた点を $x^{(i,y)}$ と書く。
$c_1,\dots,c_n\ge0$ とする。可測関数 $f\colon S\to\mathbb{R}$ が 定数 $(c_1,\dots,c_n)$ の有界差の性質 をもつとは、すべての $i$、すべての $x\in S$、$y\in S_i$ について
$$
\bigl|f(x)-f(x^{(i,y)})\bigr|\le c_i
$$
が成り立つことをいう。
言い換えると、$f$ は重みつき Hamming 距離 $d_c(x,x'):=\sum_{i:x_i\ne x_i'}c_i$ について Lipschitz 定数 $1$ である。実際、$x$ から $x'$ へ異なる座標を 1 つずつ取り替えると、$|f(x)-f(x')|\le d_c(x,x')$ となる。とくに $f$ は有界で、$\sup f-\inf f\le\sum_ic_i$ である。
$X_1,\dots,X_n$ を独立な確率変数とし、$X_i$ は $S_i$ に値をとるとする。$f\colon S\to\mathbb{R}$ が定数 $(c_1,\dots,c_n)$ の有界差の性質をもち、$\sum_ic_i^2>0$ とする。$X:=(X_1,\dots,X_n)$ とおくと、すべての $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),\qquad P\bigl(|f(X)-E[f(X)]|\ge t\bigr)\le2\exp\Bigl(-\frac{2t^2}{\sum_{i=1}^nc_i^2}\Bigr)
$$
である。
証明には、平均 $0$ で区間 $[a,b]$ に値をとる確率変数 $Z$ について $E[e^{\lambda Z}]\le e^{\lambda^2(b-a)^2/8}$($\lambda\in\mathbb{R}$)となること(Hoeffdingの不等式 の補題「Hoeffding の補題」)を使う。
条件付き期待値を積分で書く。 $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)$ とおくと、独立性から $(X_1,\dots,X_n)$ の分布は $\mu_1\otimes\cdots\otimes\mu_n$ なので、$\mathcal F_k$ の事象 $\{(X_1,\dots,X_k)\in B\}$ の上の $f(X)$ の積分を Fubini の定理で $x_{k+1},\dots,x_n$ について先に積分すると、それは $g_k(X_1,\dots,X_k)$ の同じ事象の上の積分に等しい。よって
$$
M_k:=E[f(X)\mid\mathcal F_k]=g_k(X_1,\dots,X_k)
$$
であり、$M_0=E[f(X)]$、$M_n=f(X)$ である。$(M_k)$ は $(\mathcal F_k)$ に関する マルチンゲール(Doob のマルチンゲール)である。
増分のとる値の幅。 $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)$ である。$x_{< k}$ と $y,y'\in S_k$ を固定すると、有界差の性質を残りの座標について積分して
$$
\bigl|g_k(x_{< k},y)-g_k(x_{< k},y')\bigr|\le\int\bigl|f(x_{< k},y,u)-f(x_{< k},y',u)\bigr|\,d(\mu_{k+1}\otimes\cdots\otimes\mu_n)(u)\le c_k
$$
である。よって $a(x_{< k}):=\inf_{y\in S_k}g_k(x_{< k},y)-g_{k-1}(x_{< k})$ とおくと、$Y\sim\mu_k$ について確率変数 $Z:=g_k(x_{< k},Y)-g_{k-1}(x_{< k})$ は平均 $0$ で、区間 $[a(x_{< k}),a(x_{< k})+c_k]$ に値をとる。
条件付きの積率母関数。 $\lambda\in\mathbb{R}$ を固定する。独立性と 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)
$$
である(右辺が $\mathcal F_{k-1}$-可測で、$\mathcal F_{k-1}$ の事象の上の積分が一致することを、$x_k$ について先に積分して確かめる)。Hoeffding の補題を $Z$ に当てると、すべての $x_{< k}$ で $\Psi(x_{< k})=E[e^{\lambda Z}]\le e^{\lambda^2c_k^2/8}$ である。
積に分けて Chernoff の方法。 $\lambda>0$ とする。$e^{\lambda(M_{k-1}-M_0)}$ は非負で $\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^2c_k^2/8}E\bigl[e^{\lambda(M_{k-1}-M_0)}\bigr]
$$
である。$k=n,n-1,\dots,1$ と繰り返すと $E[e^{\lambda(f(X)-E[f(X)])}]\le\exp(\lambda^2\sum_kc_k^2/8)$ となる。Markovの不等式 から
$$
P\bigl(f(X)-E[f(X)]\ge t\bigr)\le e^{-\lambda t}E\bigl[e^{\lambda(f(X)-E[f(X)])}\bigr]\le\exp\Bigl(-\lambda t+\frac{\lambda^2}8\sum_kc_k^2\Bigr)
$$
で、$\lambda:=4t/\sum_kc_k^2$ とおくと右辺は $\exp(-2t^2/\sum_kc_k^2)$ である。$-f$ も同じ定数の有界差の性質をもつので下側も同じ評価になり、2 つを足して両側の評価を得る。$\square$
主張は Ver18 Theorem 2.9.1(p. 39、$S_i$ が一般の集合でよいことは同頁の脚注 10)にあり、Hoeffding の不等式と同じ積率母関数の方法で証明できることが同書 p. 40 に述べられている。上の証明は、増分 $D_k$ そのものが小さいことではなく、過去を固定したときに $D_k$ がとる値の幅 が $c_k$ 以下であることを使う。$|D_k|\le c_k$ だけを使う吾妻の不等式(Hoeffdingの不等式 の定理「吾妻の不等式」)では指数が $t^2/(2\sum_kc_k^2)$ になり、4 倍悪い。
右辺を $\delta$ とおいて解くと、確率 $1-\delta$ 以上で
$$
f(X)< E[f(X)]+\sqrt{\tfrac12\textstyle\sum_ic_i^2\log(1/\delta)}
$$
である。この形が、統計的学習理論の汎化誤差の評価でよく使われる(Rademacher複雑度 の定理「一様な偏差の上界」)。
同じマルチンゲールの分解から、分散も抑えられる。
thm-mcd-main の仮定のもとで $\operatorname{Var}(f(X))\le\frac14\sum_{i=1}^nc_i^2$ である。
$k< l$ なら $E[D_kD_l]=E\bigl[D_kE[D_l\mid\mathcal F_{l-1}]\bigr]=0$ なので、$\operatorname{Var}(f(X))=E[(\sum_kD_k)^2]=\sum_kE[D_k^2]$ である。prf-mcd-main の記号で、平均 $0$ で長さ $c_k$ の区間 $[a,a+c_k]$ に値をとる $Z$ について $E[Z^2]=E[(Z-a-\frac{c_k}2)^2]-(a+\frac{c_k}2)^2\le c_k^2/4$ なので、Fubini の定理から $E[D_k^2\mid\mathcal F_{k-1}]\le c_k^2/4$、$E[D_k^2]\le c_k^2/4$ である。$\square$
thm-mcd-main の右辺は、分散 $\sigma^2:=\frac14\sum_ic_i^2$ の正規分布の裾の評価 $e^{-t^2/(2\sigma^2)}$ と同じ形である。指数の係数 $2$ は、仮定だけから導ける評価としては大きくできない。実際、独立に $\pm1$ を確率 $\frac12$ ずつとる $X_i$ の和 $f(x)=\sum_ix_i$ は $c_i=2$ の有界差の性質をもち、thm-mcd-main の右辺は $e^{-t^2/(2n)}$ である。これは区間 $[-1,1]$ に値をとる独立和の Hoeffding の不等式と同じ評価で、Hoeffdingの不等式 の命題「指数の係数の最良性」により、$e^{-ct^2/(4n)}$($c>2$)に置き換えると、ある $n$ と $t$ で成り立たない。分散が $\frac14\sum c_i^2$ よりずっと小さい関数では、thm-mcd-main は粗い評価になる(ex-mcd-lcs)。
$0< p< 1$ とし、頂点 $1,\dots,n$ の各辺を独立に確率 $p$ で張ったランダムグラフ $G$(Erdős–Rényiのランダムグラフ)の 彩色数 $\chi(G)$ を考える。$i=2,\dots,n$ について、頂点 $i$ とそれより前の頂点を結ぶ辺の有無の組を $X_i:=(\mathbf 1_{\{j,i\}\in E})_{j< i}\in\{0,1\}^{i-1}$ とおく。辺は独立なので $X_2,\dots,X_n$ は独立で、$\chi(G)$ はその関数である。
$X_i$ だけが異なる 2 つのグラフ $G$、$G'$ は、頂点 $i$ を除いた $G-i=G'-i$ が等しい。$G$ の $\chi(G)$ 色の彩色を $G-i$ に制限し、頂点 $i$ に新しい色を塗ると $G'$ の彩色になるので $\chi(G')\le\chi(G)+1$ で、対称性から $|\chi(G)-\chi(G')|\le1$ である。よって $c_i=1$ で、thm-mcd-main から
$$
P\bigl(|\chi(G)-E[\chi(G)]|\ge t\bigr)\le2\exp\Bigl(-\frac{2t^2}{n-1}\Bigr)
$$
である。$E[\chi(G)]$ の値を知らなくても、$\chi(G)$ は幅 $O(\sqrt n)$ の範囲に集中する。たとえば $n=1000$、$t=100$ なら右辺は約 $4.0\times10^{-9}$ である。頂点を 1 つずつ明かすこの分け方は、各辺を 1 つの変数とする分け方(変数 $\binom n2$ 個)より評価が良い。
有限集合 $\mathcal A$ の文字を独立に一様に並べた長さ $n$ の文字列 $a$、$b$ について、最長共通部分列 の長さを $L(a,b)$ とする。$a$ の 1 文字を替えると、最長共通部分列からその位置を除いたものは新しい組の共通部分列なので $L$ は高々 $1$ しか減らず、対称性から $|\Delta L|\le1$ である。$b$ についても同じなので、$2n$ 個の変数で $c_i=1$ であり、
$$
P\bigl(|L-E[L]|\ge t\bigr)\le2e^{-t^2/n},\qquad\operatorname{Var}(L)\le\frac n2
$$
である。$\mathcal A=\{0,1\}$、$n=200$ で $500$ 組を乱数で生成して(種 $20261105$)$L$ を計算すると、平均は約 $158.7$、標準偏差は約 $2.85$ で、prop-mcd-variance の上界 $\sqrt{n/2}=10$ より小さかった。$t=30$ の右辺は $2e^{-4.5}\approx0.022$ で、標本の中に平均から $30$ 以上離れたものはなかった。評価は正しいが、この関数では粗い。
ex-mcd-examples-property の 3 の $f$ は $c_i=1/n$ なので、$P(f(X)-E[f(X)]\ge t)\le e^{-2nt^2}$ である。$E[f(X)]$ を対称化で抑えると、$\mathcal F$ の Rademacher 複雑度による一様な大数の法則の評価が得られる(Rademacher複雑度 の定理「一様な偏差の上界」)。$\mathcal F$ が 1 つの関数だけなら、これは標本平均の Hoeffding の不等式である。
各行は thm-mcd-main の仮定を 1 つだけ外し、上側の不等式そのものが成り立たないことを示す。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| 独立性 | $\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$ 未満) |
| 有界差($c_i$ が有限であること) | $n=1$、$X_1$ は平均 $1$ の指数分布、$f(x)=x$ | どの $c_1$ についても、$t$ が大きいと $P(f-1\ge t)=e^{-1-t}$ が $e^{-2t^2/c_1^2}$ を上回る |
| 有界差がすべての点の組で成り立つこと | $X_i$ は独立に確率 $\frac12$ ずつで $0,1$、$f(x)=2^n\mathbf 1_{\{x=(1,\dots,1)\}}$、$c_i=1$ とおく | $P(f-1\ge n)=2^{-n}$ だが右辺は $e^{-2n}< 2^{-n}$ |
1 行目:$f(X)=n\xi$ で $E[f]=\frac n2$、$P(f-\frac n2\ge\frac n2)=P(\xi=1)=\frac12$ である。$f$ は $c_i=1$ の有界差の性質をもち、外したのは独立性だけである。右辺は $e^{-2(n/2)^2/n}=e^{-n/2}$ である。
2 行目:$f$ は非有界なので、どの有限の $c_1$ でも有界差の性質をもたない。$P(X_1-1\ge t)=e^{-1-t}$ で、$t>\max(1,c_1^2)$ なら $2t^2/c_1^2>2t> 1+t$ なので右辺 $e^{-2t^2/c_1^2}$ を上回る。
3 行目:$f$ の値が変わるのは、一方が $(1,\dots,1)$ である点の組だけで、そこでは差が $2^n$ である。それ以外のすべての組で差は $0\le c_i$ である。つまり有界差の不等式が成り立たないのは、$(1,\dots,1)$ とそれから 1 座標だけ異なる $n$ 点との組だけで($X$ がこの $n+1$ 点のどれかになる確率は $(n+1)2^{-n}$)、外した仮定は有界差の性質だけである。$E[f]=2^n\cdot2^{-n}=1$、$n\le2^n-1$ なので $P(f-1\ge n)=P(f=2^n)=2^{-n}$ で、$\sum_ic_i^2=n$ から右辺は $e^{-2n^2/n}=e^{-2n}< 2^{-n}$ である。
有界な独立変数の和の評価は W. Hoeffding、増分が有界なマルチンゲールへの拡張は吾妻一興による。それを独立な変数の一般の関数に当てる有界差の方法は、C. McDiarmid の名で呼ばれる。濃度不等式 の記事は、条件付き劣 Gauss の増分をもつマルチンゲールの評価を先に示し、その系としてこの不等式を導いている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する