KLダイバージェンスの下限(イェンセンの不等式による)

KLダイバージェンスの下限(イェンセンの不等式による)

$$ \begin{eqnarray} p_i&:&真の確率分布P(X)の事象x_iの確率 \\q_i&:&任意の確率分布Q(X)の事象x_iの確率(Q:予測や符号化など「真の確率分布Pに対するモデル」が示す確率分布) \end{eqnarray} $$ $$ \begin{eqnarray} D_{KL}(P||Q)&=&\sum_{i=1}^{k} p_i\log{\left(\frac{p_i}{q_i}\right)} \\&=&\sum_{i=1}^{k} p_i\left\{-\log{\left(\frac{q_i}{p_i}\right)}\right\} \;\cdots\;\log{\left(\frac{A}{B}\right)}=\log{\left(\left(\frac{B}{A}\right)^{-1}\right)}=-\log{\left(\frac{B}{A}\right)} \\&\geq&-\log{\left(\sum_{i=1}^{k} p_i\frac{q_i}{p_i}\right)} \\&&\;\cdots\;-\log{\left(x\right)}は凸凾数(下に凸の凾数)(判定については後述) \\&&\;\cdots\;\href{https://shikitenkai.blogspot.com/2020/08/blog-post.html}{\sum_{i=1}^{n}\phi_if(x_i)\geq f\left( \sum_{i=1}^{n}\phi_i x_i \right)\;(イェンセンの不等式(下に凸の凾数))} \\D_{KL}(P||Q) &\geq&-\log{\left(\sum_{i=1}^{k} p_i\frac{q_i}{p_i}\right)} \\&\geq&-\log{\left(\sum_{i=1}^{k} q_i\right)} \\&\geq&-\log{\left(1\right)}\;\cdots\;q_iは確率なので\sum_{i=1}^{k} q_i=1 \\&\geq&0 \end{eqnarray} $$

---

\(-\log{\left(x\right)}\)の凸凾数の判定

$$ \begin{eqnarray} \frac{\mathrm{d}^2}{\mathrm{d}x^2} \left\{ -\log{\left(x\right)} \right\} &=&-\frac{\mathrm{d}^2}{\mathrm{d}x^2} \left\{ \log{\left(x\right)} \right\} \;\cdots\; \left\{cf(x)\right\}^\prime=c\left\{f(x)\right\}^\prime \\&=&-\frac{\mathrm{d}}{\mathrm{d}x} \left\{ \frac{1}{x} \right\} \;\cdots\;\left\{\log{\left(x\right)}\right\}^\prime=x^{-1}=\frac{1}{x} \\&=&-\left(-\frac{1}{x^2}\right) \;\cdots\;\left(x^{-1}\right)^\prime=-x^{-2}=-\frac{1}{x^2} \\&=&\frac{1}{x^2} \gt0\;\cdots\;xが実数の範囲では, 二階微分が常に正なので凸凾数(下に凸の凾数)． \end{eqnarray} $$ 

---

\(\log_{\mathrm{e}}{x}\leq(x-1)\)の関係を用いたKLダイバージェンスの下限

イェンセンの不等式の証明

イェンセンの不等式

\(\phi_1,\phi_2,\cdots\phi_n\)が\(0\lt\phi_i\)かつ\(\sum_{i=1}^{n}\phi_i=1 \)を満たしまた，\(x_1,x_2,\cdots x_n\)を実数の列とするとき，凸凾数\(f(x)\)に対して以下のことが成り立つ. $$ \begin{eqnarray} \sum_{i=1}^{n}\phi_if(x_i)\geq f\left( \sum_{i=1}^{n}\phi_i x_i \right) \;\cdots\;f(x)が凸凾数(下に凸の凾数)のとき. \\\left( \sum_{i=1}^{n}\phi_if(x_i)\leq f\left( \sum_{i=1}^{n}\phi_i x_i \right) \;\cdots\;f(x)が凹凾数(上に凸の凾数)のとき. \right) \end{eqnarray} $$

---

凸凾数(下に凸の凾数)

凸凾数(下に凸の凾数)の性質

任意の\(x_1, x_2\)に対して凸凾数(下に凸の凾数)\(f(x)\)では，\((x_1, f(x_1)), (x_2, f(x_2))\)を結ぶ線分\(g(x)\)は凾数\(f(x)\)の上側にある.
逆に，\((x_1, f(x_1)), (x_2, f(x_2))\)を結ぶ線分\(g(x)\)が凾数\(f(x)\)の上側にあるので，\(f(x)\)は凸凾数(下に凸の凾数)である． 

凸凾数(下に凸の凾数)にかかる線分\(g(x)\)の式

$$ \begin{eqnarray} x_t&=&\left(1-t\right)x_1+tx_2\;\left(ただし 0\leq t \leq 1\right) \;\cdots\;x_1x_2間を単位としx_1を基準点とするtを用いたxの表現となる. \\&=&\sum_{i=1}^{2}\phi_ix_i\;\cdots\;\phi_i=\left\{1-t,\;t\right\}で，0\leq\phi_iかつ\sum_{i=1}^{2}\phi_i=1 \\ \\ \\ g(x)-f(x_1)&=&\frac{f(x_2)-f(x_1)}{x_2-x_1}\left(x-x_1\right) \;\cdots\;傾きが\frac{f(x_2)-f(x_1)}{x_2-x_1}で点(x_1, f(x_1))を通る直線の方程式 \\g(x)&=&\frac{f(x_2)-f(x_1)}{x_2-x_1}\left(x-x_1\right)+f(x_1) \\&=&\frac{f(x_2)-f(x_1)}{x_2-x_1}\left(x_t-x_1\right)+f(x_1)\;\cdots\;xをtで表現するx_tとする \\&=&\frac{f(x_2)-f(x_1)}{x_2-x_1}\left\{\left(1-t\right)x_1+tx_2-x_1\right\}+f(x_1)\;\cdots\;x_t=\left(1-t\right)x_1+tx_2 \\&=&\frac{f(x_2)-f(x_1)}{x_2-x_1}\left(x_1-tx_1+tx_2-x_1\right)+f(x_1) \\&=&\frac{f(x_2)-f(x_1)}{x_2-x_1}\left(-tx_1+tx_2\right)+f(x_1) \\&=&\frac{f(x_2)-f(x_1)}{x_2-x_1}t\left(x_2-x_1\right)+f(x_1) \\&=&\left\{f(x_2)-f(x_1)\right\}t+f(x_1) \\&=&tf(x_2)-tf(x_1)+f(x_1) \\&=&tf(x_2)+\left(1-t\right)f(x_1) \\&=&\left(1-t\right)f(x_1)+tf(x_2) \\&=&\sum_{i=1}^{2}\phi_if(x_i)\;\cdots\;\phi_i=\left\{1-t,\;t\right\}で，0\leq\phi_iかつ\sum_{i=1}^{2}\phi_i=1 \end{eqnarray} $$

---

数学的帰納法によるイェンセンの不等式の証明

\(n=2\)の証明

$$ \begin{eqnarray} g(x_t)&\geq&f(x_t)\;\cdots\;凸凾数(下に凸の凾数)の性質よりg(x)がf(x)より上側にある. \\\left(1-t\right)f(x_1)+tf(x_2)&\geq&f\left(\left(1-t\right)x_1+tx_2\right)\;\cdots\;x_t=\left(1-t\right)x_1+tx_2 \\\sum_{i=1}^{2}\phi_if(x_i)&\geq&f\left(\sum_{i=1}^{2}\phi_ix_i\right)\;\cdots\;n=2の証明. \end{eqnarray} $$

\(n=k\)を認める状況で\(n=k+1\)を証明

\(n=k+1\)の式を変形していく． $$ \begin{eqnarray} \sum_{i=1}^{k+1}\theta_if(x_i) &=&\sum_{i=1}^{k}\theta_if(x_i)+\theta_{k+1}f(x_{k+1})\;\cdots\;0\leq\theta_iかつ\sum_{i=1}^{k+1}\theta_i=1 \\&=&\Theta_k\sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}f(x_i)+\theta_{k+1}f(x_{k+1}) \;\cdots\;\Theta_k=\sum_{i=1}^{k}\theta_i=1-\theta_{k+1}\lt1,\;\sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}=\frac{1}{\Theta_k}\sum_{i=1}^{k}\theta_i=1 \\&\geq&\Theta_k f\left(\sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}x_i\right)+\theta_{k+1}f(x_{k+1}) \;\cdots\;n=kは認めるので\left(\sum_{i=1}^{k}\phi_if(x_i)\geq f\left(\sum_{i=1}^{k}\phi_ix_i\right)\right),\; \sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}f(x_i)\geq f\left(\sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}x_i\right). \end{eqnarray} $$

