Information Theory

Report
前回の復習
情報をコンパクトに表現するための符号化方式を考える
情報源符号化における基礎的な性質
一意復号可能性
クラフトの不等式
瞬時復号可能性
 −1 + ⋯ +  − ≤ 1
ハフマン符号の構成法
D. Huffman
1
ハフマン符号
符号木を再帰的に構成し,符号を作る
A
B
C
D
E
F
A
0.3
B
0.2
C
0.2
確率 符号語
0.3
0.2
0.2
0.1
0.1
0.1
0.1 0.1 0.1
D
E
F
平均符号語長は...
0.3 × + 0.2 × 0.2 ×
+ 0.1 × +0.1 × +0.1 ×
=
2
今日の講義の方向性
情報源符号が目指すべきもの
瞬時復号可能性
クラフトの不等式
 −1 + ⋯ +  − ≤ 1
平均符号語長の最小化
この制約の範囲内で,平均符号語長

 
=1
を最小化することを考える
3
あらすじ
1.
平均符号語長の下界を示す
2.
シャノン・ファノ符号の紹介
「下界に迫る」平均符号語長を持つ符号
ハフマン符号との関係
3.
情報源の拡大と情報源符号化定理
Robert Fano
1917-
4
最初の目標
約束事:
定常無記憶情報源  の発生する記号を一個ずつ符号化
記号は通り,各記号の発生確率は 1, … , 
瞬時復号可能な符号を考え,平均符号語長を  で表す
補題1:平均符号語長は必ず  ≥ 1 () となる
シャノンの補助定理(2回目の講義で紹介)を利用して証明
1 + ⋯ +   1 を満たす非負数  に対し,


− log 2  ≥
=1
− log 2 
=1
5
補題1の証明
補題1:平均符号語長は必ず  ≥ 1 () となる
符号語の長さを 1 , … ,  とし, = 2− とする
 = − log 2 

=
1 + ⋯ + 
= 2−1 + ⋯ + 2− ≤ 1
(クラフトの不等式)
 
(シャノンの補助定理)
=1

=

− log 2 
=1
≥
− log 2  = 1 ()
=1
6
補題1の意味するところ
補題1:平均符号語長は必ず  ≥ 1 () となる
情報源  の発生する記号を符号化するためには,
必ず 1  ビットの平均符号語長が必要
どれだけ高速なコンピュータや,どれだけスゴイ天才が
将来出現しても,1 ()ビットの壁を超えることはできない
エントロピー... 統計的に導かれた「情報理論的な量」
平均符号語長の下界...データ圧縮の限界という「操作的な量」
... 情報理論は,情報に関する「普遍的な物理法則」を与える
7
下界への到達可能性
補題1:平均符号語長は必ず  ≥ 1 () となる
1 ()は,あくまでも平均符号語長の「下界」
次の疑問... どこまで1 ()に迫ることができるのか?
補題2:平均符号語長が < 1() + 1となる符号を構成可能
シャノンとファノが,独立に発見した符号の構成法
⇒ シャノン・ファノ符号
(本講義では,シャノン・ファノ符号のアイデア部分だけを説明)
8
補題2の証明
補題2:平均符号語長が < 1() + 1となる符号を構成可能
5
符号の構成方法:
step 1:  = ⌈− log 2  ⌉として,符号語の 4
長さを決定する
3
step 2: 深さ 1 , … ,  に葉を持つ符号木を 2
構成する
1
step 3: 符号木から符号語を決定する
0
確認すべき事項:
本当に符号木が構成できるのか?
平均符号語長は?
− log 2 
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
⌈⌉…以上の整数

9
補題2の証明(続)
本当に符号木が構成できるのか?
=  はクラフトの不等式を満たすのか?
 = ⌈− log 2  ⌉ より  ≥ − log 2 
さらに変形すると,2− ≤ 2log2  = 
2−1 + ⋯ + 2− ≤ 1 + ⋯ +  = 1
平均符号語長は?
 < − log 2  + 1であることを利用する:

=

  <
=1
 (− log 2  + 1)
=1

=

− log 2  +
=1
 = 1  + 1
