两种熵——一道非常有趣的数学问题
2009-6-2 18:44:30  人工智能  信息论与熵 

受到计算士、张学文老师讨论的启发,这两天研究了一个非常有意思的事情:任意数值集合的两种熵,这不仅仅是一个纯粹的数学问题,而且跟很多实际问题相关。我先给出定义,在列举出来这个问题跟什么实际问题相关,最后给出我做的一些数值模拟结果,至于进一步的更细致分析,以致解析结果,还有待各位集智。

1、定义。

设任意给定一个集合A={a1,a2,...,an},其中ai都是正实数,我们首先可以定义一种概率分布叫做:

p(i)=ai/Sigma(ai)

那么,我们很容易就能定义一种熵,暂且叫做Shannon熵,

S=-Sigma(pi log pi)

另外,我们还可以把A集合看作一个随机过程K的时间序列,这样A集合也就反映了该序列的分布情况,我们可以计算集合中ai的分布,具体可以这样做,定义q(j)叫做:

q(x)=|{ai|ai=x}|/n

直观讲,就是说A中集合的具体数值有很多是重复的, 假设一个有S种不同的数值,那么q(x)就表示那些都等于x的ai的个数占n中的百分比。很显然,x的取值一定会在[min{ai},max{ai}]之中,所以我们可以定义另一种Shannon熵,叫做:

J=-Sigma(q(x) log q(x))

这就是我们这篇文章要讨论的两种熵。

我们来举一个简单的例子说明一下:

比如A={1,2,1,1,3,2,3,3,2}

那么

S=-(1 log 1 + 2 log 2 + 1 log 1 + 1 log 1 + 3 log 3 + 2 log 2 + 3 log 3 + 3 log 3 + 2 log 2 - 9 log 18)/18=0.664831

我们再对A中的数值进行归并,这样

等于1的元素有3个,等于2的有3个,等于3的也是3个,

那么q(1)=3/9, q(2)=3/9, q(3)=3/9,

所以J=-(3/3 log 1/3)=1.09861

好了,现在定义说清楚了,我们来看看这两套东西有什么用处。

2、现实中的实例及意义

(1)财富分布

现实生活中有很多例子可以说明p和q两种概率以及两种熵的应用。比如,我们考虑社会财富分布问题,假设社会上有n个人,每个人的财富是wi,这就构成了A集合。那么S熵就反映了财富分布的均匀程度。我们知道当所有的pi近乎相等的时候,S是最大的,所以S越大就表示社会财富分布越均匀。

在这个例子中,q是什么呢?它表示第x个财富阶层的总人口比例。J熵表达的是人口在财富区间上的分布均匀情况,显然J越大表示每一个财富区间都是等可能分布的。

这就有意思了,我们可以考虑一个人和人之间的随机交换财富的动态过程,这个过程既可以看作财富相对于不同人之间的转移,也可以看作是人相对于不同财富区间上的运动。而且,当财富分布越均匀的时候,J熵反而越小。

(2)物种多度分布

我们考虑一个生态系统中的不同物种。每一个物种所拥有的人口数都不同,比如我们可以指定一种可能性是:{n1,n2,..,nS},表示第一个物种有n1个个体,第二个物种有n2个个体,……显然这就定义了pi,同样可以计算S。

另外,我们也可以考察U(j)这个变量,它表示具有j个个体的物种数量,我们就有了q的定义,那么生态学里面经常讨论的物种多度分布就是指这个q的分布。我们自然也可以计算那个J熵。含义跟上面的财富分布类似。

在这个例子中,q和J的计算相对更有意义,因为考虑一个不断演化的物种,那么如果我们盯住物种看,该物种有可能灭绝,所以计算某一个物种ni的数值大小实际上意义不大。因为它总是不断变化的。但是反过来,q却是一个相对稳定的数值。因为在生态系统的稳态下,不管每一个个体物种的数目如何变化,你总的聚合曲线q的变化却不大。具体可以参考“生态中性理论”

总结来看,如果我们把我们对系统的第一次观察测得的数值叫做p的话,那么q就相当于对p的二次统计或观察。因此S是忽略的一阶信息,而J则是观察者忽略的二阶信息。同样的道理,其实有了q,我们还可以进一步定义q′,q′′,就表述忽略3级信息,忽略4级信息,……

3、模拟性质

初步看来,似乎S熵和J熵呈现相反的变化趋势,比如财富最均匀的时候,显然S最大,而J最小。但对任意情况都如此吗?我们来针对一个实际的例子进行数值模拟试验。

