信息论基础 (12).ppt

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

1、第第12章章 信息理论方法信息理论方法及其应用及其应用第第12章章 信息理论方法及其应用信息理论方法及其应用 本章主要内容：本章主要内容：1.信源熵的估计信源熵的估计 2.最大熵原理最大熵原理 3.最小交叉熵原理最小交叉熵原理 4.信息理论方法的应用信息理论方法的应用 5.小结和思考题小结和思考题 p本章主要介绍信源熵估计、最大熵原理和本章主要介绍信源熵估计、最大熵原理和 最小交叉熵原理及其部分应用。最小交叉熵原理及其部分应用。本节主要内容：本节主要内容：1.1.离散信源序列熵的估计离散信源序列熵的估计 2.2.连续信源熵的估计连续信源熵的估计 12.1 12.1 信源熵的估计信源熵的估计熵估

2、计熵估计v参数估计 给定一个信源概率密度的参数模型，首先从可能的密度函数空间中搜索最可能的密度函数，其次计算最可能密度函数所对应的熵。熵估计（续）熵估计（续）v非参数估计 （1）标准的最大似然或“插入”法，就是先估计信源符号的概率或概率密度，然后再将估计的概率代入熵的计算公式中来计算熵；（2）对于离散信源，可以利用无损信源压缩编码算法进行熵估计，通常使用通用压缩编码；（3）利用其他熵估计算法。12.1.1 12.1.1 离散信源序列熵的估计离散信源序列熵的估计 v插入熵估计v通用信源压缩编码熵估计v模板匹配熵估计插入熵估计（一）插入熵估计（一）离散无记忆信源熵估计离散无记忆信源熵估计 设一个离

3、散无记忆信源具有未知的概率分布 ，其中，符号集 ，为信源的熵，现用给定信源序列 作为训练序列，对信源熵进行插入法估计。首先利用训练序列估计信源符号的概率，表示为 其中n为训练样本数，通常估计值依赖与样本数。符号的概率采用下式估计：其中 ，成为经验分布插入熵估计（一）插入熵估计（一）离散无记忆信源熵估计离散无记忆信源熵估计 可以证明 是 的最大似然估计，且是无偏的，即 将概率的估计值代入信源熵的的公式，得信源熵的估计值：虽然概率的估计是无偏的，但熵的估计却不是无偏的。根据熵的上凸性有 可见，用插入估计得到的熵值的平均要比实际熵值低，是实际熵的欠估计。所以在进行熵估计时，要做适当的修正，以保证熵的

4、估计具有较小的偏差。插入熵估计（一）插入熵估计（一）离散无记忆信源熵估计离散无记忆信源熵估计vMiller等（1954年）提出，修正后的熵按下式计算 其中，为估计的信源符号集的大小，n为训练样本数，这里熵的单位是奈特。v还有一种偏差修正法，称为jackknife法，是统计学中对估计器的偏差和方差进行估计的有效方法，这种方法特别用于标准方法难于应用的场合。熵估计的公式为 其中，表示用样本 进行插入估计所得的熵。例12.1.1 一个二元离散无记忆信源，符号0和1的概率分别为1/4和3/4，长度为32的训练序列为1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1

5、1 0 1 1 1 0 1 1 1 1；（1）求信源熵的最大似然插入估计；（2）利用Miller修正法估计信源熵；（3）利用jackknife修正法估计信源熵。解:信源熵 比特（1）信源符号概率的ML估计为：，；信源熵的最大似然插入估计为 比特；插入熵估计（一）插入熵估计（一）离散无记忆信源熵估计离散无记忆信源熵估计（2）利用Miller修正估计信源熵为 比特；（3）比特 比特利用jackknife修正估计信源熵为 比特 插入熵估计（二）插入熵估计（二）一阶马氏链熵估计一阶马氏链熵估计设信源是一个J状态的一阶马氏链，其中状态集合 信源序列 为训练序列，现对信源的熵进行插入估计。定义示性函数在训

6、练序列中状态（i，j）同时发生次数的估计为状态i发生次数的估计为插入熵估计（二）插入熵估计（二）一阶马氏链熵估计一阶马氏链熵估计状态转移概率的估计：平稳概率的估计：注意，如果训练样本数量不够，会出现某些状态的概率统计值为零的情况。当 ，必有 ；当 ，必有 。为避免出现有些状态观察不到的情况，应该进行多次独立的观察。插入熵估计（二）插入熵估计（二）一阶马氏链熵估计一阶马氏链熵估计 信源熵的估计：与独立信源熵的估计类似，熵的估计也不是无偏的，用插入估计得到的熵值的平均要比实际熵值低。这也可根据熵的上凸性推出。插入熵估计（三）插入熵估计（三）N次扩展源（次扩展源（Ngram）的熵估计）的熵估计 （1

