情報理論のバックアップ(No.8)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
情報理論へ行く。
- 1 (2007-11-06 (火) 13:08:14)
- 2 (2008-02-03 (日) 04:48:22)
- 3 (2008-02-03 (日) 08:22:29)
- 4 (2008-02-03 (日) 10:20:10)
- 5 (2008-02-03 (日) 15:49:51)
- 6 (2008-02-03 (日) 21:34:26)
- 7 (2008-02-04 (月) 23:35:20)
- 8 (2008-02-05 (火) 04:20:22)

講義日程-2007年度冬学期

情報理論 †

担当：山本博資教授
1.5単位
- 物工：限定選択
- 数理：限定選択B
- システム：限定選択C
08:30-10:00 工学部六号館 63講義室

出席はとらないが、私語等、授業の邪魔を一切してはいけない。
講義中にはパソコンを一切使用してはいけない。
試験(３時間)で成績評価する。例年２～３割不可るので、やる気がないならとらない方が良い。
レジュメは講義当日もしくは翌週の講義で入手できる。それ以外の日では入手不可能。
レジュメは無断コピー禁止。

http://ocw.hokudai.ac.jp/Course/Faculty/Engineering/InformationTheory/2005/index.php?lang=ja&page=materials
- 北海道大学のOCW資料。具体例が豊富で参考になる。

同時分布 $P(x,y)$ に対して、
周辺分布 $P(x)=\sum_{y\in \chi}P(x,y)$ ： $y$ を指定しないときの $x$ の分布
条件付き分布 $P(y|x)=\frac{P(x,y)}{P(x)}$ ：特定の $x$ が実現したと分かったときの $y$ の分布
大数の弱法則：平均と分散の存在する同一の分布に独立に従う多数の確率変数の平均は
分布の平均に確率収束する。
ダイバージェンス：二つの確率分布 $P(x),Q(x)$ に対して、
$D(P||Q)=\sum_{x\in \chi}P(x)\log\frac{P(x)}{Q(x)}$
二つの確率分布の類似性を表す。非負実数。値が0になるのは同一の分布に対してのみ。
エントロピー：確率分布 $P(x)$ に対して、 $H(X)=-\sum_{x\in \chi}P(x)\log P(x)$
$X$ のどれかが実現したときに得られる情報量の平均値。
標準系列：特定の確率分布に従って毎回独立に生成される系列で、
各文字の出現回数の比率が出現確率に十分近いもの。
各標準系列の出現確率は $2^{-nH(X)}$ くらい
標準系列の種類は $2^{nH(X)}$ ほど。
$n$ は系列の長さ。 $H(X)$ は各文字の出現確率のエントロピー。対数の底は2をとっている。
同時エントロピー： $H(X,Y)=-\sum_{x,y}P(x,y)\log P(x,y)$
条件付きエントロピー： $H(Y|X)=-\sum_{x,y}P(x,y)\log P(y|x)$
条件付きエントロピーのチェインルール： $H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)$
相互情報量： $I(X;Y)=H(X)-H(X|Y)$ 、 $Y$ を知ることで $X$ について得られる情報量。
条件付き相互情報量： $I(X;Y|Z)=H(X|Z)-H(X|Y,Z)$ 、 $Z$ を知った上で $Y$ を知ったときに、 $X$ について得られる情報量。
相互情報量のチェインルール
$I(X;Y,Z)=I(X;Z)+I(X;Y|Z)$
$I(X,Y;Z)=I(X;Z)+I(Y;Z|X)$
定常情報源
確率過程が定常であるとは、時刻原点を任意にずらしても
任意の系列の生起確率が変化しないこと。
定常無気力情報源
確率過程の各ステップが独立に同一の確率分布に従うこと。
エントロピーレート
定常な離散時間確率過程について、
$H(X)=\lim_{n\to \infty}H(X_{n}|X_{1},X_{2},\cdots ,X_{n-1})$
それ以前に生起した文字がすべてわかっているときの、次の1文字が持っている情報量。

Presented by yambi. tzik all blame reserved.
面倒かもしれませんが，ミスは指摘してくださると助かります．