\(n=2\)の式としてみる． $$ \begin{eqnarray} \Theta_k f\left(\sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}x_i\right)+\theta_{k+1}f(x_{k+1}) &=&\lambda_1 f\left(a_1\right)+\lambda_2 f(a_2) \;\cdots\; \lambda_j=\left\{ \Theta_k,\;\theta_{k+1} \right\} ,\;a_j=\left\{ \sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}x_i,\;x_{k+1} \right\} \\&=&\sum_{j=1}^{2}\lambda_j f(a_j) \\&\geq&f\left( \sum_{j=1}^2\lambda_j a_j \right) \;\cdots\;n=2は上記で証明済み. \end{eqnarray} $$

\(\sum_{j=1}^{2}\lambda_j a_j\)を変形していく． $$ \begin{eqnarray} \sum_{j=1}^{2}\lambda_j a_j &=&\Theta_k \sum_{i=1}^{k}\frac{\theta_i}{\Theta_k}x_i + \theta_{k+1} x_{k+1} \\&=&\Theta_k\frac{1}{\Theta_k} \sum_{i=1}^{k}\theta_ix_i + \theta_{k+1} x_{k+1} \;\cdots\;\sum_{i=1}^n Cx_i=C\sum_{i=1}^nx_i \\&=&\sum_{i=1}^{k}\theta_ix_i + \theta_{k+1} x_{k+1} \\&=&\sum_{i=1}^{k+1}\theta_ix_i \end{eqnarray} $$

変形結果を戻す．

$$ \begin{eqnarray} f\left( \sum_{j=1}^2\lambda_j a_j \right) &=&f\left( \sum_{i=1}^{k+1}\theta_ix_i \right) \end{eqnarray} $$

以上より\(n=k\)を認めれば\(n=k+1\)でもイェンセンの不等式が成り立つ. $$ \begin{eqnarray} \sum_{i=1}^{k+1}\theta_if(x_i)&\geq&f\left( \sum_{i=1}^{k+1}\theta_ix_i \right) \end{eqnarray} $$

\(n=2\)及び\(n=k+1\)の証明からの結論

数学的帰納法によりイェンセンの不等式が成り立つ.