平均互信息的凸性

平均互信息的凸性第一頁，共三十四頁，2022年，8月28日平均互信息定義及含義信息/數(shù)據(jù)處理定理Review性質(zhì)：對稱性、非負性、極值性第二頁，共三十四頁，2022年，8月28日山農(nóng)信息論：為設(shè)計有效而可靠的通信系統(tǒng)提供理論依據(jù)

2.給定信道，實現(xiàn)可靠通信的最大的傳輸速率即信道容量？信源編碼定理：R>R(D)信道編碼定理：R<C

問題：對應互信息的最大值和最小值是否存在？互信息凸性回答2個問題：有效性，可靠性1.給定信源，保精度信源編碼所需最小編碼速率？第三頁，共三十四頁，2022年，8月28日凸集若集合（n維歐氏空間），有且對任意實數(shù)，有顯然，n維歐氏空間為一凸集合。0≤λ≤1則稱為C為凸集合。第四頁，共三十四頁，2022年，8月28日概率矢量構(gòu)成集合為凸集定義若一個K維矢量=(1,2,…,K)的所有分量為非負的，且和為1，即就稱為概率矢量。引理概率矢量全體所構(gòu)成的區(qū)域R是凸的。證：若,β∈R，對0≤≤1構(gòu)造矢量=＋(1-)β因此是概率矢量，仍屬于R，所以R是凸的。第五頁，共三十四頁，2022年，8月28日凸函數(shù)定義定義在凸集R上的一個實函數(shù)f，若它對所有α，β∈R和0≤≤1滿足

f()+(1－

)f(β)≤f(

＋(1－

)β)就稱函數(shù)f為R上的凸∩函數(shù)。若式中不等號的方向相反，就稱f為凸∪函數(shù)。若等號僅當=0或1時成立，就稱f為嚴格凸∩或嚴格凸∪的。第六頁，共三十四頁，2022年，8月28日在[a,b]上定義的上凸函數(shù)第七頁，共三十四頁，2022年，8月28日在[a,b]上定義的下凸函數(shù)第八頁，共三十四頁，2022年，8月28日凸函數(shù)性質(zhì)1)若f()是凸∩的，則-f()是凸∪的，反過來也成立。2)若f1(),f2(),…,fL()是R上的凸∩函數(shù)，c1,c2,…,cL是正數(shù)，則為R上的凸∩函數(shù)，若其中任一個是嚴格凸的，則和式也是嚴格凸的。

3)(Jensen不等式)若f()是R上的凸∩函數(shù)，則E[f()]

≤

f(E())第九頁，共三十四頁，2022年，8月28日Jensen不等式:若f()是R上的凸∩函數(shù)，則

E[f()]≤f(E())

其中，E表示數(shù)學期望。證明：只對離散情況證明。對于離散變量，令，則E[f()]≤f(E())可寫成可用歸納法進行證明。對兩點分布，根據(jù)凸函數(shù)的定義有假設(shè)當分布點個數(shù)為n時不等式成立，考察分布點個數(shù)為n+1時的情況。第十頁，共三十四頁，2022年，8月28日對，令則有

第十一頁，共三十四頁，2022年，8月28日定理:

如果函數(shù)f(x)在某個區(qū)間上存在非負(正)的二階導數(shù)，則f(x)為該區(qū)間上的凸∪函數(shù)(嚴格凸∪函數(shù))。證明：利用函數(shù)f(x)在x0點的泰勒級數(shù)展開:其中x*位于x0和x之間。根據(jù)假設(shè)，因此，對任意的x，最后一項總是非負。設(shè)，0<λ<1取，可得類似地，取，可得第十二頁，共三十四頁，2022年，8月28日因此，得

證畢

同理可證：如果函數(shù)f(x)在某個區(qū)間上存在的二階導數(shù)≤0（<0)，則f(x)為該區(qū)間上的上的凸∩函數(shù)(嚴格凸∩函數(shù))。第十三頁，共三十四頁，2022年，8月28日利用該定理，可以立即判定：

都是嚴格凸∪函數(shù)，為嚴格凸∩函數(shù)。

第十四頁，共三十四頁，2022年，8月28日令是定義在R上的凸∩函數(shù)，其中=(1,2,…,K)存在且在R域上連續(xù)，在R上為極大的充分必要條件是凸函數(shù)性質(zhì)Kuhn-Tucker條件為一概率矢量。假定偏導數(shù)

對所有’k>0

對所有’k=0其中為一常數(shù)。第十五頁，共三十四頁，2022年，8月28日證：首先證明充分性。設(shè)函數(shù)f在點滿足KT條件，今證明為極大值，即對任意，恒有。由于f是凸∩函數(shù)，所以

f()＋(1－

)f()≤f[

＋(1－

)]0＜＜1即f()－f()≤{f[

＋(1－

)]－f()}/

