平均互信息的凸性

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

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

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

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)格凸∪的。第六頁，共三十四頁，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ù)，若其中任一個(gè)是嚴(yán)格凸的，則和式也是嚴(yán)格凸的。

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

≤

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

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

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

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

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

證畢

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

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

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

對(duì)所有’k>0

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

f()＋(1－

)f()≤f[

＋(1－

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

＋(1－

)]－f()}/

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

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

01-p0pp

11-p1因?yàn)橐阎D(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日當(dāng)固定信源先驗(yàn)概率分布ω時(shí)，I(X,Y)是信道轉(zhuǎn)移概率p的下凸函數(shù)，如圖所示。

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

I(X,Y)

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

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

01/21ω

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

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

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

令

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