Information Theory

前回の復習

情報をコンパクトに表現するための符号化方式を考える 情報源符号化における基礎的な性質 一意復号可能性 瞬時復号可能性 ハフマン符号_の構成法 クラフトの不等式 2−𝑙1 + ⋯ + 2−𝑙𝑀 ≤ 1 D. Huffman （2元符号の場合）

前回の練習問題：ハフマン符号

符号木を再帰的に構成し，符号を作る A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1 符号語 A 0.3 B 0.2 C 0.2 D 0.1 E 0.1 F 0.1 平均符号語長は... 0.3 × + 0.2 × 0.2 × + 0.1 × +0.1 × +0.1 × =

今日の講義の方向性

情報源符号が目指すべきもの 瞬時復号可能性 平均符号語長の最小化 クラフトの不等式 2−𝑙1 + ⋯ + 2−𝑙𝑀 ≤ 1 この制約の範囲内で，平均符号語長 𝑝_𝑖𝑙_𝑖 𝑀 𝑖=1 を最小化することを考える

あらすじ

1. 平均符号語長の下界を示す 2. シャノン・ファノ符号の紹介 「下界に迫る」平均符号語長を持つ符号 ハフマン符号との関係 3. 情報源の拡大と情報源符号化定理 Robert Fano 1917-

最初の目標

前回からの「お約束」 定常無記憶情報源 𝑆 の発生する記号を一個ずつ符号化 記号は𝑀通り，各記号の発生確率は 𝑝₁, … , 𝑝_𝑀 瞬時復号可能_{な符号を考え，平均符号語長を} 𝐿 _で表す 補題１：_{平均符号語長は必ず 𝐿 ≥ 𝐻1}(𝑆) となる シャノンの補助定理（２回目の講義で紹介）を利用して証明 −𝑝_𝑖 log₂ 𝑞_𝑖 𝑀 𝑖=1 ≥ −𝑝_𝑖 log₂ 𝑝_𝑖 𝑀 𝑖=1 𝑞₁ + ⋯ + 𝑞_𝑀 1 を満たす非負数 𝑞_𝑖 に対し，

補題１の証明

補題１：_{平均符号語長は必ず 𝐿 ≥ 𝐻1}(𝑆) となる 符号語の長さを 𝑙₁, … , 𝑙_𝑀 とし，𝑞_𝑖 = 2−𝑙𝑖 とする 𝑙_𝑖 = − log₂ 𝑞_𝑖 𝐿 = 𝑝_𝑖𝑙_𝑖 𝑀 𝑖=1 = −𝑝_𝑖 log₂ 𝑞_𝑖 𝑀 𝑖=1 𝑞₁ + ⋯ + 𝑞_𝑀 = 2−𝑙1 + ⋯ + 2−𝑙𝑀 ≤ 1 （クラフトの不等式） ≥ −𝑝_𝑖 log₂ 𝑝_𝑖 𝑀 𝑖=1 = 𝐻₁(𝑆) （シャノンの補助定理）

補題１の意味するところ

補題１：平均符号語長は必ず 𝐿 ≥ 𝐻₁(𝑆) となる 情報源 𝑆 の発生する記号を符号化するためには， 必ず 𝐻₁ 𝑆 ビットの平均符号語長が必要 どれだけ高速なコンピュータや，どれだけスゴイ天才が 将来出現しても，𝐻₁(𝑆)ビットの壁を超えることはできない エントロピー... 統計的に導かれた「情報理論的な量_」 平均符号語長の下界...データ圧縮の限界という「操作的な量_」 ... 情報理論は，情報に関する「普遍的な物理法則」を与える

下界への到達可能性

補題１：平均符号語長は必ず 𝐿 ≥ 𝐻₁(𝑆) となる 𝐻₁(𝑆)は，あくまでも平均符号語長の「下界_」 次の疑問... どこまで𝐻₁(𝑆)に迫ることができるのか？ 補題２：平均符号語長が𝐿 < 𝐻₁(𝑆) + 1となる符号を構成可能 シャノンとファノが，独立に発見した符号の構成法 ⇒ シャノン・ファノ符号 （本講義では，シャノン・ファノ符号のアイデア部分だけを説明）

補題２の証明

