ludu-vorton

Machine learning, Causal Inference, Algorithmic game theoryなどに興味があります。

ヘフディングの不等式(Hoeffding's inequality)と諸々の確率の評価の不等式

今回はバンディットアルゴリズムや統計的学習理論で, 確率の評価で用いられる不等式について解説します.

最後に, 学習理論で最も重要な不等式の一つであるヘフディングの不等式まで証明します.

証明の中で, 確率論, 学習理論で用いられるテクニックがたくさんつまっているので, 証明も追うとよいと思います.

この解説記事は, スタンフォード大学のコンピューターサイエンスの授業の一つであるCS229:Machine learningレクチャーノートを参考にしています.

確率のバウンドの基本

確率論, 統計学, 機械学習などで基本的な疑問は以下のような問題です.

期待値  \mathbb{E}[Z] の確率変数 Zが与えられたとき,   Zはその期待値 \mathbb{E}[Z]近くの値になる確率はどの程度か.

この問いに答えるために, この記事では以下のような確率の上限を計算するいくつかの道具を紹介する.

 \mathbb{P}(Z \geq \mathbb{E}[Z]  + t)
  \mathbb{P}(Z \leq \mathbb{E}[Z]  - t)

ただし,  tは正の実数.

マルコフの不等式(Markov's inequality)

最初に紹介する不等式は, マルコフの不等式です

証明は簡単であるが, 全ての基本となる不等式なので, きちんと覚えておきたい.

 Z  \geq 0を確率変数とする. 任意の t  \geq 0に対して

マルコフの不等式
\mathbb{P}(Z \geq t) \leq \frac{\mathbb{E}[Z]}{t}

証明  \mathbb{P}(Z \geq t) =  \mathbb{E}[\textbf{1}\{Z \geq   t\}]であることに注意する.

  Z  \geq tのとき,  t  \gt  0より tで割ると \frac{Z}{t} \geq 1 = \textbf{1}\{Z \geq t\}.

一方で,  Z \leq tのとき,  \textbf{1}{Z \geq t} = 0であるから,  \frac{Z}{t} \geq 0 = \textbf{1}\{Z \geq t\}.

以上より,  Z tと大小関係に寄らず,

 \frac{Z}{t} \geq \textbf{1}\{Z \geq t\}.

両辺で期待値を取ればマルコフの不等式が成り立つことがわかる.


チェビシェフの不等式(Chebyshev’s inequality)

次にマルコフの不等式の発展系を紹介する.

この不等式は, 期待値で抑えるのではなく, 分散で抑えるものです.

 Zは任意の確率変数とする(正である必要はない). また, \mathrm{Var}(Z) \lt \inftyとします

任意の実数 t  \gt 0に対して

チェビシェフの不等式
\mathbb{P}(Z \geq \mathbb{E}[Z]  + t \text{  or  } Z  \leq \mathbb{E}[Z]  - t) \leq \frac{\mathrm{Var}(Z)}{t^2}

証明:

以下が同値であることを利用する.

 Z \geq \mathbb{E}[Z]  + tまたは Z  \leq \mathbb{E}[Z]  - t  \Leftrightarrow  (Z - \mathbb{E}[Z] )^{2} \geq t^{2}.

すると,

 \mathbb{P}(Z \geq \mathbb{E}[Z]  + t \text{  or  } Z  \leq \mathbb{E}[Z]  - t) = \mathbb{P}\big( (Z - \mathbb{E}[Z])^{2} \geq t^{2}\big)

マルコフの不等式において,  Zを,  (Z - \mathbb{E}[Z])^{2},  t t^{2}とみなして, 適用すると

 \mathbb{P}\big( (Z - \mathbb{E}[Z])^{2} \geq t^{2}\big) \leq \frac{\mathbb{E}[(Z - \mathbb{E}[Z])^{2}]}{t^{2}} = \frac{\mathrm{Var}(Z)}{t^2}

マルコフの不等式を使うことですぐにチェビシェフの不等式が示せました.

初めてチェビシェフの不等式を証明したときはもっと苦労した覚えがあったので, この証明法は鮮やかだったです.

よく見るチェビシェフの不等式と違う方もいるかもしれないです.

Wikipediaのチェビシェフの不等式では,

 \mathbb{P}(|Z - \mathbb{E}[Z]| \geq  k\sigma )  \leq \frac{1}{k^{2}}

ただし,  \sigmaは,  Zの分散の平方根をとったもの.

これは同じもので,  t k\sigmaとおけばよい.

チェビシェフの不等式の応用の一つとして, 標本平均の分散が有限であれば, 真の平均に近くことが証明できます.

ここでは証明は省略するが, 元のレクチャーノートでは証明もされているので, 気になる方はチェックしてみてください.

モーメント母関数(Moment generating functions)

確率変数の実現値が期待値からズレる確率をもっと厳しい不等式で評価したい場合, 分散が有限である条件より強い条件が必要になります.

そのひとつがモーメント母関数です*1.

あとで紹介するヘフディングの不等式にexponentialが出るのが不思議だったが, モーメント母関数がそれに一役買っていたことがわかってなるほどなとなりました.

任意の確率変数 Zのモーメント母関数 M_{Z}(\lambda)は,


M_{Z}(\lambda) = \mathbb{E}(e^{\lambda Z})

次にこのモーメント母関数を用いた確率の評価の不等式を紹介します.

チェルノフ上界(Chernoff bounds)

任意の確率変数 Zと任意の正の実数 t \geq 0に対して,

チェルノフ上界
\mathbb{P}(Z \geq \mathbb{E}[Z]  + t) \leq \min_{\lambda \geq 0} M_{Z - \mathbb{E}[Z]}(\lambda)e^{-\lambda t} \\
\mathbb{P}(Z \leq \mathbb{E}[Z]  - t) \leq \min_{\lambda \geq 0} M_{\mathbb{E}[Z] - Z}(\lambda)e^{-\lambda t}.

この証明もマルコフの不等式を使えば一瞬で解ける.

証明は1つ目の不等式だけ与えます.

後半も全く同じように証明できます*2

証明: 任意の \lambda \geq 0を一つ取る.

このとき,

 Z \geq \mathbb{E}[Z] + t \Leftrightarrow e^{\lambda Z} \geq e^{\lambda \mathbb{E}[Z] + \lambda t}

が成り立つ.

これは正の実数 \lambdaをかけても不等式の向きは変わらず, また eは増加関数であるからである.

最後に両辺を e^{\lambda \mathbb{E}[Z]} \geq 0で割る操作をすると,

 Z \geq \mathbb{E}[Z] + t \Leftrightarrow e^{\lambda Z - \lambda \mathbb{E}[Z]} \geq e^{\lambda t}

よって,

 \mathbb{P}\big(Z \geq \mathbb{E}[Z] + t \big) = \mathbb{P}\big(e^{\lambda Z - \lambda \mathbb{E}[Z]} \geq e^{\lambda t} \big) \leq 
\mathbb{E}[ e^{\lambda(Z -\mathbb{E}[Z]}])e^{-\lambda t}

最後の不等号はマルコフの不等式を適用した.

 \lambdaは任意だったので, 右辺が最小になる \lambdaに対しても成り立つので, チェルノフ上界は示された. 


チェルノフ上界は,  \lambdaで最小化させる前の段階を指す場合もあります.

その場合もチェルノフ上界と呼ぶことにします.

チェルノフ上界の嬉しいのは, 和の操作について"きれいに振る舞ってくれる"点です.

これはモーメント母関数がもたらす作用である.

きれいに振る舞ってくれるのいみは以下の例でわかると思います.

例えば, 確率変数の列 \{Z\}_{i=1}^nがあり, 各々が独立であるとします.

このとき, 確率変数の和 \sum_{i=1}^n Z_iのモーメント母関数は各々のモーメント母関数の積となります.

つまり


M_{Z_1 + Z_2 + \cdots + Z_n}(\lambda) = \Pi_{i=1}^n M_{Z_i}(\lambda)

 Z_iがi.i.d.*3だとして, また平均が0*4の場合, チェルノフ上界から


\mathbb{P}(\sum_{i=1}^nZ_i \geq t) \leq \frac{\Pi_{i=1}^n M_{Z_i}(\lambda)}{e^{\lambda t}} = \frac{(M_{Z_1}(\lambda))^{n}}{e^{\lambda t}}

となります.

よって一つのモーメント母関数さえ計算すれば上界が得られます.

チェルノフ上界の具体例

次は, チェルノフ上界を使って示される面白い評価式を見てみる

ラーデマッハー*5確率変数を用いた例です.

ラーデマッハー変数とは仰々しいですが, 要は確率1/2で1で, 確率1/2で-1を取る変数のことです.

まずラーデマッハー変数 Sのモーメント母関数を抑える式を証明します.

それが次式です.


\mathbb{E}[e^{\lambda S}] \leq e^{\frac{\lambda^{2}}{2}}

これの証明は少々厄介で, 指数関数のテイラー展開を用いて証明します.

証明: 指数関数のテイラー展開は,  e^{x} = \sum_{k=0}^{\infty} \frac{x^{k}}{k!} である.

これを用いると, ラーデマッハー変数 Sのモーメント母関数は,


\mathbb{E}[e^{\lambda S}] = \mathbb{E}\Big[\sum_{k=0}^{\infty} \frac{(\lambda S)^{k}}{k!} \Big]

期待値は積分なので, 無限級数の和が入れ替えられるかなど気になる方もいらっしゃると思いますが, 詳細な議論は目をつぶります.

そして,  kが奇数の場合,  \mathbb{E}[S^{k}] = 0で,  kが偶数の場合,  \mathbb{E}[S^{k}] = 1となることを利用すると


 \mathbb{E}\Big[\sum_{k=0}^{\infty} \frac{(\lambda S)^{k}}{k!} \Big] = \sum_{k=0, 2, 4, \dots} \frac{\lambda^{k}}{k!} = \sum_{k=0}^{\infty} \frac{\lambda^{2k}}{(2k)!}

また (2k)! \geq 2^{k} \cdot k!であるから,


\sum_{k=0}^{\infty} \frac{\lambda^{2k}}{(2k)!} \leq \sum_{k=0}^{\infty} (\frac{\lambda^{2}}{2})^{k} \frac{1}{k!} = e^{\frac{\lambda^{2}}{2}}

よって, ラーデマッハー確率変数のモーメント母関数は e^{\frac{\lambda^{2}}{2}}で抑えられることがわかった.


次にラーデマッハー確率変数 S_iの和を考えます.  S_iは, i.i.d.とします

 Z = \sum_{i=1}^{n} S_iとおきます.

すると,  \mathbb{E}[S_i] = 0であるから, もちろん \mathbb{E}[Z] = 0である.

よって, チェルノフ上界と先ほど証明したラーデマッハー確率変数のモーメント母関数を抑える不等式より


\mathbb{P}(Z \geq t) \leq \mathbb{E}[e^{\lambda Z} ] e^{-\lambda t} = \mathbb{E}[e^{\lambda S_1}]^{n}e^{-\lambda t} \leq e^{\frac{n\lambda^
{2} - \lambda t}{2}}

ここで, チェルノフ上界は \lambdaを最小になる部分は具体的に書けなかったが, 今回は eの指数部分が下に凸な二次関数なので, 具体的に書くことができて,


\lambda^{*} = \frac{t}{n}

のとき, 最小になる.

したがって,


\mathbb{P}(Z \geq t) \leq e^{- \frac{t^2}{2n}}

右辺の式が, きれいになるように  t = \sqrt{2n \log \frac{1}{\delta}} \geq 0とおけば,


\mathbb{P}(Z \geq \sqrt{2n \log \frac{1}{\delta}}) \leq \delta

変形して,


\mathbb{P}(Z \lt \sqrt{2n \log \frac{1}{\delta}}) \geq 1- \delta
 .

この不等式を読むと,  \deltaを小さく取ったとき, ほとんどの確率で, ラーデマッハー確率変数の n個の和 O(\sqrt{n})より小さくなるということを表しています.

ヘフディングの補題とヘフディングの不等式(Hoeffding’s lemma and Hoeffding’s inequality)

ヘフディングの不等式は, 学習理論においてもっとも大事な不等式の一つです.

確率変数の和が大きくなりすぎたり, 小さくなりすぎたりする確率を評価する際に使います.

 Z_1, Z_2, \dots, Z_nを有限で独立な確率変数とする. 任意の iで,  Z_i \in [a, b]とする. ここで,  a, bは有限.

このとき, 任意の正の実数 tに対して,

ヘフディングの不等式
\mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq t \Big) \leq e^{-\frac{2nt^{2}}{(b-a)^{2}}} \\
\mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \leq -t \Big) \leq e^{-\frac{2nt^{2}}{(b-a)^{2}}}

