0. イントロ
確率論や統計学では、ランダムな量そのものよりも、
そのランダムな量が、典型的な値からどの程度ずれるのか
を知りたい場面が頻繁に現れます。
例えば、独立なデータ X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
X ˉ n : = 1 n ∑ i = 1 n X i \bar X_n := \frac{1}{n}\sum_{i=1}^n X_i X ˉ n := n 1 i = 1 ∑ n X i を考えます。
大数の法則は、適切な仮定のもとで
X ˉ n → E X 1 \bar X_n \to \mathbb{E}X_1 X ˉ n → E X 1 と収束することを教えてくれます。しかし、実際の統計解析や機械学習では n n n
そこで知りたいのは、
Pr ( ∣ X ˉ n − E X 1 ∣ ≥ ε ) \Pr\left(
\left|\bar X_n-\mathbb{E}X_1\right|
\ge \varepsilon
\right) Pr ( X ˉ n − E X 1 ≥ ε ) が具体的にどれくらい小さいか、ということです。
このような有限標本における確率的なずれを定量的に評価する道具 が、集中不等式（Concentration Inequality）です。
集中不等式には多くの種類がありますが、本記事では次の流れで基本的なものを整理します。
Markov の不等式 ：非負性と期待値だけを使うChebyshev の不等式 ：分散まで使うChernoff 法 ：指数変換によって指数的な評価を作るHoeffding の不等式 ：独立かつ有界な確率変数の和を扱うBernstein の不等式 ：分散も利用して Hoeffding を精密化するMcDiarmid の不等式 ：和に限らず、独立変数の安定な関数を扱う
これらは単純に「後に出てくるほど強い」という関係ではありません。それぞれが利用する仮定と、扱える対象が異なります。
1. 集中不等式を読むための基本事項
まず、本記事で繰り返し現れる記法を整理しておきます。
確率変数 X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
S n : = ∑ i = 1 n X i S_n := \sum_{i=1}^n X_i S n := i = 1 ∑ n X i とし、標本平均を
X ˉ n : = S n n \bar X_n := \frac{S_n}{n} X ˉ n := n S n と書きます。
また、
X ≥ 0 almost surely X\ge 0 \quad \text{almost surely} X ≥ 0 almost surely とは、「確率 1 1 1 X ≥ 0 X\ge 0 X ≥ 0 a.s. と略記することがあります。
上側・下側・両側確率
集中不等式では、主に次の 3 種類の確率を扱います。
上側偏差：
Pr ( X − E X ≥ t ) \Pr(X-\mathbb{E}X\ge t) Pr ( X − E X ≥ t ) 下側偏差：
Pr ( X − E X ≤ − t ) \Pr(X-\mathbb{E}X\le -t) Pr ( X − E X ≤ − t ) 両側偏差：
Pr ( ∣ X − E X ∣ ≥ t ) \Pr(|X-\mathbb{E}X|\ge t) Pr ( ∣ X − E X ∣ ≥ t ) 上側と下側の評価が得られれば、和事象に対する
Pr ( A ∪ B ) ≤ Pr ( A ) + Pr ( B ) \Pr(A\cup B)\le \Pr(A)+\Pr(B) Pr ( A ∪ B ) ≤ Pr ( A ) + Pr ( B ) という union bound によって、両側評価を作ることができます。そのため、両側版ではしばしば前に係数 2 2 2
2. Markov の不等式：すべての出発点
最も基本的な tail bound が Markov の不等式です。
定理
X X X
X ≥ 0 a.s. , E X < ∞ X\ge 0 \quad \text{a.s.},
\qquad
\mathbb{E}X<\infty X ≥ 0 a.s. , E X < ∞ とします。
このとき、任意の a > 0 a>0 a > 0
Pr ( X ≥ a ) ≤ E X a \Pr(X\ge a)
\le
\frac{\mathbb{E}X}{a} Pr ( X ≥ a ) ≤ a E X が成り立ちます。
証明
事象 X ≥ a {X\ge a} X ≥ a 1 X ≥ a \mathbf{1}_{{X\ge a}} 1 X ≥ a
X ≥ a 1 { X ≥ a } X
\ge
a\mathbf{1}_{\{X\ge a\}} X ≥ a 1 { X ≥ a } です。
両辺の期待値を取れば、
E X ≥ a E 1 { X ≥ a } = a Pr ( X ≥ a ) \mathbb{E}X
\ge
a\mathbb{E}\mathbf{1}_{\{X\ge a\}}
=
a\Pr(X\ge a) E X ≥ a E 1 { X ≥ a } = a Pr ( X ≥ a ) となるので、
Pr ( X ≥ a ) ≤ E X a \Pr(X\ge a)
\le
\frac{\mathbb{E}X}{a} Pr ( X ≥ a ) ≤ a E X を得ます。
Markov の不等式は何を言っているのか
例えば a = c E X a=c\mathbb{E}X a = c E X
Pr ( X ≥ c E X ) ≤ 1 c \Pr(X\ge c\mathbb{E}X)
\le
\frac{1}{c} Pr ( X ≥ c E X ) ≤ c 1 です。
つまり、非負確率変数が平均の 10 10 10 1 / 10 1/10 1/10 100 100 100 1 / 100 1/100 1/100
仮定が極めて弱い代わりに、評価も一般には粗くなります。
高次モーメントを使う
Markov の不等式は X X X
例えば E ∣ X ∣ p < ∞ \mathbb{E}|X|^p<\infty E ∣ X ∣ p < ∞ ∣ X ∣ p |X|^p ∣ X ∣ p
Pr ( ∣ X ∣ ≥ t ) = Pr ( ∣ X ∣ p ≥ t p ) ≤ E ∣ X ∣ p t p \Pr(|X|\ge t)
=
\Pr(|X|^p\ge t^p)
\le
\frac{\mathbb{E}|X|^p}{t^p} Pr ( ∣ X ∣ ≥ t ) = Pr ( ∣ X ∣ p ≥ t p ) ≤ t p E ∣ X ∣ p を得ます。
この「扱いたい事象を、別の非負確率変数に変換して Markov を適用する 」という考え方は極めて重要です。
Chebyshev の不等式も Chernoff bound も、本質的にはこの発想から生まれます。
3. Chebyshev の不等式：分散から平均周辺への集中を見る
Markov が期待値だけを使ったのに対して、Chebyshev の不等式は分散を使います。
定理
X X X
μ : = E X \mu := \mathbb{E}X μ := E X と有限な分散
σ 2 : = Var ( X ) < ∞ \sigma^2 := \operatorname{Var}(X)<\infty σ 2 := Var ( X ) < ∞ を持つとします。
このとき、任意の t > 0 t>0 t > 0
Pr ( ∣ X − μ ∣ ≥ t ) ≤ σ 2 t 2 \Pr(|X-\mu|\ge t)
\le
\frac{\sigma^2}{t^2} Pr ( ∣ X − μ ∣ ≥ t ) ≤ t 2 σ 2 が成り立ちます。
特に σ > 0 \sigma>0 σ > 0 t = k σ t=k\sigma t = k σ
Pr ( ∣ X − μ ∣ ≥ k σ ) ≤ 1 k 2 \Pr(|X-\mu|\ge k\sigma)
\le
\frac{1}{k^2} Pr ( ∣ X − μ ∣ ≥ k σ ) ≤ k 2 1 です。
Markov からの導出
非負確率変数
Y : = ( X − μ ) 2 Y := (X-\mu)^2 Y := ( X − μ ) 2 を考えます。
すると
Pr ( ∣ X − μ ∣ ≥ t ) = Pr ( ( X − μ ) 2 ≥ t 2 ) ≤ E ( X − μ ) 2 t 2 = σ 2 t 2 . \begin{aligned}
\Pr(|X-\mu|\ge t)
&=
\Pr((X-\mu)^2\ge t^2)\\
&\le
\frac{\mathbb{E}(X-\mu)^2}{t^2}\\
&=
\frac{\sigma^2}{t^2}.
\end{aligned} Pr ( ∣ X − μ ∣ ≥ t ) = Pr (( X − μ ) 2 ≥ t 2 ) ≤ t 2 E ( X − μ ) 2 = t 2 σ 2 . したがって、Chebyshev の不等式は Markov の不等式を二乗偏差に適用したものだと理解できます。
標本平均への適用
X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
E X i = μ , Var ( X i ) = σ 2 \mathbb{E}X_i=\mu,
\qquad
\operatorname{Var}(X_i)=\sigma^2 E X i = μ , Var ( X i ) = σ 2 とします。
独立性から
Var ( X ˉ n ) = σ 2 n \operatorname{Var}(\bar X_n)
=
\frac{\sigma^2}{n} Var ( X ˉ n ) = n σ 2 なので、Chebyshev の不等式より
Pr ( ∣ X ˉ n − μ ∣ ≥ ε ) ≤ σ 2 n ε 2 \Pr(|\bar X_n-\mu|\ge \varepsilon)
\le
\frac{\sigma^2}{n\varepsilon^2} Pr ( ∣ X ˉ n − μ ∣ ≥ ε ) ≤ n ε 2 σ 2 を得ます。
ここで重要なのは、n n n
O ( 1 n ) O\left(\frac{1}{n}\right) O ( n 1 ) で減少することです。
ただし、これは後で見る Hoeffding の
exp ( − c n ) \exp(-cn) exp ( − c n ) 型の評価と比べるとかなり遅い減衰です。
4. Chernoff 法：指数的集中を作る基本原理
Markov や Chebyshev では、多項式的な tail bound しか得られませんでした。
指数的に小さな確率を得るための中心的なアイデアが Chernoff 法（Chernoff method） です。
Chernoff bound という名前は特定の公式を指して使われることもありますが、より本質的には、
指数関数で確率変数を変換し、Markov の不等式を適用して、その指数パラメータを最適化する方法
だと考えると理解しやすくなります。
一般形
確率変数 X X X
ψ X ( λ ) : = log E exp ( λ ( X − E X ) ) \psi_X(\lambda)
:=
\log
\mathbb{E}
\exp\left(
\lambda(X-\mathbb{E}X)
\right) ψ X ( λ ) := log E exp ( λ ( X − E X ) ) を中心化された log moment generating function（log-MGF）とします。
λ > 0 \lambda>0 λ > 0
Pr ( X − E X ≥ t ) = Pr ( e λ ( X − E X ) ≥ e λ t ) ≤ e − λ t E e λ ( X − E X ) = exp ( − λ t + ψ X ( λ ) ) . \begin{aligned}
\Pr(X-\mathbb{E}X\ge t)
&=
\Pr\left(
e^{\lambda(X-\mathbb{E}X)}
\ge
e^{\lambda t}
\right)\\
&\le
e^{-\lambda t}
\mathbb{E}
e^{\lambda(X-\mathbb{E}X)}\\
&=
\exp\left(
-\lambda t+\psi_X(\lambda)
\right).
\end{aligned} Pr ( X − E X ≥ t ) = Pr ( e λ ( X − E X ) ≥ e λ t ) ≤ e − λ t E e λ ( X − E X ) = exp ( − λ t + ψ X ( λ ) ) . これは任意の許される λ > 0 \lambda>0 λ > 0
Pr ( X − E X ≥ t ) ≤ inf λ > 0 exp ( − λ t + ψ X ( λ ) ) \Pr(X-\mathbb{E}X\ge t)
\le
\inf_{\lambda>0}
\exp\left(
-\lambda t+\psi_X(\lambda)
\right) Pr ( X − E X ≥ t ) ≤ λ > 0 inf exp ( − λ t + ψ X ( λ ) ) です。
同値に、
Pr ( X − E X ≥ t ) ≤ exp ( − sup λ > 0 { λ t − ψ X ( λ ) } ) \Pr(X-\mathbb{E}X\ge t)
\le
\exp\left(
-
\sup_{\lambda>0}
\left\{
\lambda t-\psi_X(\lambda)
\right\}
\right) Pr ( X − E X ≥ t ) ≤ exp ( − λ > 0 sup { λ t − ψ X ( λ ) } ) と書けます。
この λ \lambda λ
なぜ指数的な評価になるのか
指数関数には、独立な確率変数の和を積に変換できるという重要な性質があります。
独立な X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
E exp ( λ ∑ i = 1 n X i ) = E ∏ i = 1 n e λ X i = ∏ i = 1 n E e λ X i . \begin{aligned}
\mathbb{E}
\exp\left(
\lambda\sum_{i=1}^n X_i
\right)
&=
\mathbb{E}
\prod_{i=1}^n e^{\lambda X_i}\\
&=
\prod_{i=1}^n
\mathbb{E}e^{\lambda X_i}.
\end{aligned} E exp ( λ i = 1 ∑ n X i ) = E i = 1 ∏ n e λ X i = i = 1 ∏ n E e λ X i . したがって、各変数の MGF を制御できれば、その和の MGF も簡単に制御できます。
これが Hoeffding や Bernstein など多くの指数型集中不等式の基本原理です。
sub-Gaussian という共通パターン
もし中心化確率変数 X − E X X-\mathbb{E}X X − E X λ ∈ R \lambda\in\mathbb{R} λ ∈ R
E e λ ( X − E X ) ≤ exp ( σ 2 λ 2 2 ) \mathbb{E}
e^{\lambda(X-\mathbb{E}X)}
\le
\exp\left(
\frac{\sigma^2\lambda^2}{2}
\right) E e λ ( X − E X ) ≤ exp ( 2 σ 2 λ 2 ) を満たすなら、Chernoff 法から
Pr ( X − E X ≥ t ) ≤ exp ( − t 2 2 σ 2 ) \Pr(X-\mathbb{E}X\ge t)
\le
\exp\left(
-\frac{t^2}{2\sigma^2}
\right) Pr ( X − E X ≥ t ) ≤ exp ( − 2 σ 2 t 2 ) を得ます。
同様に下側も評価できるため、
Pr ( ∣ X − E X ∣ ≥ t ) ≤ 2 exp ( − t 2 2 σ 2 ) \Pr(|X-\mathbb{E}X|\ge t)
\le
2\exp\left(
-\frac{t^2}{2\sigma^2}
\right) Pr ( ∣ X − E X ∣ ≥ t ) ≤ 2 exp ( − 2 σ 2 t 2 ) です。
このように Gaussian 分布と同程度の tail を持つ確率変数を sub-Gaussian と呼びます。
Hoeffding の不等式は、「有界な確率変数は適切な意味で sub-Gaussian である」という事実を利用したものと見ることができます。
Bernoulli 和に対する multiplicative Chernoff bound
Chernoff bound という言葉は、特に Bernoulli 確率変数の和に対する次の評価を指すこともあります。
独立な
X i ∈ { 0 , 1 } X_i\in\{0,1\} X i ∈ { 0 , 1 } に対して
S n : = ∑ i = 1 n X i , μ : = E S n S_n:=\sum_{i=1}^n X_i,
\qquad
\mu:=\mathbb{E}S_n S n := i = 1 ∑ n X i , μ := E S n とします。
任意の δ > 0 \delta>0 δ > 0
Pr ( S n ≥ ( 1 + δ ) μ ) ≤ ( e δ ( 1 + δ ) 1 + δ ) μ \Pr(S_n\ge (1+\delta)\mu)
\le
\left(
\frac{e^\delta}{(1+\delta)^{1+\delta}}
\right)^\mu Pr ( S n ≥ ( 1 + δ ) μ ) ≤ ( ( 1 + δ ) 1 + δ e δ ) μ であり、より扱いやすい形として
Pr ( S n ≥ ( 1 + δ ) μ ) ≤ exp ( − δ 2 2 + δ μ ) \Pr(S_n\ge (1+\delta)\mu)
\le
\exp\left(
-\frac{\delta^2}{2+\delta}\mu
\right) Pr ( S n ≥ ( 1 + δ ) μ ) ≤ exp ( − 2 + δ δ 2 μ ) が得られます。
また 0 < δ < 1 0<\delta<1 0 < δ < 1
Pr ( S n ≤ ( 1 − δ ) μ ) ≤ exp ( − δ 2 2 μ ) \Pr(S_n\le (1-\delta)\mu)
\le
\exp\left(
-\frac{\delta^2}{2}\mu
\right) Pr ( S n ≤ ( 1 − δ ) μ ) ≤ exp ( − 2 δ 2 μ ) です。
Hoeffding が「平均からの加法的な誤差 」を扱うのに対して、この形の Chernoff bound は「期待値に対する相対誤差 」を扱う場面で特に便利です。
5. Hoeffding の不等式：有界性から指数的集中を得る
X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
Hoeffding's lemma
まず、Hoeffding の不等式の核となる補題を見ます。
確率変数 X X X
a ≤ X ≤ b a.s. a\le X\le b
\quad\text{a.s.} a ≤ X ≤ b a.s. を満たすとき、任意の λ ∈ R \lambda\in\mathbb{R} λ ∈ R
E e λ ( X − E X ) ≤ exp ( λ 2 ( b − a ) 2 8 ) \mathbb{E}
e^{\lambda(X-\mathbb{E}X)}
\le
\exp\left(
\frac{\lambda^2(b-a)^2}{8}
\right) E e λ ( X − E X ) ≤ exp ( 8 λ 2 ( b − a ) 2 ) が成り立ちます。
つまり、有界な確率変数はその分布の細かな形にかかわらず sub-Gaussian 的な MGF を持ちます。
定理
X 1 , … , X n X_1,\dots,X_n X 1 , … , X n i i i
a i ≤ X i ≤ b i a.s. a_i\le X_i\le b_i
\quad\text{a.s.} a i ≤ X i ≤ b i a.s. とします。
S n : = ∑ i = 1 n X i S_n:=\sum_{i=1}^n X_i S n := i = 1 ∑ n X i とすると、任意の t > 0 t>0 t > 0
Pr ( S n − E S n ≥ t ) ≤ exp ( − 2 t 2 ∑ i = 1 n ( b i − a i ) 2 ) \Pr(S_n-\mathbb{E}S_n\ge t)
\le
\exp\left(
-\frac{2t^2}
{\sum_{i=1}^n(b_i-a_i)^2}
\right) Pr ( S n − E S n ≥ t ) ≤ exp ( − ∑ i = 1 n ( b i − a i ) 2 2 t 2 ) が成り立ちます。
さらに両側版として、
Pr ( ∣ S n − E S n ∣ ≥ t ) ≤ 2 exp ( − 2 t 2 ∑ i = 1 n ( b i − a i ) 2 ) \Pr(|S_n-\mathbb{E}S_n|\ge t)
\le
2\exp\left(
-\frac{2t^2}
{\sum_{i=1}^n(b_i-a_i)^2}
\right) Pr ( ∣ S n − E S n ∣ ≥ t ) ≤ 2 exp ( − ∑ i = 1 n ( b i − a i ) 2 2 t 2 ) が成り立ちます。
Chernoff 法からの導出
Hoeffding's lemma と独立性を使うと、
E e λ ( S n − E S n ) = ∏ i = 1 n E e λ ( X i − E X i ) ≤ exp ( λ 2 8 ∑ i = 1 n ( b i − a i ) 2 ) . \begin{aligned}
\mathbb{E}
e^{\lambda(S_n-\mathbb{E}S_n)}
&=
\prod_{i=1}^n
\mathbb{E}
e^{\lambda(X_i-\mathbb{E}X_i)}\\
&\le
\exp\left(
\frac{\lambda^2}{8}
\sum_{i=1}^n(b_i-a_i)^2
\right).
\end{aligned} E e λ ( S n − E S n ) = i = 1 ∏ n E e λ ( X i − E X i ) ≤ exp ( 8 λ 2 i = 1 ∑ n ( b i − a i ) 2 ) . ここで
A : = ∑ i = 1 n ( b i − a i ) 2 A:=
\sum_{i=1}^n(b_i-a_i)^2 A := i = 1 ∑ n ( b i − a i ) 2 と置くと、Chernoff 法より
Pr ( S n − E S n ≥ t ) ≤ exp ( − λ t + λ 2 A 8 ) . \Pr(S_n-\mathbb{E}S_n\ge t)
\le
\exp\left(
-\lambda t+\frac{\lambda^2A}{8}
\right). Pr ( S n − E S n ≥ t ) ≤ exp ( − λ t + 8 λ 2 A ) . 右辺を λ \lambda λ
λ ∗ = 4 t A \lambda^\ast=\frac{4t}{A} λ ∗ = A 4 t なので、
Pr ( S n − E S n ≥ t ) ≤ exp ( − 2 t 2 A ) \Pr(S_n-\mathbb{E}S_n\ge t)
\le
\exp\left(
-\frac{2t^2}{A}
\right) Pr ( S n − E S n ≥ t ) ≤ exp ( − A 2 t 2 ) を得ます。
この導出を見ると、
Markov → \rightarrow → → \rightarrow → → \rightarrow →
という関係が明確になります。
標本平均への適用
特に X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
X i ∈ [ a , b ] a.s. X_i\in[a,b]
\quad\text{a.s.} X i ∈ [ a , b ] a.s. とします。
標本平均
X ˉ n = 1 n ∑ i = 1 n X i \bar X_n=\frac1n\sum_{i=1}^nX_i X ˉ n = n 1 i = 1 ∑ n X i に対して t = n ε t=n\varepsilon t = n ε
Pr ( ∣ X ˉ n − E X 1 ∣ ≥ ε ) ≤ 2 exp ( − 2 n ε 2 ( b − a ) 2 ) \Pr(
|\bar X_n-\mathbb{E}X_1|
\ge\varepsilon
)
\le
2\exp\left(
-\frac{2n\varepsilon^2}{(b-a)^2}
\right) Pr ( ∣ X ˉ n − E X 1 ∣ ≥ ε ) ≤ 2 exp ( − ( b − a ) 2 2 n ε 2 ) です。
Chebyshev の
O ( 1 n ) O\left(\frac1n\right) O ( n 1 ) という評価に対して、Hoeffding では
exp ( − c n ) \exp(-cn) exp ( − c n ) という指数的な減衰が得られています。
Bernoulli 推定の例
例えば
X i ∼ Bernoulli ( p ) X_i\sim\operatorname{Bernoulli}(p) X i ∼ Bernoulli ( p ) なら、
X i ∈ [ 0 , 1 ] , E X i = p X_i\in[0,1],
\qquad
\mathbb{E}X_i=p X i ∈ [ 0 , 1 ] , E X i = p です。
p ^ : = 1 n ∑ i = 1 n X i \hat p:=\frac1n\sum_{i=1}^nX_i p ^ := n 1 i = 1 ∑ n X i とすると、
Pr ( ∣ p ^ − p ∣ ≥ ε ) ≤ 2 e − 2 n ε 2 . \Pr(|\hat p-p|\ge\varepsilon)
\le
2e^{-2n\varepsilon^2}. Pr ( ∣ p ^ − p ∣ ≥ ε ) ≤ 2 e − 2 n ε 2 . したがって、失敗確率を δ \delta δ
2 e − 2 n ε 2 ≤ δ 2e^{-2n\varepsilon^2}\le\delta 2 e − 2 n ε 2 ≤ δ すなわち
n ≥ 1 2 ε 2 log 2 δ n
\ge
\frac{1}{2\varepsilon^2}
\log\frac{2}{\delta} n ≥ 2 ε 2 1 log δ 2 だけの標本数を取れば十分です。
同じ式を逆に解けば、確率少なくとも 1 − δ 1-\delta 1 − δ
∣ p ^ − p ∣ ≤ log ( 2 / δ ) 2 n |\hat p-p|
\le
\sqrt{
\frac{\log(2/\delta)}{2n}
} ∣ p ^ − p ∣ ≤ 2 n log ( 2/ δ ) という有限標本保証が得られます。
これが、集中不等式が統計学や機械学習で頻繁に使われる理由の一つです。
6. Bernstein の不等式：分散を利用してさらに精密に見る
Hoeffding の不等式は、各 X i X_i X i
しかし、実際には
「値域は広いが、ほとんどの場合は平均の近くにいる」
という確率変数もあります。
そのような場合には、分散の情報も使う Bernstein の不等式が有効です。
定理
X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
E X i = 0 \mathbb{E}X_i=0 E X i = 0 とします。
また、ある M > 0 M>0 M > 0
∣ X i ∣ ≤ M a.s. |X_i|\le M
\quad\text{a.s.} ∣ X i ∣ ≤ M a.s. がすべての i i i
和の分散を
v : = ∑ i = 1 n E X i 2 = ∑ i = 1 n Var ( X i ) v
:=
\sum_{i=1}^n\mathbb{E}X_i^2
=
\sum_{i=1}^n\operatorname{Var}(X_i) v := i = 1 ∑ n E X i 2 = i = 1 ∑ n Var ( X i ) とすると、任意の t > 0 t>0 t > 0
Pr ( ∑ i = 1 n X i ≥ t ) ≤ exp ( − t 2 2 ( v + M t / 3 ) ) \Pr\left(
\sum_{i=1}^nX_i\ge t
\right)
\le
\exp\left(
-\frac{t^2}{2(v+Mt/3)}
\right) Pr ( i = 1 ∑ n X i ≥ t ) ≤ exp ( − 2 ( v + M t /3 ) t 2 ) が成り立ちます。
両側版として、
Pr ( ∣ ∑ i = 1 n X i ∣ ≥ t ) ≤ 2 exp ( − t 2 2 ( v + M t / 3 ) ) \Pr\left(
\left|\sum_{i=1}^nX_i\right|\ge t
\right)
\le
2\exp\left(
-\frac{t^2}{2(v+Mt/3)}
\right) Pr ( i = 1 ∑ n X i ≥ t ) ≤ 2 exp ( − 2 ( v + M t /3 ) t 2 ) も得られます。
小偏差では Gaussian 型、大偏差では exponential 型
Bernstein の式で重要なのは、分母に
v + M t 3 v+\frac{Mt}{3} v + 3 M t という 2 種類の項が入っていることです。
t t t v v v
Pr ( ∑ i X i ≥ t ) ≈ exp ( − c t 2 v ) \Pr\left(
\sum_iX_i\ge t
\right)
\approx
\exp\left(
-c\frac{t^2}{v}
\right) Pr ( i ∑ X i ≥ t ) ≈ exp ( − c v t 2 ) という Gaussian 型、すなわち sub-Gaussian 的な減衰を示します。
一方、t t t M t Mt M t
Pr ( ∑ i X i ≥ t ) ≈ exp ( − c t M ) \Pr\left(
\sum_iX_i\ge t
\right)
\approx
\exp\left(
-c\frac{t}{M}
\right) Pr ( i ∑ X i ≥ t ) ≈ exp ( − c M t ) という exponential 型の減衰に移行します。
この
quadratic regime ⟶ linear regime \text{quadratic regime}
\quad\longrightarrow\quad
\text{linear regime} quadratic regime ⟶ linear regime という 2 つのスケールを持つのが Bernstein 型評価の特徴です。
標本平均への適用
独立同分布な X 1 , … , X n X_1,\dots,X_n X 1 , … , X n
E X i = μ , Var ( X i ) = σ 2 \mathbb{E}X_i=\mu,
\qquad
\operatorname{Var}(X_i)=\sigma^2 E X i = μ , Var ( X i ) = σ 2 かつ
∣ X i − μ ∣ ≤ M a.s. |X_i-\mu|\le M
\quad\text{a.s.} ∣ X i − μ ∣ ≤ M a.s. とします。
Z i : = X i − μ Z_i:=X_i-\mu Z i := X i − μ に Bernstein の不等式を適用すると、
Pr ( ∣ X ˉ n − μ ∣ ≥ ε ) ≤ 2 exp ( − n ε 2 2 ( σ 2 + M ε / 3 ) ) \Pr(
|\bar X_n-\mu|\ge\varepsilon
)
\le
2\exp\left(
-\frac{n\varepsilon^2}
{2(\sigma^2+M\varepsilon/3)}
\right) Pr ( ∣ X ˉ n − μ ∣ ≥ ε ) ≤ 2 exp ( − 2 ( σ 2 + M ε /3 ) n ε 2 ) となります。
Hoeffding は値域のみを見るのに対して、Bernstein では実際の分散 σ 2 \sigma^2 σ 2
そのため、分散が値域から想定される最大値よりかなり小さい場合には、Bernstein の方が大幅に鋭いことがあります。
7. McDiarmid の不等式：和ではなく「安定な関数」を集中させる
Hoeffding や Bernstein は主として確率変数の「和」を扱ってきました。
しかし、実際に興味を持つ統計量やアルゴリズムの出力は、必ずしも単純な和ではありません。
そこで使われる代表的な結果が McDiarmid の不等式 、別名 bounded differences inequality です。
有界差分条件
独立な確率変数
X 1 , … , X n X_1,\dots,X_n X 1 , … , X n と関数
f : X 1 × ⋯ × X n → R f:
\mathcal X_1\times\cdots\times\mathcal X_n
\to\mathbb{R} f : X 1 × ⋯ × X n → R を考えます。
各 i i i i i i x i x_i x i x i ′ x_i' x i ′
∣ f ( x 1 , … , x i , … , x n ) − f ( x 1 , … , x i ′ , … , x n ) ∣ ≤ c i \left|
f(x_1,\dots,x_i,\dots,x_n)
-
f(x_1,\dots,x_i',\dots,x_n)
\right|
\le c_i ∣ f ( x 1 , … , x i , … , x n ) − f ( x 1 , … , x i ′ , … , x n ) ∣ ≤ c i が常に成り立つとします。
この条件を bounded differences condition（有界差分条件） と呼びます。
直感的には、
1 個の入力だけを変更しても、出力は高々 c i c_i c i
という安定性を仮定しています。
定理
上の条件のもとで、任意の t > 0 t>0 t > 0
Pr ( f ( X 1 , … , X n ) − E f ( X 1 , … , X n ) ≥ t ) ≤ exp ( − 2 t 2 ∑ i = 1 n c i 2 ) \Pr\left(
f(X_1,\dots,X_n)
-
\mathbb{E}f(X_1,\dots,X_n)
\ge t
\right)
\le
\exp\left(
-\frac{2t^2}{\sum_{i=1}^nc_i^2}
\right) Pr ( f ( X 1 , … , X n ) − E f ( X 1 , … , X n ) ≥ t ) ≤ exp ( − ∑ i = 1 n c i 2 2 t 2 ) が成り立ちます。
同様に、
Pr ( ∣ f ( X 1 , … , X n ) − E f ( X 1 , … , X n ) ∣ ≥ t ) ≤ 2 exp ( − 2 t 2 ∑ i = 1 n c i 2 ) \Pr\left(
\left|
f(X_1,\dots,X_n)
-
\mathbb{E}f(X_1,\dots,X_n)
\right|
\ge t
\right)
\le
2\exp\left(
-\frac{2t^2}{\sum_{i=1}^nc_i^2}
\right) Pr ( ∣ f ( X 1 , … , X n ) − E f ( X 1 , … , X n ) ∣ ≥ t ) ≤ 2 exp ( − ∑ i = 1 n c i 2 2 t 2 ) です。
Hoeffding との関係
f f f
f ( x 1 , … , x n ) = ∑ i = 1 n x i f(x_1,\dots,x_n)
=
\sum_{i=1}^n x_i f ( x 1 , … , x n ) = i = 1 ∑ n x i で、各 x i x_i x i
x i ∈ [ a i , b i ] x_i\in[a_i,b_i] x i ∈ [ a i , b i ] を満たす場合を考えます。
i i i
c i = b i − a i c_i=b_i-a_i c i = b i − a i です。
したがって McDiarmid の不等式は、
Pr ( ∣ S n − E S n ∣ ≥ t ) ≤ 2 exp ( − 2 t 2 ∑ i ( b i − a i ) 2 ) \Pr(
|S_n-\mathbb{E}S_n|\ge t
)
\le
2\exp\left(
-\frac{2t^2}
{\sum_i(b_i-a_i)^2}
\right) Pr ( ∣ S n − E S n ∣ ≥ t ) ≤ 2 exp ( − ∑ i ( b i − a i ) 2 2 t 2 ) を与えます。
これはまさに Hoeffding の両側評価です。
この意味で McDiarmid の不等式は、
Hoeffding の「独立な有界確率変数の和」という構造を、「各入力に対して十分安定な一般の関数」へ拡張した結果
と見ることができます。
標本平均も有界差分関数である
例えば
f ( X 1 , … , X n ) = 1 n ∑ i = 1 n X i f(X_1,\dots,X_n)
=
\frac1n\sum_{i=1}^nX_i f ( X 1 , … , X n ) = n 1 i = 1 ∑ n X i で、
0 ≤ X i ≤ 1 0\le X_i\le1 0 ≤ X i ≤ 1 なら、1 個の入力を変更したときに f f f
c i = 1 n c_i=\frac1n c i = n 1 です。
したがって
∑ i = 1 n c i 2 = 1 n \sum_{i=1}^nc_i^2
=
\frac1n i = 1 ∑ n c i 2 = n 1 なので、
Pr ( ∣ f − E f ∣ ≥ t ) ≤ 2 e − 2 n t 2 \Pr(
|f-\mathbb{E}f|\ge t
)
\le
2e^{-2nt^2} Pr ( ∣ f − E f ∣ ≥ t ) ≤ 2 e − 2 n t 2 を得ます。
しかし McDiarmid の真価は、このような単純な平均ではなく、例えばランダムなデータセット全体から計算される複雑な統計量についても、
各サンプル 1 個が結果に与える影響が小さい
ことさえ証明できれば集中を導ける点にあります。
証明の考え方
McDiarmid の不等式の背景には martingale があります。
Z : = f ( X 1 , … , X n ) Z:=f(X_1,\dots,X_n) Z := f ( X 1 , … , X n ) として、
M i : = E [ Z ∣ X 1 , … , X i ] M_i
:=
\mathbb{E}
[
Z\mid X_1,\dots,X_i
] M i := E [ Z ∣ X 1 , … , X i ] を考えると、
M 0 = E Z , M n = Z M_0=\mathbb{E}Z,
\qquad
M_n=Z M 0 = E Z , M n = Z です。
したがって、
Z − E Z = ∑ i = 1 n ( M i − M i − 1 ) Z-\mathbb{E}Z
=
\sum_{i=1}^n(M_i-M_{i-1}) Z − E Z = i = 1 ∑ n ( M i − M i − 1 ) と分解できます。
有界差分条件によって各 martingale difference の変動幅を制御し、Hoeffding 型の指数モーメント評価を適用することで McDiarmid の不等式が導かれます。
8. それぞれの不等式は何が違うのか
ここまでの関係を整理すると次のようになります。
不等式・手法 主な仮定 扱う対象 典型的な tail Markov 非負性、1 次モーメント 非負確率変数 O ( 1 / t ) O(1/t) O ( 1/ t ) Chebyshev 有限分散 一般の確率変数 O ( 1 / t 2 ) O(1/t^2) O ( 1/ t 2 ) Chernoff 法 MGF を評価可能 一般の確率変数 MGF に依存 Hoeffding 独立性、有界性 確率変数の和 exp ( − c t 2 ) \exp(-ct^2) exp ( − c t 2 ) Bernstein 独立性、有界性、分散 確率変数の和 exp ( − c min ( t 2 / v , t / M ) ) \exp(-c\min(t^2/v,t/M)) exp ( − c min ( t 2 / v , t / M )) McDiarmid 独立入力、有界差分性 一般の関数 f ( X 1 , … , X n ) f(X_1,\dots,X_n) f ( X 1 , … , X n ) exp ( − c t 2 ) \exp(-ct^2) exp ( − c t 2 )
ただし、この表の c c c
どれを使えばよいか
大まかな判断基準は次のようになります。
非負性と期待値しか分からない
→ Markov
平均と分散まで分かる
→ Chebyshev
MGF を直接計算・評価できる
→ Chernoff 法
独立な確率変数の和で、各変数が有界
→ Hoeffding
独立な和で、有界性に加えて分散が小さいことも利用したい
→ Bernstein
独立変数の和ではなく、一般の関数を扱いたいが、1 入力の変更による影響が小さい
→ McDiarmid
9. よくある注意点
独立性を暗黙に仮定しない
Markov や Chebyshev の不等式そのものには独立性は不要です。
一方で、本記事で述べた標準的な Hoeffding、Bernstein、McDiarmid では独立性が本質的な仮定になっています。
依存する確率変数に対して同じ式をそのまま適用することはできません。
依存構造を扱う場合には martingale の Azuma-Hoeffding inequality や、mixing 条件に基づく集中不等式など別の道具が必要になります。
「有界」は観測した最大値・最小値とは違う
Hoeffding で必要なのは、
a i ≤ X i ≤ b i a.s. a_i\le X_i\le b_i
\quad\text{a.s.} a i ≤ X i ≤ b i a.s. という分布そのものに対する既知の範囲 です。
手元の標本でたまたま観測された
min i X i , max i X i \min_iX_i,\qquad\max_iX_i i min X i , i max X i を、そのまま確率変数の真の上下限として使えるわけではありません。
この違いは実際のデータ解析で特に重要です。
有界でないから集中しない、とは限らない
Gaussian 分布は有界ではありませんが、非常に強い集中を持ちます。
したがって、
Hoeffding が使えない ⇒ \Rightarrow ⇒
ではありません。
有界性は MGF を制御するための一つの十分条件にすぎず、sub-Gaussian、sub-exponential、有限高次モーメントなど、より一般的な tail 条件に対応した集中不等式が存在します。
集中不等式は分布を再現するものではない
中心極限定理は、適切に正規化された和の分布そのもの が Gaussian に近づくことを述べます。
一方、集中不等式の主目的は
Pr ( ∣ X − E X ∣ ≥ t ) \Pr(|X-\mathbb{E}X|\ge t) Pr ( ∣ X − E X ∣ ≥ t ) を上から抑えることです。
両者は関連していますが、目的が異なります。
集中不等式は有限標本での保証に強く、中心極限定理は分布の漸近的な形を記述することに強い、という違いがあります。
10. まとめ
集中不等式の基本的な流れを一つの図式として書くと、
Markov ⟶ Chebyshev \boxed{
\text{Markov}
\longrightarrow
\text{Chebyshev}
} Markov ⟶ Chebyshev と
Markov ⟶ Chernoff method ⟶ Hoeffding / Bernstein \boxed{
\text{Markov}
\longrightarrow
\text{Chernoff method}
\longrightarrow
\text{Hoeffding / Bernstein}
} Markov ⟶ Chernoff method ⟶ Hoeffding / Bernstein という 2 つの流れが見えてきます。
Markov の不等式は非常に弱い仮定から tail probability を制御する最も基本的な道具です。
Chebyshev は二乗偏差に Markov を適用し、分散によって平均からのずれを評価します。
Chernoff 法では確率変数を指数変換し、MGF とパラメータ最適化を使うことで指数的な tail bound を作ります。
Hoeffding はその枠組みに有界性を組み合わせ、
exp ( − c n ε 2 ) \exp(-cn\varepsilon^2) exp ( − c n ε 2 ) という強い有限標本保証を与えます。
Bernstein はさらに分散を利用することで、小偏差領域ではよりデータの実際の変動に即した評価を可能にします。
そして McDiarmid は、「和」という構造さえ捨て、「各入力を 1 個変えても出力が大きく変わらない」という安定性だけから一般の関数の集中を導きます。
結局、集中不等式が答えようとしている問いは一貫しています。
有限個のランダムなデータから作られた量は、どの程度その典型値の周りに安定しているのか？
統計推定、機械学習の汎化解析、ランダム行列、ランダムグラフ、アルゴリズム解析などで集中不等式が繰り返し現れるのは、この問いが確率的な問題のほぼあらゆる場所に現れるからです。
参考文献
W. Hoeffding, Probability Inequalities for Sums of Bounded Random Variables , Journal of the American Statistical Association, 58(301), pp. 13–30, 1963. DOI: 10.1080/01621459.1963.10500830
C. McDiarmid, On the Method of Bounded Differences , Surveys in Combinatorics, 1989, London Mathematical Society Lecture Note Series 141, pp. 148–188. DOI: 10.1017/CBO9781107359949.008
S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence , Oxford University Press, 2013.