補題２：平均符号語長が𝐿 < 𝐻₁(𝑆) + 1となる符号を構成可能 符号の構成方法： step 1: 𝑙_𝑖 = ⌈− log₂ 𝑝_𝑖⌉として，符号語の 長さを決定する step 2: 深さ 𝑙₁, … , 𝑙_𝑀に葉を持つ符号木を 構成する step 3: 符号木から符号語を決定する ⌈𝑥⌉… 𝑥以上の整数 𝑝_𝑖 0 1 2 3 4 5 0 0 .1 ₀.2 ₀.3 ₀.4 ₀.5 ₀.6 ₀.7 ₀.8 ₀.9 1 − log₂ 𝑝_𝑖 確認すべき事項： 本当に符号木が構成できるのか？ 平均符号語長は？ − log₂ 𝑝_𝑖

補題２の証明（続）

本当に符号木が構成できるのか？ ＝ 𝑙_𝑖はクラフトの不等式を満たすのか？ 𝑙_𝑖 = ⌈− log₂ 𝑝_𝑖⌉ より 𝑙_𝑖 ≥ − log₂ 𝑝_𝑖 さらに変形すると，2−𝑙𝑖 ≤ 2log2 𝑝𝑖 = 𝑝 𝑖 2−𝑙1 + ⋯ + 2−𝑙𝑀 ≤ 𝑝 1 + ⋯ + 𝑝𝑀 = 1 𝐿 = 𝑝_𝑖𝑙_𝑖 𝑀 𝑖=1 < 𝑝_𝑖(− log₂ 𝑝_𝑖 + 1) 𝑀 𝑖=1 = −𝑝_𝑖 log₂ 𝑝_𝑖 𝑀 𝑖=1 + 𝑝_𝑖 𝑀 𝑖=1 = 𝐻₁ 𝑆 + 1 平均符号語長は？ 𝑙_𝑖 < − log₂ 𝑝_𝑖 + 1であることを利用する：

補題２に関する補足

前スライドの証明では...符号木以降の議論を省略 シャノン・ファノ符号...具体的な符号木の作り方までを規定 確率を 2進数表記したときの，小数部に着目 「証明のために構成された符号」の色合いが強い 「一番効率が良い」わけではない たとえば，𝑀 = 2, 𝑝₁ = 0.9, 𝑝₂ = 0.1の場合... シャノン・ファノ符号では，𝑙₁ = 1, 𝑙₂ = 4 ハフマン符号では，𝑙₁ = 1, 𝑙₂ = 1

補題１＋２

補題１：_{平均符号語長は必ず 𝐿 ≥ 𝐻1}(𝑆) となる どんな符号を使っても越えられない壁 補題２：平均符号語長が𝐿 < 𝐻₁(𝑆) + 1となる符号を構成可能 シャノン・ファノ符号を使えば，下界に迫ることが可能 ハフマン符号の位置づけは？ vs.

ハフマン符号の最適性

最適符号 _＝ 平均符号語長を最小にする瞬時符号可能_符号 定理：ハフマン符号は最適符号である ... 予備的な補題 ＋ 数学的帰納法で証明する 補題：ハフマン符号の符号木，最適符号の符号木とも， 確率最小の2記号は，最も深いレベルに兄弟として存在する ...背理法で証明可能（証明略） もし，ここの確率が小さければ... より深いところと交換して， 子が1個の節点は 存在しないはず

証明：ハフマン符号は最適符号である

記号数 𝑀 に関する帰納法で証明する 𝑀 = 1のとき ... 自明 𝑀 = 𝑁以下で定理の成立を仮定，𝑀 = 𝑁 + 1の場合を考える ハフマン 符号の 符号木 最適符号の 符号木 𝑝_𝑁 + 𝑝_𝑁+1 𝑝_𝑁 𝑝_𝑁+1 𝐿 𝑝_𝑁 𝑝_𝑁+1 𝐿_opt 𝑝_𝑁 + 𝑝_𝑁+1 𝐿 − (𝑝_𝑁 + 𝑝_𝑁+1) 𝐿_opt − (𝑝_𝑁 + 𝑝_𝑁+1) これより 𝐿 ≤ 𝐿_opt したがって 𝐿 = 𝐿_opt 平均符号語長 𝐿 ≥ 𝐿_opt のはず... 記号数 𝑁 + 1 記号数 𝑁 確率最小の2記号を併合

補題１＋２，改良版

補題１：_{平均符号語長は必ず 𝐿 ≥ 𝐻1}(𝑆) となる どんな符号を使っても越えられない壁

