数学、ときどき統計、ところによりIT

理論と実践の狭間で漂流する数学趣味人の記録

確率不等式

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

補題1(マルコフの不等式) (X,\mathcal{M},\mu) を測度空間、f:X\to[-\infty,\infty] を可測関数、\(a>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*}

 

補題2(ヘフディングの補題 (\Omega,\mathcal{F},P) を確率空間とし、XE_{P}[X]=0a\le X\le b (\mathrm{a.e.})を満たす確率変数とする。このとき任意の \(t>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<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>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).

 

補題3(ヘフディングの不等式) (\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>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>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).