7、2.1.17）其中，为序列中状态 的个数N次扩展源的熵估计为 （12.1.18）修正后的熵为：（12.1.19）其中，为 的个数。插入熵估计（四）插入熵估计（四）高阶有记忆马氏源熵估计高阶有记忆马氏源熵估计v根据 ，所以一个N-1阶马氏源熵的估计为：（12.1.20）v研究表明，插入法熵估计随L的增大，熵估计精度增加。对于低阶马氏源，该方法能得到较精确的熵估计，但对于记忆长度较大的信源序列，数据长度往往不够，不能得到精确的估计结果。通用信源压缩编码熵估计通用信源压缩编码熵估计 根据仙农第一定理，无损信源编码码率的下界是信源的熵，即通过理想的信源编码后，编码器码率可以压缩到信源的熵。因此可以计算

8、无损编码后的压缩率（输出文件比特长度与输入文件比特长度的比）R，而 ，如果采用性能理想的无损信源编码算法，编码压缩率R可以作为信源熵的估计。（12.1.21）当然，压缩性能越好，估计值越接近信源的熵。通用信源压缩编码熵估计通用信源压缩编码熵估计(续续)v有很多通用信源压缩编码算法可用做熵估计，该方法相对于插入法的优点是，不依赖信源的模型，也不假设任何特殊的信源结构，主要考虑的是算法的收敛速度。v有几种常用的信源压缩编码算法可用做熵估计，例如：LZ77系列（自适应模板匹配编码）、GZIP算法（LZ77+Huffman编码）、BZIP（基于Burrows-Wheeler变换+Huffman编码）C

9、WT（上下文树加权+算术编码）等。模板匹配熵估计模板匹配熵估计 对于记忆逐渐消失的信源，设k和n为任意选择的正整数，给定观察，信源熵可由下式估计：（12.1.22）从估计过程可以看到，随着i的连续增加，匹配长度的计算在长度为n的滑动窗内进行。所以这种熵估计方法也称为滑动窗熵估计。模板匹配熵估计（续）模板匹配熵估计（续）可采用如下方法进行估计值的矫正：对给定信源序列进行信源符号概率的最大似然估计，再以估计的概率产生与信源序列长度相同的信源序列复制品，对这些复制序列做窗长不同的滑动窗熵估计。因为复制序列的熵是可以精确计算的，所以用复制序列的熵减去估计熵就得到估计偏差。在所有复制品序列中对这种偏差进

10、行平均就得到平均估计偏差。修正后的熵估计值是滑动窗熵估计加偏差值。例12.1.2：对于例12.1.1的二元离散无记忆信源，用相同的训练序列，用滑动窗熵估计法估计信源的熵，滑动窗口长度n=8，不要求对估计结果进行矫正。解 求得 ，分别为3，3，4，4，4，2，1，0，2，2，7，6，5，4，5，4，4，4，4，4，3，3，2，1；熵的估计为 比特 12.1.2 12.1.2 连续信源熵的估计连续信源熵的估计 连续信源熵的估计主要有以下两种方法：v用一个参数集合近似实际的概率密度，而这个参数集合所对应的熵是已知的；v基于对概率密度的直接估计，例如利用直方图等，然后计算信源的熵，实际上就是插入估计

11、12.2 12.2 最大熵原理最大熵原理本节主要内容：本节主要内容：1.1.最大熵原理的描述最大熵原理的描述 2.2.熵集中定理熵集中定理 3.3.几种重要的最大熵分布几种重要的最大熵分布 最大熵原理的描述最大熵原理：v在寻找满足某些约束的概率分布时，选择满足这些约束具有最大熵的概率分布。利用最大熵原理的依据：v主观依据v客观依据最大熵原理的描述离散信源 设离散信源熵：（12.2.1）满足约束 （12.2.2），（12.2.3）其中，（12.2.2）是概率的归一化约束；是已知函数，（12.2.3）通常是概率矩的描述（包括均值或方差）或其他特征的平均值，是已知常数，在解决实际问题时这些常数可能由

12、训练数据得到。最大熵原理的描述离散信源（续）定理12.2.1（离散最大熵分布定理）满足（12.2.2）和（12.2.3）的约束使（12.2.1）达到最 大值的概率分布为：，（12.2.4）其中，（12.2.5）最大熵为 （奈特）（12.2.6）参数 ，由下式确定：，（12.2.7）其中，。最大熵原理的描述离散信源（续）例12.2.1 做1000次抛掷骰子的试验，求抛掷点数的平均值。解 由于抛掷次数很多，所以各点出现的频率近似等于出现的概率。假定在每次抛掷后，骰子6个面中的每一个面朝上的概率都相同，即为1/6。这里我们利用了“不充分理由原理”，因为除知道骰子有6个面外，我们没有其他任何别的信息。

