2015/09/29

対数和不等式の証明と応用


対数和不等式(Log sum inequality)
$a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_n$ を正の数とするとき,
$\sum a_k\log\dfrac{a_k}{b_k}\geq(\sum a_k)\log\dfrac{\sum a_k}{\sum b_k}$

主に情報理論で活躍する不等式です。この記事では $\displaystyle\sum_{k=1}^n$ のことを $\sum$ と書きます。

対数和不等式の証明

$f(x)=x\log x$ にイェンゼンの不等式を用いるだけです!

$f(x)=x\log x$ は入試でも頻出の重要な関数です。凸であることは覚えておきましょう。→xlogxの極限,グラフ,積分など

証明

$f(x)=x\log x$ とおくと,$f(x)$ の微分は $\log x+1$,二階微分は $\dfrac{1}{x}$ なので $f(x)$ は $x> 0$ で凸関数である。

ここで,$\dfrac{b_k}{\sum b_k}=\lambda_k$ とおくと対数和不等式の左辺は
$\sum a_k\log\dfrac{a_k}{b_k}\\
=\sum b_k\dfrac{a_k}{b_k}\log\dfrac{a_k}{b_k}\\
=(\sum b_k)\sum \lambda_k f\left(\dfrac{a_k}{b_k}\right)$
となる。これにイェンゼンの不等式を用いると,
(上式)
$\geq (\sum b_k)f\left(\sum\lambda_k\dfrac{a_k}{b_k}\right)\\
=(\sum b_k)f\left(\dfrac{\sum a_k}{\sum b_k}\right)\\
=(\sum a_k)\log \dfrac{\sum a_k}{\sum b_k}$
となり目標の式を得る。

等号成立条件は(イェンゼンの不等式の等号成立条件より)$\dfrac{b_1}{a_1}=\dfrac{b_2}{a_2}=\cdots=\dfrac{b_n}{a_n}$ です。

ちなみに,$a_k,b_k$ の中に $0$ がある場合にも($0\log\dfrac{0}{b_k}=0$,$a_k\log\dfrac{a_k}{0}=\infty\:(a_k\neq 0)$ とみなすことで)対数和不等式は拡張できます。

KLダイバージェンスの非負性

対数和不等式の応用例です。

ギブスの不等式:
$\sum p_k=\sum q_k=1$,$p_k,q_k$ が非負のとき,
$D(P\| Q)=\sum p_k\log\dfrac{p_k}{q_k}\geq 0$

$D(P\| Q)$ はカルバック–ライブラー情報量,Kullback–Leibler divergenceなどと呼ばれる重要な量です。二つの確率分布 $P,Q$ の間の距離のようなもの(厳密には距離ではありません)です。

証明

対数和不等式で $a_k=p_k,b_k=q_k$ とすればよい。 $\sum p_k=\sum q_k=1$ を使うと右辺は $0$ になる。

ちなみに $D(P\|Q)\geq 0$ の等号成立条件は全ての $k$ について $p_k=q_k$ であること,つまり二つの確率分布が等しいことです。

ギブスの不等式は入試でもまれに登場します。→有名不等式logx≦x-1の証明と入試問題

エントロピー最大の分布

$\sum p_k=1$,$p_k$ が非負のとき,
$H(P)=-\sum p_k\log p_k\leq \log n$

等号成立条件は $p_1=p_2=\cdots=p_n$,つまり $P$ が一様分布のときです。

$H(P)$ はエントロピーと呼ばれる重要な量です。

証明

ギブスの不等式を変形すると,
$-\sum p_k\log p_k\leq -\sum p_k\log q_k$

ここで,$q_k=\dfrac{1}{n}\:(k=1,2,\cdots,n)$ とすると右辺は $\log n$ となる。

今日のネタは情報理論に強い知人のN氏によるものです,感謝!