最大熵原理与应用(2011)

1、1 u 最大熵原理来最大熵原理来 u 最大熵测量最大熵测量 u 熵集中原理熵集中原理 u 最小交叉熵原理最小交叉熵原理 u 最大熵原理应用最大熵原理应用 2 最大熵原理最大熵原理 3 起源于统计力学起源于统计力学 1957年，统计物理学家年，统计物理学家jaynes根据信息根据信息 熵的概念提出了一个熵的概念提出了一个利用部分信息确定随机利用部分信息确定随机 变量集合概率分布变量集合概率分布的方法，称为最大熵原理的方法，称为最大熵原理。 最大熵原理最大熵原理 4 信息论提供了一个基于部分知识建立概率分布的构造信息论提供了一个基于部分知识建立概率分布的构造 性准则，并导致被称作最大熵估计的一种统

2、计推断方法。性准则，并导致被称作最大熵估计的一种统计推断方法。 这是根据给定信息得到的最小可能偏差的估计。这是根据给定信息得到的最小可能偏差的估计。 如果把统计力学看成统计推断的一种形式，而不是一种如果把统计力学看成统计推断的一种形式，而不是一种 物理学理论，那么就会发现通常的计算原则，从确定分物理学理论，那么就会发现通常的计算原则，从确定分 割函数开始，都是最大熵原理的直接结果。割函数开始，都是最大熵原理的直接结果。 最大熵原理最大熵原理 5 统计力学的所有已知结果，无论是平衡统计力学的所有已知结果，无论是平衡 的还是不平衡的，基本上都是最大熵原的还是不平衡的，基本上都是最大熵原 理推导出的

3、结果理推导出的结果 。 最大熵原理最大熵原理 6 基本思想基本思想: 求满足某些约束的信源事件概率分布时，应求满足某些约束的信源事件概率分布时，应 使得信源的熵最大使得信源的熵最大 可以使我们依靠有限的数据达到尽可能客观可以使我们依靠有限的数据达到尽可能客观 的效果的效果 克服可能引入的偏差。克服可能引入的偏差。 最大熵原理最大熵原理 7 一般的最大熵原理应用于良好定义的一般的最大熵原理应用于良好定义的 假设空间和无噪情况且不完整的数假设空间和无噪情况且不完整的数 据的推断问题。据的推断问题。 8 最大熵原理应用于多个领域最大熵原理应用于多个领域: 信号检测与处理信号检测与处理 自然语言处理自

4、然语言处理 生物医学生物医学 环境水利环境水利 气象学气象学 经济学经济学 9 最大熵原理的描述最大熵原理的描述: 在寻找满足某些约束的概率分布时，在寻找满足某些约束的概率分布时， 选择满足这些约束具有最大熵的概率分布。选择满足这些约束具有最大熵的概率分布。 10 约束所提供的信息是不完整的，称作部分信息约束所提供的信息是不完整的，称作部分信息; 部分信息有若干种形式部分信息有若干种形式: 随机变量矩的约束随机变量矩的约束 概率分布形状的约束概率分布形状的约束 11 12 13 14 熵 其中， 约束 i n i i pphlog 1 n i i p 1 1 (),1, n irii i p

