マエカワの備忘録的な何か

思い立ったが吉日

情報通信システム　其の五　20170518

情報通信システム 3年科目

記憶のある情報源について

　これまで扱ってきたのはすべて記憶のない、独立した情報源集合．ここからは過去の状態に従属している情報源集合の扱い方について書いていく．

$m$ 重マルコフ情報源
　任意の時点での生起確率が直前 $m$ 個の出力に依存して決まる情報源
　状態遷移図のように書くと下の図のようになる(プリントから持ってきています)．

f:id:maekawa_yoshimiki_1119:20170524145351j:plain

状態分布 $\vec{w_t}=(w_0^{(t)},w_1^{(t)},...,w_{N-1}^{(t)})$
　時点 $t$ における確率分布のこと．

遷移確率行列 $P$
　 $i\to j$ に遷移する確率を $ij$ 成分に持った行列．

定常分布
　初期状態によらず、十分な家庭後に落ち着く定常的な状態の確率分布．
　　⇒簡単に言うと「記憶を持ってなかったとしたらどうなるのかのシミュレーション」

　導出の仕方は状態分布 $\vec{w}$ と遷移確率行列 $P$ を用いて

　　 $\displaystyle \vec{w}=\vec{w}P$

　　ただし $\displaystyle \sum_{i=0}^{N-1}w_i=1$ とする

　を計算して出てきた $\vec{w}$ と同じになっている．

$m$ 重マルコフ情報源のエントロピー $H(s)$

　　 $\displaystyle \begin{eqnarray}H(s)&=&\sum_{j=1}^{M^m}P(q_j)H(s|q_j)\\&=&-\sum_{j=1}^{M^m}P(q_j)\sum_{i=1}^{M}p(s_i|q_j)\log_rp(s_i|q_j)\end{eqnarray}$

　このときの $P(q_j)$ は状態 $q_j$ にいる確率．つまり、定常分布と同じ値をとることがわかる．

$n$ 次エントロピー $H_n(s)$ について
　定義は

　　 $\displaystyle H_n(s)=\frac{H(s^n)}{n}$

　となっている．
　記憶のない情報源集合だった場合、前回にも書いてある通り

　　 $H(s^n)=nH(s)$

　なので

　　 $H_n(s)=H(s)$

　になる．

　記憶のある情報源集合だった場合

　　 $\displaystyle \lim_{n\to\infty}H_n(s)=H(s)$

　になる．試行回数を増やしていくと定常分布のように、記憶のない情報源に近づくことを考えれば自然なこと．

　ここで少し問題を．資料にあるものを解いていきます．問題は以下のようなもの．

f:id:maekawa_yoshimiki_1119:20170524145414j:plain

f:id:maekawa_yoshimiki_1119:20170524214231j:plain

　記憶を持つ情報源の $n$ 次エントロピーの計算は記憶を持たない情報源の時と同じようにブロック符号化してあげればいい．上で紹介した極限が何チャラっていうのはおまけ程度に思っておけばいい．

　ついでにもう一つの練習問題の回答も載せておく．

f:id:maekawa_yoshimiki_1119:20170524221547j:plain

f:id:maekawa_yoshimiki_1119:20170524221405j:plain

未知情報源の符号化
　生起確率が不明な情報源のことを未知情報源と呼ぶ．
　このような情報源の符号化にはユニバーサル符号化という処理をしていく．

　　ユニバーサル符号化： $L$ を情報源エントロピーの近くまで下げくことができる．

　ある程度のひずみを許容する符号化もある．
　　⇒画像・音声の圧縮に使われる．この場合のひずみは人間が認識できないレベルのものとする．
　　⇒ $L$ を情報源エントロピーよりも下げることができる．荒くなっている分、短くできる．

　ユニバーサル符号化の例として、講義では「LZ77符号」が紹介された．
　色々資料を見てみたが、どれもアルゴリズムについての話ばかりで複雑．配られた資料の実行例を自分でなぞりながらやってみるのが一番だと思います。

　今回はこれで終了です。