13、抛掷点数的平均值：m=(1+2+3+4+5+6)/6=3.5 最大熵原理的描述离散信源（续）例12.2.2 做1000次抛掷骰子的试验后得知抛掷点数的平均值为4.5，求骰子各面朝上的概率分布。解 很明显，骰子的各面朝上的概率是不均匀的。除概率的归一性外，我们知道的信息仅有平均值，这对于确定6个面的概率是不完整的信息，必须利用最大熵原理。根据题意，平均值的约束写为 结合（12.2.3），有m=1，且只有待定常数 、，最大熵原理的描述离散信源（续）由（12.2.7），得 ；代入（12.2.4），得所求概率分布为：最大熵原理的描述离散信源（续）例12.2.2(续)求本例概率分布所对应的熵。解 奈特

14、比特 由（12.2.5）得 ；也可利用（12.2.6），得 奈特 最大熵原理的描述连续情况信源的熵 （12.2.10）满足 （12.2.11），（12.2.12）与推导离散情况类似，可以得到以下结果：最大熵原理的描述连续情况定理12.2.2（连续最大熵分布定理）满足（12.2.11）和（12.2.12）的约束使（12.2.10）达到最大值的概率密度为：（12.2.13）其中，（12.2.14）最大熵等于 （12.2.15）参数 ，由下式确定：，（12.2.16）最大熵原理的描述连续情况例12.2.3 连续信源X的取值区间为（），求达到最大熵的X的分布度 和相应的最大熵hmax。解 因为只有归一

15、化约束，由（12.2.14），得Z=b-a，由（12.2.13），所求分布密度 最大熵为 熵集中定理定理12.2.3（熵集中定理）满足约束（12.2.3）的一组概率 所产生的熵在如下范围：（12.2.20）其中 （12.2.21）为在约束（12.2.2）、（12.2.3）下，（12.2.1）的最大值。（12.2.21）的含义是，当N足够大时，渐近为维数为k（=n-m-1，n为信源符号数，m为约束方程个数），置信度为1-F的 分布的值。通常，在很高的置信度的条件下，的也值很小。熵集中定理（续）例12.2.2(续)求置信度95%和99.99%时信源熵的范围。解 根据题意，为自由度6-1-1=4的

16、分布，查表，(1)在置信度95%条件下,得 ，信源熵的范围：1.609 H 1.614(奈特)；(2)在置信度99.99%条件下,得 ，信源熵的范围：1.602 H 1.614(奈特)熵集中定理（续）v结论：在提供的信息不完全的情况下，最大熵分布不仅以最多的实现方式实现，而且随着试验次数的增多绝大多数可能的分布的熵都接近最大熵。当次数N时，除具有最大熵的分布外，其他满足约束的分布都是非典型的，出现的概率几乎为零。可以认为，具有最大熵的分布是所有满足给定约束的概率分布的代表；最大熵法是一种保险的策略，它能防止我们预测出数据没有提供的虚假结果。几种重要的最大熵分布v满足均值约束的连续最大熵分布是指

17、数分布v满足均值约束的离散最大熵分布是几何分布 v满足均值和均方值约束的最大熵分布是高斯分布 v满足几何平均值约束的最大熵分布是幂律分布。满足均值约束的连续最大熵分布是指数分布满足均值约束的连续最大熵分布是指数分布 例12.2.3 连续信源X的取值区间为0，），均值E(X)=,求达到最大熵的X的分布密度和相应的最大熵。解 根据（12.2.13）有 ，其中，；根据约束条件有 所求分布密度为 （12.2.22）根据（12.2.15），得最大熵为 （12.2.23）满足均值约束的连续最大熵分布是指数分布满足均值约束的连续最大熵分布是指数分布例12.2.4 离散信源X的取值为Ei，i=1，2，满足约束

18、，求达到最大熵的X的概率分布pi和相应的最大熵H（X）。解 根据（12.2.4），得 其中，。令 ，其中kB为波耳兹曼常数，T为绝对温度，那么 （12.2.24）v这就是物理学中的波耳兹曼分布，也称波耳兹曼吉布斯（Boltzmann-Gibbs）分布，也是指数分布，是平衡统计力学的基本定律。它指出，一个能量为Ei的某特殊状态的概率满足波耳兹曼分布。一个重要的特例就是，Ei=i，这时离散分布称为几何分布。满足几何平均值约束的最大熵分布是幂律分布满足几何平均值约束的最大熵分布是幂律分布 例12.2.6 设连续信源X的取值为正实数,概率密度为p(x),且满足约束，（12.2.25）求具有最大熵的分布