5、gxa rm () ii ppxx 15 满足约束达到最大熵的概率分布 其中 1 1 exp(),1, r m iri r pzgxin 0 11 exp()exp( ) r nm ri ir zg x 0 1 () m ri r r gx i pe 16 m r r r azh 1 max ln 证 求有约束极值 待定常数 17 0 11 11 log(1)(1) ( ) nn iii ii mn ririr ri lppp p gxa mi i , 1 , 0, 18 0/ i pl )(exp 1 1 m r iri xgzp r m r xg r ii z 1 )(1 )exp( 0

6、z)exp( rr 19 )(exp 11 n i m r irr xgz n i m r xg r ir 11 )( n i m r xg r m k xg k n i ir r ir ik xg a 11 )( 1 )( 1 )( 20 21 123 ( ) 1/2,( )( ) 1/4 xxx p ap ap a 123 ( )2/3,( )( ) 1/6 yyy p bp bp b 22 ()( )( )h xyh xh y 1/31/61/6 1/12 1/24 1/24 1/12 1/24 1/24 23 information: 1/3 of kangaroos have blu

7、e eyes, and 1/3 of kangaroos are left-handed problem: on the basis of this information alone, estimate what proportion of kangaroos are both blue- eyed and left-handed 24 ()( )( )h xyh xh y ( )(1/3)h xh ( )(1/3)h yh 25 ()( )( )h xyh xh y 1 1 (,)1/9 3 3 p xred yleft 26 solution uses a single variable

8、, 0 x 1/3 but how to choose? common sense says x = 1/9 (i.e. no correlation of attributes) is there some function of the pi which when maximised yields this preferred solution? the kangaroo problem: 2 x 2 truth table normalisation: p1+ p2 + p3 + p4 = 1 constraints: p1+ p2 = 1/3; p1+ p3 = 1/3 27 28 例

9、例1 做做1000次抛掷骰子的试验，求抛掷点次抛掷骰子的试验，求抛掷点 数的平均值。数的平均值。 解解 由于抛掷次数很多，所以各点出现的频率由于抛掷次数很多，所以各点出现的频率 近似等于出现的概率。假定在每次抛掷后，骰近似等于出现的概率。假定在每次抛掷后，骰 子子6个面中的每一个面朝上的概率都相同，即个面中的每一个面朝上的概率都相同，即 为为1/6。这里我们利用了。这里我们利用了“不充分理由原理不充分理由原理”， 因为除知道骰子有因为除知道骰子有6个面外，我们没有其他任个面外，我们没有其他任 何别的信息。何别的信息。 抛掷点数的平均值：抛掷点数的平均值： m=(1+2+3+4+5+6)/6=3

10、.5。# 29 例例1(续续) 做做1000次抛掷骰子的试验后得知抛掷点数次抛掷骰子的试验后得知抛掷点数 的平均值为的平均值为4.5，求骰子各面朝上的概率分布。，求骰子各面朝上的概率分布。 解 骰子的各面朝上的概率是不均匀的。除概率的归骰子的各面朝上的概率是不均匀的。除概率的归 一性外，我们知道的信息仅有平均值，这对于确定一性外，我们知道的信息仅有平均值，这对于确定6 个面的概率是不完整的信息，必须利用最大熵原理。个面的概率是不完整的信息，必须利用最大熵原理。 平均值的约束写为平均值的约束写为 5 . 465432 654321 pppppp 30 计算得计算得 6 1 5 1 4 1 3 1

11、 2 11 6 1 5 1 4 1 3 1 2 11 65432 5.4 6637.26 44925. 1 6 1 5 1 4 1 3 1 2 11 1 ii i p 3475. 0,2398. 0,1654. 0,1142. 0,0788. 0,0543. 0(),( 654321 pppppp 所求分布为计算所求分布为计算 31 一快餐店出售一快餐店出售4种套餐：、鱼、鸡种套餐：、鱼、鸡 肉、面条和豆腐，单价分别为肉、面条和豆腐，单价分别为8元、元、3 元、元、2元和元和1元。在某月通过调查得知，元。在某月通过调查得知， 该快餐店套餐的总营业额为该快餐店套餐的总营业额为25万元，万元， 共

12、有共有10万人次来就餐。试利用最大熵万人次来就餐。试利用最大熵 原理求本月原理求本月4种套餐所占的销售份额。种套餐所占的销售份额。 32 2鱼、鸡肉、面条和豆腐四种销售份额分别记鱼、鸡肉、面条和豆腐四种销售份额分别记 为：为： 1234 ,pppp 4 1 lo g ii i hpp 33 2约束为约束为 1234 1pppp 1234 83225/10pppp 34 解得解得 832 111 832 1111 832 2.5 1 .8359175 35 8 1 1 832 1111 0.1011p 3 1 2 832 1111 0.2478p 2 1 3 832 1111 0.2964p 1

13、 4 832 1111 0.3546p 信源的熵 满足 36 b a dxxpxph)(ln)( b a dxxp1)( ( )( ) b rr a p x gx dxa mr, 2 , 1 ， 达到最大值的概率密度 其中 最大熵为 37 )(exp)( 1 1 m r r xgzxp r dxxgxpez m r r b a r )( 1 m r r r azh 1 max ln 38 12 12111 ()() ()(|)(|) n nn hxhy yy hyhyyhyyy 为使试验次数最少，需要每次试验的熵最大为使试验次数最少，需要每次试验的熵最大 一般性假币称重鉴别问题：设有n 枚硬币

14、 ，其中仅有一枚假币，在已知或未知假币 与真币之间重量关系两种条件下，通过用 无砝码天平称重的方法鉴别假币，求所需 的最少称重次数。 39 在每次天平称重时，天平的两端应放置相同 数目的硬币，会出现3种称重结果：平衡（ 假币未参与称重），左倾（天平左端重）， 右倾（天平右端重）；每次天平称重所获得 的最大信息量为 （称重结果等概率） 40 命题命题1： 设有 n （ ）枚硬币，其中有 一假，且知其较轻或较重； 那么，发现假币 的最少称重次数k满足： 41 1log/log3knk 1 33 kk n 命题命题2： 设有n （ ）枚硬币，其中有一 假，且满足：这些硬币分成两组a、b； a有a枚，

15、b有b枚，a+b=n； 若假币属 于a，则其较轻；若假币属于b，则其较重 ；那么，发现假币的最少称重次数k满足 ： 1 33 kk n 1log/ log3knk 命题命题3： 设有n（ ）枚硬币，其 中有一假，但不知轻重，还有另外的一枚 真币；那么，称k次就能发现假币。 43 1 (31)/2(31)/2 kk n 命题命题4： 设有 n（ ）枚硬币，其 中有一假，但不知轻重；那么，称k次就能 发现假币。 44 1 (33)/2(33)/2 kk n 将硬币编号：1，2，3，4，5，6，7，8，9，10，11，12。三次 称重安排如下： 称重 左盘 右盘 其它 1 1, 2 ,3, 4 5,

16、 6, 7, 8 9, 10, 11, 12 2 1 ,6, 7, 8 5, 10, 11, 12 9, 2, 3, 4 3 5,6,10,2 9, 7, 11, 3 1, 8, 12, 4 称重结果：0：平衡，1：左倾，-1：右倾， 45 3次称重安排可表示成矩阵形式（矩阵上一行是硬币序号）： 其中，每行为称重安排，1：放左盘，-1：放右盘，0：不放。 每一列为检测结果， 检测结果对应的硬币序号为假币。如果结 果与上面符合，则对应重量为重，如果结果不包含在上述表中 ，则1、-1互换，得到的重量为轻。例如，若称重结果为110 则1号为假币，且重量较重；若称重结果为1-1 0，1与-1交换 为-

17、110， 则8号为假币，且重量较轻。 46 123456789101112 111111110000 100011110111 011011101110 47 熵集中定理熵集中定理 熵集中定理是最大熵原理的依据。熵集中定理是最大熵原理的依据。 可以证明，具有最大熵的概率分布具可以证明，具有最大熵的概率分布具 有最多的实现方法数，因此更容易被有最多的实现方法数，因此更容易被 观察到，而且是满足某些条件的分布观察到，而且是满足某些条件的分布 所产生的熵绝大部分在最大熵附近。所产生的熵绝大部分在最大熵附近。 48 49 假设做n次随机实验，每次实验有n个结 果，每种结果出现的次数为 ，设每 种结果出

18、现的概率为 ，那么当n足 够大时，有 。因此，实现某 种特殊的概率集合 的方法数为 熵集中定理熵集中定理 )!()!( ! ),( 1 1 n n npnp n ppw i p ii npn ),1,nip i i n 50 斯特灵公式： 熵集中定理熵集中定理 n e n nn)(2! hppwn i ii n logloglim 1 nh aew 方法数最多的分布最容易观测到方法数最多的分布最容易观测到 方法数与熵呈指数关系方法数与熵呈指数关系 对应最大熵的分布最容易观测到对应最大熵的分布最容易观测到 熵的另一种含义：表征某种分布实现方法熵的另一种含义：表征某种分布实现方法 数的多少，熵大则

19、表明方法数大。当试验数的多少，熵大则表明方法数大。当试验 次数足够多时，熵等于方法数的对数被试次数足够多时，熵等于方法数的对数被试 验总数除。验总数除。 51 52 满足约束的一组概率所产生的熵在如下范围：满足约束的一组概率所产生的熵在如下范围： 其中其中 max1max ),(hpphhh n 熵集中定理熵集中定理 )1 (2 2 fhn k 53 当当n足够大时，足够大时， 渐近为维数渐近为维数 为为k（=n-m-1，n为信源符号数，为信源符号数， m为约束方程个数），置信度为 为约束方程个数），置信度为 1-f的 的 分布。通常，在很高的分布。通常，在很高的 置信度的条件下，置信度的条件

20、下， 的值很小。的值很小。 2 hn2 h 54 55 56 57 许多专家学者从不同的角度和侧面研究许多专家学者从不同的角度和侧面研究 和定义信息。据说到目前为止已有上百种信和定义信息。据说到目前为止已有上百种信 息的定义或说法。息的定义或说法。 例如，例如，“信息是事物之间的差异信息是事物之间的差异”， “信息是物质与能量在时间与空间分布的不信息是物质与能量在时间与空间分布的不 均匀性均匀性”，“信息是收信着事先不知道的东信息是收信着事先不知道的东 西西”等等。等等。 58 求置信度求置信度95%和和99.99%时信源熵的范围。时信源熵的范围。 根据题意，根据题意， 为自由度为自由度6-1

21、-1=4的的 分布，分布， 查表，查表， (1)在置信度在置信度95%条件下条件下,得，得， 信源熵的范围：信源熵的范围： 1.609 h 1.614 (奈特奈特)。# (2)在置信度在置信度99.99%条件下条件下,得，得， 信源熵的范围：信源熵的范围： 1.602 h 1.614 (奈特奈特)。# 2 ,488. 92hn 00474. 0h 012.0)9999.0( 12 4 nh hn2 59 信息与物质、能量相同的特征信息与物质、能量相同的特征: : 信息可以产生、消失、携带、处理信息可以产生、消失、携带、处理 和量度和量度。 信息与物质、能量不同的特征信息与物质、能量不同的特征:

22、 : 信息可共享，可无限制地复制。信息可共享，可无限制地复制。 60 几种重要的最大熵分布几种重要的最大熵分布 1满足均值约束的分布是指数分满足均值约束的分布是指数分 布。布。 61 例例2 连续信源连续信源x的取值区间为的取值区间为0， ），均值），均值e(x)=,求达到最大熵求达到最大熵 的的x的分布密度和相应的最大熵。的分布密度和相应的最大熵。 62 01 ( ) x p xe / 1 ( ),0 x p xex )log( max eh 63 2满足均值和均方值约束的分布满足均值和均方值约束的分布 是高斯分布。是高斯分布。 64 65 3满足几何平均值约束的分布是幂 满足几何平均值约束

23、的分布是幂 律分布。律分布。 66 4 67 5 68 幂律分布幂律分布 xxp)( 泊松分布泊松分布 个体尺度在特征尺度附近变化很小，平均值 能表征整个群体特性分布。 幂律分布幂律分布 。 个体尺度在很宽的范围内变化，跨越多个数 量级。积累概率分布“长尾” 69 泊松分布 幂律分布 70 71 19世纪的意大利经济学家 世纪的意大利经济学家pareto研究研究 了个人收入的统计分布了个人收入的统计分布,发现少数人的收入发现少数人的收入 要远多于大多数人的收入，要远多于大多数人的收入， 80/2080/20 法则法则 个人收入 个人收入x不小于某个特定值不小于某个特定值x的概率与的概率与 x的

24、常数次幂亦存在简单的反比关系，即 的常数次幂亦存在简单的反比关系，即 为为pareto定律。定律。 72 自然界与社会生活中存在很多幂律分布现自然界与社会生活中存在很多幂律分布现 象。象。 1932年，年，zipf在研究英文单词出现的频在研究英文单词出现的频 率时率时,发现如果把单词出现的频率按由大到发现如果把单词出现的频率按由大到 小的顺序排列小的顺序排列,则每个单词出现的频率与它则每个单词出现的频率与它 的名次的常数次幂存在简单的反比关系，的名次的常数次幂存在简单的反比关系， 这种分布就称为这种分布就称为zipf定律。定律。 73 ) ) 74 75 76 77 对给定熵函数和概率密度求满

