平均互信息的凸性課件

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

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

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

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

5、嚴格正的，即i0。選擇另一概率矢量滿足式中 。于是有對于 也可選負值和正數(shù)，有 和即對 ，因為概率矢量的關系只能選擇 ，由此, 得證畢熵的凸性證明：令則由于當且僅當 時等號成立平均互信息量凸性由互信息的定義式：可知，它是輸入分布 及轉移概率分布 的函數(shù)。可以記為： 如果轉移概率分布固定，I(X,Y)就是先驗概率Q(X)的函數(shù)； 如果信源先驗概率固定，I(X,Y)就是轉移概率P(Y/X)的函數(shù)。例 設二元對稱信道(BSC)的信源空間為：X=0,1; Q(X)=, 1-;求I(X;Y) 0 1-p 0 p p 1 1-p 1 因為已知轉移概率，所以利用公式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)當固定信源先驗概率

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

8、)是輸入分布q(x)的凸函數(shù)。證明：令q1和q2是輸入集X上的任意兩個概率矢量，相應的互信息為I1和I2，令滿足01，q=q1(1)q2是合成概率矢量，此時輸入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ù)平均互信息的定義，得 因為 log x 是嚴格凸函數(shù)， 利用Jensen不等式， 所以 當信道一定時，平均互信息是信源先驗概率的上凸函數(shù)對于一定的信道轉移概率分布，總可以找到一個先驗概率分布為P的信源X，使平均互信息達到相應的最大

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