0＜＜1第十六頁，共三十四頁，2022年，8月28日因上式對任意(0＜＜1)成立，可令→0，得第十七頁，共三十四頁，2022年，8月28日由KT條件有將其代入上式得從而證明為極大值。現(xiàn)在證明必要性。令使f達到極大值，并假定偏導數(shù)在處連續(xù)。則對任意,有式中0＜＜1。以θ除兩邊并令θ→0得第十八頁，共三十四頁，2022年，8月28日即因為是概率矢量，所以至少有一個分量，例如i是嚴格正的，即i>0。選擇另一概率矢量滿足式中。于是有對于也可選負值和正數(shù)，有和第十九頁，共三十四頁，2022年，8月28日即對，因為概率矢量的關(guān)系只能選擇，由此,得證畢第二十頁，共三十四頁，2022年，8月28日熵的凸性證明：令則由于當且僅當時等號成立第二十一頁，共三十四頁，2022年，8月28日平均互信息量凸性由互信息的定義式：可知，它是輸入分布及轉(zhuǎn)移概率分布的函數(shù)?？梢杂洖椋喝绻D(zhuǎn)移概率分布固定，I(X,Y)就是先驗概率Q(X)的函數(shù)；如果信源先驗概率固定，I(X,Y)就是轉(zhuǎn)移概率P(Y/X)的函數(shù)。第二十二頁，共三十四頁，2022年，8月28日[例]

設(shè)二元對稱信道(BSC)的信源空間為：X={0,1};[Q(X)]={ω,1-ω};求I(X;Y)

01-p0pp

11-p1因為已知轉(zhuǎn)移概率，所以利用公式I(X,Y)=H(Y)-H(Y/X)

。

H(Y/X)=-∑∑q(xi)p(yj/xi)logp(yj/xi)=∑q(xi){-[plogp+(1-p)log(1-p)]}

=H(p)

其中：H(p)=-[plogp+(1-p)log(1-p)]

另外：為了求H(Y)，利用w(yj)=∑q(xi)p(yj/xi)；可得：

w(y=0)=ω(1-p)+(1-ω)pw(y=1)=ωp+(1-ω)(1-p)H(Y)=-{[ω(1-p)+(1-ω)p]log[ω(1-p)+(1-ω)p]+[ωp+(1-ω)(1-p)]log[ωp+(1-ω)(1-p)]}

=H(ω(1-p)+(1-ω)p)可得平均互信息量為：

I(X,Y)=H(ω(1-p)+(1-ω)p)-H(p)第二十三頁，共三十四頁，2022年，8月28日當固定信源先驗概率分布ω時，I(X,Y)是信道轉(zhuǎn)移概率p的下凸函數(shù)，如圖所示。

01/21p從圖中可知，當信源固定后，存在一種BSC信道，p=1/2，使在信道輸出端獲得信息量最小，即等于0。

I(X,Y)

H(ω)第二十四頁，共三十四頁，2022年，8月28日根據(jù)這個關(guān)系，當p值一定，即固定信道，可知I(X,Y)是ω的上凸函數(shù)，其曲線如圖：

I(X,Y)1-H(p)

01/21ω

從圖中可知，當BSC信道的信道矩陣固定后，若輸入符號集X的概率分布不同，在接收端平均每個符號獲得的信息量就不同。只有當輸入為等概分布時即，p(0)=p(1)=1/2時，接收端的信息量才為最大值1-H(p)。第二十五頁，共三十四頁，2022年，8月28日定理2.5.2當條件分布p(y/x)給定時，平均互信息I(X;Y)是輸入分布q(x)的凸∩函數(shù)。證明：令q1和q2是輸入集X上的任意兩個概率矢量，相應的互信息為I1和I2，令θ滿足0≤θ≤1，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)

第二十六頁，共三十四頁，2022年，8月28日根據(jù)平均互信息的定義，得

因為logx是嚴格凸∩函數(shù)，利用Jensen不等式，所以第二十七頁，共三十四頁，2022年，8月28日當信道一定時，平均互信息是信源先驗概率的上凸函數(shù)對于一定的信道轉(zhuǎn)移概率分布，總可以找到一個先驗概率分布為P的信源X，使平均互信息達到相應的最大值Imax，這時稱這個信源為該信道的匹配信源。不同的信道轉(zhuǎn)移概率對應不同的Imax，或者說Imax是P(Y/X)的函數(shù)。平均互信息的凸性第二十八頁，共三十四頁，2022年，8月28日定理2.5.3當集X的概率分布保持不變時，平均互信息量是轉(zhuǎn)移概率分布p(y/x)的下凸∪函數(shù)。證明：令p1和p2是兩個任意轉(zhuǎn)移概率分布，相應的平均互信息為I1和I2，令θ滿足0≤θ≤1,p=θp1＋(1－θ)p2是合成條件概率分布，此時輸入X和輸出Y之間的互信息為I。今需要證明.

令

根據(jù)平均互信息的定義，得第二十九頁，共