これを証明するためには, ヘフディングの補題という命題を証明しないといけません.

 Z [a, b]の範囲にある有限な確率変数とする.

このとき, 任意の実数 \lambdaに対して,

ヘフディングの補題
\mathbb{E}[e^{\lambda(Z-\mathbb{E}[Z])}] \leq e^{\frac{\lambda^{2}(b-a)^{2}}{8}}

この補題の少し弱い不等式を証明します.

分母の8を2にしたバージョンです.

定数の部分なので, 本質的にはそこまで影響はないと言えます.

この証明ではたくさんテクニックがつまっているので, 丁寧に追うとよいと思います.

たとえば,

  • イェンセンの不等式(Jensen's inequality)
  • 同一の確率変数を別の確率変数とみなす対称化(symmetrization)
  •  0で対称な確率変数は, ラーデマッハー確率変数をかけても分布が変わらない
  • 複数の確率変数で, 期待値を取るとき, 他の確率変数は固定してみることができる

などです.

証明: 証明で使うイェンセンの不等式をまず紹介する.

イェンセンの不等式は, 以下の不等式のことです. 詳細はここでは説明しません.

関数 fが凸関数であるとき,

イェンセンの不等式
f(\mathbb{E}[Z]) \leq \mathbb{E}[f(Z)].

今回は, 指数関数 e^{-x}が凸関数であるので, イェンセンの不等式が使えることを用いる.

次に, 補題の不等式の左辺には,  Zが2つ登場する. 片方を Zと全く同じ分布に従う別の確率変数とみなしても特に問題はない.

よって, 2つめに登場する Z Z'のようにすると(symmetrization),


\mathbb{E}[e^{\lambda(Z-\mathbb{E}[Z])}] = \mathbb{E}_{Z}[e^{\lambda(Z-\mathbb{E}_{Z'}[Z'])}] \leq  \mathbb{E}_{Z}\mathbb{E}_{Z'}[e^{\lambda(Z-Z')}]
 .

