应用信息论基础 (6).pdf

《应用信息论基础 (6).pdf》由会员分享，可在线阅读，更多相关《应用信息论基础 (6).pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 TBSI 2017 All rights reservedLecture 5Maximum Entropy and Minimum KL Divergence TBSI 2015 All rights reserved2Outline1Ill-posed Problems2Maximum Entropy3Minimal K-LDivergence4Connections between them5Intuition to ME Principle6Application of ME Principle TBSI 2015 All rights reserved3nA simple examp

2、le:sensor network localization1Ill-Posed ProblemrSensorrSensorrSensor TBSI 2015 All rights reserved4Sensor Network LocalizationnQuasi-distance between some pairs of nodesnCould we recover the coordinates of each nodes?nGPS Revisited-over deterministicnThis problem typically undeterministic TBSI 2015

3、 All rights reserved5Regime of quantitativeresearchnCategories of problemsDirect problem:model the physical laws,determinethe parameter of the model,input-outputReverse problem:based on observations,infer thesystem parameter and inputnill-posed problemsOver-deterministic:too many clues.Undeterminist

4、ic:too little clues.TBSI 2015 All rights reserved6A simplified viewnDirect problem:know X and A,resolve YnReverse problem：know Y,resolve X and A；know Y and A,resolve XSystem modelAInput:XOutput:Y TBSI 2015 All rights reserved7For over-deterministic problemsHm nnmmnrankn=AX=YAXYAXJ=AX-YAX-Y已知，其中 为矩阵，

5、为 维列向量，为 维列向量因为是过定问题，有，设（列满秩）。用最小二乘求解本问题，就是求解一个，使得最小化。TBSI 2015 All rights reserved8Under-deterministic problem-m nnmmnn rankAmore than one solutionnWhich one is most“reasonable”?nE.T.Jayne proposed ME Principlein 19572Maximum Entropy PrincipleEdwin Thompson Jaynes July 5,1922-April 30,1998 Intuitio

6、n Max Entropy-“uniform”distribution LLN-uniform distribution TBSI 2015 All rights reserved10Formal ProblemnSuppose we have a discrete RV X with unknown p.m.f.p(x).Given its expectation of some functionsdetermine the p.m.f.nConvert the problem into a constraint optimizationproblemObjective function:C

7、onstraints:Solution:1,2,mM=!()()mmxp x fxC=X()p x()()log()xH Xp xp x=X()1,()(),1,2,.,xmmxp xp x fxCmM=XX()()max()p xp xArgH X=TBSI 2015 All rights reserved11Maximum Entropy TheoremnTheorem 5.1:The p.m.f.that achieve maximumentropy iswheresatisfyProof:Apply Lagrange multiplier.01()exp()Mmmmp xfx=0,.,

8、M()p x()1,()(),1,2,.,xmmxp xp x fxCmM=XX TBSI 2015 All rights reserved12Proof of Theorem 5.1Let auxiliary function beand by takingwe havewhere 0=+1,and m(m=0,1,M)can be solved byM+1 constraints.1()()1()()MmmmxmxFH Xp xp x fxC=XX01()exp()Mmmmp xfx=11 log()()0()MmmmFp xfxp x=TBSI 2015 All rights reser

9、ved13Continuous R.V.snSubstitute entropy with differential entropy。01()0,()0,S()1()(),1,2,3,.,()exp()SmmSKmmkp xp xxp x dxp x fx dxCmMp xfx=+且当最大熵分布定理：满足约束条件且使微分熵达到最大值的分布为。TBSI 2015 All rights reserved14nME principle:No prior knowledge onp.m.f.nWhat if there is prior on p.m.f.nK-L Divergence measure

10、 thedifference between two p.m.f.nMinimum K-L Divergence:under thegiven constraints,find a p.m.f.that isas close to the prior as possible.3Minimum K-L DivergenceS.Kullback19031994 TBSI 2015 All rights reserved15最小鉴别信息原理的问题描述n问题：某随机变量X，概率分布q(x)未知，已知其先验概率密度p(x)及其若干函数的期望求在上述条件下对q(x)的最佳估计。n按照最小鉴别信息原理，上述

11、问题的求解可以表述为以下受限优化问题。取先验分布与目标分布之间的鉴别信息作为目标函数求在约束条件：下的解()(),1,2,.,mmSq x fx dxCmM=()()()log()Sq xDq xdxp x=q|p()(),1,2,.,mmsq x fx dxCmM=()1sq x dx=()()min()q xq xArgD=q|p TBSI 2015 All rights reserved16Minimum K-L Divergence PrinciplenTheorem 5.2：Given a prior p.m.f.p(x)and constraints,the minimum K-L

12、 divergence p.m.f iswhereare taken such thatsatisfies01()()exp()Mmmmq xp xfx=+0,.,M()q x()1,()(),1,2,.,xmmxq xq x fxCmM=XX TBSI 2015 All rights reserved174ConnectionsMin KL Principle is a generalization of ME principleAssume the prior is1()p xK=1D()|()()|)()()log()log()log1()log1D()|)()kkxxq xp xD q

13、 xKq xq xq aq aKKH XKq xH XK=+=+XX则则最小最大。TBSI 2015 All rights reserved18nPhysicalitynSecond Law of ThermodynamicsnStates far from equilibrium states is possible,butvery rarely seenA flock of money jumping on typewrite and type outthe British Encyclopedia.The second type of perpetual motion machineRo

14、om temperature deviated from balanced stateHalf glass of water jumping up into air5Intuition of ME Principle TBSI 2015 All rights reserved19Jaynes对最大熵原理的解释1212121212,.,.(1,2,.,)(,.,)!(,.,)()!()!.()!NKnNNNkkKKKXa aaNXxx xxKKkNNfkKW fffNW fffNfNfNfnStirlingnne=随机试验，连续进行 次试验，得到独立同分布随机序列的一个实现，即。它共有种可能。设

