ヘフディングの不等式(Hoeffding's inequality)と諸々の確率の評価の不等式
今回はバンディットアルゴリズムや統計的学習理論で, 確率の評価で用いられる不等式について解説します.
最後に, 学習理論で最も重要な不等式の一つであるヘフディングの不等式まで証明します.
証明の中で, 確率論, 学習理論で用いられるテクニックがたくさんつまっているので, 証明も追うとよいと思います.
この解説記事は, スタンフォード大学のコンピューターサイエンスの授業の一つであるCS229:Machine learningのレクチャーノートを参考にしています.
- 確率のバウンドの基本
- モーメント母関数(Moment generating functions)
- ヘフディングの補題とヘフディングの不等式(Hoeffding’s lemma and Hoeffding’s inequality)
- 参考文献
確率のバウンドの基本
確率論, 統計学, 機械学習などで基本的な疑問は以下のような問題です.
期待値の確率変数が与えられたとき, はその期待値近くの値になる確率はどの程度か.
この問いに答えるために, この記事では以下のような確率の上限を計算するいくつかの道具を紹介する.
ただし, は正の実数.
マルコフの不等式(Markov's inequality)
最初に紹介する不等式は, マルコフの不等式です
証明は簡単であるが, 全ての基本となる不等式なので, きちんと覚えておきたい.
を確率変数とする. 任意のに対して
証明 であることに注意する.
のとき, よりで割ると.
一方で, のとき, であるから, .
以上より, とと大小関係に寄らず,
両辺で期待値を取ればマルコフの不等式が成り立つことがわかる.
チェビシェフの不等式(Chebyshev’s inequality)
次にマルコフの不等式の発展系を紹介する.
この不等式は, 期待値で抑えるのではなく, 分散で抑えるものです.
は任意の確率変数とする(正である必要はない). また,とします
任意の実数に対して
証明:
以下が同値であることを利用する.
または .
すると,
マルコフの不等式において, を, , をとみなして, 適用すると
マルコフの不等式を使うことですぐにチェビシェフの不等式が示せました.
初めてチェビシェフの不等式を証明したときはもっと苦労した覚えがあったので, この証明法は鮮やかだったです.
よく見るチェビシェフの不等式と違う方もいるかもしれないです.
ただし, は, の分散の平方根をとったもの.
これは同じもので, をとおけばよい.
チェビシェフの不等式の応用の一つとして, 標本平均の分散が有限であれば, 真の平均に近くことが証明できます.
ここでは証明は省略するが, 元のレクチャーノートでは証明もされているので, 気になる方はチェックしてみてください.
モーメント母関数(Moment generating functions)
確率変数の実現値が期待値からズレる確率をもっと厳しい不等式で評価したい場合, 分散が有限である条件より強い条件が必要になります.
そのひとつがモーメント母関数です*1.
あとで紹介するヘフディングの不等式にexponentialが出るのが不思議だったが, モーメント母関数がそれに一役買っていたことがわかってなるほどなとなりました.
任意の確率変数のモーメント母関数は,
次にこのモーメント母関数を用いた確率の評価の不等式を紹介します.
チェルノフ上界(Chernoff bounds)
任意の確率変数と任意の正の実数に対して,
この証明もマルコフの不等式を使えば一瞬で解ける.
証明は1つ目の不等式だけ与えます.
後半も全く同じように証明できます*2
証明: 任意のを一つ取る.
このとき,
が成り立つ.
これは正の実数をかけても不等式の向きは変わらず, または増加関数であるからである.
最後に両辺をで割る操作をすると,
よって,
最後の不等号はマルコフの不等式を適用した.
は任意だったので, 右辺が最小になるに対しても成り立つので, チェルノフ上界は示された.
チェルノフ上界は, で最小化させる前の段階を指す場合もあります.
その場合もチェルノフ上界と呼ぶことにします.
チェルノフ上界の嬉しいのは, 和の操作について"きれいに振る舞ってくれる"点です.
これはモーメント母関数がもたらす作用である.
きれいに振る舞ってくれるのいみは以下の例でわかると思います.
例えば, 確率変数の列があり, 各々が独立であるとします.
このとき, 確率変数の和のモーメント母関数は各々のモーメント母関数の積となります.
つまり
がi.i.d.*3だとして, また平均が0*4の場合, チェルノフ上界から
となります.
よって一つのモーメント母関数さえ計算すれば上界が得られます.
チェルノフ上界の具体例
次は, チェルノフ上界を使って示される面白い評価式を見てみる
ラーデマッハー*5確率変数を用いた例です.
ラーデマッハー変数とは仰々しいですが, 要は確率1/2で1で, 確率1/2で-1を取る変数のことです.
まずラーデマッハー変数のモーメント母関数を抑える式を証明します.
それが次式です.
これの証明は少々厄介で, 指数関数のテイラー展開を用いて証明します.
証明: 指数関数のテイラー展開は, である.
これを用いると, ラーデマッハー変数のモーメント母関数は,
期待値は積分なので, 無限級数の和が入れ替えられるかなど気になる方もいらっしゃると思いますが, 詳細な議論は目をつぶります.
そして, が奇数の場合, で, が偶数の場合, となることを利用すると
またであるから,
よって, ラーデマッハー確率変数のモーメント母関数はで抑えられることがわかった.
次にラーデマッハー確率変数の和を考えます. は, i.i.d.とします
とおきます.
すると, であるから, もちろんである.
よって, チェルノフ上界と先ほど証明したラーデマッハー確率変数のモーメント母関数を抑える不等式より
ここで, チェルノフ上界はを最小になる部分は具体的に書けなかったが, 今回はの指数部分が下に凸な二次関数なので, 具体的に書くことができて,
のとき, 最小になる.
したがって,
右辺の式が, きれいになるように とおけば,
変形して,
この不等式を読むと, を小さく取ったとき, ほとんどの確率で, ラーデマッハー確率変数の個の和より小さくなるということを表しています.
ヘフディングの補題とヘフディングの不等式(Hoeffding’s lemma and Hoeffding’s inequality)
ヘフディングの不等式は, 学習理論においてもっとも大事な不等式の一つです.
確率変数の和が大きくなりすぎたり, 小さくなりすぎたりする確率を評価する際に使います.
を有限で独立な確率変数とする. 任意ので, とする. ここで, は有限.
このとき, 任意の正の実数に対して,
これを証明するためには, ヘフディングの補題という命題を証明しないといけません.
をの範囲にある有限な確率変数とする.
このとき, 任意の実数に対して,
この補題の少し弱い不等式を証明します.
分母の8を2にしたバージョンです.
定数の部分なので, 本質的にはそこまで影響はないと言えます.
この証明ではたくさんテクニックがつまっているので, 丁寧に追うとよいと思います.
たとえば,
- イェンセンの不等式(Jensen's inequality)
- 同一の確率変数を別の確率変数とみなす対称化(symmetrization)
- で対称な確率変数は, ラーデマッハー確率変数をかけても分布が変わらない
- 複数の確率変数で, 期待値を取るとき, 他の確率変数は固定してみることができる
などです.
証明: 証明で使うイェンセンの不等式をまず紹介する.
イェンセンの不等式は, 以下の不等式のことです. 詳細はここでは説明しません.
関数が凸関数であるとき,
今回は, 指数関数が凸関数であるので, イェンセンの不等式が使えることを用いる.
次に, 補題の不等式の左辺には, が2つ登場する. 片方をと全く同じ分布に従う別の確率変数とみなしても特に問題はない.
よって, 2つめに登場するをのようにすると(symmetrization),
最後の不等式はイェンセンの不等式を用いた.
よって,
は, に関して対称な確率変数なので, ラーデマッハー確率変数をかけても分布は変わらない.
つまり, はと全く同じ分布に従う.
したがって,
チェルノフ上界の具体例で示したラーデマッハー確率変数のモーメント母関数を評価する式を用いて,
は, であるから, .
したがって,
以上から, ヘフディングの補題は示された.
この補題を用いて, ヘフディングの不等式の上の式だけ証明する.
証明: チェルノフ上界より,
最後の不等式は, ヘフディングの補題を用いた.
最後に, で右辺を最小化すれば, 望む式が得られる.
参考文献
CS229 Supplemental Lecture notes Hoeffding’s inequality