平均互信息的凸性課件

1、平均互信息 定義及含義 信息/數(shù)據(jù)處理定理Review 性質(zhì)： 對(duì)稱性、非負(fù)性、極值性山農(nóng)信息論： 為設(shè)計(jì)有效而可靠的通信系統(tǒng)提供理論依據(jù) 2.給定信道，實(shí)現(xiàn)可靠通信的最大的傳輸速率即信道容量？ 信源編碼定理：RR(D)信道編碼定理：RC 問(wèn)題：對(duì)應(yīng)互信息的最大值和最小值是否存在？互信息凸性回答2個(gè)問(wèn)題：有效性，可靠性1.給定信源，保精度信源編碼所需最小編碼速率？凸集若集合（n維歐氏空間），有 且對(duì)任意實(shí)數(shù)，有顯然，n維歐氏空間 為一凸集合。01則稱為C為凸集合。概率矢量構(gòu)成集合為凸集定義 若一個(gè)K維矢量 =(1, 2, , K)的所有分量為非負(fù)的，且和為1，即就稱為概率矢量。引理 概率矢量全

2、體所構(gòu)成的區(qū)域R是凸的。證：若,R，對(duì)01構(gòu)造矢量=(1-)因此 是概率矢量，仍屬于R，所以R是凸的。凸函數(shù)定義定義在凸集R上的一個(gè)實(shí)函數(shù)f，若它對(duì)所有，R和01滿足 f()+(1 ) f ()f ( (1 ) 就稱函數(shù)f為R上的凸函數(shù)。若式中不等號(hào)的方向相反，就稱f為凸函數(shù)。若等號(hào)僅當(dāng)=0或1時(shí)成立，就稱f為嚴(yán)格凸或嚴(yán)格凸的。在a,b上定義的上凸函數(shù)在a,b上定義的下凸函數(shù)凸函數(shù)性質(zhì)1) 若f()是凸的，則-f()是凸的，反過(guò)來(lái)也成立。 2) 若f1(), f2(), fL()是R上的凸函數(shù)，c1,c2,cL是正數(shù)，則 為R上的凸函數(shù)，若其中任一個(gè)是嚴(yán)格凸的，則和式也是嚴(yán)格凸的。 3) (J

3、ensen不等式) 若f()是R上的凸函數(shù)，則Ef() f (E ()Jensen不等式: 若f()是R上的凸函數(shù)，則 E f() f (E () 其中，E表示數(shù)學(xué)期望。證明：只對(duì)離散情況證明。 對(duì)于離散變量，令 ，則E f() f (E () 可寫(xiě)成可用歸納法進(jìn)行證明。對(duì)兩點(diǎn)分布，根據(jù)凸函數(shù)的定義有假設(shè)當(dāng)分布點(diǎn)個(gè)數(shù)為n時(shí)不等式成立，考察分布點(diǎn)個(gè)數(shù)為n+1時(shí)的情況。對(duì) ，令 則有 定理: 如果函數(shù)f(x)在某個(gè)區(qū)間上存在非負(fù)(正)的二階導(dǎo)數(shù)，則 f(x)為該區(qū)間上的凸函數(shù)(嚴(yán)格凸函數(shù))。 證明：利用函數(shù)f(x)在x0點(diǎn)的泰勒級(jí)數(shù)展開(kāi):其中x*位于x0和x之間。根據(jù)假設(shè) ，因此，對(duì)任意的x，最后

4、一項(xiàng)總是非負(fù)。設(shè) ，01取 ，可得類似地，取 ，可得因此，得 證畢 同理可證：如果函數(shù)f(x)在某個(gè)區(qū)間上存在的二階導(dǎo)數(shù)0（ 0 對(duì)所有k = 0 其中為一常數(shù)。證：首先證明充分性。設(shè)函數(shù)f在點(diǎn)滿足KT條件，今證明 為極大值，即對(duì)任意 ，恒有 。由于f是凸函數(shù)，所以 f ()(1 ) f ()f (1 ) 0 1即f ()f ()f (1 )f ()/ 01因上式對(duì)任意 (0 1)成立，可令 0，得由KT條件有將其代入上式得從而證明 為極大值。現(xiàn)在證明必要性。令 使f 達(dá)到極大值，并假定偏導(dǎo)數(shù)在 處連續(xù)。則對(duì)任意 ,有式中01。以除兩邊并令0 得即因 為是概率矢量，所以至少有一個(gè)分量，例如i是

5、嚴(yán)格正的，即i0。選擇另一概率矢量滿足式中 。于是有對(duì)于 也可選負(fù)值和正數(shù)，有 和即對(duì) ，因?yàn)楦怕适噶康年P(guān)系只能選擇 ，由此, 得證畢熵的凸性證明：令則由于當(dāng)且僅當(dāng) 時(shí)等號(hào)成立平均互信息量凸性由互信息的定義式：可知，它是輸入分布 及轉(zhuǎn)移概率分布 的函數(shù)?？梢杂洖椋?如果轉(zhuǎn)移概率分布固定，I(X,Y)就是先驗(yàn)概率Q(X)的函數(shù)； 如果信源先驗(yàn)概率固定，I(X,Y)就是轉(zhuǎn)移概率P(Y/X)的函數(shù)。例 設(shè)二元對(duì)稱信道(BSC)的信源空間為：X=0,1; Q(X)=, 1-;求I(X;Y) 0 1-p 0 p p 1 1-p 1 因?yàn)橐阎D(zhuǎn)移概率，所以利用公式I(X,Y)=H(Y)-H(Y/X) 。

6、H(Y/X)=-q(xi) p(yj/xi) log p(yj/xi) =q(xi) -plog p+(1-p) log (1-p) =H(p) 其中：H(p)= -plog p+(1-p) log (1-p) 另外：為了求H(Y)，利用w(yj)= q(xi) p(yj/xi)；可得： w(y=0)=(1-p)+(1-)p w(y=1)=p+(1-)(1-p)H(Y)=-(1-p)+(1-)plog(1-p)+(1-)p+p+(1-)(1-p)logp+(1-)(1-p) =H(1-p)+(1-)p) 可得平均互信息量為： I(X,Y)=H(1-p)+(1-)p)-H(p)當(dāng)固定信源先驗(yàn)概率