19、密度。解 根据（12.2.13）有 ，满足几何平均值约束的最大熵分布是幂律分布满足几何平均值约束的最大熵分布是幂律分布根据约束条件（12.2.25）有得，所以 （12.2.26）（12.1.26）所示的分布满足幂律分布。所谓幂律是指一个随机变量的概率密度是一个幂函数，即 （12.2.27）其中，为正数。12.3 12.3 最小交叉熵原理最小交叉熵原理本节主要内容：本节主要内容：1.1.最小交叉熵原理最小交叉熵原理 2.2.交叉熵的性质交叉熵的性质 3.3.最小交叉熵推断的性质最小交叉熵推断的性质 4.4.交叉熵法交叉熵法12.3.1 12.3.1 最小交叉熵原理最小交叉熵原理v信息散度在信号处

20、理领域常称为交叉熵。v对离散和连续信源，定义在同一概率空间的两概率测度P和Q的交叉熵分别定义为：v离散情况：（12.3.1）v连续情况：（12.3.2）v交叉熵表示概率分布P和Q之间的“距离”，也表示信源从概率P变化到概率Q所需要的信息量，所以Q称为先验概率，而P称为后验概率。v在很多情况下，可能存在关于概率分布的先验知识，此时可以用最小交叉熵原理推断后验概率分布。最小交叉熵原理就是，当推断一个具有先验分布Q的随机变量的概率分布P时，选择在满足X的已知约束下使交叉熵最小的概率分布。下面是最小交叉熵分布定理。v定理12.3.1（离散最小交叉熵分布定理）满足（12.2.3）的约束使（12.3.1）

21、达到最小值的后验概率分布为：，（12.3.3）其中，（12.3.4）参数 ，由下式确定：，（12.3.5）其中，。v定理12.3.2（连续最小交叉熵分布定理）满足（12.2.12）的约束使（12.3.2）达到最小值的后验概率密度为：（12.3.6）其中，（12.3.7）参数 ，由下式确定：，（12.3.8）v以上两定理的证明与最大熵分布定理的证明类似，此处略。v设满足约束条件（12.2.3）或（12.1.12）的概率分布的集合为P，那么最小交叉熵原理可以描述为：（12.3.9）其中，（12.3.10）满足（12.3.9）的概率密度称为最小交叉熵的解。v通过比较可知，最大熵原理是最小交叉熵原理的

22、特殊情况，此时的先验概率是均匀分布。v也可以说，最小交叉熵原理是最大熵原理的推广。v例12.3.1 设先验概率为N维独立高斯分布随机矢量：N维随机矢量满足约束：，求使交叉熵最小的后验分布密度。v解根据（12.3.6），得可以看到，仍然是独立的高斯分布，再根据给定的约束条件，得#v可见，所求的密度仍然是高斯分布，不过均值和方差被新的约束值代替。12.3.2 12.3.2 交叉熵的性质交叉熵的性质交叉熵的性质总结如下：1）非负性 ，仅当 时等式成立。（12.3.11）2）下凸性 是p的下凸函数，确切地说，已知概率分布（离散或连续），和正数 ，且 ，有 （12.3.12）3）可加性这类似于熵的可加性

23、，就是独立联合分布的交叉熵等于各独立合分布的交叉熵的和。确切地说，已知概率分布 ，有 （12.3.13）4）坐标变换下的不变性在离散情况转化成置换下的不变性。确切地说，设概率密度 ，有变换 ，有 （12.3.14）5）勾股性质定理12.3.3 设 为先验概率密度，、为满足（12.2.12）约束的后验概率密度，且 ，那么 （12.3.15）（12.3.15）式类似于勾股定理。如果把满足约束的概率分布看成一个子空间C，则r，p都在C内，而q在C外。p与q的距离长度最短，相当于连接p、q的矢量和C垂直，从C中任何一点r到q的距离的平方等于r到p距离的平方加上p到q的距离的平方。v证：v其中，a：p(

24、x)满足（12.3.6），b：r(x)和 p(x)都满足约束。12.3.3 12.3.3 最小交叉熵推断的性质最小交叉熵推断的性质vJ.E.Shore等提出4个公理化条件：（1）惟一性；（2）在坐标系变换下不变性；（3）系统独立性；（4）子集独立性。提出这些公理的指导性原则就是，如果问题可以用多于一种的方法解决，那么结果要一致。他们证明了，在给定先验概率和约束条件下，由最小交叉熵原理所推出的后验概率，即最小交叉熵的解是惟一满足上述公理条件下的结果。所以，最小交叉熵原理是惟一的一致推断系统，所有其它的推断系统都将导致矛盾。v下面对最小交叉熵推断满足以上4个公理化条件做具体说明：（1）惟一性 最小