1. 確率変数 $X,Y,Z$ に対して， $H(X)=5$ bits, $H(Z)=3$ bits, $H(XY)=6$ bits, $H(XZ)=8$ bits, $I(X;Y)=3$ bits の関係がある．

(A) $H(Y), H(Y|X), H(X|Y)$ の値は？
- 解
  
  $H(Y)=H(XY)-H(X|Y)=6-2=4$
  
  $H(Y|X)=H(XY)-H(X)=6-5=1$
  
  $H(X|Y)=H(X)-I(X;Y)=5-3=2$

(B) $X$ と $Z$ ， $Y$ と $Z$ それぞれに関して，次のどれが成立するか理由をつけて述べよ．
- 確率的に独立である．
- 確率的に独立でない．
- 判定不能．
- 解
  $H(Z|X)=H(XY)-H(Z)=8-3=5$ より， $H(X)=H(Z|X)$ なので， $X$ と $Z$ は確率的に独立．
  $H(YZ)$ を求める方法がないので $Y$ と $Z$ の独立性は判定不能．（私には判定できないでも可，なのかな．）

2. アルファベット $\mathcal{X}=\{a,b,c\}$ 上の値をとる定常な単純マルコフ過程の遷移確率が次のように与えられている．
現状態 $\backslash$ 次状態 a b c
a 0.5 0.5 0
b 0.4 0 0.6
c 0.4 0.6 0

$P_{X_t}(a), P_{X_t}(b), P_{X_t}(c)$ を求めよ．
- 解
  状態遷移行列を $A$ と書くことにする．
  $A^{\top}$ の固有値1に対応する固有ベクトルは $(32/72\ 25/72\ 15/72)^{\top}$ なので， $P_{X_t}(a)=32/72=4/9,\ P_{X_t}(b)=25/72,\ P_{X_t}(c)=15/72$ である．

この情報源のエントロピーレート $H(X)$ を，関数 $h(t)=-t\lg t-(1-t)\lg(1-t)$ を用いて表せ．
- 解
  
  $\begin{align}H(X)&=P(X_{t-1}(a))H(X_t|X_{t-1}=a)+P(X_{t-1}(b))H(X_t|X_{t-1}=b)+P(X_{t-1}(c))H(X_t|X_{t-1}=c)\\&=\frac{4}{9}h(0.5)+\frac{25}{72}h(0.4)+\frac{15}{72}h(0.4)\\&=\frac{4}{9}h(0.5)+\frac{5}{9}h(0.4)}\end{align}$

3. 情報源符号化に関して，次の2つの相違を説明すると共に，それらを比較した時の互いに得失を説明せよ．
- FV符号とVF符号
  - 解
    FV符号は入力を固定長で区切って，それぞれに可変長の符号化を施すもの．
    VF符号は入力を可変長で区切って，それぞれに固定長の符号化を施すもの．
    FV符号はビット誤りに対して復号誤り伝搬が生じるが，VF符号ではそうはならない．
    VF符号は欠点が思いつきにくいが，FV符号は思いつきやすい．

Huffman符号と算術符号
- 解
  ハフマン符号は頻繁に出てくる記号を短いビット列で符号化し，あまり出てこない記号は長いビット列で符号化することによりデータ圧縮をする．
  算術符号は記号列を[0,1]区間の部分集合に対応させるもので，頻繁に出てくる記号列を広い区間に，あまり出てこない記号列は小さい区間に対応付けることによりデータ圧縮をする．
  算術符号はHaffman符号化より圧縮率が良い．
  算術符号はHaffman符号化より手順がややこしい．

エントロピー符号化とユニバーサル符号化
- 解
  エントロピー符号化はデータ系列の確率分布を利用して符号化を行うもの．
  ユニバーサル符号化はデータ系列の確率分布を利用せずに符号化を行うもの．
  エントロピー符号化は効率的に圧縮できるがデータの確率分布を知らなければならない．
  ユニバーサル符号化は効率的に圧縮できないがデータの確率分布を知らなくてもよい．