我们要求计算机生成多个数{n1,n2,...nn},并且这些数之和固定=恒定值n。比如我去n=5,那么各种可能的分布就是:

{1,1,1,1,1}, {1,1,1,2},{1,1,3},{1,4},{5},{1,1,2,1},...,这有很多种组合(大家可以想想这一共有多少种可能性呢?

这些集合就相当于生成了那个A集合,之后,我们自然就可以计算S熵和J熵了。在现实中,这就相当于社会总财富固定,或者生态系统中的可以容纳的总个体数恒定。

下面,我们就对n=40的情况进行计算机模拟。首先,我们来看看,当S最大的时候,对应的分布是什么呢?答案很简单,它应该是:

{1,1,...,1}

这种分布。那么让J最大的那种分布是什么呢?这可不是一下子能想出来的,计算机遍历了所有的结果,给我们的答案是:

{9., 8., 7., 6., 4., 3., 2., 1.}

为什么呢?大家可以想一想q(x)的定义。

显然S最大的时候,J一定=0最小值,但反过来当J最大的时候,S不一定最小。究竟J和S呈现什么规律呢?我们可以把各种可能情况下计算出来的S值作为横轴,J值作为纵轴,画出J随S变化的曲线:

这是一张非常让人觉得Wierd的曲线。首先,J随S并没有呈现简单的单调变化趋势,也就是给定一个S数值,有可能对应多个不同的J值。另外,这些曲线呈现出多个有趋势的“簇”,比如最底下的那一条曲线就好像一个明显的族,J随S呈现单调减的变化。另外,还有一些明显的(横着的“族”)。为什么会这样?我不清楚,这是第一个open problem:

究竟为什么这条曲线会呈现出不同的组?每个组意味着什么?能不能把不同的组曲线写出来?

我做的第二组实验是将S和J的线形组合看作一种目标函数,求解在最大化这个目标函数的情况下,曲线的分步情况。具体的,我们设计的第一个目标函数是:

a S + (1 - a) J

其中a为一个参数,我们在各种可能的ni中寻找能够最大化这个目标函数的分布样子,于是我们得到曲线族:

其中不同的颜色曲线表示当a取不同数值时候的pi分布情况。a越大曲线越在下面,表示pi越均匀,反过来,曲线越陡。画出q(x)的分布曲线如图:

注意,为了清楚起见这副图取了双对数。现在的问题是我们的n太小导致这个图的采样点很少,所以曲线的形状并不很清楚。

另外外一组目标函数是:

a S - (1 - a) J

优化结果是:

注意这里面坐标取了单对数,即纵坐标是取了对数之后的。这组曲线很好玩,它很近似于很多实证分布数据中的S形曲线(比如财富-排名曲线与其类似)。

这个是q(x)的分布曲线,该结果不是很好,也是因为n太小了。留给大家一个问题:如何在大n的情况下寻找优化曲线的性质

如果我们把S看作是一次观察忽略的信息,J看作是二次观察忽略的信息,那么S+J就相当于是无论一次观察还是二次观察总共忽略的信息最大。进一步,我们还可以利用J和S的组合定义很多不同的函数,那么我们的第二个Open problem就是:

能否设计出来一个优化函数:f(S,J),最大化它就导出幂律分布?

4、初步的解析性质

不失一般性,我们可以将A集合中的元素按照从大到小的顺序排列,比如A={n1,n2,..nr,..},其中ni>=n_{i+1}。这样我们可以把该集合的序号r看作横坐标轴,nr看作纵座标轴画出一条曲线来。

我们设这条曲线为x(r)。那么我们要求的pi也就可以相应转为求p(r)=x(r)/sigma(x(r)),所以p(r)曲线也是跟x(r)同样的。假设A中的元素有很多很多,这样x(r)就近似是一条连续的曲线了。那么下面的问题是,给定了x(r)之后,对应的q分布是什么样子的呢?注意q分布相当于是把x(r)的各种之看作随机变量,计算落在小区间[x,x+dx]中的点数,在连续的情况下,可以证明,落在该小区间中的点数为:

dx/(|x′|)

于是q(x)的分布就是

1/(|x′|)

其中要注意x′表示x(r)对r取导数,并且将表达式中的r用x^{-1}(r)来替换,就是求x(r)的反函数。

比如,我们可以针对几种x(r)讨论一下,如果x(r)~Exp(- b r),那么可以证明q(x)~1/(b x),这就相当于前两天跟计算士讨论的问题,即当小球访问不同能量级Ei的时候,最后稳态了得到了玻尔兹曼分布,那么对应的访问第i各能级的概率pi的分布是什么样子呢?现在清楚了,它就是一个指数为-1的幂律分布。

再来一个例子,当x(r)~r^(-a)的时候,q(x)~x^{(a+1)/a},都是幂律分布。

一个开放性问题是:对于任意的概率分布x(r),对应的q(x)跟x(r)的特征函数存在什么关系吗?

那么既然能写出解析式,我么能写出关于S熵和J熵的表达式吗?进一步我们如何利用这两种熵来扩展最大化熵框架?我们可以来做一个计算机模拟,比如撞球试验,看看S熵和J熵分别如何随时间演化

总之,这里面的可讨论问题还有很多很多。

最后,附上我写的Mathematica源程序,方便大家重复我的实验

RecursiveProcess[num_, left_] := Module[{i, out = {}, tb1, tb2, tb3},
   If[num == 0, Return[{{0}}]];
   For[i = Min[num, left], i >= 1, i--,
    tb2 = RecursiveProcess[num - i, i];
    tb1 = {{i}};
    tb3 = Flatten[Join[tb1, #]] & /@ tb2;
    out = Join[out, tb3];
    ];
   Return[out];
   ];
FinalTwo[num_] := Module[{out},
   out = RecursiveProcess[num, num];
   out = PadRight[#, num] & /@ out;
   Return[out];
   ];
ShannonEntropy[state_] :=
  Module[{t}, t = Total[state];
   Sum[If[state[[i]] == 0, 0, -state[[i]] * Log[state[[i]]/t]], {i, 1,
       Length[state]}]/t];
JakeEntropy[state_] := Module[{J, phis},
  J = Total[state];
  phis = BinCounts[state, {1, J + 1, 1}];
  Return[ShannonEntropy[phis]];
  ]
GivePhis[state_] := Module[{J, phis},
  J = Total[state];
  phis = BinCounts[state, {1, J + 1, 1}];
  Return[phis];
  ]

注意前两个函数为生成n个数,使得他们相加等于num的所有可能组合的。后面的ShannonEntropy和JakeEntropy分别计算S和J熵,输入参数state都是一种可能的组合。GivePhis这个函数就是给定一个集合state,计算各个q(x)的数值。

2009-6-2 23:01:43
  


这是非常好的探讨!也是Jake大人的本色,碰到问题写一个程序算一算,当你能够用一个模拟去演算某个数学问题的时候,才表示你理解了这个问题(不是解决了这个问题)。同时,熵增也是我们的核心学问。(回头对大家说:走过路过不要错过,不要看到公式就皱眉,这两个熵的区别非常重要,请进来的人都仔细研究一下)

这两种熵,前一种A熵是根据数字大小算出来的,后一种B熵只是把数字当作一个标志来看待,无所谓数字大小。这有一点类似于基数和序数。(我觉得叫AB比较容易记)

Jake大人说“我们知道当所有的pi近乎相等的时候,S是最大的,所以S越大就表示社会财富分布越均匀……而且,当财富分布越均匀的时候,J熵反而越小”这段话说的有点含混,贫僧再说清楚一点:

其实熵就是对于某一个观察方法建立的复杂度标志,故而对一个集合,如果你用不同的方法观察它,可以有不止一个熵,例如许多人分钱,你是观察人还是观察钱?

1、如果观察钱,就是用钱的多少来标志人,比如所有1块钱的人通通归于一类,10块钱的又是一类,等等,这样得到的熵就是J熵,J熵最大对应于指数分配,也就是碎石头(打碎一块石头,一定大大小小,绝不会碎成许多块一样大小的石头)

2、如果观察人,就是人是不动的,不管钱多钱少,都是单独算一类。(你可以想象很多人站在操场中间,从天上往下均匀撒钱,但是每个人只拣脚下的钱)这样得到的是S熵,S熵最大就是均匀分配。

那么显而易见的问题就是,为啥同样分钱,会得到两种不同的结果?原因就是如Jake大人所说,熵本身就是观察的结果,分配过程同样也是观察的结果。实际上一切物理现象都是观察的结果。如佛所说,一切法以分别心而得。

Jake大人又说“因此S是忽略的一阶信息,而J则是观察者忽略的二阶信息。”

我觉得这里你好像受到计算士误导了。对计算士兄弟我们要注意一些,他的学问虽然数学不多,但却是属于上乘内功,也就是含有哲学内涵的那种。因而特别要小心,不要被他带走。从上面我的分析可以看到,AB熵完全是对称的,处于同样地位的,谈不上那一个是另一个的“导数”,固然观察者会忽略很多信息导致新的观察,研究这个忽略极其重要。但是这种忽略的内涵是同这个基数序数很不一样的,不信你看看进一步定义的q′,q′′有什么物理意义吗?没有。

下面提出了第一个问题:

还有一些明显的(横着的“族”)。为什么会这样?

究竟为什么这条曲线会呈现出不同的组?每个组意味着什么?能不能把不同的组曲线写出来?

回答:其实很简单,你其实就是在问,为啥对于同一个B熵可以有许多不同的A熵。这是因为B熵只在乎集合里面“有几个不一样的元素”不在乎“每个元素的大小”。

比如{1、9} {2、8}{4、6} {3、4}等等二元集合,它们的B熵都相等(2log2=2bit),但是A熵却不同,就是这样而已。

因此我觉得把B熵和A熵混起来进行线性优化的做法有点怪异,因为它们是不一样的东西,简单的加起来能得到什么意义吗?好像你把质量和密度加起来取个最大值,能有什么物理意义吗?

下面还有一些问题,明天继续讨论吧。

 

 

 



>jake在两种熵——一道非常有趣的数学问题中写道:
---------------------------

受到计算士、张学文老师讨论的启发,这两天研究了一个非常有意思的事情:任意数值集合的两种熵,这不仅仅是一个纯粹的数学问题,而且跟很多实际问题相关。我先给出定义,在列举出来这个问题跟什么实际问题相关......

2009-6-3 12:09:35
  


此外我还有一事不明,请Jake大人为我讲解:

就比如100个人分钱,钱是从天上掉下来的,因而没有一个人有更大的机会拿到钱,每个人的期望收获因此都是相等的。这样看,得到的结果应该是随机分布。

实际上我们知道最后分布应该是一个正态分布的钟形曲线,而不是平的一根线。也就是说有一部分人可以期望拿到比别人更多的钱,这和从个人的角度看是不一样的,为啥?为啥?

更奇怪的事情是,整体的概率分布不是部分之和,也就是说概率分布也是含有一种“涌现”特点的。那么我就在疑惑,为啥这里整体不是部分之和?涌现是怎么出现的?



>东方隐在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------


这是非常好的探讨!也是Jake大人的本色,碰到问题写一个程序算一算,当你能够用一个模拟去演算某个数学问题的时候,才表示你理解了这个问题(不是解决了这个问题)。同时,熵增也是我们的核心学问......

2009-6-3 12:21:57
  

你这个正态分布是说q(x)为正态分布,而不是p。也就是你考察的是财富的分布,而不是每个人获得多少钱。当每个人获得的钱数相近的时候,得到的钱数的分布一般就刚好是正态分布了。

假设让这些随便从地上捡起钱了,然而故事并没有结束,这些人又会相互竞争、那么钱就会随机倒手,经过足够长时间,q(x)就不是正态了,而是指数分布,即玻尔兹曼分布。


>东方隐在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------


此外我还有一事不明,请Jake大人为我讲解:

就比如100个人分钱,钱是从天上掉下来的,因而没有一个人有更大的机会拿到钱,每个人的期望收获因此都是相等的。这样看,得到的结......

2009-6-3 12:47:31
  

偶还是没明白,财富和每个人获得多少钱有啥区别?

而且大人说钱“钱就会随机倒手,经过足够长时间,q(x)就不是正态了,而是指数分布,即玻尔兹曼分布”,这不对吧。指数分布是说一个人有很多很多钱,然后下一个人的钱比他少很多,再下一个人的钱更少,然后有很多很多穷人。随机倒手的时候,其他穷人一定上来把此人的钱分完的,绝对不会有这样的怪事出现。


>jake在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------

假设让这些随便从地上捡起钱了,然而故事并没有结束,这些人又会相互竞争、那么钱就会随机倒手,经过足够长时间,q(x)就不是正态了,而是指数分布,即玻尔兹曼分布。

2009-6-3 13:56:46
   要好好思量一下·····


>东方隐在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------


这是非常好的探讨!也是Jake大人的本色,碰到问题写一个程序算一算,当你能够用一个模拟去演算某个数学问题的时候,才表示你理解了这个问题(不是解决了这个问题)。同时,熵增也是我们的核心学问......

2009-6-3 14:42:12
  


 

冤枉那,我虽然说了这是忽略信息(实际上我说就一次,第一次熵是表示了系统所有的信息/不确定性,——正如张学文所说,系统的信息是一个固定值——,第二次熵比第一次熵少掉的部分才是忽略的信息/不确定性啊),我可没用“一阶”“二阶”,那是jake自己加上去的···

 

········你好我叫分割线!初次见面多多关照············

Jake大人又说“因此S是忽略的一阶信息,而J则是观察者忽略的二阶信息。”


我觉得这里你好像受到计算士误导了。

2009-6-3 14:49:13
  


jake一直在关注的就是“双层流”,因此他也许是想找到在“两个层次”上都最大化熵的函数及其优化结果。

我也觉得这应该不是一个线性加总,但还有两种可能,一个是相乘,乘数效应在这里是否存在呢?

另一个,最大化两个熵相减的差可能也是有意义的。这个差是随着系统的复杂程度变化而变化的,在系统S熵最大的时候,也就是等概率的时候,J熵的计算是不丧失信息的;但在S熵最小的时候,J熵的计算是丧失信息的···



>东方隐在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------


这是非常好的探讨!也是Jake大人的本色,碰到问题写一个程序算一算,当你能够用一个模拟去演算某个数学问题的时候,才表示你理解了这个问题(不是解决了这个问题)。同时,熵增也是我们的核心学问......

2009-6-3 14:56:50
  


哈,和尚,我也被这个问题困扰了很久!

其实我们在教科书里看到的所有概率分布函数,都是q而不是p,因为都是累加合并以后的结果。

在张学文书里,最原始的那种表格,就是每个元素对应一个标志值的列举,才是p,

把标志值相同的元素合并后,就是有的标志值的元素多,有的标志值的元素少,这就是q了。所谓的各种分布,我们一般都是对q的函数形式说的,及y(处于该标志值的数目)与x(该标志值)之间的关系。

我被这个问题困扰,是思考复杂网络怎样才能最大熵,一直以为是度分布达到最大,后来发现,度分布其实是q而不是p!

这个问题很容易乱!你说,我们以前说的最大熵,是在p上说,还是在q上说的?我感觉我们以前就没有清楚界定过这个问题!


>东方隐在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------

偶还是没明白,财富和每个人获得多少钱有啥区别?

而且大人说钱“钱就会随机倒手,经过足够长时间,q(x)就不是正态了,而是指数分布,即玻尔兹曼分布”,这不对吧。指数分布是说......

2009-6-3 15:37:22
  


贫僧不像Jake大人耳根子软,我从来没有被这个问题困惑过。(除了这一次被误导以外)

每个人有多少钱,和某个收入档次上有多少人,当然是两个不同的分布;这是很基本的事情,没有必要特别声明一下。(不过确实容易混淆,就像我把幂律和指数弄混一样),而对于某一个特定问题,我们关心的分布只有一个,这取决于系统中不同元素的标志值是如何产生的。

Jake大人前面确实错了,玻尔兹曼分布是建立在气体自由交换能量的基础上的,但是请注意,这里真正交换的是动量,而不是能量!因而动量是正态分布,能量则是指数分布。如果把气体分子的例子换成钱的随机交换的话,钱还是正态分布的。在这里我们关心的都是q(x)。然而我问的不是这个。

我提的问题还没有得到回答,现在我们不要管什么pqAB,就是随机分配导致正态分布这个问题,一方面每个人的期望收获是相等的,另一方面有一部分人可以期望拿到比别人更多的钱。

为什么?为什么?
为什么?为什么?


>计算士在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------


哈,和尚,我也被这个问题困扰了很久!

其实我们在教科书里看到的所有概率分布函数,都是q而不是p,因为都是累加合并以后的结果。

在张学文书里,最原始的那种表......

2009-6-3 15:43:03
  



不需要Jake大人讲解了,我自己觉悟了。

这个问题等价于:

每个人在生下来时候寿命都是随机的,但是死掉的时候寿命各个不同。因此一方面每个人的期望寿命是相等的,另一方面有一部分人可以期望比其他人活得更长。

为啥?一个是生下来时候向前看,一个是死掉以后回头看,观察角度的不同。


>东方隐在回复:两种熵——一道非常有趣的数学问题中写道:
---------------------------

 

我提的问题还没有得到回答,现在我们不要管什么pqAB,就是随机分配导致正态分布这个问题,一方面每个人的期望收获是相等的,另一方面有一部分人可以期望拿到比别人更多的钱。

登录后才可以评论,马上登录