25、交叉熵的解是惟一的。这可以从是p的下凸函数推出。（2）坐标变换下的不变性 在两个不同的坐标系中的最小交叉熵解具有坐标变换关系。也就是说，先求最小交叉 熵的解，再变换得到的后验概率密度和先变换再求最小交叉熵解结果是相同的。（3）系统独立性 系统独立性含义是，对于多维系统，对各维分别进行最小交叉熵推断实现和用联合概率用最小交叉熵直接推断实现得到相同的后验概率。下面以2维分布为例来说明。设先验概率密度 ，后验概率密度 及其边际概率密度 和 ，现通过 估计 。因为 所以，求 相当于求 ，而 ，因此相当于分别求 和 。（4）子集的独立性 子集独立性含义是，用最小交叉熵推断后验概率时，可以用整个概率密度计

26、算来实现也可以将概率密度划分成若干状态下条件概率密度分别实现。设先验与后验概率密度分别划分成若干不相交区间 ，且 ，其中 ，分别为 和 的概率。（12.3.15）所以，求 相当于求 ，对所有i。12.3.4 12.3.4 交叉熵法交叉熵法v在信息处理中，往往要求一个概率密度接近另一个目标概率密度，而目标概率密度的参数未知的。这样，将（12.3.2）式 作为目标概率密度，为含有参数的概率密度，写成 ，可以通过改变u使交叉熵最小。由于因此，使 最小，相当与使上式第二项最大，即 （12.3.16）上式就是当前被称为交叉熵法的理论依据。v交叉熵法是一个迭代算法，包含两步：1）应用一个动态参数集产生随机

27、数据样本；2）应用数据样本本身对控制随机数据产生的参数进行更新，以进一步改进数据样本。v交叉熵法首先由Rubinstein在1997年提出，用做估计稀有事件概率的自适应算法，后来作为解决很多优化问题，特别是NP难题的通用而有效的工具。交叉熵法已经成功应用到很多复杂的优化问题，例如邮递员旅行问题、二次分配问题、最大割集问题等。12.4 12.4 信息理论方法的应用信息理论方法的应用本节主要内容：本节主要内容：1.DNA1.DNA序列的熵估计和压缩序列的熵估计和压缩 2.2.最大熵谱估计和最小交叉熵谱估计最大熵谱估计和最小交叉熵谱估计 3.3.最大熵建模及其在自然语言处理中最大熵建模及其在自然语言

28、处理中的应用的应用 4.4.最大熵原理在经济学中的应用最大熵原理在经济学中的应用 5.5.信息理论方法应用展望信息理论方法应用展望12.4.1 DNA12.4.1 DNA序列的熵估计和压缩序列的熵估计和压缩 v近些年来，生物学领域的研究取得很大进展，很多物种完整DNA（脱氧核糖核酸）序列已经被发现，关于基因的一系列重要问题已成为研究的热点，这里就包括DNA序列的处理以及有效存储和传送问题，DNA序列熵的估计和压缩是用来解决这类问题的方法之一。v 我们知道，细胞核中的DNA是生物的遗传物质。它的单体是核苷酸，由一个碱基，脱氧核糖分子（S）和磷酸分子（P）构成。碱基有四种：腺嘌呤（A）、鸟嘌呤（G

29、）、胞嘧啶（C）和胸腺嘧啶（T）。因此共四种核苷酸，简记为A，G，C，T，所以DNA序列可以表示字母表为A，T，G，C的符号串。在DNA的编码区，能够对蛋白质进行编码的序列称为外显子（exon），而不能对蛋白质进行编码的序列称为内含子（intron）。对各种遗传序列的测试表明，内含子和外显子的熵存在很大的差别。v 前面介绍的离散序列熵估计算法都可用来估计内含子和外显子序列的熵，但由于DNA序列中外显子序列较短，要求熵估计器的收敛必须足够快，以便得到精确的估计值。v因为DNA序列是有记忆的，最常用的方法就是k次扩展估计方法。先把序列分割成长度为k的子序列，对每个k，估计长度为k的子序列的概率，利

30、用插入法得到每符号熵的估计值如下式表示：（12.4.1）其中，为所估计的长度为k的子序列的概率。v也可用滑动窗模板匹配法进行熵估计。Farach等用此算法来测试外显子和内含子熵差别，发现外显子的平均熵73%的时间较大，而内含子的变化80%的时间较大。vLoewenstern和Yianilos提出一个称作CDNA的估计DNA序列熵的算法。他们观察到，DNA序列包含很多重复，偶尔也可以预测。该算法使用两个参数表示这种不精确匹配，一个参数w表示子串的长度，另一个参数h表示汉明距离。这两个参数用来构建一个预测专家平台pw，h，它们各有不同的w和h的值，然后应用期望值最大法对各个专家平台参数的加权值进行

