2009-应用信息论基础-张林-Chap-6-88408904

第六章最大熵原与最小鉴别信息原最大熵原理与最小鉴别信息原理MaximumEntropyandMinimumDiscriminationInformationPrinciple2009年12月28日©THU2009–Allrightsreserved清华大学电子系－张林本章脉络本章脉络1111非适定问题2222最大熵原理3333最小鉴别信息原理4444二者之间的联系5555最大熵原理的合理性6666最大熵原理的应用©THU2009–Allrightsreserved21111非适定问题„由一个例子来了解什么是非适定问题„传感器网络自定位问题SensorSensorSensorrrr©THU2009–Allrightsreserved3传感器网络自定位问题传感器网络自定位问题„给出了一个网络中若干节点之间的测距信息能否唯的恢复网络中每个节点的空间座标？„能否唯一的恢复网络中每个节点的空间座标？„回顾一下GPS定位的原理„在传感器自定位问题中，往往是欠定的。©THU2009–Allrightsreserved4科学研究的模式科学研究的模式„系统的参数化：定性——定量„建立模型：前向建模，反向建模正问题发现物理规律确定系统参数进而根据系…正问题：发现物理规律，确定系统参数，进而根据系统的输入参数，预测系统的输出。…逆问题：根据可得到的观察值（输出值）推断系统参数及输入。„问题的分类：…过定所给出的条件过多…过定：所给出的条件过多…欠定：条件不够，数据不足、不确定或不准确©THU2009–Allrightsreserved5关于正问题、反问题的形式化表述（以线性系统为例）关于问题反问题的形式化表述系统传递数系统输入:X系统输出:Y函数：A„正问题：已知X、A，求Y„反问题：已知Y，求X、A；已知YA求X已知Y、A，求X©THU2009–Allrightsreserved6求解过定问题的方法求解定问题的方法mnnmmnrankn×=AX=YAXYA已知，其中为矩阵，为维列向量，为维列向量因为是过定问题有设（列满秩）mnrankn=A因为是过定问题，有，设（列满秩）。HˆX用昀小二乘求解本问题，就是求解一个，使得Hˆˆ⎡⎤⎡⎤⎣⎦⎣⎦J=AX-YAX-Y昀小化。注释9对于实验数据的拟合9在观测有噪声前提下的数据分析9…©THU2009–Allrightsreserved7求解欠定问题的方法求解欠定问题的方法mnnm×AX=YAXY已知，其中为矩阵，为维列向量，为维列向量mn因为是欠定问题，有。-nrankAAX=0对于这类问题，一般的解决方法是求方程的解，一般有个然后考虑再求原方程的解Y个，然后考虑再求原方程的解。问题9在所有可行解中是否还有倾向？9如何给出所有可行解的昀准确估计？9…©THU2009–Allrightsreserved82222最大熵原理„面对欠定问题时，方程的可行解多于个于一个„这变成了一个估计问题究竟取哪个解才昀合理？„究竟取哪一个解才昀合理？„E.T.Jayne在1957年提出了昀大熵原理原理„本质上是一种统计方法EdwinThompsonJaynesJuly51922-April301998直观理解9在约束下的昀大熵蕴含着…July5,1922-April30,19989约束条件下的“等概”分布，而…9这是由大数定理造成的——AEP©THU2009–Allrightsreserved9最大熵原理的问题表述最熵原的问题表述„设有某一离散随机变量X，其概率分布未知，已知其与若干函数的期望：()px已知其与若干函数的期望：求昀佳估计1,2,,mM=()()mmxpxfxC∈=∑Xˆ()求昀佳估计„按照昀大熵原理求解该问题，则可以表述成这样的一个约束优化问题：()px约束优化问题：…取概率分布的熵为目标函数…求在约束条件()()log()xHXpxpx∈=−∑X求在约束条件()1,()(),1,2,...,xpxpxfxCmM∈===∑∑X…下的解()(),1,2,...,mmxpxfxCmM∈∑Xˆ()max()pxArgHX=©THU2009–Allrightsreserved10()()max()pxpxArgHX=最大熵分布定理最熵分布定„„定理定理6.16.1：：欠定约束下昀大熵分布满足01ˆ()exp()Mmmmpxfxλλ=⎡⎤=−−⎢⎥⎣⎦∑的形式，式中的取值使得满足约束条件：0,...,Mλλˆ()px()1,()()12xpxfCM∈=∑∑X证明：证明：()(),1,2,...,mmxpxfxCmM∈==∑X这是一个典型的利用拉格朗日乘子方法求解约束极值的问题。这是一个典型的利用拉格朗日乘子方法求解约束极值的问题。©THU2009–Allrightsreserved11定理6.1中解的形式的合理性定中解的形式的合性作Lagrange辅助函数1()()1()()MmmmxmxFHXpxpxfxCβλ∈=∈⎛⎞⎛⎞=−−−−⎜⎟⎜⎟⎝⎠⎝⎠∑∑∑XXM取M⎡⎤11log()()0()MmmmFpxfxpx∂βλ∂==−−−−=∑得01ˆ()exp()Mmmmpxfxλλ=⎡⎤=−−⎢⎥⎣⎦∑01,(0,1,2,....,)1ˆ()mmMMpxλβλ=+=+其中则可由个约束条件解出。所得到的即为昀大熵分布。()px解出。所得到的即为昀大熵分布。©THU2009–Allrightsreserved12定理6.1的极值性证明定的极值性证明假设p*是满足定理定理6.16.1的一个分布，p是任意满足约束的分布。**()()()ln()()ln()pxHpxpxpxpx=−=−∑∑p**()()()()()()()()ln()xxxpppppxDpxpx∈∈∈=−−∑∑∑XXX*pp||p()*()ln()()()xxpxpxfλλ∈∈≤−∑∑∑XX等号成立的条件蕴涵着最大熵分布唯的结论()()0*0()()()()iixiipxfxpxfxλλλλ∈=−+=−+∑∑∑∑X大熵分布唯一的结论。()0**()()()ln()()iixxpfpxpxH∈∈=−=∑∑∑XX*p©THU2009–Allrightsreserved13连续随机变量连续随机变量„在连续随机变量的条件下，昀大熵原理依然成立，以微分熵代替微分熵代替。()0()0Spxpxx≥=∉且当()0,()0,S()1Spxpxxpxdx≥=∉=∫且当()(),1,2,3,...,mmSpxfxdxCmM==∫昀大熵分布定理：满足约束条件且使微分熵达到昀大值0ˆ()exp[()]Kmmpxfxλλ=+∑昀大熵分布定理：满足约束条件且使微分熵达到昀大值的分布为。1k=©THU2009–Allrightsreserved143333最小鉴别信息原理„昀大熵原理给出的是在没有任何先验信息前提下求解欠定问题的种方信息前提下，求解欠定问题的一种方法。如果存在个先验的分布如何求解„如果存在一个先验的分布，如何求解昀合理的分布？„鉴别信息是度量两个分布之间差异的S.Kullback„鉴别信息是度量两个分布之间差异的指标。„鉴别信息昀小化：在满足约束前提下，1903–1994„鉴别信息昀小化：在满足约束前提下，给出的分布距离先验分布尽量近。©THU2009–Allrightsreserved15最小鉴别信息原理的问题描述最小鉴别信息原的问题描述„问题：某随机变量X，概率分布q(x)未知，已知其先验概率密度p(x)及其若干函数的期望及其若干函数的期望求在上述条件下对q(x)的昀佳估计。()(),1,2,...,mmSqxfxdxCmM==∫求在上述条件下对q(x)的昀佳估计。„按照昀小鉴别信息原理，上述问题的求解可以表述为以下受限优化问题。…取先验分布与目标分布之间的鉴别信息作为目标函数…求在约束条件()()()log()SqxDqxdxpx=∫q||p…求在约束条件：()(),1,2,...,mmsqxfxdxCmM==∫()1sqxdx=∫…下的解()ˆ()min()qxqxArgD=q||p©THU2009–Allrightsreserved16()q最小鉴别信息分布定理最小鉴别信息分布定„„定理定理6.26.2：：满足先验分布p(x)和欠定约束条件的昀小鉴别信息分布满足信息分布满足0ˆ()()exp()Mmmqxpxfxλλ⎡⎤=+⎢⎥⎣⎦∑其中的取值使得满足约束条件：01mmm=⎢⎥⎣⎦∑0,...,Mλλˆ()qx()1,()()12xqxqxfxCmM∈===∑∑X()(),1,2,...,mmxqxfxCmM∈==∑X自己练习证明自己练习证明©THU2009–Allrightsreserved174444二者之间的联系最小鉴别信息原理是最大熵原理的推广最小鉴别信息原理是最大熵原理的推广在离散情形，设先验概率等概1()pxK=K1D(()||())(()||)qxpxDqxK=则()()log()log()log1kkKqxqxqaqaK==+∑∑XX1()logxxKHXK∈∈=−+XX()g1D(()||)()qxHXK⇒则昀小昀大。©THU2009–Allrightsreserved18K5555最大熵原理的合理性„从物理概念上进行的直观理解„热力学第二定律中的平衡态就是热力熵昀大的远离平衡态的状态会出现但是概率很小„远离平衡态的状态会出现，但是概率很小…一群猴子在打字机上乱蹦乱跳，打印出一部《大英百科全书》的概率…第二类永动机工作的概率…屋子里面出现冷热分区的状态的概率…一杯水的上半部向上飞起的概率…杯水的上半部向上飞起的概率©THU2009–Allrightsreserved19Jaynes对最大熵原理的解释y对最熵原的解释{}1212,,...,NKnNNXaaaNXxxxxKKk==随机试验，连续进行次试验，得到独立同分布随机序列的一个实现，即。它共有种可能。设在种可能序列中，第个1212...(1,2,...,)(,,...,)!()NkkKxxxxKKkNNfkKWfffNWfff===的个实现，即。它共有种可能。设在种可能序列中，第个事件出现次的序列共有个。1212(,,...,)()!()!...()!!KKWfffNfNfNfnStirlingnn=⎛≈⎝使用阶乘近似公式，当足够大时，n⎞⎜⎟⎠e⎝!1lim()limiNNfKNNeWfff⎜⎟⎠⎛⎞⎜⎟⎛⎞⎝⎠⎜⎟∏121211212lim(,,...,)lim()!()!...()!...1KKNfNfNfNNiKiKKWfffNfNfNffNfNfNfeee→∞→∞=⎝⎠===⎜⎟⎛⎞⎛⎞⎛⎞⎝⎠⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠∏[]12112121(,,...,)ln(,,...,)exp(,,...,)KKiiiKKHfffffWfffNHfff===∑而故©THU2009–Allrightsreserved20[]1212(,,,)p(,,,)KKffffffJaynes对最大熵原理的解释（续）y对最熵原的解释（续）{,1,2,...,}kKfkKKP=于是，频率可以看作是维空间中的一个点，它构成一个凸集112{:0,1}(,,...,)0KkkkKSPffSHfff==≥=•=∑。在的顶点：12max(,,...,)log11KSHfffKMLKMS•=+在的内部：个线性约束下存在维凸约束集所有的可行解被限制在集合11'1'MMMLKMSSSSKMSS+=−−=∩−−′•个线性约束下，存在维凸约束集，所有的可行解被限制在集合中，其维数为。具有这样的性质：满足约束条件的解在上取到1SLKM′•=−−熵是上的凸函数，存在唯一昀大值点在空间中进行座标的线性变换，使熵函数在原点处取得昀大值。©THU2009–Allrightsreserved21Jaynes对最大熵原理的解释（续）y对最熵原的解释（续）S2()(0)HPHara=−+将熵函数在原点附近进行级数展开max121()...,(0)()LkkHPHararPrx==−+=∑是到原点的距离S’r22max2