=1
10
補題2に関する補足
前スライドの証明では...符号木以降の議論を省略
シャノン・ファノ符号...具体的な符号木の作り方までを規定
確率を 2進数表記したときの,小数部に着目
「証明のために構成された符号」の色合いが強い
「一番効率が良い」わけではない
たとえば, = 2, 1 = 0.9, 2 = 0.1の場合...
シャノン・ファノ符号では,1 = 1, 2 = 4
ハフマン符号では,1 = 1, 2 = 1
11
補題1+2
補題1:平均符号語長は必ず  ≥ 1 () となる
どんな符号を使っても越えられない壁
補題2:平均符号語長が < 1() + 1となる符号を構成可能
シャノン・ファノ符号を使えば,下界に迫ることが可能
ハフマン符号の位置づけは?
vs.
12
ハフマン符号の最適性
最適符号 = 平均符号語長を最小にする瞬時符号可能符号
定理:ハフマン符号は最適符号である
... 予備的な補題 + 数学的帰納法で証明する
補題:ハフマン符号の符号木,最適符号の符号木とも,
確率最小の2記号は,最も深いレベルに兄弟として存在する
子が1個の節点は
...背理法で証明可能(証明略)
存在しないはず
もし,ここの確率が小さければ...
より深いところと交換して,
平均符号語長の削減が可能
13
証明:ハフマン符号は最適符号である
記号数  に関する帰納法で証明する
 = 1のとき ... 自明
 = 以下で定理の成立を仮定, =  + 1の場合を考える
ハフマン
符号の
符号木


平均符号語長
 ≥ opt のはず...
最適符号の
符号木
opt
+1

+1
確率最小の2記号を併合
 − ( + +1 )
 + +1
opt − ( + +1 )
 ≤ opt
したがって  = opt
 + +1
14
補題1+2,改良版
補題1:平均符号語長は必ず  ≥ 1 () となる
どんな符号を使っても越えられない壁
補題2:平均符号語長が < 1() + 1となる符号を構成可能
ハフマン符号を使えば,下界に迫ることが可能
1  ≤ opt = Huffman ≤ Shannon⋅Fano < 1  + 1
15
2ページの例で確認
符号木を再帰的に構成し,符号を作る
平均符号語長は Huffman = 2.5
A
B
C
D
E
F
確率
0.3
0.2
0.2
0.1
0.1
0.1
符号語
00
10
11
010
0110
0111
エントロピーは
  = −0.3 log 2 0.3 − 0.2 log 2 0.2 − ⋯ − 0.1 log 2 0.1 = 2.45
1  ≤ opt = Huffman ≤ Shannon⋅Fano < 1  + 1
2.45
2.5
?
3.45
16
シャノン・ファノ符号の場合
5
4
3
 = ⌈− log 2  ⌉
