わからなかったこと

Newman (2018) の序盤で，

Employing the well-known Jensen inequality
$$\log\sum_i x_i \ge \sum_i q_i \log\frac{x_i}{q_i}$$

とあるが，この形のイェンセンの不等式がどう導かれるのかわからず，本題に入る前から躓いていた．

不等式の導出

そもそも上記の不等式は，イェンセンの不等式ではなかった．対数和不等式 (log sum inequality) というらしい．対数和不等式は $f(x) = x\log x$ にイェンセンの不等式を用いて導くことができる．導出には，以下のサイトを参照した．

イェンセンの不等式

$f(x)$ が凸関数のとき，任意の実数 $x_1,\ldots, x_n$ と $\sum_i \lambda_i = 1$ を満たす任意の非負の実数 $\lambda_1,\ldots, \lambda_n$ について，

\sum_i^n \lambda_if(x_i) \ge f\left(\sum_i^n \lambda_i x_i \right)

が成り立つ．つまり，関数 $f$ のアウトプットの加重平均は，インプットの加重平均を与えた時のアウトプットの値以上であるという不等式である．この不等式の両辺に $-1$ をかけた

-\sum_i^n \lambda_if(x_i) \le -f\left(\sum_i^n \lambda_i x_i \right)

という関係を以下で使用する．

対数和不等式

$f(x) = x\log x~~(x > 0)$ について，$f'(x) = \log x + 1, ~~ f''(x) = x^{-1}$ より，$f(x)$ は凸関数である．任意の正の実数 $x_1,\ldots, x_n$ と $\sum_i q_i = 1$ を満たす任意の非負の実数 $q_1,\ldots, q_n$ を考える．$\lambda_i = x_i/\sum_i x_i$ とすると，対数和不等式の右辺は，

\begin{align}
\sum_iq_i\log\frac{x_i}{q_i} &= -\sum_iq_i\log\frac{q_i}{x_i} \\
&= -\sum_i x_i\frac{q_i}{x_i}\log\frac{q_i}{x_i} \\
&= -\sum_i x_i f\left(\frac{q_i}{x_i}\right) \\
&= -\sum_i \lambda_i\left(\sum_i x_i\right) f\left(\frac{q_i}{x_i}\right) \\
&= -\left(\sum_i x_i\right)\sum_i \lambda_i f\left(\frac{q_i}{x_i}\right) \\
& \le -\left(\sum_i x_i\right)f\left(\sum_i\lambda_i\frac{q_i}{x_i}\right) \\
&= -\left(\sum_i x_i\right)f\left(\frac{\sum_iq_i}{\sum_ix_i}\right) \\
&= -\left(\sum_i x_i\right)f\left(\frac{1}{\sum_ix_i}\right) \\
&= -\left(\sum_i x_i\right)\frac{1}{\sum_ix_i}\log\frac{1}{\sum_ix_i} \\
&= -(-1)\log\sum_ix_i \\
&= \log\sum_ix_i.
\end{align}

最初と最後を比べると，途中で $\le$ を挟んで対数和不等式となっていることが確認できる．