31、训练，使得将它们组合成一个单独预测器时预测能力最强。vKevin Lonctot等提出一种称做语法变换分析和压缩（GTAC）熵估计器，应用一种新的数据结构以线性时间解最长非重叠模式问题，其特点是运行时间短，估计值精确。该方法以基于语法的编码分析为基础，并利用了DNA序列的反向互补特性。这种估计器是通用的，适用于任何序列。v如前所述，无损压缩编码也可用做熵的估计，所以提出了若干无损压缩编码用于DNA序列熵的估计和压缩。实践证明，适用于文本压缩的通用无损信源编码往往对DNA序列的压缩效果不好，主要原因是：（1）这些算法大部分仅具有渐近最佳特性，而DNA序列往往没有足够的长度；（2）这些算法未利用D

32、NA序列本身的特性。v我们知道，DNA序列有如下特性：（1）序列中存在重复，（2）存在近似重复（有个别差错的重复），（3）存在反向互补重复（reverse complement），（4）局部频率非均匀。v在DNA序列中，A与T互补，G与C互补。如果两序列x=x1xn 和y=y1yn 中 xi与yn+1-i(1in)互补，则称x 和y反向互补，也称回文（palindrome）。例如AAACGT与ACGTTT就是反向互补。v迄今为止已经提出多种DNA序列的压缩算法，主要有BioCompress(BioCompress-2)，Cfact，GenCompress，CTW+LZ，DNCompress，D

33、NASequitur，DNAPack和GenomeCompress等。vBiocompress和它的第2版Biocompress-2(Grumbach和Tahi,1994)是第一个DNA专用压缩算法，其要点是：（1）精确检测直接和反向互补重复，（2）在每一步，选择从当前位置开始与前面开始的最长匹配，用LZ编码，其中一个子符号串编成一对整数，一个表示匹配长度，另一个表示匹配位置，（3）不重复的数据段用2比特编码，（4）当未发现重复时，Biocompress-2用2阶算术编码器编码。vCfact（Rivals 等，1996）算法的要点是：（1）寻找最长的精确匹配，（2）两次通过（保证增益），（3）

34、用后缀树寻找最长重复，（4）对于不重复部分用2比特编码。vGenCompress（Chen等，1999）算法要点：（1）考虑近似重复，（2）在每一步，DNA序列中还未编码部分（后缀）的最佳前缀（增益函数），（3）如果在使用最佳前缀中无任何增益，就在缓冲器中加一个字母，（4）汉明距离和编辑距离用做近似重复。vCTW+LZ（Matsumoto等，2000）算法要点：（1）GenCompress和CTW（上下文树加权）的组合，（2）长的精确或近似的重复用LZ77型算法，而短重复用CWT编码，（3）用局部启发式解贪婪选择问题，（4）执行时间长，不能用于长序列。vDNCompress（Chen等，200

35、0）要点：（1）使用LZ压缩，（2）用PatternHuter工具进行预处理，寻找所有的近似重复包括反向互补重复，（3）对近似重复和非重复区域编码，（4）执行时间短。vDNASequitur（Cherniavsky 和Ladner，2004）是一个基于语法的压缩算法，其要点是：（1）提供一个上下文无关的语法来表示输入数据，（2）Sequitur（Nevill-Manning和Witten，1997）的要点是，Digram Uniqueness（在语法中，相邻符号对的出现不多于1次）和Rule Utility（每条原则至少用2次，起始原则除外）；（3）DNASequitur：为适配DNA序列，S

36、equitur的改进型。vDNAPack（Behshad Behzadi等，2005）是一个基于动态规划的算法，要点：（1）汉明距离用于重复和反向互补，（2）用CTW或2阶算术编码对非重复区编码，（3）用动态规划选择重复。（4）使用加速技术，也适用于长序列。vGenomeCompress（Umesh Ghoshdastider等）算法据报道是压缩最好的算法。v所有这些方法有很多共性，其中包括：（1）利用DNA序列本身的特性，将序列分成重复 （包括近似重复的反向互补）段和非重复段；（2）采用类似于LZ的算法压缩重复段；（3）采用性能好的通用压缩算法，例如算术编码、CWT等算法压缩非重复段；（4）

37、采用改进的搜索算法寻找重复段。v资料表明，这些算法可以把DNA序列压缩到1.7比特左右。12.4.2 12.4.2 最大熵谱估计和最小交叉熵最大熵谱估计和最小交叉熵 谱估计谱估计 我们知道，信号的时间相关函数可直接利用信号的时间波形样值计算，而相关函数和功率谱是互为富氏变换的关系。所以信号功率谱的估计通常要通过计算相关函数来实现。常规的谱估计方法要对信号的样值序列加窗，利用有限时间内的样值计算相关函数，然后进行功率谱的估计。如果所使用的时间段太长，就不能保证信号的平稳性，而使用的时间段太短，就会降低功率谱的分辨率。而且由于加窗的影响，还使窗内的信号失真，同时还迫使窗外的信号为零，而窗外实际的信