2
0
− log 2 
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
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
符号語 vs. ハフマン
00
00
010
10
100
11
1011
010
1100
0110
1110
0111
Shannon⋅Fano = 0.3 × 2 + ⋯ + 0.1 × 4
= 3.0
1  ≤ opt = Huffman ≤ Shannon⋅Fano < 1  + 1
2.45
2.5
3.0
3.45
17
ここまでのまとめ
補題1:平均符号語長は必ず  ≥ 1 () となる
どんな符号を使っても越えられない壁
補題2:平均符号語長が < 1() + 1となる符号を構成可能
ハフマン符号を使えば,下界に迫ることが可能
1  ≤ opt = Huffman ≤ Shannon⋅Fano < 1  + 1
この +1 が気になる
18
符号化の単位とブロック化
1個の記号を,1個の符号語に変換する
平均符号語長は,必ず 1以上となる
2元情報源の符号化を考えても,意味がない
A B A C C A
記号
確率 C1 C2
A
0.8
0
1
0 10 0 11 11 0
B
0.2
1
0
1.0 1.0
平均符号語長
複数の記号をまとめて符号化(ブロック符号化)すると...
1記号あたりの平均符号長を1以下にできるかも...
2元情報源の符号化にもチャンスが... A B A C C A
10
1101 01
19
ブロック符号化のイメージ
記号の系列
ABCBCBBCAA...
ブロック化
ブロック化された AB CBC BB CAA...
記号の系列
ハフマン符号化
符号語系列
01 10 001 1101...
(実際には,符号語の間のスペースはナシ...)
20
ブロック符号化の例(2-1)
確率 符号語
0
A 0.8
1
B 0.2
AA
AB
BA
BB
確率 符号語
0.64
0
0.16 10
0.16 110
0.04 111
平均符号語長は
0.8×1 + 0. 2×1 = 1.0
長さ2のブロックを考える
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元情報源でも,効率改善
21
ブロック符号化の例(2-2)
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
長さ3のブロックを考える
AAAの発生確率 = 0.83=0.512 ....
平均符号語長は
0.512×1 +... + 0.008×5 = 2.184
記号1個当たりでは,2.184 / 3 = 0.728
ブロック長 1記号あたり平均符号語長
1
1.0
ブロック長を大きくすると,
2
0.78
1記号あたり平均符号語長は 3
0.728
小さくなる(効率が良くなる)
:
:
22
ブロック符号の平均符号長
ブロック長を大きくすると,1記号あたり平均符号語長は小さくなる
... ただの偶然?
個単位でブロック化した記号=次拡大情報源   の記号1個
⇒ 「記号を 1個ずつ符号化する」場合の
議論が適用できる
ブロック長  のときの平均符号語長を  とすると
平均符号語長は必ず  ≥ 1 (  ) となる
平均符号語長が  < 1   + 1となる符号を構成可能
23
不等式の変形
1   ≤  < 1   + 1
で割る
1  
 1   + 1
≤
<



極限を取る
1  

1   + 1
lim
≤ lim
< lim
→∞
→∞ 
→∞


極限エントロピーで表現する

  ≤
<  +

1記号あたりの平均符号語長
24
情報源符号化定理
情報源に対し,瞬時復号可能な符号を構成する
構成した符号の,1記号あたりの平均符号長をとする

  ≤
<  +

シャノンの情報源符号化定理
【逆定理】  < ()であるような符号は存在しない
【順定理】 が()に限りなく近い符号を構成することができる
25
情報源符号化定理の意味するところ
【逆定理】  < ()であるような符号は存在しない
⇒どれだけブロック長を大きくしても,エントロピーの壁は
越えられない
【順定理】 が()に限りなく近い符号を構成することができる
⇒ブロック長を大きく設定し,ハフマン符号を使えば,
いくらでも下界に近づくことができる
確率 符号語
0
A 0.8
1
B 0.2
H(S) = 0.723
ブロック長 一通報あたり平均符号長
1
1.0
2
0.78
3
0.728
:
:
0.723 + 
26
別視点からの説明
ブロック化すると,どうして効率が良くなるか?
理想的な符号語長は実数値  = −log 2 
1 = 0.8, 2 = 0.2 の場合,理想的な符号語の長さは...
0.81 + 0.22 → min
s.t. 2−1 + 2−2 ≤ 1
1 = − log 2 0.8 ≈ 0.322
2 = − log 2 0.2 ≈ 2.322
現実には,符号語長は整数値しか許されない
シャノン・ファノ符号の場合, = ⌈− log 2  ⌉
⌈− log 2  ⌉
倍になる
符号語長は,理想的な場合の
− log 2 
27
別視点からの説明(続)
15
確率値が大きくなると,
理想と現実のギャップが顕著に 10
⌈− log 2  ⌉
− log 2 
5

0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0
ブロック化すると...
各記号の発生確率が比較的小さくなる
理想と現実の間に多少ギャップがあっても,
「1記号あたり」で考えるために で割れば,影響は小さくなる
28
本日のまとめ
シャノンの情報源符号化定理
【逆定理】  < ()であるような符号は存在しない
【順定理】 が()に限りなく近い符号を構成することができる
情報源をブロック化し,ハフマン符号を使えばよい
理論的に完結しているが,実用上の問題は残る
符号化・復号の(時間・空間)計算量削減
前提条件の緩和(確率分布が未知のケース etc.)
「可逆でない」情報源符号化
⇒ 続きは,III 期の「符号理論」で...
29
練習問題
ハフマン符号を構成するプログラムを作成せよ
さらに,拡大情報源に対して利用できるよう改良せよ
30

similar documents