今回は情報源について記述していきたいと思います。

 

情報源とは何か

 

まず情報源とは何かについて考えていきましょう。

 

Wikipedeiaには以下のように記載されています。

 

情報源(じょうほうげん)には主に次の2つの意味がある。

  1. 情報の提供者、入手元、入手経路、発信源(ソース、information source)。例えば、歴史においては史料historical source)、調査・研究においては資料source text)。ジャーナリズムにおいては、取材源 (Journalism sourcing
  2. 情報理論の概念。情報理論においては、情報源とはビット列(もしくはより一般になんらかのシンボルの有限列)が、選ばれるもととなる空間の事[要出典]。より厳密に言えば、シンボルの有限列全体の空間とその上の確率分布の組のこと。シンボルの有限列はその確率分布に従って選ばれる[要出典]

もちろん今回は2番の意味での情報源をさしています。

 

流石のWikipedia、できる限り難しく説明しています。

 

しかし、実際はそんなに難しく考える必要はありません。

 

情報理論において情報は以下のように伝達されるとされています。

情報源→符号化→伝送路→復号化→受け手

このように情報が伝達する際の一番初めのフェーズが情報源です。(名前の通りですね)

 

例えばサイコロを降る時を考えてください。

 

何も難しいことはなくサイコロの出目が情報源ということになります。

 

本来であればその出目はそのまま情報として自分の目や耳に飛び込んでくるわけですが、パソコンを通す場合0,1の情報で表さなくてはいけないですね。(パソコンの世界は2進法なので)

 

つまり以下のような感じで変換されるわけです。(感の良い方はビット列00が11を表すか3を表すか分からないじゃんと気がつくかもしれません。情報源を符号化する際もルールがあります。それら今度記述します。)

 

1→0

2→1

3→00

4→01

5→10

6→11

 

回りくどくなりましたが、Wikipediaで言う所のビット列(もしくはより一般になんらかのシンボルの有限列)」というのが矢印の右側の0,1で表されている部分でサイコロの出目が「選ばれるもととなる空間」つまるところ情報源だということがお分りいただけたでしょうか。

 

情報源の種類

 

なんとなく情報源がどのようなものかわかったところで情報源の種類についてお話をしていきます。

 

情報源が2種類あると言われた時に、どのように分けられると思いますか?

 

 

 

答えは記憶があるかないかです。

 

 

いや、情報源に記憶もクソもあるか。と思いますが自分たちが想像している記憶とは少し違います。

 

例えばサイコロを降る時を想像してください。サイコロを1回目に降る時の情報をA、2回目に降る時の情報をBとします。

 

Aは1でした。ではBは何である確率が高いですか?

 

と言われたってイカサマサイコロでなければ全ての出目は等しく1/6の確率で出るため予想もクソもありません。

 

このように2つの事象がなんの関係もなく独立している状態の場合の情報源は記憶のない情報源とされ無記憶情報源と呼ばれます。

 

一方、以前条件付エントロピーについて記述した際に扱った例なのですが

 

晩御飯はカレーかラーメンの2択です。晩御飯を作るのは母親か姉のどちらかです。母親はカレーが好きなのでカレーを作る確率が高いです。姉はラーメンが好きなのでラーメンを作る確率が高いです。

 

このような状況を想像してください。

 

晩御飯を作る人が母親だとわかった時に今日の晩御飯は何である確率が高いと考えますか?

 

また、晩御飯としてラーメンが出てきた時に母親と姉のうちどちらが作った可能性が高いと考えますか?

 

上記の質問に答えることは難しいことではないと思います。

 

このように現在の事象が過去の履歴と関係するような情報源を記憶のある情報源とされマルコフ情報源と呼ばれます。

 

ここで以下の画像をみてください。

 

情報源は大きく分けて記憶があるか無いかの2種類に分けられますが、もう少し細かく考えると記憶があるマルコフ情報源の中にもエルゴードマルコフ情報源と正規マルコフ情報源と呼ばれる情報源があります

 

この話は余談になるので飛ばしてもらっても構いませんが、正規マルコフ情報源は以下の条件を持たしている必要があります。

  1. 全ての記号が満遍なく発生する
  2. 周期性を持たない
  3. 初期状態によらない

 

マルコフ情報源のエントロピー

 

無記憶情報源のエントロピーの計算を覚えていますか?

 

覚えていない方はこちらのページで確認ができるので気になった方はみてください。

 

情報理論におけるエントロピーとは何か

 

ここではマルコフ情報源のエントロピーの求め方について確認していきます。

 

以下の3次マルコフ情報源について考えていきます。

 

$$S={A,B,C}$$

 

この情報源が次の遷移状態行列Pを持つこととします。

 

$$P=\begin{bmatrix}
\frac{1}{2} & \frac{1}{2} & 0\\
\frac{1}{3} & 0 & \frac{2}{3}\\
\frac{2}{3} & 0 & \frac{1}{3}
\end{bmatrix}$$

 

この遷移状態行列が初対面だという方に簡単に説明します。

 

マルコフ情報源は1つ前の結果が今回の結果に影響を及ぼすような情報源です。

 

下の図をみていただくとわかりやすいかと思いますが、例えば1つ前の記号がAだったとします。

 

一番左のA1という文字をみてください。そこから右に目線を動かした時に(1/2,1/2,0)と3つの数字が確認できます。

 

その数字から上をみた時にA2,B2,C2という文字が確認できると思いますが、これが次の記号を表しています。

 

つまり1つ前の記号がAであった場合、1/2の確率でAかBになり、Cになる確率はないということを表しています。

 

 

このように一つ前の値によって次の値が変わるような情報源(マルコフ情報源)のエントロピーを求めていきましょう。

 

エントロピーの求め方

 

今回は正規マルコフ情報源のエントロピーの求め方についてです。

 

ここで覚えて欲しいことは正規マルコフ情報源には定常分布というものが存在するということです。

 

定常分布ってなに?という話になってきますが、遷移状態行列にしたがって値を決めていくと確率ベクトルが特定の値に収束して一意に決まるんですね。

 

簡単に説明するとA,B,Cが出る確率が一意に定まるということです。

 

そしてエントロピーを求めるためにはまずその定常分布を求めなければなりません。

 

定常分布zは以下のような式で求められます。

 

$$z=zP$$

 

上記の状態遷移行列の場合このような式になります。

 

$$(z_1,z_2,z_3)=(z_1,z_2,z_3)
\begin{pmatrix}
\frac{1}{2} & \frac{1}{2} & 0\\
\frac{1}{3} & 0 & \frac{2}{3}\\
\frac{2}{3} & 0 & \frac{1}{3}
\end{pmatrix}$$

 

この行列の計算をすると

$$z_1=2z_2$$

$$z_2=z_3$$

という関係式を導くことができます。

 

また、$$z_1,z_2,z_3$$は確率ベクトルであるため

$$z_1+z_2+z_3=1$$

というルールを持つことから定常分布は以下のようになります。

$$(z_1,z_2,z_3)=(\frac{1}{2},\frac{1}{4},\frac{1}{4})$$

 

そしてその次に1つ前の値がAだった場合、Bだった場合、Cだった場合に場合分けを行なってエントロピーの計算を行なっていきます。

 

$$H(S|A)=-\frac{1}{2}log\frac{1}{2}-\frac{1}{2}log\frac{1}{2}=1$$

$$H(S|B)=-\frac{1}{3}log\frac{1}{3}-\frac{2}{3}log\frac{2}{3}=log3-\frac{2}{3}$$

$$H(S|C)=-\frac{2}{3}log\frac{2}{3}-\frac{1}{3}log\frac{1}{3}=log3-\frac{2}{3}$$

 

そしてその後、全体のエントロピーを計算していくのですがここで先ほど求めた定常分布を用います。

 

$$H(S|S)=1\times\frac{1}{2}+(log3-\frac{2}{3})\times\frac{1}{4}+(log3-\frac{2}{3})\times\frac{1}{4}$$

 

ここから約0.959bitであることが求められました。

 

上の式はA,B,Cが定常分布に従って出ていると考えて、そこからエントロピーを計算するという流れです。

 

このようにマルコフ情報源の場合はエントロピーを求める際に無記憶情報源よりも面倒な計算をしなければなりません。

 

今回はこのあたりで。