38、号未必是零。还有一种谱估计方法方法，就是将自相关函数向未知区域延伸，但如何合理延伸是一个关键问题。Burg提出最大熵谱估计的方法，在自相关函数的延伸时，使由功率谱所确定的熵率最大，即在所计算的自相关函数的约束下，把使信源熵率最大的功率谱作为估计的结果。1最大熵谱估计最大熵谱估计v一个限带高斯连续时间信源的熵率与它的功率谱的关系由下式确定：（12.4.2）其中，W为信号的带宽，S（f）为信号的功率谱密度。v通过计算得到的信号的自相关函数序列就是功率谱的约束，即 ，（12.4.3）其中，t为时间抽样间隔，2p+1为自相关函数样值的个数。v最大熵谱估计就是求在给定约束下使熵率达到最大的信号功率谱。下

39、面求在（12.4.3）的约束下，（12.4.2）的极值。v令 求J对S(f）“导数”，并令其为零，得 （12.4.4)可以证明 （12.4.5)其中，可通过与自相关函数有关的方程组求解。将（12.4.5)代入（12.4.4)，得到最大熵功率谱估计为 （12.4.6)满足（12.4.6)式的信号x(t)称为自回归过程，其时间序列满足：（12.4.7)其中，xi 为x(t)的抽样值，zi 为均值为0，方差为2 的高斯白噪声序列。根据（12.4.7)，得 （12.4.8)（12.4.9)（12.4.8)和（12.4.9)称做Yule-Walker方程。利用x(t)的抽样值xi 估计相关函数R(i)，

40、再用Yule-Walker方程来计算 和 ，最后根据（12.4.6)式得到信号频谱的估计。根据相关函数R(i)估计的方式不同可分为自相关法和协方差法以求解方程组。v最大熵谱估计比常规的谱估计的分辨率有很大提高，成为当前重要的实用谱估计算法。2最小交叉熵谱估计最小交叉熵谱估计v最小交叉熵谱估计可以看成自相关函数的另一种延伸方式，这里考虑到一个先验估计，在谱估计时，使被估计的过程和先验估计之间的交叉熵最小。如果先验估计是平坦谱，那么最小交叉熵谱估计就归结为最大熵谱估计。v设概率密度p属于某概率集合P，该集合是已知的，但p本身未知，q为先验密度，同时还有p满足的约束条件。最小交叉熵谱估计的原理就是：

41、在所有满足约束的密度中，选择与先验密度q交叉熵最小的概率密度p，如（12.3.9)式。v由于利用了先验信息，最小交叉熵谱估计比最大熵谱估计的性能有改善。12.4.3 12.4.3 最大熵建模及其在自然语言最大熵建模及其在自然语言 处理中应用处理中应用1.最大熵建模基本原理最大熵建模基本原理v建模就是构造一个精确表示随机过程行为的随机模型，估计在给定上下文x条件下输出y 的概率p（y|x），其中x为模型的输入，y为输出。v为设计一个适合某种过程的模型，需要对该过程的行为进行一段时间的观察，收集样本值作为训练数据。设训练样本集有N对样本值，表示为(x1,y1),(x2,y2),(xN,yN)。v定

42、义两种分布，一是经验分布，就是通过训练数据得到的分布；二是模型分布，就是信源实际的分布。训练集合中数据对的分布称为经验分布，定义为：（12.4.11）通常，一个特殊的数据对要么不出现，要么出现多次。v最大熵建模就是以训练数据为依据，用最大熵原理构造一个产生训练样本经验分布 的统计模型，这里估计的是条件概率 。v建模的一个重要步骤就是从训练数据中提取特征。特征或特征函数指的是x与y之间存在的某种特定关系，可以用一个输出为0或1的二值函数（或示性函数）表示。特征实际上是一种映射：，其中，。A为y的符号集，表示一个可能的类集合；B为x的符号集，为上下文集合。v对于一个特征(x0,y0)，定义特征函数

43、：（12.4.12）v 实际上，特征函数的定义与所解决的问题有关。以文本分类问题为例。假设有4类文本：政治、经济、体育和文艺。每个词在不同类的文本中出现的概率是不同的，特别是具有代表性的词类。例如，“货币”一词经常出现在经济类的文本中，而“比赛”一词经常出现在体育类的文本中。对于一个特征（“球”，“体育”），其中“球”属于上下文集合，“体育”属于类集合，其特征函数定义为：v用经验分布对特征求平均是有用的统计量，对每一个特征，表示为 （12.4.13）v用模型 对f的期望值为 （12.4.14）v其中，为训练样本中x的经验分布。我们令经验分布特征平均值与模型分布特征平均值相同，即要求对每一个特征