7、分布時(shí)，I(X,Y)是信道轉(zhuǎn)移概率p的下凸函數(shù)，如圖所示。 0 1/2 1 p從圖中可知，當(dāng)信源固定后，存在一種BSC信道，p=1/2，使在信道輸出端獲得信息量最小，即等于0。 I(X,Y) H() 根據(jù)這個(gè)關(guān)系，當(dāng)p值一定，即固定信道，可知I(X,Y)是的上凸函數(shù)，其曲線如圖： I(X,Y) 1-H(p) 0 1/2 1 從圖中可知，當(dāng)BSC信道的信道矩陣固定后，若輸入符號(hào)集X的概率分布不同，在接收端平均每個(gè)符號(hào)獲得的信息量就不同。只有當(dāng)輸入為等概分布時(shí)即，p(0)=p(1)=1/2時(shí)，接收端的信息量才為最大值1-H(p)。定理2.5.2 當(dāng)條件分布 p(y/x)給定時(shí)，平均互信息I(X;Y

8、)是輸入分布q(x)的凸函數(shù)。證明：令q1和q2是輸入集X上的任意兩個(gè)概率矢量，相應(yīng)的互信息為I1和I2，令滿足01，q=q1(1)q2是合成概率矢量，此時(shí)輸入X和輸出Y之間的互信息為I。 今需要證明: . 令p1(xy)=q1(x)p(y/x), p2(xy)=q2(x)p(y/x), 有 p(xy)= q(x)p(y/x)=p1(xy) (1) p2(xy) 根據(jù)平均互信息的定義，得 因?yàn)?log x 是嚴(yán)格凸函數(shù)， 利用Jensen不等式， 所以 當(dāng)信道一定時(shí)，平均互信息是信源先驗(yàn)概率的上凸函數(shù)對(duì)于一定的信道轉(zhuǎn)移概率分布，總可以找到一個(gè)先驗(yàn)概率分布為P的信源X，使平均互信息達(dá)到相應(yīng)的最大

9、值Imax，這時(shí)稱這個(gè)信源為該信道的匹配信源。不同的信道轉(zhuǎn)移概率對(duì)應(yīng)不同的Imax，或者說(shuō)Imax是P(Y/X)的函數(shù)。 平均互信息的凸性定理2.5.3 當(dāng)集X的概率分布保持不變時(shí)，平均互信息量是轉(zhuǎn)移概率分布p(y/x)的下凸函數(shù)。證明：令p1和p2是兩個(gè)任意轉(zhuǎn)移概率分布，相應(yīng)的平均互信息為I1和I2，令滿足01,p=p1(1)p2是合成條件概率分布，此時(shí)輸入X和輸出Y之間的互信息為I。今需要證明 . 令 根據(jù)平均互信息的定義，得因?yàn)閘ogx是嚴(yán)格凸函數(shù)，利用Jensen不等式，所以 證畢 當(dāng)信源一定，平均互信息是信道轉(zhuǎn)移概率的下凸函數(shù)對(duì)于一個(gè)已知先驗(yàn)概率為P的離散信源，總可以找到一個(gè)轉(zhuǎn)移概率分布為P(Y/X)的信道，使平均互信息達(dá)到相應(yīng)的最小