最後の不等式はイェンセンの不等式を用いた.

よって,


\mathbb{E}[e^{\lambda(Z-\mathbb{E}[Z])}] \leq  \mathbb{E}_{Z, Z'}[e^{\lambda(Z-Z')}]
 .

 Z - Z'は,  0に関して対称な確率変数なので, ラーデマッハー確率変数 Sをかけても分布は変わらない.

つまり,  Z - Z' S(Z - Z')と全く同じ分布に従う.

したがって,


\mathbb{E}_{Z, Z'}[e^{\lambda(Z-Z')}] = \mathbb{E}_{Z, Z', S}[e^{\lambda S(Z-Z')}] = \mathbb{E}_{Z, Z'}\mathbb{E}_{S}[e^{\lambda S(Z-Z')}| Z, Z'] 
 .

チェルノフ上界の具体例で示したラーデマッハー確率変数のモーメント母関数を評価する式を用いて,


\mathbb{E}_{S}[e^{\lambda S(Z-Z')}| Z, Z'] \leq e^{\frac{\lambda^{2}(Z-Z')^{2}}{2}}
 .

 Z, Z'は,  [a, b]であるから,  (Z-Z')^{2} \leq (b-a)^{2}.

したがって,


\mathbb{E}_{Z, Z'}[e^{\lambda(Z-Z')}] \leq e^{\frac{\lambda^{2}(b-a)^{2}}{2}}
 .

以上から, ヘフディングの補題は示された.


この補題を用いて, ヘフディングの不等式の上の式だけ証明する.

ヘフディングの不等式の上から抑える式(再掲)
\mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq t \Big) \leq e^{-\frac{2nt^{2}}{(b-a)^{2}}}

証明: チェルノフ上界より,


\mathbb{P}\Big(\frac{1}{n}\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq t \Big) = \mathbb{P}\Big(\sum_{i=1}^{n}(Z_i - \mathbb{E}[Z_i]) \geq nt \Big) \\
 \leq \mathbb{E}\big[ e^{\lambda \sum (Z_{i} - \mathbb{E}[Z_{i}])}\big] e^{-\lambda n t} \\
= \Big(\Pi_{i=1}^{n} \mathbb{E}\big[ e^{\lambda (Z_i - \mathbb{E}[Z_i]}\big]\Big)e^{-\lambda n t} 
\leq e^{\frac{n\lambda^{2}(b-a)^{2}}{8} - \lambda n t}

最後の不等式は, ヘフディングの補題を用いた.

最後に,  \lambdaで右辺を最小化すれば, 望む式が得られる.


参考文献

CS229 Supplemental Lecture notes Hoeffding’s inequality

Wikipedia: Moment-generating function

ウィキペディア: ラーデマッハー

*1:期待値や分散は, モーメントによって表現されるので, モーメント母関数が存在することは分散が有限であることより強い条件になる.

*2:数学書によくある同様に証明できる詐欺ではないです

*3:Independent and identically distributed

*4:簡単のため

*5:Rademacher 読み方はHans Rademacherに敬意を払ってドイツ読みにしています