4. 2つの情報源出力 $X$ と $Y$ を歪を許して情報源符号化する場合を考える．
- 情報源出力 $X$ と $Y$ が共に2値で，その生起確率が $P_X(0)=1-P_X(1)=0.3,\ P_Y(0)=1-P_Y(1)=0.2$ で与えられているものとする．歪をハミング歪で測るものとして， $X$ を平均歪み $D_X=0.2$ まで許して符号化する場合と $Y$ を平均歪み $D_Y=0.1$ まで許して符号化する場合について考える．最適な符号化が行える場合，どちらの方がより多くの符号化レートを必要とするか？
  - 解
    2値情報源におけるハミング歪のレート歪関数は $R^*(D)=h(q)-h(D)$ で与えられる（ $0\le D\le q\le 0.5$ ）．
    $x=\frac{h(0.3)-h(0.2)}{0.1}$ ， $y=\frac{h(0.2)-h(0.1)}{0.1}$ とおくと $h(t)$ は凹関数なので $x<y$ ．
    よって $Y$ の方がより多くの符号化レートを必要とする．

情報源出力 $X$ と $Y$ が，それぞれの分散 $\sigma_X^2=10,\ \sigma_Y^2=3$ を持つ正規分布に従うものとする．歪みを2乗誤差歪みで測るものとして， $X$ を平均歪 $D_X=5$ まで許して符号化する場合と， $Y$ を平均歪み $D_Y=2$ までえ許して符合化する場合を考える．最適な符号化が行える場合，どちらのほうがより多くの符号化レートを必要とするか？
- 解
  分散 $\sigma^2$ の正規分布における2乗誤差歪の符号化レートは $\frac{1}{2}\lg\frac{\sigma^2}{D}$ で与えられる．
  $X$ の符号化レートは $\frac{1}{2}\lg\frac{10}{5}=\frac{1}{2}$ ， $Y$ の符号化レートは $\frac{1}{2}\lg\frac{3}{2}$ なので， $X$ がより多くの符号化レートを必要とする．

5. 通信路の入力アルファベット $\mathcal{X}$ と出力アルファベット $\mathcal{Y}$ が $\mathcal{X}=\{a_1,a_2,a_3},\ \mathcal{Y}=\{b_1,b_2,b_3\}$ であるとする．このとき，通信路の遷移確率 $P(y|x)$ 次のように与えられる時，それぞれの通信路容量 $C$ を関数 $h(t)=-t\log_2 t-(1-t)\log_2(1-t)$ を用いて表せ．

$\backslash$	$b_1$	$b_2$	$b_3$
$a_1$	0.8	0.2	0
$a_2$	0	0.8	0.2
$a_3$	0.2	0	0.8

解
これは一様通信路なので，
$C=\lg 3+\sum_{y\in\mathcal{Y}}P(y|x)\lg P(y|x)=\lg 3-3*\frac{1}{3}h(0.2)=\lg 3-h(0.2)$

$\backslash$	$b_1$	$b_2$	$b_3$
$a_1$	0.3	0	0.7
$a_2$	0	1	0
$a_3$	0.7	0	0.3

解
$\mathcal{X_1}=\{a_1,a_3\}, \mathcal{Y_1}=\{b_1,b_3\}$ からなる通信路 $C_1$ と $\mathcal{X_2}=\{a_2\}, \mathcal{Y_2}=\{b_2\}$ からなる通信路 $C_1$ との和通信路なので，
$C_1=\lg 2+\sum_{y\in\mathcal{Y}}P(y|x)\lg P(y|x)=\lg 2-h(0.3)$

$C_2=\lg 1+\sum_{y\in\mathcal{Y}}P(y|x)\lg P(y|x)=0$
より，
$C=\lg(2^{C_1}+2^{C_2})=\lg(2*2^{-h(0.3)}+1)$

6. 生成行列 $G$ が次式で与えられるハミング符号がある．
$G=\begin{pmatrix}1&0&0&0&1&1&1\\0&1&0&0&1&1&0\\0&0&1&0&1&0&1\\0&0&0&1&0&1&1\end{matrix}$
- この符号の符号化レート $R$ を求めよ．
  - 解
    
    $R=\frac{K}{N}=\frac{4}{7}$

