情報源と情報量

　データ列からある要素を取り出したとき、その要素の持つ情報量は- log pで定義される。ただし、pとはその要素の出現する確率であるとする。
　データ列を生成した情報源が無記憶情報源であると仮定できるなら、pは十分に長い間データ列を観測し、統計を取る事で求められる。例えば、さいころを振った結果というのは、無記憶情報源から生成された情報であると仮定してよいであろう。無記憶情報源から生成されたデータ列は、そのエントロピー以下のサイズに圧縮することはできない。
　それに対し、一般的に人間が生成したデータ列は複雑な相互依存関係を持ち、その依存関係を用いる事で、さらに圧縮が可能である。データの要素がそれ以前のデータ列に依存するようなデータ列を生成する情報源をマルコフ情報源という。マルコフ情報源におけるエントロピーは一般に、無記憶情報源よりも小さくなる。つまり、データ圧縮の下限サイズは無記憶情報源の場合よりも小さくなる。では、マルコフ情報源における確率は、どのようにして求めればよいだろうか？
　基本的には無記憶情報源の場合と同じで、十分に長い間データ列を観測し、統計を取れば良い。ここで、2つの問題が出てくる。直前のN個の要素にのみデータの出現確率が依存するような情報源をN重マルコフ情報源という。まず問題としなければならないのは、このNの大きさをどうやって決めるかである。もちろん、理想的にはN=∞と取りたいのだが、計算機資源は有限であるため、無限のデータを記録することはできない。また、一般には観測できるデータ列の量も決まっているので、信頼性のあるデータを取るためにも、Nの値は制限する必要がある。Nの値が制限されてしまうことで、マルコフ情報源における要素の出現確率pは正しく推定できなくなる。例えば、データがN重マルコフ情報源から生成されたと仮定して統計を取っているのに、実際にはN+1重マルコフモデルからデータが生成されていたとしたらどうなるだろうか？正しい確率の推定は不可能だろう。（もちろん、無記憶情報源であると仮定するよりはマシな結果を出せるが、下限サイズにまで圧縮は出来ない。）
　情報源が記憶を持つと仮定した瞬間に、それは現実のデータ圧縮の下限を定める。N=∞のマルコフ情報源は、この世の全ての情報源を含む。（はず。マルコフ情報源のきちんとした定義にあたってないので、そうは解釈できないかもしれないけど、その場合でも簡単な拡張でこの世の全ての情報源を含むようにできるはずだ。）つまり、N=∞のマルコフ情報源とは、それほど強力な概念なのである。
　というような事を修論用に書いていたのだけれど、最後まで書ききれなかったので修論には載せなかった。（そもそも予測入力の問題なので、これを書いた後にさらに情報圧縮と予測入力の共通点について論じなければならない。）普通の論文にはこういう事を書くスペースはないし、後期課程に行くことがあっても予測入力はやらないだろう。つまり、もう他に載せる場所がない。のでここに置いておく。
　よく考えたらここまでは非常にありきたりな事しか書いてないな…。