25、足最大熵的 约束 已知熵： 概率分布： 求： 78 i n i i pphlog 1 i p (),1, n irii i p gxa rm 已知 和 求 79 b a dxxpxph)(ln)( ()px ( )( ) b rr a p x gx dxa mr, 2 , 1 ， 均匀分布 指数分布： 高斯分布： 80 0 1 ( )p xe ba / 1 () x p xe 0 ()xpx d x 0 ()xpx d x 22 0 ()()xpx d x 2 2 () 2 1 () 2 x p xe 拉普拉斯分布： 伽玛分布 81 1(1)ln ( ) ( )( ) axaxx aa p x

26、exe 1 0 ()xpx d x 2 0 ln()xpx d x |/ 1 () 2 x pxe |()xpxd x pareto分布 贝塔分布 82 (1) 1(1)ln ( )() x x p xex ln()xpx d x 11(1)ln(1)ln(1) 11 ( )(1) (, )(, ) mnmxnx p xxxe beta m nbeta m n 1 1 0 ln()xpx d x 1 2 0 ln (1)()xpx d x 83 84 . . 85 . . 86 最小交叉熵原理最小交叉熵原理 dx xq xp xpqpd b a )( )( log)()|( b a rr ad

27、xxgxp)()(mr,2, 1 b a dxxp1)( 87 )(exp)()( 1 0 m r r xgxqxp r 88 交叉熵法交叉熵法 在信息处理中，往往要求一个概率密度接近在信息处理中，往往要求一个概率密度接近 另一个目标概率密度，而目标概率密度的参另一个目标概率密度，而目标概率密度的参 数未知的。这样，将（数未知的。这样，将（12.3.2）式作为目标）式作为目标 概率密度，为含有参数的概率密度，写成，概率密度，为含有参数的概率密度，写成， 可以通过改变可以通过改变u使交叉熵最小。由于使交叉熵最小。由于 89 仙农建立了三项基本技术的理论基础仙农建立了三项基本技术的理论基础 信息论

28、是前两项技术的理论基础信息论是前两项技术的理论基础 最大熵谱分析最大熵谱分析 信号功率谱的估计通常要通过计算相关信号功率谱的估计通常要通过计算相关 函数来实现。常规的谱估计方法要将信号函数来实现。常规的谱估计方法要将信号 的样值序列进行适当截短，即利用在有限的样值序列进行适当截短，即利用在有限 时间内的样值计算相关函数，然后进行功时间内的样值计算相关函数，然后进行功 率谱的估计。如果所使用的时间段太长，率谱的估计。如果所使用的时间段太长， 就不能保证信号的平稳性，而使用的时间就不能保证信号的平稳性，而使用的时间 段太短，就会降低功率谱的分辨率。段太短，就会降低功率谱的分辨率。 90 91 92

29、 burg提出最大熵谱估计提出最大熵谱估计: 在所计算的自相关函数的约束下，把使信在所计算的自相关函数的约束下，把使信 源熵率最大的功率谱作为估计的结果。源熵率最大的功率谱作为估计的结果。 一个限带高斯连续信源的熵由它的功率谱一个限带高斯连续信源的熵由它的功率谱 所决定，而通过计算得到的信号的自相关函数所决定，而通过计算得到的信号的自相关函数 序列就是功率谱的约束。最大熵谱估计就是求序列就是功率谱的约束。最大熵谱估计就是求 在此约束下使熵率达到最大的信号的功率谱。在此约束下使熵率达到最大的信号的功率谱。 93 设设 对所有对所有i， 那么，满足上面约束的最大熵率随机过程那么，满足上面约束的最大

30、熵率随机过程 是是 如下形式的如下形式的p阶高斯马尔科夫过程：阶高斯马尔科夫过程： 其中，其中， 为独立同分布为独立同分布 ，且，且 的的 选择满足上面的约束。选择满足上面的约束。 注：未假定：零均值，高斯和广义平稳注：未假定：零均值，高斯和广义平稳 94 (),0, ii kk e x xkp i x 1 p iki ki k xa xz i z 2 (0,)n 2 , p aa 熵率熵率 yule-walker方程方程 95 *2 1 log(2) 2 he 1 ,1, p iki k k ra rip 2 0 1 p kk k ra r 96 熵率熵率: 自相关函数序列就是功率谱的约束自

31、相关函数序列就是功率谱的约束: 令令 最大熵谱估计就是使最大熵谱估计就是使j最大的谱，令最大的谱，令 得得 11 ()log(2)log ( ) 24 w w h xes f df w ( )( )exp( 2) w w r ks fjfk t df pkp 11 log(2)log ( )( ) 24 p w k w kp jes f dfr k w 0 () j sf 97 1 ( ) exp( 2) p k kp s f jfk t 2 2 2 1 () 1 p jfkt k k sf a e 98 经典谱估计（非参数法）经典谱估计（非参数法） 相关法相关法:blackman-turke

32、y,:blackman-turkey, （间接法（间接法) ) 周期图法周期图法( (periodogramperiodogram):():(直接法）直接法） bartlettbartlett提出提出 ,welch ,welch 改进改进 现代谱估计现代谱估计( (参数法）参数法） ar谱估计谱估计 ma谱估计谱估计 arma谱估计谱估计 最大熵最大熵 (maximun entropy)谱估计谱估计 最大似然最大似然(maximum- likelihood)谱估计谱估计 99 ar谱估计谱估计 模型模型 自相关法，自相关法，yule-walker法法 协方差法协方差法 burg 法法(最大熵法

33、最大熵法) ( )1/( ) ppn enazy 100 自相关法，自相关法，yule-walker法法 保证稳定保证稳定 加窗加窗 精度差精度差 1 2 0 ( )min np p n en 101 协方差（协方差（covariance）法）法 存在稳定性问题存在稳定性问题 不加窗不加窗 精度高精度高 1 2 ( )min n p np en 102 burg法法 计算反射系数计算反射系数 保证稳定保证稳定 精度高精度高 1 22 ( )( ) min n pp np enen 103 ar谱估计谱估计 经典方法（经典方法（bartlett） yule-walker法法 ml法法 burg

34、法法(最大熵法最大熵法) （见比较图）（见比较图） 104 105 106 最小交叉熵谱估计可以看成考虑到一 个先验估计的 自相关函数另一种延伸 方式； 在谱估计时，使被估计的过程和先验 估计之间的交叉熵最小； 如果先验估计是平坦谱，那么最小交 叉熵谱估计就归结为最大熵谱估计。 107 设概率密度p属于某概率集合p，该集合是 已知的，但p本身未知，q为先验密度，同 时还有p满足的约束条件。最小交叉熵谱 估计的原理就是：在所有满足约束的密度 中，选择与先验密度q交叉熵最小的概率 密度p。 由于利用了先验信息，最小交叉熵谱估 计比最大熵谱估计的性能有改善。 108 109 110 111 112

35、最大熵建模及其在自然语言处理中应用最大熵建模及其在自然语言处理中应用 1. 最大熵建模基本原理最大熵建模基本原理 建模就是构造一个精确表示随机过程行为的随机模型， 估计在给定上下文x条件下输出y 的概率p（y|x），其中 x为模型的输入，y为输出。 为设计一个适合某种过程的模型，需要对该过程的行为 进行一段时间的观察，收集样本值作为训练数据。设训 练样本集有n对样本值，表示为 (x1,y1),(x2,y2),(xn,yn)。 113 定义两种分布，一是经验分布，就是通过训练数据得到的 分布；二是模型分布，就是信源实际的分布。训练集合中 数据对的分布称为经验分布，定义为 在训练集合中出现的次数

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

37、5 其他 且若 0 xy1 ),( 00 , 00 xy yxf yx 实际上，特征函数的定义与所解决的问题有关。以文本分 类问题为例。假设有4类文本：政治、经济、体育和文艺 。每个词在不同类的文本中出现的概率是不同的，特别是 具有代表性的词类。例如，“货币”一词经常出现在经济 类的文本中，而“比赛”一词经常出现在体育类的文本中 。对于一个特征（“球”，“运动”），其中“球”属于 上下文集合，“运动”属于类集合，其特征函数定义为： 116 其他0 出现 运动”且“球”在x中1 ),( , “ 运动球 yif yxf 用经验分布对特征求平均是有用的统计量，表示为 用模型 对f 的期望值为 其中，

38、 为训练样本中x的经验分布。 117 yx p yxfyxpfe , ),(),( )( yx p yxfxypxpfe , ),()|()( )( )|(xyp )( xp 我们令经验分布特征平均值与模型分布特征平均值相同， 即要求对每一个特征有， ，或 称为约束方程或简称约束。当样本数足够多时，可信度 高的特征的经验概率与期望概率是一致的。 118 )()(fefe pp yx yxfxypxp , ),()|()( yx yxfyxp , ),(),( 定义p表示所有满足（12. 4. 15）约束的条件概率分布的 集合，即 ， 条件熵表示为 119 | )|(xyppp, 2 . 1 )

39、,()(nifefe ipip yx xypxypxpph , )|(log)|()( )( 120 qpp * 最大熵建模就是：从满足约束条件的集合p中，选择具有 最大熵的分布 ，即 这是一个求有约束优极值化问题， 121 )(maxarg * php pp pp * 122 应用拉格朗日乘子法，引入拉格朗日乘子 ，得 123 ),(exp)()|( 1 yxfxzxyp i i i 124 结论：结论： 最大熵建模的解最大熵建模的解p*满足：满足： （1） （2） （3） （4） 是惟一的。是惟一的。 qpp * )(maxarg * php pp )(maxarg * plp pqp *

40、 p 125 最大熵建模在简单情况可以求出解析解，例如有一、最大熵建模在简单情况可以求出解析解，例如有一、 二个约束情况。但一般情况最大熵问题没有显式解，二个约束情况。但一般情况最大熵问题没有显式解， 求参数必须借助数值解法。有些实际问题，有时可求参数必须借助数值解法。有些实际问题，有时可 能有上千个约束条件，计算量和花费的时间巨大，能有上千个约束条件，计算量和花费的时间巨大， 必须使用有效的算法。必须使用有效的算法。 一个专门用于最大熵问题的就是由一个专门用于最大熵问题的就是由danroch 和和 rateliff于于1972年提出了一个称为年提出了一个称为 gis(generalized iterative scaling algorithm)的算法，该算法要求特征为非负值，的算法，该算法要求特征为非负值， 没有解析解，收敛速度较慢。没有解析解，收敛速度较慢。 d.pietra等改进了原有的求解算法，降低了求解等改进了原有的求解算法，降低了求解 的约束条件，提出了的约束条件，提出了iis(improved iterative scaling algorithm)算法，增加了算法的适用