15、在种可能序列中，第 个事件出现次的序列共有个。使用阶乘近似公式，当 足够大时，1212112121211212!1lim(,.,)lim()!()!.()!.1(,.,)ln(,.,)exp(,.,)iKnNNfKKNfNfNfNNiKiKKKiiiKKNNeW fffNfNfNffNfNfNfeeeH fffffW fffNH fff=而故 TBSI 2015 All rights reserved20Jaynes对最大熵原理的解释（续）11212,1,2,.,:0,1(,.,)0max(,.,)log111kKkkkKKMMfkKKPSP ffSH fffSH fffKMLKMSSSSKM

16、SS=+=于是，频率可以看作是 维空间中的一个点，它构成一个凸集。在 的顶点：在 的内部：个线性约束下，存在维凸约束集，所有的可行解被限制在集合中，其维数为。具有这样的性质：满足约束条件的解在 上1SLKM=取到熵是 上的凸函数，存在唯一最大值点在空间中进行座标的线性变换，使熵函数在原点处取得最大值。TBSI 2015 All rights reserved21Jaynes对最大熵原理的解释（续）SSr取得Hmax的位置2max12122max2max2maxmax().,(0)():()()()exp()exp()()LkkRRH PHararPrxSPHH PaRSHHH PaRW HN

17、HHNaRW HR=+=将熵函数在原点附近进行级数展开是 到原点的距离 设集合集合中的分布的熵与最大熵的距离小于，而根据熵函数的连续性，这些分布与最大熵分布也相差不多。则所以，在半径为 的球中对应的210NRRNarLRNKFerdrFK序列数目在种可能序列中所占的比例为。TBSI 2015 All rights reserved22Jaynes对最大熵原理的解释（续）()2102221RNarLLRerdrLN HF为自由度为的分布的分布函数。Chi方分布 TBSI 2015 All rights reserved23最大熵分布的例子611,26max210004.5.(,.,)0.0543

18、,0.0788,0.1142,0.1654,0.2398.0.34751.61358:kkLkff ffH=：投骰子试验。投次，已知平均点数为：其最大熵分布为：（）此时则按分布可得例6.1NFHFHNRLRL2)1()1(222=)1(2RLFHRF0.959.4880.0047440.9913.2770.006638561358.1609.1 H61358.1602.1 HmaxmaxHHHH TBSI 2015 All rights reserved246Application of ME PrinciplenUnder the following constraints,solve ME

19、 p.m.f.S=a,b S=0,)，EXS=(,)，EXS=(,)，EX1，EX22 TBSI 2015 All rights reserved25Spectrum EstimationnZero-meanstationary stochasticprocess XinAutocorrelationR(k)=EXiXi+knFourier transformationof autocorrelationfunctionis thespectrum density of the processnTypically,we have finite lengthsample trajectoryof

20、 theprocess to estimatethe spectrumnThe problems areBigger k,R(k)could not be estimatedreliablySmall k,coarse grain spectrum estimation()(),immSR m e=11()n kii kiR kX Xnk+=TBSI 2015 All rights reserved26ME Principle applied to spectrum estimationnJ.P.Burg,1967nFormulationGiven p+1 autocorrelation fu

21、nction valuesBased on p+1 constraints,solve the maximal ME stochastic processnThe solution is a Gaussian-Markov processwhose parameters are given by Yule-Walker Equations12,0,1,.,(0,)1iii kkpiki kikiiXEX Xr kpipXXZZNp+=+?221()1piklkkS le=+2011,1,2,.,pkkkplk l kkrrrrlp=+=Yule-Walker Equations TBSI 20

22、15 All rights reserved27Burg最大熵率定理TheoremTheorem 5.35.3：12,0,1,.,(0,)1iii kkpiki kikiiXEX Xr kpipXXZZNp+=+设有随机过程满足约束条件：，对所有使之满足最大熵率的随机过程为具有以下形式的 阶高斯马尔可夫过程:式中，是独立同分布的高斯随机变量，称为自回归系数，由个约束确定。证明本定理的诀窍：证明随机过程的有限长样本序列的熵受限于与其具有同样协方差矩阵的高斯过程，而后者受限与高斯马尔可夫过程的熵率。TBSI 2015 All rights reserved28定理6.3的证明概略n设X1,X2,X

23、n是任意满足约束EXiXi+k=rk的随机过程，设Z1,Z2,Zn是具有与X1,X2,Xn相同协方差矩阵的高斯过程。n定义Z1,Z2,Zn为p阶高斯马尔可夫过程，使之具有与Z1,Z2,Zn相同的1,2,p阶分布。于是1212112111121(,.,)(,.,)(,.,)(|,.,)(,.,)(|,.,)nnnpiiiipnpiiiipiph XXXh Z ZZh ZZh ZZZZh ZZh ZZZZ=+=+=+12112111211(,.,)(,.,)(|,.,)(,.,)(|,.,)(,.,)nnpiiii pi pnpiiii pni ph XXXh ZZh ZZZZh ZZh ZZZZ

24、h ZZ=+=+=+=TBSI 2015 All rights reserved29Burg定理的应用n求解定理定理6.36.3中的p+1个约束方程是关键n上述方程称为Yule-Walker方程组，其解的形式为n在实际的问题中，获得长度为n的样本序列后，计算p个自相关，外推到最大熵分布。2011,1,2,.,pkkkplk l kkrrrrlp=+=221()1piklkkS le=+TBSI 2015 All rights reserved30ConclusionnDirect and reverse problemnUnder-deterministic problemnME and Min KL Divergence PrinceiplesnIntuition to the ME PrinciplenApplication of ME in Spectrum Estimation