有用な確率不等式のまとめ - Counterfactualを知りたい

はじめに

機械学習に関連する諸分野では何かしらの統計量（期待判別誤差やリグレットなど）を上から評価したい場面が多くあります. そのような場面で大活躍するのが確率不等式と呼ばれる不等式の数々です. 今後本ブログでもこれらの不等式を多用することが予想されるため, 一度まとめておきます. いくつかの不等式は証明もします. 証明は, MLPシリーズの『統計的学習理論』のAppendix Aを参考に, 自分なりに行間を埋めてみました.

Jensen's inequality

まず, 凸関数の定義を確認します.

凸関数: 関数 $f: \mathbb{R}^d \rightarrow (- \infty, \infty ]$ が, 任意の ${\bf x}, {\bf y} \in \mathbb{R}^d$ と任意の $\alpha \in [0, 1]$ に対して,

$\begin{aligned} f (\alpha {\bf x} + (1 - \alpha) {\bf y}) \leqq \alpha f ({\bf x}) + (1 - \alpha) f({\bf y}) \end{aligned}$

を満たす時, $f$ を凸関数という.

ここで, 以降のHoeffding's ineqの証明などでも用いられる期待値演算にJensen's ineqを適用した形を紹介します.

Jensen's Inequality: $X$ を有限な期待値を持つ確率変数とする. $f(x)$ を $X$ の値域を含む区間において凸な関数とする. この時, 次の不等式が成り立つ.

$\begin{aligned} f \left( \mathbb{E} \left[ X \right] \right) \leqq \mathbb{E} \left[ f(X) \right] \end{aligned}$

Markov's inequality / Chebyshev's inequality

ここでは, Markov's ineqとChebyshev's ineqを紹介します. これらは統計学の教科書にもだいたい掲載されていると思います.

Marcov's Inequality: 非負確率変数 $X$ と任意の $\epsilon > 0, p > 0$ に対して, 次の不等式が成り立つ.

$\begin{aligned} \mathbb{P} \left( X \geqq \epsilon \right) \leqq \frac{ \mathbb{E} \left[ X^p \right] }{\epsilon^p} \end{aligned}$

導出

$\begin{aligned} \epsilon^p \mathbb{P} \left( X \geqq \epsilon \right) & = \epsilon^p \int_{ X \geqq \epsilon } f(x)dx\\ & = \int_{ X \geqq \epsilon } \epsilon^p f(x)dx\\ & \leqq \int_{ X \geqq \epsilon } X^p f(x)dx \\ & \leqq \mathbb{E} \left[ X^p \right] \end{aligned}$

特に, $X$ を $| Z - \mathbb{E} [ Z ] |$ , $p=2$ と置いた時の形をChebyshev's ineqと呼びます. この不等式は, 確率変数 $Z$ がその期待値から大きく外れた値をとる確率を分散を用いて評価しています.

Chebyshev's inequality: 確率変数 $Z$ と任意の $\epsilon > 0$ に対して, 次の不等式が成り立つ.

$\begin{aligned} \mathbb{P} \left( |Z - \mathbb{E} [ Z ] | \geqq \epsilon \right) \leqq \frac{ \mathbb{V} \left[ Z \right] }{\epsilon^2} \end{aligned}$

Hoeffding's inequality

ここで紹介するHoeffding's ineqは機械学習の論文で頻出なので, かなり重要です. これを示す前に, 一つ補題 (Hoeffding's lemma) を示します.

Hoeffding's lemma: 確率変数 $X$ が $\mathbb{E} [X ] = 0$ , $a \leqq X \leqq b$ を満たすとき, 任意の $s > 0$ に対して, 次の不等式が成り立つ.

$\begin{aligned} \mathbb{E} \left[ \exp (sX) \right] \leqq \mathbb{E} \left[ \exp \left( \frac{s^2 (b - a)^2}{8} \right) \right] \end{aligned}$

導出
$a \leqq x \leqq b$ を満たすような $x$ について, $0 \leqq \lambda \leqq 1$ を次のように置きます.

$\begin{aligned} \lambda = \frac{b - x}{b - a} \end{aligned}$

これを変形すると, $sx = s \lambda a + (1 - \lambda)b$ です. $\exp(\cdot)$ は凸関数なので,

