比べる2つの分布：情報源の $p$ と符号の $q_C$

相対エントロピーから情報と物理を組み立てる　第1部 第5章 §1.5.1　★★★ 符号を定義し、符号語の長さから分布 $q_C$ を作る。符号が「どの記号が出やすいか」の見込みを持っていることを式にする

手元に記号の列があり、それを $0$ と $1$ の列に直して保存したい。記号ごとに $0$ と $1$ の列（符号語）を1つずつ割り当てるとき、よく出る記号に短い符号語を、まれな記号に長い符号語を割り当てれば、列全体は短くなる。どこまで短くできるか、というのがこの章の問いである。答えは「1記号あたり平均で $H(X)/\ln 2$ ビットまで、それより短くはできない」で、Shannon がこれを示した¹1C. E. Shannon (1948), Bell System Technical Journal 27, 379–423, 623–656.下の脚注へ閉じる。この章では、この答えを相対エントロピーの非負性からそのまま出す。

鍵になるのは、符号語の長さ $\ell(x)$ の並びを確率分布 $q_C(x)\propto 2^{-\ell(x)}$ に読み替えることである。長さ $\ell$ の符号語を記号 $x$ に割り当てることは、「$x$ の確率はおよそ $2^{-\ell}$ だ」と見込むことと同じになる。そう読み替えると、平均の符号長は

$$(\ln 2)\times(\text{平均の符号長})=H(p)+D(p\,\|\,q_C)-\ln K(C)$$

と3つの項に分かれる（$K(C)\le1$ は後で定義する Kraft 和）。第1項は情報源だけで決まり、第2項と第3項はどちらも $0$ 以上なので、平均の符号長は $H(p)/\ln2$ ビットを下回ることはない。第2項は、符号が見込んだ分布 $q_C$ と本当の分布 $p$ のずれの代価である。この分解によって、相対エントロピー $D(p\,\|\,q)$ は「分布を取り違えて符号を作ると、1記号あたり $D/\ln2$ ビット余分にかかる」という操作的な意味を持つ。

この章の型は第1部の他の章と同じで、比べる2つの分布（情報源の $p$ と符号の $q_C$。1.5.1節）、$q_C$ が確率分布になる理由（Kraft–McMillan の不等式。1.5.2節）、当てる性質（$D$ の非負性。1.5.3節）、出てくるもの（最適な符号を作る Huffman の方法と、ブロックにして限界 $H$ に近づく情報源符号化定理。1.5.4節・1.5.5節）の順に進み、最後に情報理論の授業での書き方と並べる（1.5.6節）。

この章では、符号の長さを数える都合で符号長をビットで測る。エントロピー $H$ と相対エントロピー $D$ はこの巻の流儀どおり自然対数（nat）で書くので、ビットに直した値は $H(X)/\ln2$、$D(p\,\|\,q)/\ln2$ の形で現れる。$\log_2$ は2を底とする対数である。

情報源と符号

情報源とは、有限集合 $\mathcal X$ に値をとる確率変数 $X$ のことで、その分布を $p(x)$ と書く。$\mathcal X$ の元を記号と呼ぶ。同じ分布に従う独立な記号が次々に出てくる情報源を無記憶情報源と呼び、この章ではこれだけを扱う。$0$ と $1$ を有限個並べた列（空の列も含む）の全体を $\{0,1\}^*$ と書く。

符号が使い物になるためには、受け取った $0$ と $1$ の列から元の記号の列がただ1通りに戻らなければならない。この要求には強さの違う2つの段階がある。

語頭符号は一意に復号することができる。受け取った列を頭から読み、符号語の1つと一致した時点で、その記号だと決めてよい。一致した符号語より長い符号語がその頭から始まることはないので、この判断は後の記号を見ても覆らない。この性質から、語頭符号は瞬時符号とも呼ばれる。たとえば $\mathcal X=\{a,b,c,d\}$ に

$$C(a)=0,\quad C(b)=10,\quad C(c)=110,\quad C(d)=111\tag{1.5.2}$$

を割り当てると語頭符号になり、$0110100111$ は頭から $0|110|10|0|111$ と区切れて $acbad$ に戻る。

語頭符号は、根から $0$ と $1$ の枝が出る2分木の葉と1対1に対応する（図 1.5.1）。根から葉までの枝のラベルを読んだものが符号語で、符号語の長さは葉の深さである。どの符号語もほかの符号語の語頭にならないことは、符号語に当てた節点がすべて葉で、どの符号語の節点もほかの符号語の節点の祖先にならないことと同じである。

符号が見込んでいる分布

符号語の長さの並び $\ell(x)$ から、次の量を作る。

$q_C$ は和が $1$ の正の数の並びなので、それだけで確率分布である。1.5.2節では、一意に復号できる符号なら必ず $K(C)\le1$ となることを示す。したがって $2^{-\ell(x)}$ そのものが、和が $1$ 以下の「確率の割り振り」になっている。

この読み替えには次の中身がある。語頭符号の符号の木の根から、各分かれ道で $0$ と $1$ を確率 $\tfrac12$ ずつで選んで降りていくと、深さ $\ell$ の葉に着く確率は $2^{-\ell}$ である。完全な符号の木では、どの分かれ道の先にも葉があるので、この降り方は必ずどこかの葉に着き、着く確率がちょうど $q_C(x)=2^{-\ell(x)}$ になる。逆に言えば、符号の受け手が受け取る $0$ と $1$ が公平な硬貨の列のように見えるのは、記号が $q_C$ どおりに出てくるときである。符号を設計する人は、短い符号語を当てた記号ほど出やすいと見込んでいて、その見込みを確率分布の形で書いたものが $q_C$ である。こうして、この章で比べる2つの分布がそろう。1つは情報源が実際に従う分布 $p$、もう1つは符号が見込んでいる分布 $q_C$ である。

1　C. E. Shannon (1948), Bell System Technical Journal 27, 379–423, 623–656.