確率不等式 - 数学、ときどき統計、ところによりＩＴ

学習アルゴリズムの評価において必要となる不等式を証明します。

補題１（マルコフの不等式）　 $(X,\mathcal{M},\mu)$ を測度空間、 $f:X\to[-\infty,\infty]$ を可測関数、 $a \gt 0$ とする。このとき次が成り立つ：

$\displaystyle \mu(\{x\in X\,|\,|f(x)|\ge a\})\le\frac{1}{a}\int_{X}|f(x)|\mu(dx).$

証明

\begin{equation*}\begin{split}\int_{X}|f(x)|\mu(dx) & =\int_{|f(x)|\ge a}+\int_{|f(x)|<a} \\ & \ge\int_{|f(x)|\ge a} \\ & \ge a\,\mu(\{x\in X\,|\,|f(x)|\ge a\}). \end{split}\end{equation*}

補題２（ヘフディングの補題）　 $(\Omega,\mathcal{F},P)$ を確率空間とし、 $X$ を $E_{P}[X]=0$ 、 $a\le X\le b$ $(\mathrm{a.e.})$ を満たす確率変数とする。このとき任意の $t\gt 0$ に対して次の不等式が成り立つ：\begin{equation*} E_{P}[\exp(tX)]\le\exp\left(\frac{1}{8}t^{2}(b-a)^{2}\right). \end{equation*}

証明　 $E_{P}[X]=0$ より $a\lt 0$ となることに注意する。指数関数は凸関数より

$\displaystyle \exp(tX)\le\frac{X-a}{b-a}\exp(tb)+\frac{b-X}{b-a}\exp(ta),\quad(\mathrm{a.e.})$

であるから

$\displaystyle E_{P}[\exp(tX)]\le\frac{-a}{b-a}\exp(tb)+\frac{b}{b-a}\exp(ta).$

いま

$\displaystyle p:=\frac{-a}{b-a},\quad u:=t(b-a)$

と置くと $0\le p\le1$ , $u\gt 0$ であり

$\displaystyle E_{P}[\exp(tX)]\le p \exp( (1-p)u)+(1-p)\exp(-pu).$

さらに

\begin{equation*} \begin{split}\phi(u) & :=\log(p\exp( (1-p)u)+(1-p)\exp(-pu) )\\ & =\log(\exp( (1-p)u)\cdot(p+(1-p)\exp(-u) ) )\\ & =(1-p)u+\log(p+(1-p)\exp(-u)) \end{split} \end{equation*}

と置くと、

\begin{gather*}\phi'(u)=1-p+\frac{-(1-p)\exp(-u)}{p+(1-p)\exp(-u)},\\ \phi''(u)=\frac{p(1-p)\exp(-u)}{(p+(1-p)\exp(-u))^{2}}\end{gather*} である。ここでテイラーの定理より、ある $u_{0}\in(0,u)$ が存在して

$\displaystyle \phi(u)=\phi(0)+\phi'(0)u+\frac{1}{2}\phi''(u_{0})u^{2}=\frac{1}{2}\phi''(u_{0})u^{2}$

と書けるが、相加平均と相乗平均の関係により

$\displaystyle \phi''(u_{0})=\frac{p\cdot(1-p)\exp(-u_{0})}{(p+(1-p)\exp(-u_{0}))^{2}}\le\frac{1}{4}$

であることに注意すると

$\displaystyle \phi(u)\le\frac{1}{8}u^{2}$

が成り立つ。よって

$\displaystyle E_{P}[\exp(tX)]\le\exp(\phi(u) )\le\exp\left(\frac{1}{8}u^{2}\right)=\exp\left(\frac{1}{8}t^{2}(b-a)^{2}\right).$

補題３（ヘフディングの不等式）　 $(\Omega,\mathcal{F},P)$ を確率空間とし、 $X_{1},\ldots,X_{n}$ を独立同分布な確率変数で $a_{i}\le X_{i} \le b_{i}\ (\mathrm{a.e.})$ を満たすとする。また $S:=\sum_{i=1}^{n}X_{n}$ とする。このとき任意の $\varepsilon\gt 0$ に対して次の不等式が成り立つ： \begin{gather*} P(S-E_{P}[S]\ge\varepsilon)\le \exp\left(-\frac{2\varepsilon^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right),\\ P(S-E_{P}[S]\le-\varepsilon)\le\exp\left(-\frac{2\varepsilon^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right). \end{gather*}

証明　任意の $t\gt 0$ に対して\begin{align*} P(S-E_{P}[S]\ge\varepsilon) & =P(\exp(t(S-E_{P}[S]))\ge\exp(t\varepsilon))\\ & \le\exp(-t\varepsilon)E_{P}[\exp(t(S-E_{P}[S]))] & \text{(マルコフの不等式)}\\ \mathrm{} & \le\exp(-t\varepsilon)\prod_{i=1}^{n}E_{P}[\exp(t(X_{i}-E_{P}[X_{i}]))] & \text{(独立性)}\\ \mathrm{} & =\exp(-t\varepsilon)\exp\left({\displaystyle \frac{1}{8}t^{2}\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right) & \text{} \end{align*} が成り立つ。

\begin{equation*}\begin{split}\frac{1}{8}t^{2}\sum_{i=1}^{n} & (b_{i}-a_{i})^{2}-t\varepsilon\\ = & \frac{1}{8}\left(\sum_{i=1}^{n}(b_{i}-a_{i})^{2}\right)\left(t-\frac{4\varepsilon}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right)^{2}-\frac{2\varepsilon^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}} \end{split} \end{equation*} であるから

$\displaystyle P(S-E_{P}[S]\ge\varepsilon)\le\exp\left(-\frac{2\varepsilon^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

同様に

$\displaystyle P(S-E_{P}[S]\le-\varepsilon)\le\exp\left(-\frac{2\varepsilon^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$