間違った分布で驚く：$D$ が余分な驚きとして現れる

相対エントロピーから情報と物理を組み立てる　第1部 第2章 §1.2.5　★★★ 真の分布 $p$ の系列を別の分布 $q$ で評価すると、1文字あたりの驚きは $H(p)+D(p\,\|\,q)$ に集まる。この巻で $D$ が最初に現れる場所

比べる2つの分布

ここまでは、系列を生む分布と、驚きを計算する分布が同じ $p$ だった。実際には、情報源の本当の分布 $p$ は分からず、手元のモデル $q$ で確率を見積もることが多い。たとえば英文の圧縮器は、英文の文字の頻度について何らかの仮定 $q$ を持って符号を作る。このとき、$p$ から出た系列を $q$ で評価した1文字あたりの驚き$-\frac1n\ln q^n(X^n)$ がどこへ集まるかを調べる。この節が比べる2つの分布は、真の分布 $p$ と仮定した分布 $q$ である。

右辺の $-\sum_xp(x)\ln q(x)$ を交差エントロピーと呼ぶ（機械学習の損失関数の名前でもある）。式 (1.2.15) は、分布を取り違えると平均の驚きが $D(p\,\|\,q)$ だけ増えることを言っている。$q=u$ なら $-\sum p\ln u=\ln\lvert \mathcal X\rvert$ なので、式 (1.2.6) に戻る。次の章で示す $D(p\,\|\,q)\ge0$（等号は $q=p$ のときに限る）を使うと、交差エントロピーを最小にする $q$ は真の分布 $p$ そのものである。平均して最も驚かずに済むのは、正しい分布で予想したときに限る。この性質が、最尤推定（第1部第7章）と最大エントロピー原理（第2部第1章）の両方の出発点になる。

図 1.2.4　真の分布 $p(1)=0.1$ の系列を $q$ で評価したときの、1文字あたりの驚きの収束先 $H(p)+D(p\,\|\,q)$（実線）。$q=p$ で最小値 $H(p)$（点線）に接し、そこからの高さが $D(p\,\|\,q)$ である。

$q$ のもとで $p$ の典型集合が出る確率

取り違えた結果をもう1つの向きから見る。$p$ の典型集合 $A_\epsilon^{(n)}$ に入る系列が、$q$ のもとでどれくらいの確率で出るかを考える。$p$ にとって典型で、しかも $q$ で評価した驚きも式 (1.2.15) の値に近い系列の集合を

$$B_\epsilon^{(n)}=\Bigl\{x^n\in A_\epsilon^{(n)}:\ \Bigl|-\frac1n\ln q^n(x^n)-H(p)-D(p\,\|\,q)\Bigr|\le\epsilon\Bigr\}$$

とする。定理 1.2.8 から $p$ のもとでの確率は $n\to\infty$ で $1$ に近づき、元の数は $\lvert A_\epsilon^{(n)}\rvert \le\mathrm{e}^{n(H+\epsilon)}$ 以下である。$B_\epsilon^{(n)}$ の元の $q$ のもとでの確率は $\mathrm{e}^{-n(H+D-\epsilon)}$ 以下なので

$$q^n\bigl(B_\epsilon^{(n)}\bigr)\le\mathrm{e}^{n(H+\epsilon)}\,\mathrm{e}^{-n(H+D-\epsilon)}=\mathrm{e}^{-n(D(p\,\|\,q)-2\epsilon)}\tag{1.2.16}$$

となる。$p$ から出たように見える系列を $q$ が出す確率は、$n$ について $\mathrm{e}^{-nD(p\,\|\,q)}$ の速さで小さくなる。下からも同じ指数で押さえられることは定理 1.2.6 (c) と同じ手順で示せる。2つの仮説 $p,q$ のどちらから出た系列かを判定するとき、誤って $q$ を $p$ と見なす確率の減り方の指数が $D$ である、という Stein の補題の中身がこれで、第1部第8章で正確に述べる。