$\begin{aligned} e^{sx} = e^{s \lambda a + (1 - \lambda)b} \leqq \lambda e^{sa} + (1 - \lambda) e^{sb} = \frac{b - x}{b - a} e^{sa} + \frac{x - a}{b - a} e^{sb} \end{aligned}$

両辺の期待値をとると,

$\begin{aligned} \mathbb{E} \left[ e^{sX} \right] = \mathbb{E} \left[ \frac{b - X}{b - a} e^{sa} + \frac{X - a}{b - a} e^{sb} \right] = \frac{b }{b - a} e^{sa} - \frac{a}{b - a} e^{sb} \end{aligned}$

$X$ の期待値が0であることを用いました. ここで, $p = - a / (b - a)$ と置くと, $1 - p = b / (b-a)$ なので,

$\begin{aligned} \frac{b }{b - a} e^{sa} - \frac{a}{b - a} e^{sb} = (1 - p) e^{sa} + p e^{sb} \end{aligned}$

と表されます. また, $u = s(b - a)$ と置き, $u$ についての関数 $\phi (u)$ を次のように定義しておきます.

$\begin{aligned} & (1 - p) e^{sa} + p e^{sb} = pe^{(1 - p)u} + (1 - p)e^{-pu} \\ & \phi (u) = \log \left( pe^{(1 - p)u} + (1 - p)e^{-pu} \right) \end{aligned}$

このとき,

$\begin{aligned} \phi(0) & = \log \left(p - (1 - p) \right) = 0 \\ \phi'(0) & = 0 \quad \left( \phi'(u) = -p + \frac{p e^u}{1 - p + p e^u} \right) \\ \phi'' (u) & = \frac{1 - p}{1 - p + pe^u} \cdot \frac{pe^u}{1 - p + pe^u} \\ & = \frac{1 - p}{1 - p + pe^u} \cdot \left( 1 - \frac{1 - p}{1 - p + pe^u} \right) \leqq \frac{1}{4} \end{aligned}$

したがって, テイラーの定理より, $0 \leqq v \leqq u$ となる $v$ が存在して,

$\begin{aligned} \phi(u) = \phi(0) + u \phi'(0) + \frac{u^2}{2} \phi'' (0) \leqq \frac{u^2}{8} \end{aligned}$

$u = s(b - a)$ だったことを思い出すと,

$\begin{aligned} \phi(u) = \log \left( \mathbb{E} \left[ e^{sX} \right] \right) \leqq \frac{ s^2(b - a)^2}{8} \Leftrightarrow \mathbb{E} \left[ \exp \left( sX \right) \right] \leqq \exp \left( \frac{s^2 (a-b)^2}{8} \right) \end{aligned}$

これにて, Hoeffding's lemmaを得ました.

このHoeffding's lemmaを用いて, Hoeffding's ineqを導出します.

Hoeffding's Inequality: 確率変数 $X_1, ..., X_n$ は独立でかつそれぞれが有界区間 $[ a_i, b_i ]$ に値をとるとする. この時, 任意の $\epsilon > 0$ に対して次の不等式が成り立つ.

$\begin{aligned} \mathbb{P} \left( \frac{1}{n} \sum_{i=1}^n X_i - \frac{1}{n} \sum_{i=1}^n \mathbb{E} \left[ X_i \right] \geqq \epsilon \right) \leqq \exp \left( - \frac{2 n^2 \epsilon^2}{ \sum_{i=1}^n (b_i - a_i) } \right) \end{aligned}$

導出
まず, $Z_i = X_i - \mathbb{E} [ X_i ]$ と置く. このとき, $\mathbb{E} [Z_i ] = 0$ であり, $a_i \leqq Z_i \leqq b_i$ が成り立つので, 確率変数 $Z_i$ はHoeffding's lemmaの仮定を満たす. ここで,

$\begin{aligned} & \mathbb{P} \left( \sum_{i=1}^n Z_i \geqq \epsilon \right) \\ & = \mathbb{P} \left( \exp \left( s \sum_{i=1}^n Z_i \right) \geqq \exp(s \epsilon ) \right) \\ & \leqq \exp \left( -s \epsilon \right) \mathbb{E} \left[ \prod_{i=1}^n \exp (s Z_i) \right] \quad \because Marcov's \: ineq \\ & = \exp \left( -s \epsilon \right) \prod_{i=1}^n \mathbb{E} \left[ \exp (s Z_i) \right] \quad \because independency \\ & \leqq \exp \left( -s \epsilon \right) \prod_{i=1}^n \exp \left( \frac{s^2 (b_i - a_i)^2} {8} \right) \quad \because Hoeffding's \: lemma \\ & = \exp \underbrace{ \left( \frac{s^2}{8} \sum_{i=1}^n (b_i - a_i)^2 - s \epsilon \right)}_{(1)} \end{aligned}$