44、有，或 （12.4.15）（12.4.15）称为约束方程或简称约束。当样本数足够多时，可信度高的特征的经验概率与期望概率是一致的。v 设有n个特征函数fi，i=1，n，这是建模中重要的统计量，我们希望所寻找的模型符合这些统计量。定义P表示所有满足（12.4.15）约束的条件概率分布的集合，即 ，（12.4.16）条件熵表示为 （12.4.17）最大熵建模就是：从满足约束条件的集合P中，选择具有最大熵的分布 ，即 （12.4.18）这是一个求有约束优极值化问题，应用拉格朗日乘子法，引入拉格朗日乘子 ，并仿照（12.2.4）的推导，得 （12.4.19）其中，（12.4.20）（12.4.21）设

45、 （12.4.22）可以看到，最大熵建模的解p*满足 （12.4.23）v由于训练序列各样本对都是独立的，所以一个N长的训练序列的对数似然函数为：（12.4.24）将（12.4.19）的结果代入（12.4.24），并求满足最大值的 ，通过推导得知，当满足（12.4.15）的约束时，（12.4.24）达到最大值，即满足（12.4.19）式的条件概率使训练序列的对数似然函数达到最大值。v因此可得到以下结论：最大熵建模的解p*满足：（1）；（2）；（3）；（4）是惟一的。v最大熵建模在简单情况可以求出解析解，例如有一、二个约束情况。但一般情况最大熵问题没有显式解，求参数 必须借助数值解法。有些实际问

46、题，有时可能有上千个约束条件，计算量和花费的时间巨大，必须使用有效的算法。v一般化的迭代尺度算法（GIS，Generalized Iterative Scaling Algorithm)是一个专门用于最大熵问题的算法（Danroch 和Rateliff，1972），该算法要求特征为非负值，没有解析解，收敛速度较慢。以后，D.Pietra等改进了原有的求解算法，降低了求解的约束条件，提出了IIS(Improved Iterative Scaling Algorithm)算法，增加了算法的适用性，IIS算法是目前最大熵参数求解中的常用算法。2最大熵统计模型的优缺点最大熵统计模型的优缺点v最大熵建模

47、方法有很多优点：（1）与极大似然估计结果同，所建立的模型是唯一的；（2）最大熵统计模型可以灵活地设置约束条件。通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度；（3）通常性能优于其他方法。v最大熵统计模型的缺点：（1）运算量大；（2）存在过拟合问题，通常在求极值时需加入先验随机函数进行平滑。3最大熵建模在自然语言处理中的应用最大熵建模在自然语言处理中的应用v最大熵建模已成功应用到自然语言处理的许多方面，其中包括：单词聚类(S.Pietra)机器翻译（A.L.Berger）句子边界检测，词类标注(Ratnaparkli,1998)自适应统计语言建模(Rosenfeld,19

48、96)组块分析(Osborne,2003;Koeling,2003)垃圾邮件过滤(Zhang,2003)名实体识别(A.Borthwick)12.4.4 12.4.4 最大熵原理在经济学中的应最大熵原理在经济学中的应 用用v前面指出物理学中的波耳兹曼分布是一个指数分布。推导该定律的基本依据是能量守恒定律。因此，我们可以推断，在一个大系统中任何守恒的量都应该具有指数概率分布。在物理学中指数Boltzmann-Gibbs分布和封闭经济系统中的货币的平衡分布具有类似性，与能量类似，在一个封闭经济体中，货币在经济代理商之间的相互作用中在局部是守恒的，所以货币也遵循Boltzmann-Gibbs分布，其

49、等效温度等于平均每个代理商的货币量。财富不但包含货币还包含物质财富，所以不守恒，一个早期的研究者Vilfledo Pareto在19世纪末发现，在一个人口均匀分布的地理范围内，人们之间的财富的分布按一个幂律分布，因此这种分布经常称做Pareto分布。下面利用最大熵原理推导和分析封闭的经济体中货币和财富的分布。1.封闭经济体中货币量的分布封闭经济体中货币量的分布v守恒的交换市场可以看成大量的经济代理商组成，他们之间通过买卖相互作用。在这种市场中，生产活动并不存在，而且在每次交易中只是货币的交换，例如，一个保险公司中一个代理人的行为，所有其他代理人都可以看成行为的环境。他们按市场手段进行交换，此环

50、境吸收代理人损失的货币同时又提供给代理人货币作为其收入。这里货币的总量是守恒的。v假设在一个经济体中，总货币量为M元，总代理商数为N。假定在经济发展的每个阶段，一个代理商随机选择另一个代理商，并给所选择的代理商汇入1元，规定无资金的代理商不能借贷。求货币的稳态分布（拥有货币量i元的代理商的概率），设交易初始每代理商具有相同的货币量。v解可以利用最大熵原理解决这个问题。设 为有i元代理商的概率，为有i元的代理商个数，根据题意有 ，当N很大时，所求的概率近似为占总体的比例数，即 ，所以 （12.4.25a）（12.4.25b）实际上，确定货币的稳态分布,就是求在满足（12.4.25）约束下对应最大