Upload
others
View
7
Download
1
Embed Size (px)
Citation preview
講義「情報理論」
第2回 事前知識の準備(確率,対数計算)
情報理工学部門 情報知識ネットワーク研究室喜田拓也
2019/6/21講義資料
情報理論での情報伝達のモデル(おさらい)
情報を「記号の列」だと割り切って取り扱う
その意味内容には立ち入らない送信される情報は記号{晴,曇,雨,雪}の列
あなた(受け手)の世界は,記号(列)の集合とその統計的知識
2
あなた(受け手)の世界
日々の天気の結果の列
情報の発信元
(実際の天気)
記号列としての天気の結果の集合
統計的知識
確率分布𝑃𝑃(𝑋𝑋)
出現頻度など
{晴,曇,雨,雪}
情報理論が取り組む4つの問題(おさらい)
【問題1】 できるだけよい情報源符号化法(復号法)を見出すこと
【問題2】 情報源符号化の限界を知ること
【問題3】 できるだけよい通信路符号化法(復号法)を見出すこと
【問題4】 通信路符号化の限界を知ること
3
デジタル情報源
情報源符号化
あて先
2元通信路
通信路符号化
情報源復号
通信路復号
符号化
復号
誤りやひずみ
今日の内容
付録A 対数とその性質
確率について基本的なお話
4
対数の定義
定義A.1:𝑎𝑎 ≠ 1 を正の実数とする.このとき,任意の実数 𝑥𝑥 > 0に対し
𝑥𝑥 = 𝑎𝑎𝑝𝑝
を満たす実数 𝑝𝑝が唯一に決まる.これを 𝑝𝑝 = log𝑎𝑎 𝑥𝑥 と書き,𝑎𝑎 を底とする 𝑥𝑥 の対数(logarithm)と呼ぶ.
定義A.2:
𝑒𝑒 = lim𝑡𝑡→0
1 + 𝑡𝑡1𝑡𝑡 = 2.71828182845904⋯
で定義される定数𝑒𝑒 をネイピア数(またはオイラー数)という.
• 底が10のときを常用対数(Log 𝑥𝑥)• 底が𝑒𝑒 のときを自然対数(ln 𝑥𝑥)• 底が2のときを二進対数(lg 𝑥𝑥,log 𝑥𝑥)
5
情報理論では二進対数が良く用いられる
対数の基本的な定理
定理A.1: 𝑎𝑎 ≠ 1 を正の実数とする.任意の正の実数𝑥𝑥,𝑦𝑦 と任意の
実数𝑏𝑏 に対し,以下が成り立つ.
(1) 𝑎𝑎log𝑎𝑎 𝑥𝑥 = 𝑥𝑥(2) log𝑎𝑎 𝑎𝑎 = 1(3) log𝑎𝑎 1 = 0(4) log𝑎𝑎 𝑥𝑥𝑦𝑦 = log𝑎𝑎 𝑥𝑥 + log𝑎𝑎 𝑦𝑦 (4’) log𝑎𝑎
𝑥𝑥𝑦𝑦
= log𝑎𝑎 𝑥𝑥 − log𝑎𝑎 𝑦𝑦
(5) log𝑎𝑎 𝑥𝑥𝑏𝑏 = 𝑏𝑏 log𝑎𝑎 𝑥𝑥 (5’) log𝑎𝑎1𝑥𝑥
= log𝑎𝑎 𝑥𝑥−1 = − log𝑎𝑎 𝑥𝑥(6) 𝑎𝑎 > 1 かつ𝑥𝑥 < 𝑦𝑦のとき,log𝑎𝑎 𝑥𝑥 < log𝑎𝑎 𝑦𝑦(7) 𝑎𝑎 > 1 のとき, lim
𝑥𝑥→+∞log𝑎𝑎 𝑥𝑥 = +∞
定理A.2: 正の実数𝑎𝑎, 𝑏𝑏 ≠ 1 および任意の正の実数𝑥𝑥 に対し,
log𝑎𝑎 𝑥𝑥 =log𝑏𝑏 𝑥𝑥log𝑏𝑏 𝑎𝑎
が成り立つ. 6
底の変換!
掛け算が足し算に! 割り算が引き算に!
ノート A.1
𝑥𝑥の𝑎𝑎を底とした対数log𝑎𝑎 𝑥𝑥 は,𝑥𝑥を𝑎𝑎進数表示したときの桁数
(記述長)に対応する.
例えば,ある自然数𝑛𝑛の10進数での桁数を𝑚𝑚とする.このとき,
10𝑚𝑚−1 ≤ 𝑛𝑛 < 10𝑚𝑚 .各辺の対数をとると
𝑚𝑚 − 1 ≤ log10 𝑛𝑛 < 𝑚𝑚 ,∴ log10 𝑛𝑛 < 𝑚𝑚 ≤ log10 𝑛𝑛 + 1 .
したがって,
𝑚𝑚 = log10 𝑛𝑛 + 1 .
例題: 10進数で 225 は,二進数で何桁か?
log2 225 = log2 52 � 32 = 2 log2 5 + 2 log2 3≒ 2 2.322 + 1.585 = 7.814
すなわち,7 ≤ log2 225 < 8 なので,8桁である. 7
11100001
床関数 𝑥𝑥 : 𝑥𝑥 以下の最大の整数
※ Kenneth E. Iverson が1962年に導入
𝑦𝑦 = log𝑎𝑎 𝑥𝑥の性質
𝑎𝑎 > 1 のとき,log𝑎𝑎 𝑥𝑥は単調増加
(𝑥𝑥 に対してなだらかに増加する)
𝑥𝑥 → +∞ ⇒ log𝑎𝑎 𝑥𝑥 → +∞𝑥𝑥 < 𝑦𝑦 ⟺ log𝑎𝑎 𝑥𝑥 < log𝑎𝑎 𝑦𝑦0 < 𝑥𝑥 < 1 の間は負の値をとる
𝑥𝑥 → 0 ⇒ log𝑎𝑎 𝑥𝑥 → −∞
定理A.3: 𝑑𝑑𝑑𝑑𝑥𝑥
log𝑒𝑒 𝑥𝑥 = 1𝑥𝑥
.
一般的には,𝑑𝑑𝑑𝑑𝑥𝑥
log𝑎𝑎 𝑥𝑥 = log𝑎𝑎 𝑒𝑒𝑥𝑥
.
定理A.4: 正の実数𝑎𝑎 ≠ 1 に対して,次が成り立つ.
(1) 𝑦𝑦 = log𝑎𝑎 𝑥𝑥 の曲線は𝑦𝑦 = 𝑎𝑎𝑥𝑥 の曲線と直線𝑦𝑦 = 𝑥𝑥 に関して対称
(2) ln 𝑥𝑥 ≤ 𝑥𝑥 − 18
-4
-3
-2
-1
0
1
2
3
4
5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
図 𝑦𝑦 = log2 𝑥𝑥 のグラフ
Try 問3,問4
ちょっと休憩
9
確率とは
「ある事象についての起こりやすさの指標」
もとは,賭け事の戦略や,金銭の公平な分配を
考えるために用いられた概念
10
「1個のサイコロを振って,奇数だったら私の勝ち,偶数だったらあなたの勝ち.参加費は100円.勝ったら180円をあげるよ.勝負する?」
事象,起こりやすさの指標って?
偶然現象において,起こりうる事柄を事象という
それぞれの事象が起こりうる可能性を,すべての
起こりうる事象に対する割合として表すとき,その
値を確率という
11
偶然現象って何?サイコロ振りだって物理現象でしょ?ロボットが振ったらいつも同じじゃん
𝑃𝑃 𝐴𝐴 =𝑟𝑟𝑛𝑛
事象Aが起こる場合の数
すべての場合の数古典的な
確率の定義
現代の確率の定義は末尾の資料を参照
まあ難しい話はおいといて・・・
「1個のサイコロを振って,奇数だったら私の勝ち,偶数だったら
あなたの勝ち.参加費は100円.勝ったら180円をあげるよ.
勝負する?」
12
標本集合 Ω = {1,2,3,4,5,6},あなたが勝つ事象 𝐴𝐴 = {2,4,6}
事象𝐴𝐴が起こる確率 𝑃𝑃 𝐴𝐴 = ⁄𝐴𝐴 Ω = 36
= 12
得られる賞金額を確率変数𝑋𝑋とすると,その確率分布𝑃𝑃𝑋𝑋は
𝑃𝑃𝑋𝑋 𝑋𝑋 = 0 = 12
, 𝑃𝑃𝑋𝑋 𝑋𝑋 = 180 = 12
.
得られる賞金額の期待値𝐸𝐸(𝑋𝑋)は
𝐸𝐸 𝑋𝑋 = �𝑥𝑥∈{0,180}
𝑥𝑥 ⋅ 𝑃𝑃𝑋𝑋(𝑋𝑋 = 𝑥𝑥) = 0 ×12
+ 180 ×12
= 90.
Try 問1
𝑋𝑋は確率によって取
る値が決まる変数
確率変数の「見込み」の値
𝐸𝐸 𝑋𝑋 = ∑𝑖𝑖 𝑥𝑥𝑖𝑖𝑃𝑃𝑋𝑋 𝑋𝑋 = 𝑥𝑥𝑖𝑖
確率を表す関数
確率の統計的な定義
標本集合のどの要素(根源事象)も同程度に確からしく
起こる場合は古典的定義で問題ない
この仮定が適用できない場合は困る
13
根源事象の
生起にかたより
がある場合
試行を𝑛𝑛回繰り返し行ったときに事象𝐴𝐴が起こった
回数を𝑛𝑛(𝐴𝐴)とする.このとき,
𝑃𝑃 𝐴𝐴 = lim𝑛𝑛→∞
𝑛𝑛 𝐴𝐴𝑛𝑛
を事象𝐴𝐴の確率とする.
(現実に無限回の試行は不可能なので極限を取らないことも)
とある病院での,患者と女医の会話
14
・・・この手術の成功率は30%と言われています
えっ!そんなに少ないの・・・
私は失敗しないのでっ!
大門か・・・
条件付き確率と独立性
𝑃𝑃 𝐴𝐴 > 0のとき,
𝑃𝑃 𝐵𝐵 𝐴𝐴 =𝑃𝑃 𝐴𝐴 ∩ 𝐵𝐵𝑃𝑃 𝐴𝐴
を,事象𝐴𝐴が起こったもとでの事象𝐵𝐵の条件付き確率と定義する.
このとき,明らかに次式が成り立つ.
𝑃𝑃 𝐴𝐴 ∩ 𝐵𝐵 = 𝑃𝑃 𝐴𝐴 𝑃𝑃 𝐵𝐵 𝐴𝐴 .
事象𝐵𝐵の起こる確率が事象𝐴𝐴の生起に無関係な場合,すなわち
𝑃𝑃 𝐵𝐵 𝐴𝐴 = 𝑃𝑃 𝐵𝐵
が成り立つとき,事象𝐴𝐴と事象𝐵𝐵は独立であるという.
このとき,明らかに次式が成り立つ.
𝑃𝑃 𝐴𝐴 ∩ 𝐵𝐵 = 𝑃𝑃 𝐴𝐴 𝑃𝑃 𝐵𝐵 .15
= lim𝑛𝑛→∞
𝑛𝑛 𝐴𝐴 ∩ 𝐵𝐵𝑛𝑛 𝐴𝐴
条件付き確率の簡単な例
1個のサイコロを振る試行を考える.
サイコロの出目が偶数である事象を𝐴𝐴,サイコロの出目が4以上である事象を𝐵𝐵とする
事象𝐴𝐴の確率𝑃𝑃(𝐴𝐴)は 𝑃𝑃 𝐴𝐴 = 36
= 12
事象𝐵𝐵の確率𝑃𝑃(𝐵𝐵)は 𝑃𝑃 𝐵𝐵 = 36
= 12
事象𝐴𝐴 ∩ 𝐵𝐵の確率は 𝑃𝑃 𝐴𝐴 ∩ 𝐵𝐵 = 26
= 13
このとき,事象𝐴𝐴で条件付けた事象𝐵𝐵の確率𝑃𝑃 𝐵𝐵 𝐴𝐴 は
𝑃𝑃 𝐵𝐵 𝐴𝐴 =𝑃𝑃 𝐴𝐴 ∩ 𝐵𝐵𝑃𝑃 𝐴𝐴
=1312
=23
.
16
偶数である確率
4,5,6である確率
4か6である確率
出目が偶数であること
は分かっている場合で
4以上である確率
ベイズの定理
全事象 Ωを互いに排反な 𝑛𝑛個の事象 𝐵𝐵1,𝐵𝐵2, … ,𝐵𝐵𝑛𝑛 に分割する.
すなわち,
𝐵𝐵𝑖𝑖 ∩ 𝐵𝐵𝑗𝑗 = ∅ 𝑖𝑖 ≠ 𝑗𝑗 ,𝐵𝐵1 ∪ 𝐵𝐵2 ∪ ⋯∪ 𝐵𝐵𝑛𝑛 = Ω .
このとき,任意の事象𝐴𝐴に対して次が成り立つ.
𝑃𝑃 𝐵𝐵𝑘𝑘 𝐴𝐴 =𝑃𝑃 𝐵𝐵𝑘𝑘 𝑃𝑃 𝐴𝐴 𝐵𝐵𝑘𝑘
∑𝑖𝑖=1𝑛𝑛 𝑃𝑃 𝐵𝐵𝑖𝑖 𝑃𝑃(𝐴𝐴|𝐵𝐵𝑖𝑖)
17
次の関係はΩ = 𝐵𝐵 ∪ �𝐵𝐵の場合の簡略版
𝑃𝑃 𝐵𝐵 𝐴𝐴 =𝑃𝑃 𝐵𝐵 𝑃𝑃 𝐴𝐴 𝐵𝐵
𝑃𝑃 𝐵𝐵 𝑃𝑃 𝐴𝐴 𝐵𝐵 + 𝑃𝑃 �𝐵𝐵 𝑃𝑃(𝐴𝐴| �𝐵𝐵)=𝑃𝑃 𝐴𝐴,𝐵𝐵𝑃𝑃 𝐴𝐴
.
𝑃𝑃 𝐴𝐴,𝐵𝐵 は
𝑃𝑃 𝐴𝐴 ∩ 𝐵𝐵と同じ意味
𝐵𝐵1 𝐵𝐵2 𝐵𝐵3 𝐵𝐵4 𝐵𝐵5
𝐴𝐴
Ω𝑃𝑃(𝐴𝐴,𝐵𝐵4)
ベイズの定理
ベイズの定理を使う例題
ガンを診断するための検査法があり,あなたがそれを受けると仮定しよう.
𝐶𝐶 を,被検査者がガンであるという事象,
𝐴𝐴を,検査の結果が被検査者はガンであると示す事象とする.
(つまり検査結果が陽性となる事象)
検査法の認識力が95% (𝑃𝑃 𝐴𝐴 𝐶𝐶 = 0.95 かつ 𝑃𝑃(�̅�𝐴|�̅�𝐶) = 0.95)であるとし,
検査を受ける人の中で実際にガンである割合が 𝑃𝑃(𝐶𝐶) = 0.01であるとする.
このとき・・・
18
あなたガンですよ.検査の結果から常識的に考えて・・・
ガーーーン
検査の結果が陽性だったとき,あなたが本当にガンである確率はいくらか?
(つまり,𝑃𝑃(𝐶𝐶|𝐴𝐴)を求めなさい)
ベイズの定理を使う例題の答え
ベイズの定理より,
𝑃𝑃 𝐶𝐶 𝐴𝐴 =𝑃𝑃 𝐶𝐶 𝑃𝑃 𝐴𝐴 𝐶𝐶
∑𝑖𝑖=12 𝑃𝑃 𝐶𝐶𝑖𝑖 𝑃𝑃(𝐴𝐴|𝐶𝐶𝑖𝑖)=
𝑃𝑃 𝐶𝐶 𝑃𝑃 𝐴𝐴 𝐶𝐶𝑃𝑃 𝐶𝐶 𝑃𝑃 𝐴𝐴 𝐶𝐶 + 𝑃𝑃 �̅�𝐶 𝑃𝑃(𝐴𝐴|�̅�𝐶)
である.これに,
𝑃𝑃 𝐶𝐶 = 0.01, 𝑃𝑃 �̅�𝐶 = 1 − 𝑃𝑃 𝐶𝐶 = 0.99,𝑃𝑃 𝐴𝐴 𝐶𝐶 = 0.95, 𝑃𝑃 𝐴𝐴 �̅�𝐶 = 1 − 𝑃𝑃 �̅�𝐴 �̅�𝐶 = 0.05
を代入すると,
𝑃𝑃 𝐶𝐶 𝐴𝐴 =0.01 × 0.95
0.01 × 0.95 + 0.99 × 0.05=
19118
≒ 0.161.
19
たったの16%!よかったお
Try 問2
今日のまとめ
確率の考え方について学んだ
確率の定義標本集合,事象,平均(期待値)
対数とその性質について復習した
次回テーマ
情報量とエントロピー
20
現代の確率の考え方
「サイコロの目がどう出るかは最初のサイコロの持ち方と
その振り方によって決まる.そこには何の偶然性もない.
ただし,その因果関係はあまりにも複雑なので,結果を
予想するのはほぼ不可能である.・・・(中略).このよう
な予測しにくいこと,制御しにくいことを「偶然である」とみ
なすのが確率統計の出発点である.」
(金谷健一著,「確率統計を学ぶにあたって」岡山大学工学部講義資料)
21
現代の確率論は,「確率」が何を意味するかは問わない.
「確率」が満たすべき数学的な性質を規定し,その性質
から導かれる定理を論じる.公理主義
確率の公理による定義
ある空でない集合 Ω (結果の集合,標本集合)について,
その任意の部分集合を事象という.
事象全体の集合をℱ(= 2Ω)とする.
写像𝑃𝑃: ℱ → 0,1 が任意の𝐴𝐴 ∈ ℱについて次を満たす
とき,𝑃𝑃(𝐴𝐴)を事象𝐴𝐴の確率という.
22
𝑃𝑃𝑟𝑟(𝐴𝐴)と書くことも1. 0 ≤ 𝑃𝑃 𝐴𝐴
2. 𝑃𝑃 Ω = 1
3. 𝐴𝐴1,𝐴𝐴2, … ∈ ℱについて𝐴𝐴𝑖𝑖 ∩ 𝐴𝐴𝑗𝑗 = ∅ (𝑖𝑖 ≠ 𝑗𝑗)ならば,
𝑃𝑃 ∪𝑖𝑖=1∞ 𝐴𝐴𝑖𝑖 = ∑𝑖𝑖=1∞ 𝑃𝑃 𝐴𝐴𝑖𝑖
∅: (ヌル)空集合
by コルモゴルフ(Kolmogorov)
確率の三公理
公理から導かれる確率の基本的性質
1. 𝑃𝑃 ∅ = 0
2. 𝑃𝑃 �̅�𝐴 = 1 − 𝑃𝑃(𝐴𝐴)
3. 事象𝐴𝐴,𝐵𝐵 ∈ ℱに対して
𝐴𝐴 ⊂ 𝐵𝐵ならば𝑃𝑃 𝐴𝐴 ≤ 𝑃𝑃(𝐵𝐵)
4. 任意の事象𝐴𝐴 ∈ ℱに対して𝑃𝑃 𝐴𝐴 ≤ 1
5. 事象𝐴𝐴,𝐵𝐵 ∈ ℱに対して
𝑃𝑃 𝐴𝐴 ∪ 𝐵𝐵 = 𝑃𝑃 𝐴𝐴 + 𝑃𝑃 𝐵𝐵 − 𝑃𝑃(𝐴𝐴 ∩ 𝐵𝐵)
23
�̅�𝐴は事象𝐴𝐴が起こらない事象(余事象)
0 ≤ 𝑃𝑃 𝐴𝐴 ≤ 1
確率の加法定理
確率変数と確率分布
確率変数𝑋𝑋とは,標本集合Ωから実数空間ℝ(ℝ𝑛𝑛)
への(確率と関連付いた)写像である
確率変数𝑋𝑋がある値になる確率を確率分布という
24
0 1
標本集合Ω 実数の空間ℝ𝑛𝑛
𝑋𝑋−1(𝐴𝐴) 𝐴𝐴
確率 𝑃𝑃(𝑋𝑋−1(𝐴𝐴))
確率変数 𝑋𝑋
確率分布 𝑃𝑃𝑋𝑋 𝐴𝐴
𝑃𝑃𝑋𝑋 𝐴𝐴 = 𝑃𝑃(𝑋𝑋−1(𝐴𝐴))
なんでこんなに面倒な議論をするの?
A. 抽象的な概念を抽出して議論することで,
様々なケースに適用できるから
離散的な集合だけでなく,連続的な集合の上でも
同じようにして確率を定義できる
確率的な性質さえ満たすなら,何でもいい
→ 主観的な確信の度合いとして確率を用いても
よかろうもん(ベイズ主義)
25
直接に統計情報を取れない事象を推測するのに用いる