補題２：平均符号語長が𝐿 < 𝐻₁(𝑆) + 1となる符号を構成可能

ハフマン符号_{を使えば，下界に迫ることが可能}

2ページの例で確認

符号木を再帰的に構成し，符号を作る 平均符号語長は 𝐿_Huffman = 2.5

エントロピーは

𝐻 𝑆 = −0.3 log₂ 0.3 − 0.2 log₂ 0.2 − ⋯ − 0.1 log₂ 0.1 = 2.45

A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1 符号語 00 10 11 010 0110 0111

𝐻₁ 𝑆 ≤ 𝐿_opt = 𝐿_Huffman ≤ 𝐿_{Shannon⋅Fano} < 𝐻₁ 𝑆 + 1

シャノン・ファノ符号の場合

A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1 𝑙_𝑖 2 3 3 4 4 4 𝑝_𝑖 0 1 2 3 4 5 0 0 .1 0 .2 0 .3 0 .4 0 .5 0 .6 0 .7 0 .8 0 .9 1 − log₂ 𝑝_𝑖 𝑙_𝑖 = ⌈− log₂ 𝑝_𝑖⌉ 符号語 00 010 100 1011 1100 1110 ハフマン 00 10 11 010 0110 0111 vs. 𝐿_{Shannon⋅Fano} = 0.3 × 2 + ⋯ + 0.1 × 4 = 3.0

𝐻₁ 𝑆 ≤ 𝐿_opt = 𝐿_Huffman ≤ 𝐿_{Shannon⋅Fano} < 𝐻₁ 𝑆 + 1

ここまでのまとめ

補題１：_{平均符号語長は必ず 𝐿 ≥ 𝐻1}(𝑆) となる どんな符号を使っても越えられない壁

補題２：平均符号語長が𝐿 < 𝐻₁(𝑆) + 1となる符号を構成可能

ハフマン符号_{を使えば，下界に迫ることが可能}

𝐻₁ 𝑆 ≤ 𝐿_opt = 𝐿_Huffman ≤ 𝐿_{Shannon⋅Fano} < 𝐻₁ 𝑆 + 1

「お約束」を破る：符号化の単位とブロック化

1個の記号を，1個の符号語に変換する 平均符号語長は，必ず 1以上となる 2元情報源の符号化を考えても，意味がない A 0 B 10 A 0 C 11 C 11 A 0 記号 A B 平均符号語長 確率 0.8 0.2 C₁ 0 1 1.0 C₂ 1 0 1.0 複数の記号をまとめて符号化（ブロック符号化_{）すると...} 1記号あたりの平均符号長を１以下にできるかも... 2元情報源の符号化にもチャンスが... A B 10 A C C 1101 A 01

ブロック符号化のイメージ

記号の系列 ブロック化 ABCBCBBCAA... AB CBC BB CAA... ハフマン符号化 01 10 001 1101... ブロック化された 記号の系列 符号語系列 （実際には，符号語の間のスペースはナシ...）

ブロック符号化の例（２－１）

平均符号語長は 0.8×1 + 0. 2×1 = 1.0 A B 確率 0.8 0.2 符号語 0 1 AA AB BA BB 確率 0.64 0.16 0.16 0.04 符号語 0 10 110 111 長さ２のブロックを考える AAの発生確率 = 0.8×0.8=0.64 .... 平均符号語長は 0.64×1 + 0.16×2 + ... + 0.04×3 = 1.56 記号1個当たりでは，1.56 / 2 = 0.78 ⇒ 2元情報源でも，効率改善

ブロック符号化の例（２－２）

長さ３のブロックを考える AAAの発生確率 = 0.83_{=0.512 ....} 平均符号語長は 0.512×1 +... + 0.008×5 = 2.184 記号1個当たりでは，2.184 / 3 = 0.728 AAA AAB ABA ABB BAA BAB BBA BBB 確率 0.512 0.128 0.128 0.032 0.128 0.032 0.032 0.008 符号語 0 100 101 11100 110 11101 11110 11111 ブロック長 1 2 3 : 1記号あたり平均符号語長 1.0 0.78 0.728 : ブロック長を大きくすると， 1記号あたり平均符号語長は 小さくなる（効率が良くなる）

ブロック符号の平均符号長