$\bold{y}=(1100010)$ を受信した時，そのシンドロームを求め，この $\bold{y}$ に誤りが含まれているか否かを定めよ．誤りがない場合は「誤りなし」と下記，その理由を説明せよ．また，誤りが含まれている場合は，1ビットの誤りであると仮定してその誤りを訂正せよ．
- 解
  
  $H=\begin{pmatrix}1&1&1&0&1&0&0\\1&1&0&1&0&1&0\\1&0&1&1&0&0&1\end{pmatrix}$
  より，
  $\bold{y}H^{\top}=(0\ 1\ 1)$
  となるので誤りがある．
  また，誤りを1ビットであると仮定すると，4ビット目であるので，正しい受信信号は
  $\begin{pmatrix}1&1&0&1&0&1&0\end{pmatrix}$
  である．

このハミング符号に対して，誤り訂正は行わないで誤り検出のみを行うとき，何ビットの誤りまで検出可能か？
- 解
  2ビットまで．
  3ビットだと2,3,4ビット目などを誤られると検出不能．

7. 次の各説明が正しいか誤っているかを解答せよ．ただし，誤っている場合は，その理由を説明せよ．
- エントロピー $H(X)$ ，微分エントロピー $H_d(X)$ ，相互情報量 $I(X:Y)$ ，相対エントロピー $D(P\| Q)$ などの情報量は全て非負の量である．
  - 解
    上の4つについては正しい．
    しかしながら作為的な定義をすれば負の値を持つ情報量を定義することはたやすい（エントロピーから1を引いたものなど）．ところで情報量の定義ってなに？

FV符号において，長さ2ビットの符号語が1個，長さ3ビットの符号語が4個，長さ4ビットの符号語が3個，長さ5ビットの符号語が4個の符号は，工夫すれば瞬時符号として作れる．
- 解
  クラフトの不等式について
  $\sum_{x\in\mathcal{X}}2^{-l(x)}=2^{-2}+2^{-3}\times 4+2^{-4}\times 3+2^{-5}\times 4=\frac{17}{16}>1$
  となるので，瞬時符号は存在しない．

誤り訂正符号における最尤復号法は，常に最小の復号誤り率を達成できるため，広く用いられている．
- 解
  常にが間違い．符号語が等確率で生起する場合でのみしか最小の復号誤り率を達成できない．

$\{0,1\}$ を100ビット用いると $2^{100}$ の情報を表現できる．しかし，通信路容量 $C=0.1$ を持つ2値対称通信路を通して情報を伝送する場合は，誤りが生じる可能性がある．誤り訂正するためには $2^{100}$ 個全てを符号語として用いることができず，冗長性を持たせてその一部のみ符号語として用いることになる．通信路容量 $C$ が0.1なので，十分余裕を見て $0.001\times 2^{100}$ 個程度の符号後を，ハミング距離が互いにもっとも離れるように配置すれば，十分小さい復号誤り率を達成できる誤り訂正符号が作れる．
- 解
  符号化レートは $\frac{\lceil\lg 0.001\times 2^{100}\rceil}{100}>\frac{100-11}{100}=0.89>0.1=C$ なので通信路符号化定理の強逆定理より復号誤り率は符号語長を長くすると1に近づいてしまう．

雑音電力密度 $N_0=$ (Watt/Hz)を持つ加法的白色ガウス雑音通信路に対して，時間連続信号波形 $x(t)$ を用いて情報を伝送する場合を考える． $x(t)$ を用いて最大で $1/2W$ 秒ごとに独立な情報を送ることができる．したがって，信号電力 $S$ が一定の時，帯域幅 $W$ を大きくすれば送れる情報量が増え，その通信路容量 $C$ も $W$ の増加につれていくらでも大きくできる．
- 解
  
  $C=W\lg\left(1+\frac{S}{N_0W}\right)=\frac{W}{\ln 2}\left(\frac{S}{N_0W}+\frac{S^2}{N_0^2W^2}+\dots\right)\to \frac{S}{\ln 2N_0}$
  と $W$ を増加させても $\frac{S}{\ln 2N_0}$ に収束してしまう．

現状態 $\backslash$ 次状態	a	b	c
a	0.5	0.5	0
b	0.4	0	0.6
c	0.4	0.6	0

情報理論 のバックアップ(No.8)

情報理論 †

情報理論のバックアップ(No.8)