信息論基礎(chǔ) 1~8

1 緒論與概覽

2 熵 相對(duì)熵與互信息

2.1 熵

2.2 聯(lián)合熵

定理2.2.1(鏈?zhǔn)椒▌t): H(X,Y)=H(X)+H(Y|X)H(X,Y)=H(X)+H(Y|X)

2.3 相對(duì)熵與互信息

相對(duì)熵(relative entropy): D(p||q)=∑x∈Xp(x)logp(x)q(x)=Eplogp(x)q(x)D(p||q)=∑x∈Xp(x)log?p(x)q(x)=Eplog?p(x)q(x)

互信息(mutual information): I(X;Y)=∑x∈X∑y∈Yp(x,y)logp(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))I(X;Y)=∑x∈X∑y∈Yp(x,y)log?p(x,y)p(x)p(y)=D(p(x,y)||p(x)p(y))

2.4 熵與互信息的關(guān)系

互信息I(X;Y)是在給定Y知識(shí)的條件下X的不確定度的縮減量

2.5 熵,相對(duì)熵與互信息的鏈?zhǔn)椒▌t

定理2.5.1(熵的鏈?zhǔn)椒▌t): H(X1,X2,…,Xn)=∑ni=1H(Xi|Xi?1,…,X1)H(X1,X2,…,Xn)=∑i=1nH(Xi|Xi?1,…,X1)

定理2.5.2(互信息的鏈?zhǔn)椒▌t): I(X1,X2,…,Xn;Y)=∑ni=1I(Xi;Y|Xi?1,…,X1)I(X1,X2,…,Xn;Y)=∑i=1nI(Xi;Y|Xi?1,…,X1)

條件相對(duì)熵: D(p(y|x)||q(y|x))=∑xp(x)∑yp(y|x)logp(y|x)q(y|x)=Ep(x,y)logp(Y|X)q(Y|X)D(p(y|x)||q(y|x))=∑xp(x)∑yp(y|x)log?p(y|x)q(y|x)=Ep(x,y)log?p(Y|X)q(Y|X)

定理2.5.3(相對(duì)熵的鏈?zhǔn)椒▌t): D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))

2.6 Jensen不等式及其結(jié)果

定理2.6.2(Jensen不等式): 若給定凸函數(shù)f和一個(gè)隨機(jī)變量X,則 Ef(X)≥f(EX)Ef(X)≥f(EX)

定理2.6.3(信息不等式): D(p||q)≥0D(p||q)≥0

推論(互信息的非負(fù)性): I(X;Y)≥0I(X;Y)≥0

定理2.6.4: H(X)≤log|X|H(X)≤log?|X|

定理2.6.5(條件作用使熵減小): H(X|Y)≤H(X)H(X|Y)≤H(X)

從直觀上講,此定理說(shuō)明知道另一隨機(jī)變量Y的信息只會(huì)降低X的不確定度. 注意這僅對(duì)平均意義成立. 具體來(lái)說(shuō), H(X|Y=y)H(X|Y=y) 可能比H(X)H(X)大或者小,或者兩者相等.

定理2.6.6(熵的獨(dú)立界): H(X1,X2,…,Xn)≤∑ni=1H(Xi)H(X1,X2,…,Xn)≤∑i=1nH(Xi)

2.7 對(duì)數(shù)和不等式及其應(yīng)用

定理2.7.1(對(duì)數(shù)和不等式): ∑ni=1ailogaibi≥(∑ni=1ai)log∑ni=1ai∑ni=1bi∑i=1nailog?aibi≥(∑i=1nai)log?∑i=1nai∑i=1nbi

定理2.7.2(相對(duì)熵的凸性): D(p||q)D(p||q) 關(guān)于對(duì)(p,q)是凸的

定理2.7.3(熵的凹性): H(p)是關(guān)于p的凹函數(shù)

2.8 數(shù)據(jù)處理不等式

2.9 充分統(tǒng)計(jì)量

這節(jié)很有意思,利用統(tǒng)計(jì)量代替原有抽樣,并且不損失信息.

2.10 費(fèi)諾不等式

定理2.10.1(費(fèi)諾不等式): 對(duì)任何滿足 X→Y→X^,X→Y→X^, 設(shè) Pe=Pr{X≠X^},Pe=Pr{X≠X^}, 有

上述不等式可以減弱為

或

引理 2.10.1: 如果X和X’獨(dú)立同分布,具有熵H(X),則

3 漸進(jìn)均分性

4 隨機(jī)過程的熵率

4.1 馬爾科夫鏈

4.2 熵率

4.3 例子:加權(quán)圖上隨機(jī)游動(dòng)的熵率

4.4 熱力學(xué)第二定律

4.5 馬爾科夫鏈的函數(shù)

5 數(shù)據(jù)壓縮

5.1 有關(guān)編碼的幾個(gè)例子

5.2 Kraft不等式

定理5.2.1(Kraft不等式): 對(duì)于D元字母表上的即時(shí)碼,碼字長(zhǎng)度 l1,l2,…,lml1,l2,…,lm必定滿足不等式

5.3 最優(yōu)碼

5.4 最優(yōu)碼長(zhǎng)的界

5.5 唯一可譯碼的Kraft不等式

5.6 赫夫曼碼

5.7 有關(guān)赫夫曼碼的評(píng)論

5.8 赫夫曼碼的最優(yōu)性

5.9 Shannon-Fano-Elias編碼

5.10 香農(nóng)碼的競(jìng)爭(zhēng)最優(yōu)性

5.11由均勻硬幣投擲生成離散分布

6 博弈與數(shù)據(jù)壓縮

6.1 賽馬

6.2 博弈與邊信息

6.3 相依的賽馬及其熵率

6.4 英文的熵

6.5 數(shù)據(jù)壓縮與博弈

6.6 英語(yǔ)的熵的博弈估計(jì)

7 信道容量

離散信道: C=maxp(x)I(X;Y)C=maxp(x)I(X;Y)

7.1 信道容量的幾個(gè)例子

7.2 對(duì)稱信道

如果信道轉(zhuǎn)移矩陣 p(y|x)p(y|x) 的任何兩行相互置換,任何兩列也相互置換,那么稱該信道是對(duì)稱的.

7.3 信道容量的性質(zhì)

7.4 信道編碼定理預(yù)覽

7.5 定義

7.6 聯(lián)合典型序列

7.7 信道編碼定理

7.8 零誤差碼

7.9 費(fèi)諾不等式與編碼定理的逆定理

7.10 信道編碼定理的逆定理中的等式

7.11 漢明碼

7.12 反饋容量

7.13 信源信道分離定理

8 微分熵

8.1 定義

均勻分布 h(X)=logah(X)=log?a

正態(tài)分布 h(X)=1/2log2πeδ2h(X)=1/2log?2πeδ2

8.2 連續(xù)隨機(jī)變量的AEP

8.3 微分熵與離散熵的關(guān)系

8.4 聯(lián)合微分熵與條件微分熵

8.5 相對(duì)熵與互信息

8.6 微分熵, 相對(duì)熵以及互信息的性質(zhì)