ブロック長を大きくすると，1記号あたり平均符号語長は小さくなる ... ただの偶然? 𝑛個単位でブロック化した記号＝𝑛次拡大情報源 𝑆𝑛_{の記号１個} ⇒ 「記号を 1個ずつ符号化する」場合の 議論が適用できる ブロック長 𝑛 のときの平均符号語長を 𝐿_𝑛 とすると 平均符号語長は必ず 𝐿_𝑛 ≥ 𝐻₁(𝑆𝑛) となる 平均符号語長が 𝐿_𝑛 < 𝐻₁ 𝑆𝑛 + 1となる符号を構成可能

不等式の変形

𝐻₁ 𝑆𝑛 ≤ 𝐿_𝑛< 𝐻₁ 𝑆𝑛 + 1 𝑛で割る 極限を取る 𝐻₁ 𝑆𝑛 𝑛 ≤ 𝐿_𝑛 𝑛 < 𝐻₁ 𝑆𝑛 + 1 𝑛 lim 𝑛→∞ 𝐻₁ 𝑆𝑛 𝑛 ≤ lim𝑛→∞ 𝐿_𝑛 𝑛 < lim𝑛→∞ 𝐻₁ 𝑆𝑛 + 1 𝑛 𝐻 𝑆 ≤ 𝐿𝑛 𝑛 < 𝐻 𝑆 + 𝜖 極限エントロピーで表現する 1記号あたりの平均符号語長

情報源符号化定理

情報源𝑆に対し，瞬時復号可能な符号を構成する 構成した符号の，1記号あたりの平均符号長を𝐿とする 𝐻 𝑆 ≤ 𝐿𝑛 𝑛 < 𝐻 𝑆 + 𝜖 シャノンの情報源符号化定理 【逆定理】 𝐿 < 𝐻(𝑆)であるような符号は存在しない 【順定理】 𝐿が𝐻(𝑆)に限りなく近い符号を構成することができる

情報源符号化定理の意味するところ

【逆定理】 𝐿 < 𝐻(𝑆)であるような符号は存在しない ⇒どれだけブロック長を大きくしても，エントロピーの壁は 越えられない 【順定理】 𝐿が𝐻(𝑆)に限りなく近い符号を構成することができる ⇒ブロック長を大きく設定し，ハフマン符号を使えば， いくらでも下界に近づくことができる A B 確率 0.8 0.2 符号語 0 1 ブロック長 1 2 3 : 一通報あたり平均符号長 1.0 0.78 0.728 : 0.723 + 𝜖 H(S) = 0.723

別視点からの説明

ブロック化すると，どうして効率が良くなるか？ 理想的な符号語長は実数値 _𝑙𝑖 = −log₂ 𝑝_𝑖 𝑝₁ = 0.8, 𝑝₂ = 0.2 の場合，理想的な符号語の長さは... 現実には，符号語長は整数値しか許されない シャノン・ファノ符号の場合，𝑙_𝑖 = ⌈− log₂ 𝑝_𝑖⌉ 0.8𝑙₁ + 0.2𝑙₂ → min s.t. 2−𝑙1 + 2−𝑙2 ≤ 1 𝑙₁ = − log₂ 0.8 ≈ 0.322 𝑙₂ = − log₂ 0.2 ≈ 2.322 符号語長は，理想的な場合の ⌈− log2 𝑝𝑖⌉ − log₂ 𝑝_𝑖 倍になる

別視点からの説明（続）

確率値が大きくなると， 理想と現実のギャップが顕著に 0 5 10 15 0 0 .1 ₀.2 ₀.3 ₀.4 ₀.5 ₀.6 ₀.7 ₀.8 ₀.9 1 ⌈− log₂ 𝑝_𝑖⌉ − log₂ 𝑝_𝑖 𝑝_𝑖 ブロック化すると... 各記号の_{発生確率が比較的小さくなる} 理想と現実の間に多少ギャップがあっても， 「1記号あたり」で考えるために 𝑛で割れば，影響は小さくなる

本日のまとめ

シャノンの情報源符号化定理 【逆定理】 𝐿 < 𝐻(𝑆)であるような符号は存在しない 【順定理】 𝐿が𝐻(𝑆)に限りなく近い符号を構成することができる 情報源をブロック化し，ハフマン符号を使えばよい 理論的には完結しているが，実用上の問題は残る 符号化・復号の（時間・空間）計算量削減 前提条件の緩和（確率分布が未知のケース etc.） 「可逆でない」情報源符号化 ⇒ 続きは，III 期の「符号理論」で...

練習問題

ハフマン符号を構成するプログラムを作成せよ