よりtightなboundを得るため, (1)を最小化する $s = 4 \epsilon / \sum_{i=1}^{n} (b_i - a_i)^{2}$ を代入すると,

$\begin{aligned} \mathbb{P} \left( \sum_{i=1}^n Z_i \geqq \epsilon \right) \leqq \exp \left( \frac{-2 \epsilon ^2} { \sum_{i=1}^n (b_i - a_i)^2 } \right) \end{aligned}$

ここで, $Z_i = X_i - \mathbb{E} [ X_i ]$ を代入し, 両辺を $n$ で割ることで, Hoeffding's ineqを得ます.

Hoeffding's ineqは, 有限仮説集合の汎化誤差解析やバンディット問題におけるリグレット解析など至る所で出てくる印象です. 定理自体, $X_1, ..., X_n$ が独立であれば成り立ちますが, 実際はiidが仮定されていることが多いと思います. (iidの仮定がある場合, $\frac{1}{n} \sum_{i=1}^n \mathbb{E} \left[ X_i \right]$ の部分が単に $\mathbb{E} \left[ X_i \right]$ となります.)

McDiarmid's inequality

最後に, McDiarmid ineqを紹介します. これは, 後に紹介する予定のRademacher Complexityに関連する不等式を導くときなどに役立ちます. これを示す前に, 一つ補題 (Azuma's ineq) を示します.

Azuma's inequality: 確率変数 $X_i, Z_i, V_i: i=1, ..., n$ に対して, $V_i$ は $X_i, ..., X_i$ の関数でありかつ $\mathbb{E} [V_i | X_i, ..., X_{i-1} ] =0$ が成り立つとする. また, $Z_i$ は, $X_1, ..., X_{i-1}$ の関数として表すことができ, $i = 1, ..., n$ について $Z_i \leqq V_i \leqq Z_i + c_i$ を満たすような定数 $c_i$ が存在するとします. このとき, 任意の $\epsilon > 0$ に対して, 次の不等式が成り立つ.

$\begin{aligned} \mathbb{P} \left( \sum_{i=1}^n V_i \geqq \epsilon \right) \leqq \exp \left( - \frac{2 \epsilon^2}{\sum_{i=1}^m c_i^2 } \right) \end{aligned}$

導出
まず $V_i$ についての部分和を $S_k = \sum_{i=1}^k V_i$ としておきます. ここで $t > 0$ を用いて,

$\begin{aligned} & \mathbb{P}\left( \sum_{i=1}^n V_i \geqq \epsilon \right) \\ & = \mathbb{P} \left( S_n \geqq \epsilon \right) \\ & = \mathbb{P} \left( \exp \left( t S_n \right) \geqq \exp (t \epsilon ) \right) \\ & \leqq \exp (- t \epsilon ) \mathbb{E} \left[ \exp \left( t S_n \right) \right] \quad \because Marcov's \, ineq \\ & = \exp (-t \epsilon ) \mathbb{E}_{ X_1, ..., X_{n - 1} } \left[ \exp (t S_n) \mathbb{E}_{X_n} \left[ \exp(t V_n) | X_1, ..., X_{n-1} \right] \right] \\ & \leqq \exp (-t \epsilon ) \mathbb{E}_{ X_1, ..., X_{n - 1} } \left[ \exp (t S_n) \right ] \exp \left( \frac{t^2 c_n^2}{8} \right) \quad \because Hoeffding's \, lemma \\ & \leqq \exp \underbrace{ \left( \frac{t^2}{8} \sum_{i=1}^n c_i^2 - t \epsilon \right) }_{(2)} \end{aligned}$

Hoeffding's lemmaの部分は, 仮定より $X_1, ..., X_{n-1}$ で条件付けたとき $V_i$ の期待値が0であることからlemmaの仮定を満たします. 最後の不等式は, Hoeffding's lemmaを繰り返し用いることで得ます. 最後に, (2)を最小化する $t = 4 \epsilon / \sum_{i=1}^{n} c_i^{2}$ を代入することで,

$\begin{aligned} \mathbb{P} \left( \sum_{i=1}^n V_i \geqq \epsilon \right) \leqq \exp \left( - \frac{2 \epsilon^2}{\sum_{i=1}^m c_i^2 } \right) \end{aligned}$

を得ます.

さて, これを用いてMcDiarmid's ineqを示します.

McDiarmid's inequality: ある集合 $\mathcal{X}$ に値をとる独立な確率変数を $X_1, ..., X_n$ とする. また, 関数 $f: \mathcal{X}^n \rightarrow \mathbb{R}$ と任意の $x_1, ..., x_n, x_i' \in \mathcal{X}$ について, 次の条件 (boundedness condition) を満たすような定数 $c_1, ..., c_n$ が存在するとする.

$\begin{aligned} | f(x_1, ..., x_i, ..., x_n) - f(x_1, ..., x'_i, ..., x_n) | \leqq c_i, \quad \forall i \in \{1, 2, .., n \} \end{aligned}$

この時, 任意の $\epsilon > 0$ に対して, 次の不等式が成り立つ.

$\begin{aligned} \mathbb{P} \left( f(X_1, ..., X_n) - \mathbb{E} \left[ f(X_1, ..., X_n) \right] \geqq \epsilon \right) \leqq \exp \left( - \frac{2 \epsilon^2}{\sum_{i=1}^n c_i^2} \right) \end{aligned}$

導出
最初に $f (X_1, ..., X_n)$ を $f (S)$ と表しておきます. また, $V_1, ..., V_n$ を

$\begin{aligned} V_k = \mathbb{E} \left[ f(S) | X_1, ..., X_k \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] \end{aligned}$

とします ( $V_1 = \mathbb{E} \left[ f(S) | X_1 \right] - \mathbb{E} \left[ f(S) \right]$ ). ここで, 今定義した $V_k$ がAzuma's ineqの仮定を満たすことを確認します. まず, $V_k$ の第1項は $X_1, ..., X_k$ で条件付けた時の期待値なので, これらの確率変数の関数です. さらに,

$\begin{aligned} \mathbb{E} [ V_k | X_1, ..., X_{k-1} ] & = \mathbb{E}_{X_k, ..., X_n} \left[ f(S) | X_1, ..., X_k \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] \\ & = \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] \\ & = 0 \end{aligned}$

ここで, boundedness conditionより

$\begin{aligned} \sup_{x, x'} \{\mathbb{E} \left[ f(S) | X_1, ..., X_{k-1}, x \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1}, x' \right] \} \leqq c_i \end{aligned}$

