情報理論

前回の練習問題
ABACABADACABADを,LZ77法により符号化せよ
4文字前
長さ3
A
B
AC
2文字前
長さ1
ABAD
ACABAD
6文字前
長さ6
符号語系列は
(0, 0, A), (0, 0, B), (2, 1, C), (4, 3, D), (6, 6, *)
上記問題により得られた符号語系列を復号せよ
4文字前
符号化と逆の手順を行えばよい
長さ3
A
B
AC
2文字前
長さ1
ABAD
ACABAD
6文字前
長さ6
1
前回の練習問題
LZWアルゴリズムの特許に関し,どのような問題が
発生したか調べよ
UNISYS社が特許権を保有していた
当初は特許権の行使をしないと言明 ⇒ 後に方針転換
GIF 画像を扱うソフトウェアの取り扱いに混乱
2003年に米国,2004年に日本での特許失効
非可逆符号化を実現するアルゴリズムにはどのような
ものがあるか調べよ
(アルゴリズムとデータフォーマットの区別が明確でないが)
JPEG, MPEG, GIF 等
2
本日の講義
乱数,擬似乱数について...「情報理論」からは少し寄り道
乱数,擬似乱数
Kolmogorovによる乱数の定義
擬似乱数の統計的検定
x2検定
擬似乱数の生成法
3
乱数とは
乱数,乱数系列(random numbers, random sequence)
広辞苑による記述:
0から9までの数字から無作為復元抽出を繰り返して得られる数
の列.完全に無秩序でかつ全体としては出現の頻度が等しい.
工学の立場からは,上記の記述では不十分
「0から9までの数字」というのは本質的でない
⇒ 0 と 1 だけからなる乱数を考える場合も多い
「完全に無秩序」が,どのような状態を示すのか明確でない
4
「無秩序さ」の定式化
「無秩序さ」:統計的に記述するのが一般的だが...
計算機の出現により,「無秩序さ」にも新しい定式化が出現
有限系列 x を出力するプログラムの集合を (x) とする
プログラム...入力なしの決定性プログラム(毎回同じ動作)
プログラム pの記述長を |p| と書く(文字数,行数等)
x のコルモゴロフ複雑さ(Kolmogorov complexity)
K ( x)  min | p |
p ( x )
(x を出力する最小のプログラムのサイズ)
5
コルモゴロフ複雑さの例(1)
x1 = “0101010101010101010101010101010101010101”... 40文字
x1 を出力するプログラム
プログラムp1 : printf(“010101...01”); ...51文字
プログラム p2 : for(i=0;i<20;i++)printf(“01”); ...30文字
⇒K(x1)  30 < 40
x2 = “0110100010101101001011010110100100100010”... 40文字
x2 を出力するプログラム
プログラムp1 : printf(“011010...10”); ...51文字
⇒K(x2)  51
6
コルモゴロフ複雑さの例(2)
x3 = “11235813213455891442333776109871597...”... 100万文字
x3 を出力するプログラム
プログラムp1 : printf(“1123...”); ...100万+11文字
プログラム p2 :
フィボナッチ数列を計算して出力 ⇒ 数百文字で十分
⇒K(x3) は数百文字以下
コルモゴロフ複雑さ K(x):
x の統計量ではなく,x の持つ構造・規則性の指標となっている
7
コルモゴロフ複雑さと無秩序さ
コルモゴロフ複雑さが大きいほど「無秩序」の程度が大きい
ただし,コルモゴロフ複雑さを実際に計算することは困難
「無秩序さ」を定式化するための概念的なもの
エントロピーとの違いは?
エントロピーは,記号発生の統計的側面だけに着目
コルモゴロフ複雑さは,記号発生のメカニズムも考慮に
8
コルモゴロフ的な乱数の定義
コルモゴロフ複雑さに基づく乱数の定義:
系列 x について,K(x)  |x| のとき,x を乱数(系列)という
x を記述するには,x を「ベタ書き」するしかない
x をコンパクトに表現することができない(圧縮不能)
プログラムもデータも2進系列で表現すると考えると...
長さ n の2進系列...2n 個存在
長さ n 未満の2進系列...2n – 1 個しか存在しない
⇒ 必ず,K(x)  x である系列(圧縮不能な系列)が存在する
⇒ 任意長の(コルモゴロフの意味での)乱数が必ず存在する
9
乱数の存在確率
Vn:長さ n の2進系列集合,|Vn| = 2n, |V1|+ |V2|+...+|Vn–1| = 2n–1
もし,Vn に属する系列のうち 2n – 1 個が圧縮可能だとすると,
V1, ..., Vn–1 に属する系列はいずれも圧縮不能ということになる
サイズn未満のプログラムはすべて,長さ n の系列を出力
1
n–2
n–1
n
n+α
長さ n 未満の系列は,サイズ n以上のプログラムでしか作れない
⇒ ほとんどすべての系列は圧縮不能(乱数である)ことを導ける
10
乱数の計算可能性
ほとんどすべての系列は乱数である:
乱数の存在は保証しているが,具体的な作り方は不明
サイコロを振る,無作為に生成されるデータを利用 etc.
十分に無秩序で良い乱数を得ることができる
大量の乱数を得るには効率が悪い
専用の乱数生成装置を利用
大量の乱数を効率よく生成できる
特殊なハードウェアが必要でコスト高
真の乱数(真性乱数)を,大量かつ安価に生成するのは困難
11
擬似乱数
擬似乱数 (pseudorandom numbers):
ある種の規則性にしたがって生成される「乱数のようなもの」
コルモゴロフ的な意味での乱数ではない
コンピュータプログラム等により,大量かつ安価に生成可能
⇒ 各種の実験やシミュレーション等の実施に有益
擬似乱数にも良いものと悪いものがある
⇒ 各種の検定により,擬似乱数の品質を評価することが必要
(検定法を頭に入れた後で,具体的な擬似乱数生成法を学ぶ)
12
統計的検定
擬似乱数の評価尺度:
予測が困難か?
暗号等の用途では重要だが,評価が難しい
十分に無秩序か?
数列の統計的性質を検定すれば良い...比較的容易
本講義では,統計的検定法について紹介
「あるプログラムから生成された十分長い系列が,
どれだけ真性乱数に近い統計的性質を有するか」を議論
「特定の系列が乱数か否か」を判定する問題ではない
13
復習:確率,確率密度関数
確率変数:ある試行にともなって,なんらかの値を取る変数
確率分布:
確率変数が,どの確率でどの値を取るかをあらわしたモノ
確率変数が離散的な場合,確率分布は表の形で与えられる
確率変数が連続的な場合,確率分布は関数により与えられる
晴
曇
雨
雪
0.3
0.4
0.2
0.1
確率密度関数
14
確率密度関数について
=
確率密度関数(probability density function, pdf )
連続的な確率変数の確率分布を表現する関数
y
確率変数が x 以上 y 未満の値を取る確率= x f (t )dt
ここの面積
x
y
x → 最小値,y → 最大値のとき,面積=1
15
x2値の定義
確率変数Xの取る値を,有限個のクラス C1, C2, ..., Cl に分割する
たとえば X が 0 から 100 の値を取る場合...
C1 = [0, 10), C2 = [10, 30), C3 = {30以上の偶数}, C4 =その他
理想的なケースにおいて,X が Ci に属する確率は pi とする
実際に観測された値の系列を a = a1, a2, ... an とする
系列 a が,どれだけ理想に近いか評価したい
⇒ 以下の x2 値(x2 value, Chi square value)を評価すれば良い
(カイ2乗値)
2
l
(
n

np
)
i
x2   i
npi
i 1
ni...系列 a において Ci に属する要素の個数
16
x2値の解釈
ni...系列 a において Ci に属する要素の個数
npi...長さnの理想的系列における ni の期待値
2
(
n

np
)
i
x2   i
npi
i 1
l
系列 a が理想的な系列に近ければ...
⇒ 分子部分は 0 に近づく
⇒ x2 値も 0 に近づく
17
x2値の計算例
1, 2, ...6 からなる42文字の系列(n = 42)を考える
これが真性乱数なら,pi = 1/6 ⇒ npi = 7
a1 = 145325415432115341662126421535631153154363
n1 = 10, n2 = 5, n3 = 8, n4 = 6, n5 =8, n6 = 5
x2 = 32/7 + 22/7 + 12/7 + 12/7 + 12/7 + 22/7 = 20/7
a2 = 112111421115331111544111544111134411151114
n1 = 25, n2 = 2, n3 = 3, n4 = 8, n5 =4, n6 = 0
x2 = 182/7 + 52/7 + 42/7 + 12/7 + 32/7 + 72/7 = 424/7
a1 のほうが a2 よりも理想的なケースに近い
18
x2値の計算例(続)
a3 = 111111111111222222...666666 (長さ 72)
n1 = 12, n2 = 12, n3 = 12, n4 = 12, n5 =12, n6 = 12
x2 = 02/12 + 02/12 + 02/12 + 02/12 + 02/12 + 02/12 = 0/12
理想的な乱数? 当然 no
長さ2のブロック化を考える...n = 36ブロック
理想は,“11”, ... “66” が1/36 の確率で発生,npi = 1
n11 = 6, n12 = 0, ..., n22 = 6, ...
x2 = (6 – 1)2/1 + (0 – 1)2/1 + ... = 180 ⇒ かなり大きい
様々なクラス分割により,多面的に評価する必要がある
19
x2値の評価
理想的な系列であっても,x2 値が必ず0になるとは限らない
理想的系列における x2 値の分布と,実測値とを比較すべき
[定理]
分割クラス数が l のとき,理想的系列における x2 値の分布は,
自由度が l – 1 のx2 分布 (Chi square distribution)にしたがう
自由度 2
自由度 4
自由度 6
O
x2
20
x2値の比較
a3 = 111111111111222222...666666 (長さ 72)
x2 = 02/12 + 02/12 + 02/12 + 02/12 + 02/12 + 02/12 = 0/12
クラス数が6 ⇒ 自由度が 5 の x2 分布に従うはず
自由度 5
O
x2
理想系列では,x2 値が 0 になる確率はきわめて小さい
観測系列の x2 値が 0 ⇒ 理想系列では考えにくい振る舞い
x2 値の大小だけでなく,理想的なx2分布と比較することが重要
21
x2値検定の実施例
x2 値の大小だけでなく,理想的なx2分布と比較することが重要
実際には...
1. 元のデータをいくつかのデータセット(部分集合)に分割
2. 各データセットに対して x2 値を計算
3. 得られた x2 値の集合の妥当性を検証
再び統計的検定を行う
上下パーセント点と比較する
上側1%点...
100回に1回くらいは,この値を超えるかもという点
22
その他の統計的検定手法
KS検定 (Kolmogorov-Smirnov検定)
x2 検定の連続変数バージョン(クラス分割不要)
ラン長検定
長さ k のラン発生確率 = 0.5×長さ k – 1 のラン発生確率
(2元の無記憶定常情報源で,通報発生が等確率のとき)
ランの発生個数について,x2検定を行う手法
ポーカー検定,衝突検定,間隔検定 etc.
いずれの方法も,十分長い系列に対して行う必要がある
(短い系列では,統計的性質が出現しにくい)
23
擬似乱数生成アルゴリズムについて
様々な擬似乱数生成アルゴリズムが提案されている
その多くが,少量の乱数の種(シード, seed)から,多量の
擬似乱数系列を生成するもの
線形合同法 (linear congruent method)
漸化式に基づいて擬似乱数を生成する方式
i 番目の値が Xi のとき,Xi+1 = aXi + c mod M とする
a, c, M は適当なパラメータ(選び方にはコツがある)
得られる値は 0 から M – 1の整数値
24
線形合同法の性質について
得られる擬似乱数列の周期は,必ず M 以下となる
M は,ある程度大きな値にすべき
M の選択がまずいと,Xiの下位ビットのランダム性が悪化する
M は素数にするのが良い
処理を簡便にするため,M = 2e とする実装もある
パラメータ a や c の選択についても,ある程度経験則が存在
25
線形合同法の問題点
(Xi, Xi+1) で与えられる2次元平面上の点を考える
(Xi, Xi+1) の点が,平面全体に広がることが理想的
線形合同法では,Xi が決まれば Xi+1 が一意に決まる
⇒ 直線 x = a 上には,高々一個の点しか配置されない
Xi+1 = 5Xi + 1 mod 7 のとき...
平面上の点を一個選んで...
という用途には使えない
6
5
4
3
2
1
O
(初期値が
5のとき)
1 2 3 4 5 6
26
M系列法
M系列法 (M-sequence method)
線形フィードバックシフトレジスタを利用して擬似乱数を生成
p 段シフトレジスタ ⇒ 状態数は 2p 通り存在する
結線方法によっては,周期2p–1の擬似乱数系列が生成可能
特異点(全ゼロ状態)以外のすべての状態を経由
⇒ 2p–1 という周期は,レジスタ数 p 段では最大値(Max)
結線
or
断線
Xi
Xi–p Xi–p+1 Xi–p+2
Xi–1
27
M系列法について
結線方法は,原始多項式の係数にしたがって決定(省略)
生成される系列は,非常に優れた統計的性質を持つ
レジスタの初期値の違い ⇒ 生成される系列の位相の違い
シフト加法性
高い自己相関性を持つ ⇒ CDMA などの通信方式でも利用
28
その他の擬似乱数生成法
メルセンヌ・ツイスタ法 (MT法,Mersenne Twister method)
松本眞氏(現広島大),西村拓士氏(現山形大)により提案
メルセンヌ素数を使い,シフトレジスタ法を一捻りした方
高品質の擬似乱数を高速に生成することが可能
予測不能な擬似乱数生成法
いわゆる「記憶のない」乱数生成 ⇒ 暗号的用途に向く
Blum 法など
線形合同法,M系列法,MT法は,暗号用途には使えない
29
まとめ
コルモゴロフ的な乱数の定式化
擬似乱数の統計的検定
x2検定
具体的な擬似乱数生成アルゴリズム
線形合同法,M系列法
30
練習問題
a = 110010111110001000110100101011101100とする(|a|=36)
a を長さ2のブロックに区切り,x2値を計算せよ
長さ3,4のブロックに区切り,それぞれx2値を計算せよ
線形合同法を実装し,擬似乱数を生成せよ
上記で生成した擬似乱数を,2次元平面にプロットせよ
(スライドの26ページ参照)
レポート課題: http://www.naist.jp/~kaji/ 参照,5/10提出
report assignment: available from the above URL, due by May 10
31