そもそも情報とはなに? ある事柄に関して知識を得たり判断のより所としたりするために不可欠な何らかの手段で伝達 ( 入手 ) された種々の事項 ( の内容 ) ( 新明解国語辞典第 6 版三省堂より一部抜粋 ) コンピュータで取り扱う情報の定義 Claud Elwood Shannon( 情報理論

Size: px

Start display at page:

Download "そもそも情報とはなに? ある事柄に関して知識を得たり判断のより所としたりするために不可欠な何らかの手段で伝達 ( 入手 ) された種々の事項 ( の内容 ) ( 新明解国語辞典第 6 版三省堂より一部抜粋 ) コンピュータで取り扱う情報の定義 Claud Elwood Shannon( 情報理論"

まいえおおふさ
5 years ago
Views:

1 情報理論の基礎 l 自己情報量 (self information) l 平均情報量 (average information) l エントロピー (entropy) l 最大エントロピー (maximum entropy) l 冗長度 (redndancy) 可逆圧縮の原理と実践 l ランレングス符号化 l ハフマン符号化 ( エントロピー符号化 )

2 そもそも情報とはなに? ある事柄に関して知識を得たり判断のより所としたりするために不可欠な何らかの手段で伝達 ( 入手 ) された種々の事項 ( の内容 ) ( 新明解国語辞典第 6 版三省堂より一部抜粋 ) コンピュータで取り扱う情報の定義 Claud Elwood Shannon( 情報理論の発案者 ) 変化するパターンの中から選択できるもの例 :T 子さんが結婚する ( 未婚既婚への変化 )

3 ここで問題です Q. オバケの Q 太郎という漫画には毎日三食とも必ずラーメンを食べている小池さんというキャラクターが登場します小池さんが今日何を食べたかは情報と呼べるでしょうか? A. 小池さんはいつでも必ずラーメンを食べているのですからまったく変化がありませんしたがって小池さんが今日何を食べたかは情報とは呼べませんもしも小池さんの食事がラーメンを食べる / カレーを食べるのように変化するなら情報と呼べます

4 情報の最小単位天気という情報は晴れ曇り雨雪の 4 通りに変化します道路信号は青黄赤の 3 通りに変化しますそれでは最も少ない変化は何通りでしょう YES/ NO 男 / 女前 / 後のような 2 通りの変化ですすなわち 2 通りの変化が情報の最小単位でありこれをビットと呼びますビット (bit) は binary digit(2 進数 ) を略した言葉です情報源電線伝達先電線本でビットの情報を伝える電圧がかかっていない 0 電圧がかかっている

5 情報の基本単位コンピュータは 8 本の電線をセットで使った 8 ビットを情報の基本単位としていますこれをバイトと呼びます 8 ビット = バイト (byte) です最近のコンピュータは 64 ビット CPU (central processing unit: 中央処理装置 ) が搭載されている 800 京通り 8 本 = バイトで表せるパターンは 256 通りすなわち 256 通りの変化を処理できる 024 byte(b) = KB ( キロバイト ) 024 KB = MB ( メガバイト ) 024 MB = GB ( ギガバイト ) 024 GB = TB ( テラバイト ) 2 0 byte 2 20 byte 2 30 byte 2 40 byte

6 情報の量とはその情報を得た人にとっての内容の豊富さのことであると考えてよいこれから S 君の部屋へ遊びに行くぞ! 部屋はどこだっけ? A 君入口アパートのモデル図 A 君は入口で次の情報を教えてもらった情報 : S 君は号室に住んでいるこの情報は A 君にとって果たしてどれぐらいの情報の量であったのか Q. ケースとケース2では, どちらが入口で得た情報の量が多い ( 豊富 ) と考えられるか? /6 Case :A 君は S 君が何階に住んでいるのか知らなかった. Case 2:A 君は S 君が 3 階に住んでいるのを知っていた. /4

7 情報の量は, 情報を得る前の可能性の数 ( 前例では部屋の数 ) に関係し, その数が増すにつれ情報の量も増すようでなければならない ( 単調増加関数 ). 情報の加法性が成り立たなければならない. 情報 :S 君の部屋は6 室の号室である. 情報 2:S 君の部屋は3 階にある. 情報 3:S 君の部屋は左から3 番目の部屋である. 情報の量 = 情報 2 の量 + 情報 3 の量情報の量は, 可能性の数の対数で定義するのが便利対数の底を 2 にとると, 最小の情報 ( 二択 ) の量は log 2 2= となり, 情報量の単位として都合がよい.

8 情報量の定義 I( p i : ある出来事が発生する確率 ( 事前確率 ) p i ) = = log log 2 2 事後確率事前確率 = log2 p i p i I(p i ) 自己情報量 or 選択情報量自己情報量のグラフ p i 情報量の単位はビット [bit] p i = /2 のとき I(p i ) = p i = のとき I(p i ) = 0

9 自己情報量の例 [ 例 ] 赤ん坊が生まれたときその男女比が : とする男が生まれる事象を boy 女が生まれる事象を girl とするとそれぞれの自己情報量は次のようになる I ( boy) = log 2 2 = bit I ( girl) = log 2 2 = bit [ 例 2] ある試験では合格する可能性が /8 であるこの試験に合格した場合の自己情報量は I( 合格 ) = log 2 8 = 3 bit となる一方不合格になったときの自己情報量は 7 I( 不合格 ) = log 2 8 = log 2 7+ log 2 8 = = 0.93 bit

10 情報の加法性情報 :S 君の部屋は 6 室の号室である. 情報 2:S 君の部屋は 3 階にある. 情報 3:S 君の部屋は左から 3 番目の部屋である. 情報の量 = 情報 2 の量 + 情報 3 の量 log 2 6 = 4 log 2 4 = 2 log 2 4 = 2 [ 例 ] ジョーカーを除いた 52 枚のトランプを相手に引いて貰いその内容を教えてもらうことを考える引いたカードがハートのAであることを知ったときの情報量は I( ハートのA) = log bit 52 引いたカードがハートであることのみを知ったときの情報量は I( ハート ) = log 2 = 2 bit 4 引いたカードが Aであることのみを知ったときの情報量は I(A) = log bit 3

11 平均情報量 (average information) 情報量の平均 ( 期待値 ) について考えよういまある事象系を {a, a 2,, a N } とするこれら N 個の事象は互いに排反でその生起確率 p i の総和はとする ( 完全事象系 ) このとき情報量 I(p i ) の平均すなわち平均情報量 H は次のように示される H = p ( log 2 p ) + p 2 ( log 2 p 2 ) + + p N ( log 2 p N ) = N i= p i log 2 p i ただし N i= p i =.0 平均情報量の取りうる値は 0 H log 2 N bit 事象系 {a, a 2,, a N } において一つの事象 a i の生起確率が p i = でその他の事象の生起確率がすべて 0 のとき H = 0 これは結果を聞く前から結果が既知なので情報としては価値がない事象系 {a, a 2,, a N } においてすべての事象の生起確率が p i = /N と一様の場合は平均情報量は最大の H = log 2 N bit となるこれはどれが起きるか全く予想できない状態

12 平均情報量の例 [ 例 ] ある家の本日の晩ご飯の生起確率が以下の通りだとする p( カレー ) = p( からあげ ) = p( ステーキ ) = 4 8 6,,, p( ハンバーグ ) = p( とんかつ ) = p( すき焼き ) = 4 8 0,, p( 焼き魚 ) = p( さしみ ) = 8 6 H = log 4 = = i= + p i log2 p i log2 3 log = = ただし x 0 のとき x log 2 x 0 2 0log bit 2 0

13 エントロピー (entropy) 無秩序, 混乱熱力学における分子の無秩序さを表す尺度熱力学におけるエントロピー H = K k n k ln n k K はポルツマン定数,n k は気体分子の k 番目のエネルギー状態にある確率情報理論におけるエントロピー H 2 = k p i log p i 熱力学におけるエントロピーと平均情報量は定数倍, 対数の底を除いて一致する. そのため, 平均情報量を情報理論におけるエントロピーと呼ぶことにする.

14 最大エントロピー (maximum entropy) 2 種類の文字 A,B が, それぞれ確率 p, p で生起する情報源のエントロピーは次のように表される. H { p log p + ( p) log( p) } = H(p) H を確率 p の関数として示すと右のようなグラフ ( エントロピー関数 ) になる. 文字 A と B どちらであるか半々である状態 H が零になるのは,p = か p = 0 のとき. H が最大になるのは,p = 0.5 のとき. 文字 B であるにきまっている p 文字 A であることがわかりきっているすべての出来事が等確率で発生すると仮定した場合のエントロピーを最大エントロピー (maximum entropy) という.

15 最大エントロピーの例以下の例はいずれも各事象の生起確率が等確率と仮定する. サイコロを一回振る時の最大エントロピー 6 H max = log2 = log2 6 = 6 6 i= 英数字 (A~Z と空白, 計 27 文字 ) の最大エントロピー 27 H max = log2 = log2 27 = i= bit bit 常用漢字 (945 文字 ) の最大エントロピー 945 H max = log2 = log2 945 = i= bit

16 冗長度 (redundancy) 最大エントロピー :H max とエントロピー :H の違いは情報源に含まれる無駄さである. 与えられた情報源がどれだけ無駄なものを含むかの度合いを冗長度 (Redundancy) という. これは情報の中で実際の情報以外のものの割合とも言える. 冗長度 :r は次のように定義される r H = = H max エントロピー最大エントロピー冗長性があるおかげで... データの圧縮が可能正確な情報通信が可能情報そのものは減らすことなく, 情報以外の冗長な部分を切り詰めるあえて冗長な部分を付加利用して, 情報の正確さを判定担保する

17 例 : 4 つの文字 (A,B,C,D) からなるデータ出現率が均等である場合 p A = p B = p C = p D = ¼ 冗長度がなく, 最大エントロピー H max に一致する平均情報量 H = log 2 4 = 2.0 bit 出現率に偏りがある場合 p A = /2, p B = /4, p C = p D = /8 冗長度があり, 得られる情報量は見かけより少ない平均情報量 H = ½ log ¼ log 2 4 +¼ log 2 8 = =.75 bit 冗長度 r = -.75/ 2.0 = 0.25 情報量を, 情報を表現できるビット数であると考えれば, 出現率に偏りがある情報のほうが情報量が小さくなる. すなわち, 少ないビット数で表現できることを意味する. これは, データ圧縮, 特に可逆圧縮の基本原理である. 可逆圧縮は元のデータに完全に復元できる. それに対して非可逆圧縮は元のデータに完全には復元できない.

18 最小符号長平均情報量 ( エントロピー ) = 冗長性を廃した場合のデータ量 = 最小符号長例 : 4 つの値からなるデータ (A,B,C,D) ( 情報を表現するのに必要な最低限の符号の長さ ) 出現率が均等である場合 p A = p B = p C = p D = /4 平均情報量 =2.0 ビット出現率に偏りがある場合 p A = /2, p B = /4, p C = p D = /8 平均情報量 =.75 ビット 4 つの値を表現するのに必要なビット数に一致する 4 つの値を表現するのに必要なビット数より少ない統計的な偏りがあれば, 情報量を保持したままデータを圧縮することができる

19 データ量と情報量例 : 00 種類の文字からなる 00 文字の文字列データ量文字 =8 ビット 8 00=800 ビット ( アルファベットなど ) 文字 =6 ビット 6 00=600 ビット ( ひらがな, 漢字など ) 情報量データ量は変わっても, 情報の質は変わらない 00 文字の文字列である情報量は同じでも, データ化によってデータ量に差が生じる情報量 < データ量データの冗長性

20 FAX FAX には基本的なデータ圧縮処理が使われている

21 FAX で使われる圧縮技術 Run Length encoding ランレングス符号化 ( 連長符号化 )

22 FAX で使われる圧縮技術 2 Haffman encoding ハフマン符号化エントロピー符号化の一種

23 ランレングス符号化元データデータ内に同じ値が並んでいる場合, その並びの数を記録していく方法圧縮データ

24 ランレングス符号化のバリエーション元データ方法基本的なランレングス符号化方法 2 ランレングスを示すコードを挿入する 0xFF 4 0 0xFF 4 0xFF 3 2 0xFF 5 3 方法 3 ラン長部分をランレングスを示すコードとする 0x84 0 0x84 0x82 2 0x85 3

25 エントロピー符号化データ値の出現頻度に応じてビット長の違う符号を割り当てる方法モールス符号と基本的には同じ考え方普通の符号化出現頻度に基づく符号化データ値符号データ値出現頻度符号 A 00 B 0 C 0 D A B 0. 0 C D 0.05 平均符号長 = 2.0 ( ビット ) 平均符号長 =.3 ( ビット ) 代表的なもの : シャノンファノ符号化, ハフマン符号化

26 ハフマン符号化各データを重みを持った葉と捉え, 出現頻度の低いものをまとめてハフマン木と呼ばれる木構造のデータを構築し, ハフマン木から各データに割り当てるビット列を決定するハフマン木の例 :

27 ハフマン木の作成法データのなかで出現頻度の低いもの 2 つをまとめ, ツリー状のデータ構造で表現するそして, 2 つの出現頻度を合計したものを新たなデータ値の出現頻度とする 2 で作成したデータ値と次に出現頻度の低いデータとでの処理を行うこれをハフマン木がつにまとまるまで繰り返す

28 ハフマン木の作成例

29 ハフマン符号化されたデータの復号復号にもハフマン木が必要元のデータの出現頻度情報を付加しておくデータ値バイト A B C D バイトバイトバイト出現頻度バイト 4 バイト 4 バイト 4 バイト 4 バイト + 6 バイト出現頻度情報の付加によるデータ量の増加分 = 20 バイトハフマン木のための付加情報によってデータ量が多くなってしまうこともあり得る

30 圧縮してみよう! 画素を bit で表現した 2 値画像 :(6 6 画素 ) データ量はいくつか? 平均情報量はいくつか? ランレングス符号化後のデータ量はいくつか? ランレングス符号化 + ハフマン符号化後のデータ量はいくつか?

情報理論第5回情報量とエントロピー

情報理論第5回情報量とエントロピー 5 () ( ) ( ) ( ) p(a) a I(a) p(a) p(a) I(a) p(a) I(a) (2) (self information) p(a) = I(a) = 0 I(a) = 0 I(a) a I(a) = log 2 p(a) = log 2 p(a) bit 2 (log 2 ) (3) I(a) 7 6 5 4 3 2 0 0.5 p(a) p(a) = /2 I(a)