を満たします. ここで, $Z_k = \inf_x \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1}, x \right]$ とすると, $X_k, V_k, Z_k: k=1, ..., n$ がAzuma's ineqの仮定を満たします. 最後に,

$\begin{aligned} \sum_{i=1}^n V_i & = \left( \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] - \mathbb{E} \left[ f(S) | X_1, ..., X_{k-1} \right] \right) \\ & \quad + \cdot \cdot \cdot + \left( \mathbb{E} \left[ f(S) | X_1 \right] - \mathbb{E} \left[ f(S) \right] \right) \\ & = f(X_1, ..., X_n) - \mathbb{E} \left[ f(X_1, ..., X_n) \right] \end{aligned}$

と見て, これにAzuma's ineqを適用すれば, MacDiamid's ineqを得ます.

さいごに

さて, 本記事では機械学習の周辺分野でよく使われる確率不等式（特に, Hoeffding's inequalityとMacDiamid's inequality）を導出してみました. 一見どのように役立つかわからないかもしれませんが, 今後本ブログで記事にするつもり内容と密接な関連があります.
なお, 導出部分で私が勘違いして誤った記述をしている可能性が大いにあります. 誤りを見つけた場合, ご指摘いただけたら幸いです.

参考

[金森 (2015)] 金森敬文. 2015. 統計的学習理論. 講談社機械学習プロフェッショナルシリーズ.
[Duchi] John Duchi. Probability Bounds. URL: http://www.cs.berkeley.edu/~jduchi/projects/probability_bounds.pdf.