授業で習った形との対応

相対エントロピーから情報と物理を組み立てる　第1部 第5章 §1.5.6　★★ 教科書の「$L\ge H$ の証明」「Lagrange 乗数による最適な長さ」「Huffman の表」を、この章の分解式と並べる

エントロピーと平均符号長の不等式

学部の情報理論の授業や教科書では、エントロピーを $2$ を底にして $H(X)=-\sum_ip_i\log_2p_i$ ビットと定義し、平均符号長を $L=\sum_ip_il_i$ と書くことが多い。この記法では、情報源符号化定理の1記号版は

$$H(X)\le L<H(X)+1\qquad(\text{ビット}),\qquad \sum_i2^{-l_i}\le1\tag{1.5.11}$$

と書かれる。この章の記法との対応は、$H_{\text{教科書}}=H(X)/\ln2$、$L=\bar\ell$、$l_i=\ell(x_i)$ である。

(1.5.11) の左の不等式の証明として教科書でよく見るのは、$\ln y\le y-1$ を使う次の計算である。$q_i=2^{-l_i}$ とおくと

$$H-L=\sum_ip_i\log_2\frac{2^{-l_i}}{p_i}=\frac1{\ln2}\sum_ip_i\ln\frac{q_i}{p_i}\le\frac1{\ln2}\sum_ip_i\Bigl(\frac{q_i}{p_i}-1\Bigr)=\frac1{\ln2}\Bigl(\sum_iq_i-1\Bigr)\le0 .$$

途中の $\sum_ip_i\ln(q_i/p_i)\le\sum_iq_i-1$ は、$q$ の和が $1$ のとき $-D(p\,\|\,q)\le0$ そのもので、Gibbs の不等式と呼ばれることもある。この計算は、分解 (1.5.5) の右辺の2つの非負の項（$D(p\,\|\,q_C)$ と $-\ln K$）を、1回の不等式でまとめて捨てたものにあたる。2つを分けて書くと、捨てたものが「分布のずれ」と「木の使い残し」の2種類であることが見える。

Lagrange 乗数で最適な長さを出す

教科書のもう1つの定番は、長さが整数であるという条件を外して、$\sum_ip_il_i$ を $\sum_i2^{-l_i}=1$ のもとで最小にする計算である。Lagrange 関数

$$\mathcal L=\sum_ip_il_i+\lambda\Bigl(\sum_i2^{-l_i}-1\Bigr)$$

を $l_i$ で微分して $0$ とおくと $p_i=\lambda\ln2\cdot2^{-l_i}$ で、制約と $\sum_ip_i=1$ から $\lambda\ln2=1$、すなわち $l_i^*=-\log_2p_i$ を得る。そのときの値は $\sum_ip_il_i^*=H$ ビットである。この章の言葉では、$l_i^*=-\log_2p_i$ は $q_C=p$ と選ぶことで、$D(p\,\|\,q_C)=0$ にする選び方にあたる。長さを整数に戻すと $D=0$ は一般に達成できず、切り上げた Shannon 符号は $1$ ビット未満の代価を、Huffman 符号はその中で最小の代価を払う。

統計学との対応：符号長と対数尤度

統計学の授業では、データ $x_1,\dots,x_n$ に対してモデル $q_\theta$ の対数尤度 $\sum_k\ln q_\theta(x_k)$ を最大にする $\theta$ を最尤推定量と呼ぶ。第1部第3章では、対数尤度の平均が $-H(\hat p)-D(\hat p\,\|\,q_\theta)$ に等しいことから、最尤推定は $D(\hat p\,\|\,q_\theta)$ の最小化と同じだと示した。ここではそれを符号長の言葉で読み直す。この章の言葉では、$-\log_2q_\theta(x)$ は分布 $q_\theta$ を見込んだ符号の（整数に丸める前の）符号長なので、対数尤度を最大にすることは、データを $q_\theta$ 用の符号で書いたときの全長を最小にすることと同じである。最尤推定は「手元のデータを最も短く書ける符号を選ぶ」ことと言い換えることができる。データの経験分布を $\hat p$ とすると、全長は $n\bigl(H(\hat p)+D(\hat p\,\|\,q_\theta)\bigr)/\ln2$ ビットで、第1項は $\theta$ によらないので、最も短く書ける $\theta$ は $D(\hat p\,\|\,q_\theta)$ を最小にする $\theta$ と一致する。推定と相対エントロピーの関係は、第1部第7章（第1部第7章）で Fisher 情報として、第1部第8章（第1部第8章）で大偏差として扱う。