はじめに
先日、PAC-Bayesに関する論文(McAllester, 2003)を読んでいて、簡単に済まされていた不等式があったので、その導出の備忘録。
示したいこと
$0 < p < q < 1$が成り立つときに、
\begin{align}
KL(p || q) \geq \frac{(q \ – \ p)^2}{2q}
\end{align}
が成り立つ。ここで、$KL(p || q)$は、パラメータがそれぞれ$p, q \in [0, 1]$の2つのベルヌーイ分布のKL情報量の略記号であり、
$$KL(p || q) := p \ln \frac{p}{q} + (1 – p) \ln \frac{1-p}{1-q}$$
である。
導出
$p \in [0, 1]$を固定。$p < x < 1$なる$x$に対して、
\begin{align}
f(x) := p \ln \frac{p}{x} + (1 – p) \ln \frac{1-p}{1-x} – \frac{(x – p)^2}{2x}
\end{align}
が非負であることを示す。$f(p) = 0$であり、$f$を$x$で微分すると、
\begin{align}
f'(x) = – \frac{p}{x} + \frac{1-p}{1-x} -\frac{1}{2} \left(1 – \frac{p^2}{x^2}\right)
\end{align}
となる。これが$x > p$で非負であることを示せばよい。
\begin{align}
f'(x)
&= \frac{-p(1-x) + x(1-p)}{x(1-x)} -\frac{x + p}{2x^2} \\
&= \frac{x-p}{x(1-x)} -\frac{x + p}{2x^2} \\
&= (x-p) \left(\frac{1}{x(1-x)} – \frac{x+p}{2x^2}\right) \\
\end{align}
が成り立つ。$x – p > 0$であるので、$\frac{1}{x(1-x)} – \frac{x+p}{2x^2} > 0$であることを示すと良い。
\begin{align}
\frac{1}{x(1-x)} – \frac{x+p}{2x^2}
&= \frac{2x – (x+p)(1-x)}{2x(1-x)}
\end{align}
であり、上式右辺の分母は、$0 < x < 1$であるので、$2x(1-x) > 0$である。あとは、分子が非負であることを示せば良い。
\begin{align}
2x – (x + p)(1 – x)
&= 2x + x^2 + px – x – p\\
&= x^2 + px + x – p \\
& > p^2 + p^2 + p – p \ \ (\because \ x > p \text{より}) \\
&= 2p^2 \\
&> 0
\end{align}
であるので、$f'(x) > 0 \ (x > p)$が成り立つ。よって、求めたい不等式$KL(p || q) \geq \frac{(q – p)^2}{2q} \ (q > p)$が示せた。
編集後記
- Pinskerの不等式から、$KL(p || q) \geq 2(q-p)^2$ が成り立つことは文献を調べたら出てきた。それに引っ張られて、微分して非負であることを示すという基本のやり方がすっぽ抜けてた
- この論文の主定理読むのに数時間かかってるのに、慣れている人からすれば10秒で終わる話らしい。
- 数学やめようかな笑
コメント