確率論の不等式 - The Big Computing

どんな確率分布でも（一部条件付き）、以下の不等式が成り立つ。これらの不等式は、機械学習の理解に役立つことがある。

Table of Contents

チェビシェフの不等式

期待値から離れる確率は小さい。

$\displaystyle \Pr(\left|X-\mu \right|\geq k\sigma )\leq {\frac {1}{k^{2}}}$

確率変数が期待値より大きくなる確率は小さい。

一般的な形ではないが下の形が自明でわかりやすい。

$\displaystyle aI_{(|X|\geq a)}\leq |X|\$

モーメント母関数（is確率変数）が期待値より大きくなる確率はどんなtでも小さい。

$\displaystyle \Pr(X\geq a)=\Pr(e^{t\cdot X}\geq e^{t\cdot a})\leq {\frac {\mathrm {E} \left[e^{t\cdot X}\right]}{e^{t\cdot a}}}$

この式の右辺のinfをとるとシャーノフの限界が得られる。

確率変数の和が期待値より大きくなる確率はとても小さい。

分母にΣが現れる理由は、シャーノフバウンドの分母による。

$\Pr(\displaystyle\sum X_i - E[\displaystyle\sum X_i]) \leq \exp ({\frac {-2t^{2}}{\displaystyle\sum (\max X_{i}-\min X_{i})^{2}}})$

上の式をマルチンゲールに拡張したもの。

$\displaystyle {\text{P}}(X_{N}-X_{0}\geq \epsilon )\leq \exp ({-\epsilon ^{2} \over 2\sum _{k=1}^{N}c_{k}^{2}})$

これらの不等式がすごいのは、ほとんどの確率分布で成立するということである。

そのため、機械学習の論文には普遍的に登場し続けている。

完全に習得できれば、理論の理解度のレベルがグッと上がるはずだ。